Недетерминированная машина Тьюринга Википедия. В теоретической информатике недетерминированная машина Тьюринга машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат. Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево. В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. Например, X на ленте и состояние 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево. Как НМТ узнат, какой из возможных путей приведт в допускающее состояниеЕсть два способа это представить. Можно считать, что НМТ чрезвычайно удачлива то есть всегда выбирает переход, который в конечном счте приводит к допускающему состоянию, если такой переход вообще есть. Можно представить, что в случае неоднозначности перехода текущая комбинация состояния и символа на ленте допускает несколько переходов НМТ делится на копии, каждая из которых следует за одним из возможных переходов. То есть в отличие от ДМТ, которая имеет единственный путь вычислений, НМТ имеет дерево вычислений в общем случае экспоненциальное число путей. Говорят, что НМТ допускает входные данные, если какая нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает. Однако любой язык, допускающийся НМТ, также допускается ДМТ ДМТ может моделировать любой переход НМТ, делая многократные копии состояния, если встречается неоднозначность. Очевидно, что это моделирование требует значительно больше времени. Насколько больше неизвестно. В частном случае ограничения по времени в виде полинома от длины входа этот вопрос представляет собой классическую задачу P NP см. Тогда b длина входных данных, по отношению к которой рассматривается время вычисления. Ответ ДА число составное и НЕТ простое. Эта задача является комплементарной к тесту на простоту. Недетерминированный алгоритм для этой задачи может быть, например, следующий Выбрать недетерминированно целое число m такое что 1lt mlt N. Машина Тьюринга Курсовая Работа' title='Машина Тьюринга Курсовая Работа' />Разделить нацело N на m, остаток обозначим через a. Если a0 выдать ответ ДА m тогда делитель. N, иначе выдать ответ НЕТ. Дуа На Татарском Языке. Алгоритм написан не непосредственно в виде определения машины Тьюринга. Во времени вычисления этого алгоритма определяющей частью является время выполнения деления, которое может быть выполнено за Ob. Таким образом, задача находится в классе P. Для реализации такого времени вычисления требуется удачно выбирать число m или выполнять вычисления по всем возможным путям для всех возможных m одновременно на множестве копий машины. Если моделировать этот алгоритм на детерминированной машине Тьюринга, пробуя по очереди все возможные варианты, требуется проверить N 2O2b ветвей. В теоретической информатике недетерминированная машина Тьюринга машина Тьюринга, функция перехода которой представляет собой. Курсовая работа, добавлен 16. Машина Тьюринга. Парадигма программирования. Тьюринг как английский математик, логик, криптограф,. Машина Тьюринга Курсовая Работа' title='Машина Тьюринга Курсовая Работа' />Таким образом, общее время вычислений будет Ob. Таким образом, этот алгоритм не попадает в класс P. Введение в теорию автоматов, языков и вычислений Introduction to Automata Theory, Languages, and Computation.