Недетерминированная машина Тьюринга
-
Определение и свойства машины Тьюринга
- Машина Тьюринга — это абстрактная вычислительная машина, которая может имитировать любую вычислимую функцию.
- Машина Тьюринга состоит из ленты, головки, состояния и функции перехода.
- Машина Тьюринга может быть детерминированной (DTM) или недетерминированной (NTM).
-
Детерминированная машина Тьюринга (DTM)
- DTM имеет однонаправленный путь вычислений.
- DTM может быть определена как шестикорпусная машина с конечным множеством состояний, символов и принимающих состояний.
- Отношение перехода DTM является функцией, а не просто отношением.
-
Недетерминированная машина Тьюринга (NTM)
- NTM имеет множество возможных путей вычислений, которые могут привести к принятию входных данных.
- NTM может быть формально определена как шестикорпусная машина с множеством состояний, символов, принимающих состояний и отношением перехода.
- Отношение перехода NTM является отношением, а не функцией.
-
Вычислительная эквивалентность и моделирование NTM
- Задачи, решаемые с помощью DTM, могут быть решены с помощью NTM.
- Временная сложность может быть разной для DTM и NTM.
- DTM могут моделировать NTM с использованием различных подходов, включая использование нескольких конфигураций или 3-ленточных машин.
-
Проблема P = NP и квантовые компьютеры
- Проблема P = NP касается соотношения между полиномиальным временем решения задач с помощью NTM и DTM.
- Квантовые компьютеры могут быть ошибочно приняты за NTM, но их мощность, вероятно, не сравнима с NTM.
Полный текст статьи: