Какая связь между машинами Тьюринга с конечной лентой и конечными автоматами?

9

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

Джесси Берлин
источник
Сколько возможных состояний будет у машины Тьюринга с конечной лентой?
Дэйв Кларк
Это будет конечное число, но, как показывает приведенный ниже ответ, этого не обязательно достаточно для получения эквивалентности.
Джесси Берлин

Ответы:

9

Это зависит от того, что вы подразумеваете под «конечной лентой». Если вы связали длину ленты с помощью какой-либо функции ввода, то нет - вы можете распознавать нерегулярные языки. Например, рассмотрим LBA .

Но если вы имеете в виду ограниченную ленту, где лента имеет ячеек для некоторого фиксированного , тогда да - вы действительно получаете модель, которая эквивалентна DFA.kk

Чтобы доказать это, подумайте, какая информация вам нужна для определения будущего запуска ТМ: вам нужно содержимое ленты, местоположение головки и состояние. Если лента имеет постоянное количество ячеек и алфавит фиксирован, то у вас есть постоянное количество конфигураций, которые вы можете кодировать как состояния конечного автомата.

Shaull
источник
Ваш ответ за ограниченную ленту был именно тем, что я искал. Спасибо!
Джесси Берлин