Отличается ли недетерминированность в недетерминированной машине Тьюринга от конечных автоматов и автоматов с опущением?

9

Пусть входная строка будет задана как . Затем, если NFA в настоящее время находится в состоянии (и прочитал входной алфавит ), то перед чтением следующего входного символа NFA разделяется на два NFA, один из которых находится в состоянии а другой - в , если происходит переход тип . Если существует цикл типа , где - некоторые состояния NFA, тогда бесполезно вспоминать другой NFA в состоянии до точки, где ввод был прочитан до алфавита r w i r s r ϵ s r ϵ s ϵ q 1 . , , , & epsi ; → д к & epsi ; → г д я г ш Iвес1вес2,,,весNрвесярsрεsrϵsϵq1....ϵqkϵrqirwi,

Если КПК (недетерминированный) находится в состоянии (и ввод читается до ) и существует цикл (где переход средство означает, что ничего после читается из ввода, ничего не выталкивается или не читается из стека, а алфавит помещается в стек), затем перед чтением следующего входного алфавита будет бесконечный КПК в состоянияхw i r ϵ , ϵ a s ϵ , ϵ a q 1 . , , , ϵ , ϵ a q k ϵ , ϵ arwirϵ,ϵasϵ,ϵaq1....ϵ,ϵaqkϵ,ϵarϵ,ϵawiawi+1r,s,q1,...qk потому что в отличие от NFA, хотя состояния конечного стека могут быть разными (бесконечные возможности), если я не ошибаюсь.

Как и в случае с NFA и PDA, сила недетерминизма проистекает из переходов. Поэтому я предполагаю, что недетерминированная машина Тьюринга также получает свою недетерминированность от ϵ переходов, таких как NFA и PDA (больше похоже на PDA). Я знаю, что детерминированная машина Тьюринга может симулировать недетерминированную (я знаю доказательство, которое использует поиск в первую очередь). Но сейчас я сомневаюсь, как это возможно. Поскольку, если цикл типа, описанного выше в КПК, существует на диаграмме состояний недетерминированной машины Тьюринга, то перед чтением следующего символа w i + 1ϵϵwi+1детерминированная машина Тьюринга даже при моделировании конфигурации в некоторой ветви недетерминированной машины Тьюринга (в то время как bfs) должна будет отслеживать бесконечную машину Тьюринга (опять-таки состояния конечны, но символы на ленте имеют бесконечные возможности).
Так как именно недетерминизм определяется в случае машин Тьюринга? Я неправильно понимаю что-то тривиальное? Используют ли недетерминированные машины Тьюринга переходы?ϵ


Я прошу прощения за мои тривиальные сомнения. Если что-то не так, я могу обновить свой вопрос.

SashaS
источник
2
Что касается вопроса о названии, то в формальных определениях нет большой разницы. Что касается эмерджентной мощности, да, она имеет много разных последствий в каждой модели машины. Что касается остальной части вопроса, трудно разобрать. :(
vzn
1
Вы проверяли Википедию? en.wikipedia.org/wiki/Non-deterministic_Turing_machine
Yuval Filmus
@YuvalFilmus да у меня есть. Определение переходной функции включает в себя набор мощности, который я понимаю. Но дело о переходов в машинах Тьюринга до сих пор неясно мне. епsяLоN
Саш
@vzn Я так и думал. Я действительно сожалею. Я плохо выдвигаю свои сомнения. Но я могу улучшить, если вы дадите предложения.
Саш

Ответы:

8

Недетерминизм - это одно и то же понятие во всех контекстах - машине разрешено использовать несколько опций в любой заданной точке. Однако семантика немного отличается, так как DFA / NFA и PDA всегда определяют общие функции, тогда как машины Тьюринга (детерминированные или недетерминированные) в целом определяют частичные функции.

Частичная функция - это функция, определенная только для части домена. Если не определено на x, то мы пишем f ( x ) = . (Таким образом, f на самом деле является полной функцией, но в диапазоне есть специальный элемент, обозначающий, что выходные данные не определены.) Детерминированная машина Тьюринга M определяет частичную функцию следующим образом: если M останавливается на x, то M ( x ) является содержимое ленты, когда M останавливается на x ; и в противном случае M ( x ) = fxf(x)=fMMxM(x)MxM(x)=,

Детерминированная машина Тьюринга Решающий имеют два вида остановочных состояний, принятие и отказ, и определяет частичную функцию следующим образом : если останавливается на х на допускающем состоянии, то М ( х ) = 1 ; если он останавливается в состоянии отказа, то M ( x ) = 0 ; если он не останавливается, то M ( x ) = . Если M всегда останавливается, мы говорим, что он принимает язык L = { x : M ( x)MxM(x)=1M(x)=0M(x)=M .L={x:M(x)=1}

Недетерминированной машине Тьюринга (которая всегда является решающим фактором) разрешается «ветвиться» (иметь несколько возможных вариантов в любой заданный момент времени) и имеет следующую семантику:

  • если на входе x машина M останавливается на всех ветвях, останавливаясь в принимающем состоянии по крайней мере для одной ветви.M(x)=1xM
  • если на входе x машина M останавливается на всех ветвях, всегда останавливаясь в состоянии отклонения.M(x)=0xM
  • если на входе x существует ветвь, на которой M не останавливается.M(x)=xM

Учитывая это определение, мы надеемся, что будет ясно, как имитировать недетерминированную машину Тьюринга, используя детерминистское решение для машины Тьюринга: вы пробуете все ветви, проверяя, приводит ли какая-либо из них к принятию состояния остановки. После остановки всех веток вы можете решить, переходить ли в состояние принятия или в состояние отклонения. Если недетерминированная машина Тьюринга не останавливается на некоторой ветви, то будет и детерминированная.


Что о служит для перемещения? Они вызывают проблемы в том, что соответствующий автомат может никогда не остановиться. Для конечных автоматов (NFA и PDA) мы молчаливо игнорируем вычисления без остановки. Наша причина для этого заключается в том, что полученные языки всегда вычислимы, хотя наивный алгоритм их детерминированного моделирования (имитация всех путей вычислений) не совсем работает. Это не так сложно для НФА, которые могут быть преобразованы в ДФА. Однако детерминированные КПК строго слабее, чем недетерминированные КПК. Тем не менее, вы можете показать, что каждый КПК эквивалентен одному без ϵ- перехода (хотя доказательство может проходить через контекстно-свободные грамматики).ϵϵ

Вы можете смоделировать перемещения в машинах Тьюринга, но вы должны быть осторожны, чтобы не было циклов, которые бы приводили к непрерывным вычислениям. Однако в некоторых случаях мы можем использовать тот же прием, что и выше. Например, предположим, что ваша машина Тьюринга ограничена в пространстве: мы знаем верхнюю границу используемого пространства (в зависимости от длины ввода). В этом случае каждое вычисление без остановки обязательно циклично (поскольку машина Тьюринга имеет конечное число состояний, включая содержимое ленты), и поэтому, если мы «игнорируем» вычисления без остановки, как указано выше, полученная модель вычисления все еще вычислима. В более общем смысле, это работает до тех пор, пока нам гарантировано, что каждый не прекращающийся цикл вычислений. (Это касается NFA, но не PDA.)ϵ

Юваль Фильмус
источник
rb,casrbbcaϵacϵ
@sasha Выполнение «разделяется» всякий раз, когда есть несколько вариантов продолжения.
Юваль Фильмус
ϵ
1
ϵ
1
AaB1B2BnAaAB1BnϵAa