3 Как устроена машина Тьюринга

Как устроена машина Тьюринга

Иллюстрация к заданию 12, рисунок 1

У машины три части:

  • Лента — бесконечная в обе стороны, разбита на ячейки. В каждой ячейке — один символ из алфавита. Особый символ λ («лямбда») означает пустую ячейку.

  • Каретка (головка) — стоит над одной ячейкой, читает её символ, может записать новый и сдвинуться на одну ячейку влево или вправо. У каретки есть текущее состояние (q₀, q₁, …); в начале — q₀.

  • Программа — таблица переходов. Строки — состояния, столбцы — символы. На пересечении «текущее состояние × символ под кареткой» стоит команда.

Каждая команда состоит из трёх частей:

(какой символ записать) , (куда сдвинуть каретку) , (в какое состояние перейти)

Сдвиг обозначают буквами: L — влево, R — вправо, N — остаться на месте, S — стоп (машина останавливается).

📌 Один шаг машины

Смотрим состояние каретки и символ под ней → находим клетку таблицы → записываем новый символ в текущую ячейку → сдвигаем каретку (L/R/N) → переходим в новое состояние. И так до команды стоп (S).