Лямбда-переход не определен в машинах Тьюринга? В чем причина этого? Кто-нибудь, пожалуйста, объясните мне.
Заранее спасибо.
Почему лямбда-переходов нет в машине Тьюринга?
comment
лямбда-переходы кажутся не связанными с машинами Тьюринга...
- person Chris Dodd schedule 02.06.2017
comment
В моем выпускном курсе теории вычислений мы изучаем следующую последовательность: лемма о накачке, конечные автоматы (DFA, NFS), автоматы с отталкиванием, машина Тьюринга, разрешимая проблема, NP, NP-полное. В то время как лямбда-переход в NFA делает вещи более простыми и понятными, связь с очень сложной моделью Тьюринга и ставит этот вопрос на самом деле не так уж плохо.
- person Ken Cheung schedule 02.06.2017
Ответы (1)
Надеюсь, что моя память 20-летней давности все еще актуальна, пожалуйста, исправьте, если какая-то ошибка!
Вы говорите о лямбда-переходе в NFA? Лямбда-переход в NFA в основном предназначен только для упрощения сложности FA. Вы также должны узнать, как конвертировать NFA в DFA s.t. она детерминистична, и «машина» способна «выполнить» ее шаг за шагом, чтобы обработать отражающий ее формальный язык.
Машина Тьюринга — это абстрактная машина в соответствии с теорией Тьюринга и моделью большинства современных компьютеров (кроме квантовых компьютеров, которые все еще редкость в нашем мире). Насколько я понимаю, машина Тьюринга является детерминированной и выполняется через кран для выполнения «вычислений». Внутри нет недетерминированного элемента.
person
Ken Cheung
schedule
02.06.2017
Спасибо, Кен. Да, я говорю о лямбда-переходах в NFA. И да, когда я погуглил, я обнаружил, что машины Тьюринга детерминированы. Не могли бы вы немного пояснить это предложение. Внутри нет недетерминированного элемента. Спасибо.
- person blackilDiamond; 02.06.2017
Извините за мой плохой английский. Я просто хочу четко заявить, что для машины Тьюринга все должно быть детерминировано. Если у нас есть лямбда-переход, это означает, что у нас может быть два или более действительных и возможных следующих состояния, из-за которых TM не сможет определить, что он должен делать дальше.
- person Ken Cheung; 03.06.2017
Это неверно, что машины Тьюринга не могут быть недетерминированными. Фактически, определение класса NP (в проблеме P vs NP) определяется классом задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время... важная тема.
- person Colin D; 16.03.2018
