3 Как устроена машина Тьюринга
Как устроена машина Тьюринга
У машины три части:
Лента — бесконечная в обе стороны, разбита на ячейки. В каждой ячейке — один символ из алфавита. Особый символ λ («лямбда») означает пустую ячейку.
Каретка (головка) — стоит над одной ячейкой, читает её символ, может записать новый и сдвинуться на одну ячейку влево или вправо. У каретки есть текущее состояние (q₀, q₁, …); в начале — q₀.
Программа — таблица переходов. Строки — состояния, столбцы — символы. На пересечении «текущее состояние × символ под кареткой» стоит команда.
Каждая команда состоит из трёх частей:
(какой символ записать) , (куда сдвинуть каретку) , (в какое состояние перейти)
Сдвиг обозначают буквами: L — влево, R — вправо, N — остаться на месте, S — стоп (машина останавливается).
📌 Один шаг машины Смотрим состояние каретки и символ под ней → находим клетку таблицы → записываем новый символ в текущую ячейку → сдвигаем каретку (L/R/N) → переходим в новое состояние. И так до команды стоп (S). |