Машины Тьюринга и вычислимые функции

Мотивация: что такое «алгоритм»?

До 1930-х годов понятие «алгоритм» было интуитивным. Тьюринг в 1936 году предложил математическую модель вычислений — машину Тьюринга (МТ) — и обосновал тезис: любое, что человек может вычислить «механически», вычисляет МТ. Это позволило строго доказать существование невычислимых функций.

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

Детерминированная МТ M = (Q, Σ, Γ, δ, q₀, q_acc, q_rej):

Q — конечное множество состояний.
Σ ⊆ Γ — входной алфавит (□ ∉ Σ, □ — символ пробела).
Γ — ленточный алфавит.
δ: Q × Γ → Q × Γ × {L, R} — функция переходов (прочитать, записать, сдвинуть головку).
q₀ — начальное состояние; q_acc, q_rej — принимающее и отвергающее.

Конфигурация: (q, u, a, v) — состояние q, лента = u·a·v, головка над a. Компактная запись: u_q_v (подчёркивает позицию головки).

Принятие: M принимает w, если вычисление из начальной конфигурации достигает q_acc. Отвергает — если достигает q_rej. Зацикливается — если не достигает ни того, ни другого.

Разрешитель: МТ, которая останавливается на любом входе (принять или отвергнуть). Если L принимается разрешителем — L разрешим (decidable). Если только распознаётся МТ — L перечислим (RE, recursively enumerable).

Тезис Черча–Тьюринга

Тезис: Функция вычислима «в интуитивном смысле» ⟺ вычислима машиной Тьюринга.

Это тезис (философский принцип), а не математическая теорема: нельзя формально доказать, что интуитивное понятие совпадает с МТ. Косвенное подтверждение — совпадение МТ с λ-исчислением (Черч), примитивно-рекурсивными функциями + минимизацией (Гёдель–Эрбран–Клини), RAM-машинами.

Частично рекурсивные функции: замкнуты относительно суперпозиции, примитивной рекурсии и μ-минимизации. Совпадают с вычислимыми на МТ.

Языки и иерархия

Разрешимые ⊊ RE (перечислимые) ⊊ Все языки.
co-RE = {L : L̄ ∈ RE}. L разрешим ⟺ L ∈ RE ∩ co-RE.

Численный пример

Задача: Описать работу МТ, распознающей палиндромы над {a, b}.

Шаг 1. Идея: читать первый символ, запоминать в состоянии (состояние кодирует «первый символ = a» или «= b»), перемещаться в конец, проверять совпадение последнего символа, стирать оба, повторять.

Шаг 2. Состояния Q = {q₀, qₐ, q_b, q_seek_a, q_seek_b, q_return, q_acc, q_rej}.

Шаг 3. Трассировка на w = «aba»:

Начало: _q₀_aba. Читаем 'a', запоминаем (переходим в qₐ), стираем первый символ (→ □): □qₐ_ba. Перемещаемся вправо до конца: □b_qₐ_a. Читаем последний 'a': совпадает с qₐ → стираем: □b_q_ret□.
Возвращаемся влево: q_ret□b□. Находим следующий символ 'b', переходим в q_b, идём вправо: □_q_seek_b_b□. Последний 'b' совпадает: □q_ret□□□. Лента пуста → принять ✓.

Шаг 4. На w = «ab»:

Читаем 'a' → qₐ: □_qₐ_b. Последний символ 'b' ≠ 'a' → отвергнуть ✓.

Формально МТ имеет O(1) состояний и работает за O(n²) шагов (каждый проход — O(n), n/2 проходов).

Реальное приложение

Компиляторы: синтаксический анализ проверяет, является ли программа «словом» в языке грамматики. Грамматики Хомского соответствуют уровням иерархии МТ. Регулярные выражения — конечные автоматы; парсинг JSON — контекстно-свободные грамматики; полный язык программирования — разрешимая МТ.

Дополнительные аспекты

Теория вычислимости изучает, какие функции в принципе могут быть вычислены любым формальным алгоритмом. Тезис Чёрча–Тьюринга утверждает эквивалентность всех разумных моделей: машины Тьюринга, λ-исчисление, рекурсивные функции, машины с регистрами, клеточные автоматы (Game of Life Конвея — полна по Тьюрингу). Из неразрешимости проблемы остановки следует неразрешимость проверки эквивалентности программ, проверки покрытия путей выполнения, верификации произвольных программ. Тем не менее на практике статические анализаторы (Coverity, Infer, MIRAI) применяют аппроксимирующие алгоритмы — они дают конечный ответ за приемлемое время, жертвуя либо полнотой (могут пропустить ошибку), либо корректностью (могут поднять ложную тревогу).

Связь с другими разделами математики

Понятие вычислимости естественно связывается с теорией дифференциальных уравнений через результаты Питера Пура (Pour-El) и Йорга Ричардса о существовании хорошо поставленных задач для уравнения теплопроводности и волнового уравнения, чьи решения на некоторых точках оказываются невычислимыми при вычислимых начальных данных. Это иллюстрирует, что даже классические задачи анализа могут скрывать «вшитый» эффект универсальной машины Тьюринга.

В алгебре ключевым мостом является проблема слова в группах. Работы Новикова и Бунге (1940-е) показали существование конечно заданных групп с неразрешимой проблемой слова; конструкция опирается на кодирование конфигураций машин Тьюринга в соотношениях групп. Позднее Адыян и Рабинович развивали эти идеи, связывая рекурсивно перечислимые множества с нормальными формами слов.

В топологии известен результат Марка Дэвиса и соавторов о неразрешимости проблемы распознавания шаровости 3-многообразий: существует алгоритмически неразрешимое различение, является ли данное компактное 3-многообразие топологическим 3-шаром. Конструкции также используют симуляцию машин Тьюринга на уровне фундаментальных групп и триангуляций.

Теория вероятностей соприкасается с вычислимостью через алгоритмическую теорию информации. Колмогоров, Левин и Чайтин определяют случайность последовательности через несуществование короткой программы на универсальной машине Тьюринга, порождающей ее начальные отрезки. Возникает невычислимая константа Чайтина, связанная с вероятностью остановки универсальной машины.

Численные методы и вычислительная математика используют машины Тьюринга как эталон для анализа сложности. Классические работы Трейсера, Кохреста и Трауба исследуют, какие задачи численного интегрирования или решения нелинейных уравнений могут быть решены за полиномиальное число шагов модели Тьюринга, вводя понятие информационной сложности и связывая непрерывные задачи с дискретной теорией сложности.

Историческая справка и развитие идеи

Идея формализации алгоритма формировалась параллельно в нескольких традициях. В 1936 году Алан Тьюринг опубликовал в Proceedings of the London Mathematical Society статью «On Computable Numbers, with an Application to the Entscheidungsproblem», где ввел абстрактную машину и доказал неразрешимость задачи об общезначимости формул первого порядка. Независимо Алонзо Черч в 1936 году в журнале American Journal of Mathematics использовал λ-исчисление и понятие эффективной вычислимости для доказательства тех же пределов формальных систем. Курт Гёдель еще в 1934 году в лекциях в Принстоне обсуждал примитивно-рекурсивные функции, а Гёдель, Эрбран и Клини (1930-е) добавили оператор минимизации, создав альтернативное определение частично рекурсивных функций, эквивалентное тьюринговскому. Эмиль Пост предложил свою модель продукции (Post systems) и сформулировал проблему Поста о равновесии, позже оказавшуюся эквивалентной задачам о неразрешимости. Во второй половине XX века теория развивалась в сторону классификации неразрешимых задач и иерархий по степеням сложности.