Универсальная машина Тьюринга: одна программа для всех

Обычная машина Тьюринга умеет ровно одно: её таблица переходов жёстко зашита и решает единственную задачу. Универсальная машина Тьюринга ломает это ограничение. Она принимает на вход не только данные, но и описание другой машины - её программу, закодированную как строку символов, - и затем точно воспроизводит поведение этой машины. Одна фиксированная машина, способная исполнить любой алгоритм: именно эта идея, доказанная Аланом Тьюрингом в 1936 году, стала математическим прообразом программируемого компьютера. Разберём, как устроена универсальная машина Тьюринга, как она кодирует и эмулирует чужие машины и почему она занимает центральное место в теории вычислимости.

Ниже - интерактивный сборщик: выберите, что именно нужно разобрать про UTM, и получите развёрнутый ответ с примером кодирования.

Что такое универсальная машина Тьюринга

Универсальная машина Тьюринга (universal Turing machine, UTM) - это одна конкретная машина Тьюринга $U$, которая способна моделировать работу любой другой машины Тьюринга. На вход $U$ подаётся пара: код $\langle M \rangle$ моделируемой машины $M$ и её входное слово $w$. Результат работы $U$ на этой паре совпадает с результатом работы $M$ на $w$:

$$U(\langle M \rangle, w) = M(w).$$

Если $M$ на входе $w$ останавливается и выдаёт ответ - то же самое сделает и $U$. Если $M$ зацикливается - зациклится и $U$. Машина $U$ не «знает» заранее ни одного алгоритма, кроме одного: как читать чужую программу и пошагово её выполнять. В этом смысле UTM - это интерпретатор, реализованный средствами самой модели вычислений.

Рассчитать для своей задачи

Ключевое слово здесь - универсальность. До работы Тьюринга считалось естественным, что каждая вычислительная задача требует своего отдельного устройства. UTM показала: достаточно одного устройства, если уметь передавать ему программу как данные.

Кодирование машины: программа становится данными

Чтобы $U$ могла прочитать машину $M$, машину нужно записать в виде строки - закодировать. Это центральный приём всей конструкции. Машина $M$ полностью задаётся конечным набором переходов вида:

$$\delta(q_i, a) = (q_j, b, D),$$

где $q_i$ - текущее состояние, $a$ - прочитанный символ, $q_j$ - новое состояние, $b$ - записываемый символ, $D \in \{L, R\}$ - направление сдвига головки. Каждое такое правило кодируется числом или блоком символов; все правила склеиваются разделителями в одну длинную строку $\langle M \rangle$.

Например, состояния можно пронумеровать в унарном коде ($q_1 = 1$, $q_2 = 11$, $q_3 = 111$), символы - тоже, направления обозначить парой кодов, а между правилами поставить разделитель. Тогда вся таблица переходов превращается в конечное слово над фиксированным алфавитом. Конкретная схема кодирования не важна - важно лишь, что она существует и обратима: по строке $\langle M \rangle$ однозначно восстанавливается машина $M$.

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

Как UTM эмулирует чужую машину

Получив на ленте код $\langle M \rangle$ и вход $w$, универсальная машина организует на своей ленте три области:

1. Описание переходов $M$ - таблица правил, прочитанная из $\langle M \rangle$.
2. Лента моделируемой машины - копия содержимого, с которым работает $M$, с пометкой положения её головки.
3. Текущее состояние $M$ - записанный код состояния, в котором сейчас находится $M$.

Рассчитать для своей задачи

Дальше $U$ работает циклом, имитируя один шаг $M$ за итерацию:

• считывает символ под «головкой» моделируемой ленты;
• находит в области правил подходящий переход $\delta(q_i, a)$;
• записывает новый символ $b$ в моделируемую ленту;
• обновляет код текущего состояния на $q_j$;
• сдвигает пометку головки влево или вправо согласно $D$.

Когда $M$ переходит в принимающее или отвергающее состояние, $U$ останавливается с тем же вердиктом. Один шаг $M$ обходится универсальной машине в несколько проходов по ленте, поэтому работа $U$ медленнее, но логически она воспроизводит $M$ точно.

Почему достаточно одной машины: тезис Чёрча-Тьюринга

