Кажется, я вспоминаю из студенческого класса, что для машины Тьюринга с конечной лентой всегда будут существовать соответствующие конечные автоматы, но я не смог найти это подтверждение где-либо в Интернете. Это на самом деле так, или я неправильно помню?
turing-machines
finite-automata
Джесси Берлин
источник
источник
Ответы:
Это зависит от того, что вы подразумеваете под «конечной лентой». Если вы связали длину ленты с помощью какой-либо функции ввода, то нет - вы можете распознавать нерегулярные языки. Например, рассмотрим LBA .
Но если вы имеете в виду ограниченную ленту, где лента имеет ячеек для некоторого фиксированного , тогда да - вы действительно получаете модель, которая эквивалентна DFA.k k
Чтобы доказать это, подумайте, какая информация вам нужна для определения будущего запуска ТМ: вам нужно содержимое ленты, местоположение головки и состояние. Если лента имеет постоянное количество ячеек и алфавит фиксирован, то у вас есть постоянное количество конфигураций, которые вы можете кодировать как состояния конечного автомата.
источник