Машина Тьюринга

1936 год. Тьюринг пишет статью о математической логике - не о компьютерах, их ещё нет. Он придумывает воображаемую машину с лентой, чтобы доказать теорему. Через 9 лет фон Нейман использует эту идею для EDVAC. Через 80 лет каждый смартфон реализует архитектуру, описанную Тьюрингом на 36 страницах. UTM - самая влиятельная идея в истории вычислений.

• **Python exec() как UTM:** когда Python выполняет exec(code), он буквально реализует UTM - принимает описание программы (код) и входные данные, симулирует выполнение. Это не метафора, это прямая реализация концепции
• **LLVM IR:** промежуточное представление компилятора Rust/C++/Swift - это стандартное кодирование МТ. Разные языки компилируются в один IR, который потом оптимизируется и транслируется в машинный код
• **WebAssembly:** открытый стандарт бинарного формата для браузеров - кодирование UTM, портируемое между архитектурами. Rust, C, C++, Go компилируются в WASM и запускаются в браузере
• **Game of Life:** клеточный автомат Конвея Тьюринг-полон. Паттерн Golly реализует работающий x86-процессор внутри Game of Life - UTM, реализующая другую UTM

Формальное определение МТ

1936 год. Алан Тьюринг задаётся вопросом: что значит «вычислить»? Он описывает воображаемую машину - бесконечную ленту с символами и головку, которая читает, пишет и двигается. Никаких регистров, никаких ОЗУ, никакого кэша. Семь компонентов - и этого достаточно для описания любого алгоритма, когда-либо написанного человечеством.

**Машина Тьюринга M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject):** Q - конечное множество состояний. Σ - входной алфавит (без символа-пустышки ␣). Γ - ленточный алфавит (Σ ⊆ Γ, ␣ ∈ Γ). δ: Q × Γ → Q × Γ × {L, R} - функция переходов. q₀ - начальное состояние. q_accept и q_reject - принимающее и отвергающее состояния.

Конфигурации и вычисления

**Конфигурация** МТ - мгновенный снимок состояния: текущее состояние + содержимое ленты + позиция головки. Записывается как `uqv`, где q - состояние, u - левая часть ленты, v - правая (начиная с текущей позиции). Вычисление - цепочка конфигураций, связанных переходами δ.

МТ может **зависнуть** - войти в бесконечный цикл без достижения q_accept или q_reject. Это фундаментальное свойство, а не ошибка реализации. Язык **разрешим** если МТ всегда останавливается. Язык **распознаваем** если МТ принимает все строки языка, но может зависнуть на строках не из языка.

Разрешимость и распознаваемость

Три исхода МТ на входе w: принять (q_accept), отвергнуть (q_reject), зависнуть. Язык L **распознаваем** (Turing-recognizable, RE) если существует МТ, принимающая все w ∈ L. Язык L **разрешим** (decidable) если существует МТ, которая принимает все w ∈ L и отвергает все w ∉ L - никогда не зависает.

**Теорема:** L разрешим тогда и только тогда, когда L ∈ RE и L̄ ∈ RE (оба распознаваемы). Доказательство: запускаем оба распознавателя параллельно (через доvetailing - чередующееся выполнение шагов). Один обязательно остановится и даст ответ. Этот аргумент «параллельного запуска» используется в десятках доказательств.

Универсальная машина Тьюринга

МТ можно **закодировать как строку** - описать переходы в виде текста. Универсальная МТ (UTM) принимает на вход `<M, w>` - описание МТ M и входную строку w - и симулирует M на w. UTM - первый в истории **интерпретатор**: программа, исполняющая другие программы. Тьюринг описал это в 1936 году - за 10 лет до первого компьютера с хранимой программой.

UTM делает возможным **программируемые компьютеры**: вместо тысячи специализированных машин - одна универсальная с разными программами. Фон Нейман читал черновик Тьюринга в 1945-м и использовал идею UTM при проектировании EDVAC. Принцип «программа хранится в той же памяти, что и данные» - прямое следствие архитектуры UTM.

Ключевые идеи

• **МТ = (Q, Σ, Γ, δ, q₀, q_accept, q_reject):** функция переходов δ: (состояние, символ) → (состояние, запись, направление). Три исхода: принять, отвергнуть, зависнуть
• **Разрешимый:** МТ всегда останавливается. **Распознаваемый (RE):** принимает L, может зависать на L̄. L разрешим ⟺ L ∈ RE и L̄ ∈ RE
• **UTM:** симулятор произвольной МТ по её описанию. Основа принципа хранимой программы - каждый CPU это физическая UTM
• **МТ - не игрушка:** тезис Чёрча-Тьюринга утверждает эквивалентность МТ и всех разумных моделей вычислений. Ограничения МТ = ограничения любого реального языка

Связанные темы

МТ - вершина иерархии Хомского и основа теории вычислимости:

• Тезис Чёрча-Тьюринга — Утверждает эквивалентность МТ, λ-исчислению и всем другим разумным моделям вычислений
• Проблема остановки — Первая неразрешимая задача - доказана через диагонализацию свойств UTM
• Варианты МТ — Многоленточные, недетерминированные МТ - удобнее, но эквивалентны по вычислительной мощности

Вопросы для размышления

• Python-интерпретатор реализует UTM. Значит ли это, что Python может вычислить всё то же, что и МТ? Что ограничивает реальный Python?
• МТ для {0^n 1^n} работает O(n²) шагов, современный компьютер - O(n). Означает ли это, что компьютер мощнее МТ как модели вычислений?
• Если программа на Python уходит в бесконечный цикл, как это соотносится с зависанием МТ? Можно ли написать программу, которая обнаруживает зависание другой программы?

Связанные уроки

• comp-18-type-checking