Существование UTM тесно связано с тезисом Чёрча-Тьюринга: всё, что вообще вычислимо в интуитивном смысле, вычислимо машиной Тьюринга. Если это так, то универсальная машина вычисляет всё вычислимое - ведь она моделирует любую машину Тьюринга, а значит и любой алгоритм.

Отсюда следует фундаментальный вывод: не нужно строить новое устройство под каждую задачу. Достаточно одного универсального исполнителя и сменной программы. Современный процессор - физическое воплощение этой идеи: фиксированная аппаратура исполняет произвольный код, загружаемый в память. UTM - это формальная модель «компьютера общего назначения», появившаяся раньше самих компьютеров.

Насколько маленькой может быть UTM

Естественный вопрос: какой минимальный размер у универсальной машины? Размер измеряют парой «число состояний $\times$ число символов алфавита». Чем меньше произведение, тем «проще» машина. Исследователи десятилетиями строили всё более компактные UTM:

$$\begin{aligned} &\text{Шеннон, 1956} && \text{машина с 2 символами (за счёт роста состояний)} \\ &\text{Минский, 1962} && \text{7 состояний, 4 символа} \\ &\text{Роджожа, 2000-е} && \text{вплоть до } (2,3),\ (3,2) \text{ - на грани универсальности} \end{aligned}$$

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

UTM и проблема остановки

Универсальная машина - это инструмент, который делает невозможным один соблазнительный замысел. Раз $U$ умеет запускать любую $M$ на любом $w$, хочется добавить к ней «детектор зацикливания», который заранее сказал бы, остановится ли $M(w)$. Тьюринг доказал, что такой машины не существует: проблема остановки алгоритмически неразрешима.

Доказательство как раз опирается на универсальность. Если бы существовала машина $H$, решающая проблему остановки, из неё диагональным приёмом строится противоречивая машина, которая останавливается тогда и только тогда, когда не останавливается. Возможность подать код машины самой себе на вход - прямое следствие того, что программы кодируются как данные, на чём и стоит UTM.

Частые ошибки

• Путать UTM с обычной машиной Тьюринга. Любая машина Тьюринга вычисляет одну функцию; универсальной её делает именно способность принимать код другой машины как часть входа.
• Думать, что UTM «мощнее» по разрешимости. Универсальная машина не решает ни одной задачи, которую не решает какая-то обычная машина Тьюринга. Она лишь объединяет их все в одном устройстве, но множество вычислимых функций то же самое.
• Считать кодирование $\langle M \rangle$ деталью. Без обратимого кодирования «программа как данные» вся конструкция рассыпается - именно оно превращает машину в строку и делает универсальность возможной.
• Игнорировать накладные расходы. UTM воспроизводит $M$ верно, но не мгновенно: один шаг $M$ требует нескольких проходов, и время растёт.
• Смешивать универсальность и эффективность. Минимальные UTM универсальны, но чудовищно медленны; малый размер таблицы не означает быстрых вычислений.

FAQ

Чем универсальная машина Тьюринга отличается от обычной? Обычная машина имеет жёстко зашитую таблицу переходов и решает одну задачу. Универсальная принимает на вход код произвольной машины $\langle M \rangle$ вместе с данными $w$ и моделирует работу $M$ на $w$. Грубо говоря, обычная машина - это одна программа, а UTM - интерпретатор, исполняющий любую программу.

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

Существует ли самая маленькая универсальная машина Тьюринга? Известны крайне компактные UTM - например, машина Минского с 7 состояниями и 4 символами, а также машины на грани $(2,3)$ и $(3,2)$. Однако для самых малых машин понятие универсальности зависит от того, как разрешено кодировать вход, поэтому единого «рекордного минимума» без оговорок нет.

Коротко

Универсальная машина Тьюринга - это одна машина $U$, которая по коду $\langle M \rangle$ другой машины и её входу $w$ воспроизводит результат $M(w)$. Её сердце - приём «программа как данные»: машина кодируется строкой, которую $U$ читает и пошагово исполняет, имитируя ленту, состояние и переходы $M$. UTM не расширяет класс вычислимых функций, но объединяет все алгоритмы в одном устройстве, обосновывает идею компьютера с хранимой программой и служит опорой для доказательства неразрешимости проблемы остановки.