Машина ленты Тьюринга фиксированного размера, которая не может писать на входе, эквивалентна DFA

Question

Я должен доказать, что машина Тьюринга с лентой фиксированного размера, которая не может писать на входе, эквивалентна конечному автомату (DFA или NFA).

Важно добавить, что размер ленты - это размер ленты, который исключает входные данные. Например, если размер входного файла равен n, то размер ленты будет равен k + n, где k - длина ленты, которая исключает входные данные.

Я понимаю основную идею, но это очень сложно доказать. Заранее спасибо.

Answer 1

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

Показывать, что вы можете эмулировать TM на DFA, немного сложнее, но сводится к тому, что есть только k возможных мест для записи m символов, гдеm - размер букв алфавита машины.Поэтому ваша TM имеет только k^m возможных состояний ленты в дополнение ко многим состояниям машины, которые мы назовем n.Таким образом, DFA с n*k^m состояниями может покрывать состояния TM.

Очевидно, что это волнообразный набросок доказательства.Вы можете взять его отсюда.