Разница между машиной Тьюринга и конечным автоматом?

27

Я делаю презентацию о машинах Тьюринга, и я хотел бы рассказать о FSM, прежде чем представлять машины Тьюринга. Проблема в том, что я действительно не знаю, что ОЧЕНЬ отличается друг от друга.

Вот что я знаю, это другое:

FSM имеет последовательные состояния в зависимости от соответствующего условия, в то время как машины Тьюринга работают на бесконечной «ленте» с головкой, которая читает и пишет.

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

Но кроме этого, я не знаю намного больше различий, которые делают машины Тьюринга лучше, чем машины FSM.

Не могли бы вы мне помочь?

terminology turing-machines finite-automata machine-models Хулио Гарсия
источник
2
Нетрудно найти Google для "FSM vs. Turing Machine"! Это забавная часть ваших собственных исследований. Основное отличие состоит в том, что машина Тьюринга обладает бесконечной «памятью», а автомат FSM - нет.
Дай
Хорошо, я немного обманул там>.> ;; Попался! Благодарность!
Хулио Гарсия
3
аргумент об «ошибке» не верен. Попробуйте википедию и учебники. Посмотрите, каковы их основные различия, цель использования каждого из них (например, когда мы не можем выбрать FSM вместо TM?) И их отношение.
Пархам
@MahmoudAlimohamadi Я имею в виду, что у ФСМ больше шансов попасть в бесконечное состояние.
Хулио Гарсия
@Dai: Правильнее сказать , что машина Тьюринга может использовать в сколь угодно большой объем памяти. Используемое количество никогда не бывает бесконечным.
reinierpost

Ответы:

24

Основное различие между тем, как работают DFA (детерминированный конечный автомат) и TM, заключается в том, как они используют память.

Интуитивно понятно, что DFA вообще не имеют «царапины» памяти; конфигурация DFA полностью определяется состоянием, в котором он находится в данный момент, и текущим прогрессом в чтении ввода.

Интуитивно понятно, что ТМ имеют «скретч» память в виде ленты; конфигурация ТМ состоит из ее текущего состояния и текущего содержимого ленты, которое ТМ может изменить при выполнении.

DFA можно рассматривать как TM, который не меняет символы ленты и не перемещает голову влево. Эти ограничения делают невозможным распознавание определенных языков, которые могут быть приняты ТМ.

Обратите внимание, что я использую термин «DFA», а не «FSM», поскольку технически я бы рассматривал TM как машину с конечным числом состояний, поскольку TM по определению имеет конечное число состояний. Разница между DFA и TM заключается в количестве конфигураций, которое равно количеству состояний для DFA, но бесконечно велико для TM.

Patrick87
источник
Ах, понял. Один вопрос, касающийся части «без памяти»: я видел пример торгового автомата, который складывал выданные монеты. Откуда они знают, сколько денег есть, если у них нет памяти?
Хулио Гарсия
@JulioGarcia Трудно сказать, не зная точно, что ты видел. Существуют машины Мура и Мили, которые могут выводить символы при переходах. Деятельность торгового автомата может быть лучше смоделирована одним из этих механизмов. Ванильный DFA только принимает и отклоняет строки ... торговый автомат должен «принимать» любую «строку» чеканки. В зависимости от того, как вы смоделируете дополнительные побочные эффекты от внесения изменений, тип необходимой рабочей памяти может быть нулевым или неограниченным произвольным доступом.
Patrick87
Не видя вашего примера, я не могу быть полностью уверен, но у меня есть две догадки. Во-первых, он не знает, сколько там денег: он просто предполагает, что достаточно. Вы не хотели бы строить настоящий торговый автомат таким образом, но это все еще полезный пример концепции. Другая возможность состоит в том, что это не совсем «чистый» FSA: он подключен к датчику, который может каким-то образом получать эти данные «снаружи» машины. Машина не знает и не заботится о том, откуда поступают данные, и не может ничего хранить в датчике (так что это на самом деле не «память»), но она все равно может влиять на то, что она там видит.
Ложная
16

Машины Тьюринга описывают гораздо больший класс языков, класс рекурсивно перечислимых языков. Конечные автоматы описывают класс регулярных языков.

У конечных автоматов нет «памяти», она ограничена своими состояниями.

Конечный автомат - это ограниченная машина Тьюринга, в которой головка может выполнять только операции «чтения» и всегда перемещается слева направо.

Возьмите этот язык в качестве примера:

L={aibi| i>=0}

Поскольку машины с конечным состоянием ограничены в том смысле, что у них нет памяти, FSM, принимающий L, не может быть создан.

Обобщить:

Конечные автоматы описывают небольшой класс языков, в которых не требуется память.

Машины Тьюринга представляют собой математическое описание компьютера и принимают гораздо больший класс языков, чем это делают автоматы.

Машины Тьюринга обладают большей вычислительной мощностью, чем FSM. Есть задачи, которые не может выполнить ни один FSM, но которые могут выполнять машины Тьюринга.

mrjasmin
источник
3

У меня было то же самое сомнение, и я увидел два очень поучительных видео и одно объяснение по Quora следующим образом:

Конечный автомат - это просто набор состояний и переходов. Единственная память, в которой он находится - это то, в каком состоянии он находится. Таким образом, число состояний памяти ... конечно.

Машина Тьюринга - это конечный автомат плюс память на магнитной ленте. Каждый переход может сопровождаться операцией на ленте (перемещение, чтение, запись).

Из этого я понял, что машина Тьюринга использует / имеет конечный автомат в качестве части своей операционной процедуры, а также добавляет к ней немного редактируемой памяти.

Пожалуйста, посмотрите также эти два видео, они освещают!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

user5193682
источник
2

Насколько я понимаю различия между (стандартная модель) Тьюринга и (стандартная модель) Мили машинами:

  • Машины Тьюринга читают и пишут на одной ленте, а Мили - машины читают на одной входной ленте и пишут на другой выходной ленте.
  • Машины Тьюринга могут изменить «направление движения ленты» (продолжить влево или вправо [или прекращение]) по сравнению с Мучнистыми Машины могут только продолжить вправо (вот почему нет направления множества {L, R, H} в функции перехода Мили машины [это неявно {R}, что означает отсутствие выбора вообще))
  • Машины Тьюринга могут останавливаться на любой ленточной ячейке, а Мили-машины читают полный ввод, а затем прекращают принимать или отклонять его.
Майкл Клауб
источник
-3

Машина Тьюринга может хранить как часть ленты то, что она хочет запомнить.

Ричард Маллинс
источник
5
Непонятно, что вы подразумеваете под «этим», но это могут сделать как машины Тьюринга, так и автоматы, так что это не будет иметь значения.
Дэвид Ричерби
@DavidRicherby Но FSM может хранить только заранее определенное количество, тогда как машины Тьюринга могут хранить столько, сколько они хотят. То есть принципиальная разница.
Жиль "ТАК ... перестать быть злым"
1
@ Жиль Согласен, но это не то, что говорит ответ.
Дэвид Ричерби