Машина Тьюринга: формальное определение

Цели урока

• Назвать семь компонентов формального определения TM и объяснить роль каждого
• Читать и писать конфигурации (ID) и трассировать цепочку вычисления
• Воспроизвести схему доказательства неразрешимости Halting Problem
• Различать разрешимые, рекурсивно-перечислимые и нераспознаваемые языки

Предварительные знания

• Вычислимые и невычислимые функции

Alan Turing, 1936. Одна бумага. 12 страниц. До появления компьютеров Тьюринг доказал, что некоторые задачи нельзя решить алгоритмически - в принципе. LLVM компилятор, ChatGPT inference engine, Python интерпретатор - все они реализуют ту же машину Тьюринга. И все они не могут решить Halting Problem.

• **LLVM / GCC компиляторы** - любой компилятор реализует TM: читает исходный код (лента), применяет правила грамматики (переходы), выдаёт машинный код (результат)
• **Python интерпретатор** - байткод-цикл интерпретатора прямо соответствует функции переходов delta: текущий опкод + стек = следующее состояние
• **Статический анализ кода** - lint-инструменты вроде mypy и tsc ограничены Halting Problem: они не могут доказать корректность произвольной программы
• **Формальная верификация** - Coq, Lean, Isabelle используют конфигурации TM для доказательства корректности алгоритмов
• **Квантовые компьютеры** - квантовая TM быстрее классической для отдельных задач, но не решает неразрешимые задачи - пределы вычислимости те же

Тьюринг 1936 - бумага, изменившая математику

В 1936 году Алан Тьюринг опубликовал 'On Computable Numbers, with an Application to the Entscheidungsproblem'. Ему было 24 года. Бумага решала задачу Гильберта о разрешимости (Entscheidungsproblem) - ответом оказалось 'нет'. Параллельно Алонзо Чёрч доказал то же через лямбда-исчисление. Вместе они сформулировали тезис Чёрча-Тьюринга: все разумные формализации вычисления эквивалентны. Компьютеров ещё не было - Тьюринг изобрёл их концепцию, чтобы доказать теорему о пределах математики.

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

**Alan Turing, 1936. 12 страниц. До появления электронных компьютеров.** Тьюринг описал устройство с бесконечной лентой и головкой - и доказал, что оно вычисляет всё, что вычислимо в принципе. LLVM компилирует C++ в ассемблер. Python интерпретатор исполняет байткод. Оба - реализации той же абстракции. Семь компонентов, которые нельзя упростить без потери мощности.

**Машина Тьюринга** - это семёрка M = (Q, Sigma, Gamma, delta, q0, q_accept, q_reject), где: Q - конечное множество состояний, Sigma - входной алфавит (без пробела), Gamma - ленточный алфавит (Sigma c Gamma, пробел в Gamma), delta: Q * Gamma -> Q * Gamma * {L, R} - функция переходов, q0 - начальное состояние, q_accept - принимающее, q_reject - отвергающее.

Минимализм здесь принципиален. Конечная память (состояния) + бесконечная лента (данные) + головка (адресация) + таблица переходов (программа). Убрать любой компонент - и модель слабеет. Добавить вторую головку - и мощность не меняется. Тьюринг нашёл минимум.

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

Снимок работающей машины в момент t - это **конфигурация** (мгновенное описание, ID). Три элемента: содержимое ленты, позиция головки, текущее состояние. Вычисление - цепочка конфигураций, связанных отношением перехода. Это не метафора - так TM доказываются корректными в Coq и Lean.

Конфигурация записывается как строка: uqv, где u - содержимое ленты слева от головки, q - текущее состояние, v - символ под головкой и всё правее. Например: 101 q3 10 означает состояние q3, головка на первом '1' из '10', слева '101'.

Принимающее вычисление - цепочка, которая заканчивается конфигурацией с q_accept. Отвергающее - с q_reject. Зависающее (looping) - бесконечная цепочка. Это разграничение критично: именно из-за третьего варианта Halting Problem неразрешима.

Проблема остановки - первое доказательство невычислимости

**1936. Тьюринг доказывает: нельзя написать программу, которая для произвольной программы и входа определяет, остановится ли она.** Не потому что компьютеры плохие. Не потому что задача сложная. По фундаментальным логическим причинам. Статический анализатор кода, дебаггер, верификатор - все они сталкиваются с этим пределом.

**Проблема остановки (Halting Problem)**: дана TM M и вход w. Останавливается ли M на w? Формально: HALT = {<M, w> | TM M останавливается на входе w}. Тьюринг доказал: HALT неразрешима - не существует TM H, которая всегда правильно отвечает да/нет.

Это не хитрый программистский трюк - это логическая структура диагонализации Кантора. Тот же метод, которым Кантор доказал несчётность вещественных чисел. Тьюринг применил его к вычислениям. Следствие для практики: ни один статический анализатор не может гарантированно определить завершаемость произвольной программы.

Язык машины Тьюринга

Каждая TM **задаёт язык** - множество строк, которые она принимает. Это мост между теорией вычислимости и теорией формальных языков. Тот же мост, по которому лексер и парсер компилятора проверяют корректность программы.

**Язык машины M** - это L(M) = {w в Sigma* | M(w) = accept}. Множество всех строк, на которых M останавливается в принимающем состоянии. Строки, на которых M отвергает или зависает, в L(M) не входят.

Критичное различие: **reject и loop** различны с точки зрения наблюдателя, но одинаковы с точки зрения языка (строки нет в L(M)). Именно эта асимметрия порождает разницу между разрешимыми и перечислимыми языками - тему следующего урока.

Возврат к началу: машина Тьюринга - простейшее устройство (лента + головка + правила), чья языковая мощь превосходит все конечные и магазинные автоматы. И всё же даже TM не может распознать **все** языки - нераспознаваемые языки существуют, как будет показано далее.

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

• **TM = (Q, Sigma, Gamma, delta, q0, q_accept, q_reject)** - семь компонентов полностью задают поведение машины
• **Конфигурация (ID)** фиксирует полный снимок: лента, позиция головки, состояние. Вычисление - цепочка конфигураций
• **Halting Problem неразрешима** - доказано через самоприменение и диагонализацию: H(<D, <D>>) ведёт к противоречию
• **L(M)** - язык машины - множество строк, на которых TM останавливается в q_accept
• **reject vs loop** - разные исходы для наблюдателя, но оба означают 'не в языке'
• Мощь модели - в минимализме: добавить вторую головку или ленту не меняет класс вычислимых функций

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

Машина Тьюринга - центральное понятие, связывающее вычислимость, формальные языки и сложность:

• Вычислимые и невычислимые функции — TM - формальная модель, через которую определяются вычислимые функции
• Разрешимые и RE-языки — Классификация языков по поведению TM (останавливается / зависает)
• Классы P и NP — Сложность измеряется числом шагов TM - прямое продолжение модели

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

• Почему Тьюринг выбрал ленту и головку, а не другую модель? Какие свойства ленты делают модель достаточно мощной?
• Если дать TM вторую ленту или вторую головку - станет ли она мощнее (решит ли больше задач)?
• Как пределы TM связаны с теоремой Гёделя о неполноте? Почему оба результата появились в одно время?

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

• comp-01 — Понятие вычислимой функции задано в предыдущем уроке
• comp-03 — Классификация языков (RE, рекурсивные) строится на поведении TM
• cplx-01 — Сложность алгоритмов измеряется числом шагов TM
• aut-01-fsm — FSM - частный случай TM без бесконечной ленты
• alg-01-big-o — Big-O описывает количество шагов в вычислении TM
• fl-18-turing-machine