Основные компоненты
Машина Тьюринга удивительно проста. Она состоит всего из трех частей, которых достаточно для любого вычисления.
1. Головка (Сканер/Процессор)
Это "мозг" и "руки" машины. Головка всегда находится над одной ячейкой ленты.
- Читает: Видит символ в текущей ячейке (например, '0', '1' или пробел).
- Пишет: Может стереть старый символ и написать новый.
- Двигается: Перемещается на одну ячейку влево (←) или вправо (→).
2. Лента (Память)
Представьте себе бесконечную кассу с отсеками (ячейками), уходящими в бесконечность влево и вправо.
Важно: В каждый момент времени заполнена данными только конечная часть ленты. Остальные ячейки считаются пустыми (обычно обозначаются символом пробела '_' или '∅'). Это наша оперативная память.
3. Таблица правил (Программа)
Это инструкция для головки. В ней записано: "Если ты в состоянии А и видишь символ Х, сделай Y, перейди в состояние В и сдвинься".
Например, простая программа для сложения двух чисел может содержать всего десяток таких правил.
Интерактивная модель
Перед вами действующая машина Тьюринга. На ленте записано число двоичными цифрами. Нажимайте "Сделать шаг", чтобы увидеть, как головка выполняет программу.
Действие: Жду запуска
Как она думает прямо сейчас:
Смотрю: Головка видит символ в желтой ячейке.
Сверяюсь: Машина ищет этот символ в таблице правил.
Меняю: Перезаписывает символ и едет дальше.
