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

Автомат из прошлой главы проверяет даты, почтовые адреса и номера телефонов, но не сосчитает скобки и не сравнит две половины строки: всё прошлое у него сжато в одно из конечного числа состояний. Стек справился со скобками, но споткнулся на строках вида aaabbbccc с равным числом букв каждого сорта. Глава кончилась предложением: дать автомату память без всяких ограничений — бесконечную ленту, на которой можно писать и к написанному возвращаться. Получится машина, проще которой трудно что-нибудь придумать, — и, как выяснится, сильнее которой не придумал никто.

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

Кембридж, 1935. Человек с карандашом

Слово computer в 1935 году означало не машину, а человека: вычислителя, который по инструкции считает таблицы для артиллеристов, астрономов, страховщиков. С него Тьюринг и начал, разобрав его работу на мельчайшие движения. Вычислитель пишет символы на бумаге в клетку и в каждый момент видит несколько клеток. Он помнит, на каком месте инструкции остановился, и состояний ума у него конечное число, иначе он путал бы близкие. По увиденному и запомненному он делает простейший шаг: меняет символ в клетке, переводит взгляд на соседнюю клетку, переходит к другому пункту инструкции.

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

Уровень 0. Лента, головка, таблица

У машины есть лента — ряд клеток, бесконечный в обе стороны. В каждой клетке записан один символ из конечного алфавита, обычно почти все клетки пусты: в них пробел, который мы будем рисовать знаком _. Над одной клеткой стоит головка. А внутри машины — конечный автомат из прошлой главы: он в каждый момент находится в одном из конечного числа состояний.

Шаг устроен так. Машина смотрит на пару «моё состояние, символ под головкой» и находит в своей таблице правило для этой пары. Правило говорит три вещи: какой символ записать в клетку, куда сдвинуть головку — влево, вправо или остаться на месте — и в какое состояние перейти. Если правила для пары нет, машина останавливается. Больше она ничего не умеет.

Машина Тьюринга — это лента, головка и конечная таблица правил вида «в состоянии $q$ вижу символ $a$ — пишу $b$, сдвигаюсь на $d$, перехожу в $r$». Таблицу пишут по строчке на правило. Вот машина из одного состояния, которая идёт вдоль двоичного числа и меняет каждую цифру на противоположную:

Чтобы описать машину в любой момент её работы, достаточно трёх вещей: что записано на ленте, где головка и в каком состоянии автомат. Эту тройку называют конфигурацией и записывают одной строкой: имя состояния в квадратных скобках ставят прямо перед клеткой, над которой стоит головка. Работа машины — это цепочка конфигураций, где каждая следующая однозначно получается из предыдущей по таблице. Модуль курса cs.turing умеет печатать такую цепочку.

Пять конфигураций: головка четыре раза шагнула вправо, переворачивая цифры, и в пятой стоит над пробелом, для которого правила нет. Машина остановилась, на ленте 0100. Теперь ваша очередь: с этой же машины начинается игра. Её таблица под лентой устроена как сетка, где строки соответствуют состояниям, столбцы символам, а в клетке записано правило.

На первом уровне не хватает одного правила: машина не знает, что делать с единицей, и останавливается на первой же. Допишите его. Если всё верно, «Проверить» прогонит машину на нескольких числах, включая пустую ленту, и отметит уровень пройденным. Уже здесь видно, как придирчива проверка: тест смотрит и на ответ, и на то, остановилась ли машина. Таблица, которая вечно бегает вправо, ответа не даёт вовсе.

Уровень 2. Плюс один

На втором уровне машине впервые придётся считать: на ленте двоичное число, головка на его первой цифре, и к числу нужно прибавить единицу. На бумаге для этого идут к младшему разряду, то есть к правому краю. Последняя цифра 0 становится 1 — и готово. Последняя цифра 1 становится 0, и единица переносится в следующий разряд слева, где всё повторяется. Это перенос, который в главе 30 бежал по цепочке сумматоров, только здесь его несёт головка.

Значит, машине нужны два состояния. Первое идёт вправо до пробела, ничего не меняя, а на пробеле делает шаг назад и переходит во второе. Второе несёт перенос влево: единицы превращает в нули и идёт дальше, на первом нуле пишет единицу и останавливается. Остался крайний случай. Что будет с числом 111? Перенос пройдёт все разряды и упрётся в пробел слева от числа. Подумайте, какое правило нужно для этой пары, — и соберите машину на втором уровне игры.

Уровень 3. Удвоение: метки на ленте

Теперь число записано в единичной системе — 111 значит три, как зарубки на палке, — и его нужно удвоить: оставить на ленте шесть единиц. Автомат из прошлой главы этого не смог бы и в принципе. Ему пришлось бы помнить, сколько единиц он прошёл, а памяти у него столько, сколько состояний, и на любой конечный набор состояний найдётся число побольше.

У машины Тьюринга память есть — лента, и главный приём работы с ней — метки. Машина помечает обработанную единицу, заменяя её на x, бежит в конец и дописывает туда копию, тоже x, возвращается к первой непомеченной единице и повторяет. Когда единиц не останется, на ленте будут только иксы, вдвое больше, чем было единиц; осталось превратить их обратно в единицы. Тонкое место — возвращение: идя влево, машина должна понять, где кончаются копии и начинаются необработанные единицы, и заметить, что единиц не осталось совсем. У авторского решения пять состояний и одиннадцать правил.

На длинном числе головка снуёт туда и обратно, каждый раз чуть дальше. У авторской машины двадцать единиц удваиваются за 880 шагов, сорок — за 3360. Время растёт как квадрат длины: машина, у которой одна головка, расплачивается беготнёй за то, что процессор с памятью по адресу из главы 31 делает одним прыжком. Для вопроса «что можно вычислить» эта разница не важна, для вопроса «как быстро» — очень. Ко второму вопросу мы вернёмся в главе 57.

Уровень 4. Палиндром

Палиндром — слово, которое одинаково читается в обе стороны: «шалаш», «топот», abba. В главе 7 Python проверял это одной строчкой, сравнивая строку с её разворотом. В прошлой главе выяснилось, что конечный автомат не сравнит две половины строки, а значит, не по силам ему и палиндромы: дочитав до середины, он должен помнить всю первую половину, а она бывает сколь угодно длинной.

Машине Тьюринга хватает челнока. Она стирает первую букву и запоминает её — в состоянии: «несу a» или «несу b», это два разных состояния. Бежит вправо до пробела, шагает назад и смотрит на последнюю букву. Не совпала — ответ «нет». Совпала — стирает и её, возвращается к началу и повторяет со словом, ставшим на две буквы короче. Когда стирать нечего, ответ «да». Ответ — это состояние, в котором машина остановилась: в игре для этого есть два особых состояния, «да» и «нет».

Сколько стоит челнок? На слове длины $n$ машина пробегает его почти целиком, потом слово длины $n - 2$, потом $n - 4$… Это сумма из главы 13, около $n^2/2$ шагов. Посчитаем точно на машине, которую модуль курса знает под именем челнока.

Удвоили длину — шагов стало почти вчетверо больше, и число шагов держится рядом с $n^2/2$. Внизу диаграмма «пространство — время»: в каждой строке лента после очередного шага, время идёт сверху вниз. Слово тает с двух концов, а головка рисует зигзаг. Квадрат здесь не случаен: можно доказать, что любой машине с одной лентой на палиндромы нужно порядка $n^2$ шагов. Машине с двумя лентами хватает линейного времени: она копирует слово на вторую ленту и сравнивает, идя навстречу.

Уровень 5. Поровну

На лестнице машин из прошлой главы над конечным автоматом стоит автомат со стеком. Он проверяет скобки, но спотыкается на строках вида aaabbbccc: чтобы сравнить число a с числом b, стек приходится опустошить, и для c ничего не остаётся. Машине Тьюринга снова помогают метки. За один проход слева направо она вычёркивает по одной a, b и c, заменяя их на x, и заодно следит за порядком букв. Потом возвращается к началу и повторяет. Нужной буквы в проходе не нашлось — «нет»; вычёркивать больше нечего — «да».

Пройдя пятый уровень, вы поднялись на лестнице машин на две ступени выше конечного автомата. Выше машины Тьюринга на этой лестнице ничего нет: языки, которые она распознаёт, — самый широкий класс в таблице Хомского. Почему выше ничего не построить — вопрос всей оставшейся главы.

Уровень 6. Усердный бобёр

Последний уровень — соревнование. Лента пуста, символов два — пробел и единица, состояний не больше трёх, не считая остановки. Постройте машину, которая проработает как можно дольше — и всё-таки остановится. Машина, которая не останавливается, очков не получает: иначе любой написал бы бесконечный цикл. Эту игру в 1962 году придумал венгерский математик Тибор Радо и назвал задачей об усердном бобре: бобёр, который трудится дольше всех, но в конце концов отдыхает.

Рекорд для трёх состояний — 21 шаг, больше не бывает. Доказать это можно перебором: машин с тремя состояниями конечное число, их можно выписать все и для каждой выяснить, остановится ли она и когда. Для двух состояний рекорд — 6 шагов, для четырёх — 107. Вся трудность спрятана в слове «выяснить». Рекорд для пяти состояний ждал доказательства больше шестидесяти лет, а для шести он неизвестен и, возможно, не станет известен никогда. Почему — об этом следующая глава, где бобёр вернётся.

Машина за двенадцать строк

Игра на этой странице написана на JavaScript, модуль cs.turing — на Python, но в обоих сердце одно и то же, и оно короче этого абзаца. Таблица хранится в словаре: ключ — пара «состояние, символ», значение — тройка «что записать, куда сдвинуться, куда перейти». Лента — тоже словарь, от номера клетки к символу, и пустых клеток в нём нет вовсе. Так лента получается бесконечной в обе стороны, а клетки слева от начала получают отрицательные номера.

Функция возвращает состояние, в котором машина остановилась, ленту без пробелов по краям и число шагов. Если нажать «Шаги», видно, как меняются cells и head: в них и живут конфигурации. В этом коде есть одна шероховатость: если машина не остановилась за limit шагов, функция всё равно вернёт ленту, как будто всё в порядке. Аккуратный симулятор в таком случае говорит «не знаю, не дождался»; написать его — одна из задач главы.

Функции run, кстати, всё равно, какую машину выполнять: прибавление единицы, палиндромы, бобра. Машина для неё — данные, словарь, который можно прочитать из файла, получить по сети, сгенерировать другой программой. Так одна программа выполняет любую машину.

Таблица на ленте

Тьюринг заметил это в той же статье 1936 года и сделал следующий шаг: построил такую программу в виде машины Тьюринга. Таблица любой машины — конечный текст, её можно записать на ленту, как мы записывали число. Тьюринг описал одну машину $U$ с одной фиксированной таблицей, которая читает с ленты описание другой машины $M$ и вход для неё, а потом делает то же, что сделала бы $M$: шаг за шагом, бегая между описанием и данными. Её называют универсальной машиной.

Универсальная машина медленнее той, которую выполняет: на каждый шаг чужой машины она делает десятки и сотни своих, ведь ей приходится искать правило в описании. Но платит она временем, а умеет столько же. И нужно для универсальности совсем немного. В 1962 году Марвин Минский построил универсальную машину с семью состояниями и четырьмя символами, позже Юрий Рогожин и другие нашли ещё более скромные, например с четырьмя состояниями, шестью символами и всего 22 правилами.

Вам эта идея знакома из главы 32: программа лежит в той же памяти, что и данные, а одна неизменная схема, процессор, выполняет любую программу. Логик Мартин Дэвис, написавший и историю вычислений, убедительно показывал, что идея Тьюринга повлияла на то, как фон Нейман в 1945 году описал EDVAC. Друг друга они знали по Принстону: в 1938 году фон Нейман звал Тьюринга остаться у него ассистентом. Универсальная машина — это компьютер за десять лет до компьютеров.

Принстон, 1936. Другая дорога

С Алонзо Чёрчем мы встречались в главе 10: его λ-исчисление — язык, где нет ничего, кроме функций. Чёрч предложил считать вычислимым всё, что выражается в λ-исчислении, и весной 1936 года доказал с его помощью, что у проблемы разрешения нет решения. Тьюринг узнал об этом, когда его статья была почти готова. Дороги оказались настолько разными, что статью всё равно напечатали — с приложением, где Тьюринг показывает: его машины и λ-исчисление вычисляют одно и то же.

У Чёрча было определение, у Тьюринга — объяснение, почему оно правильное. λ-исчисление выглядит как произвольная формальная игра, а машина Тьюринга выросла из разбора того, что делает человек с карандашом, — в этом её убедительность. Чёрч, рецензируя статью своего ученика, признал, что после неё отождествление вычислимости по Тьюрингу с вычислимостью в обычном смысле становится очевидным. В той же рецензии он впервые написал «машина Тьюринга».

Утверждение «всё, что можно вычислить механической процедурой, вычисляет машина Тьюринга» называют тезисом Чёрча — Тьюринга; тезисом его в 1940–1950-х стал называть Стивен Клини. Доказать тезис нельзя: «механическая процедура» — понятие неформальное, а доказывают только утверждения о формальных. Это скорее определение, проверенное временем. Тезис можно было бы опровергнуть, предъявив способ вычислять, который явно механический, но машиной Тьюринга не воспроизводится. За девяносто лет такого способа не нашлось. Зато нашлось множество моделей вычислений, придуманных независимо и совсем непохожих, — и все оказались равносильны машине Тьюринга.

Вот одна задача — удвоить число — на четырёх таких моделях. Python. Машина Тьюринга с третьего уровня игры. Brainfuck из главы 49: удвоитель на нём — семь команд. И числа Чёрча из главы 10, где удвоить $n$ значит повторить действие $n$ раз, а потом ещё $n$ раз.

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

Все машины равны

Это несложно, если позволить машине большой алфавит. Пусть символы ленты — числа от 0 до 255, как клетки Brainfuck, а состояние машины — номер текущей команды программы. Тогда каждая команда превращается в правила сама собой: + в состоянии $i$ пишет $v + 1$ на место $v$ и переходит в состояние $i + 1$; > сдвигает головку; [ смотрит на символ и переходит либо в $i + 1$, либо за парную скобку. Лента Brainfuck и лента машины здесь одна и та же — недаром Коррадо Бём в 1964 году описал свой язык P′′, предка Brainfuck, именно для машины с лентой. Напишем переводчик.

Таблица получилась большая — 256 правил на каждую команду, — но машина по ней выполняет программу шаг в шаг. Можно обойтись и двоичным алфавитом: каждое число от 0 до 255 займёт на ленте восемь клеток, и машина станет медленнее, но не слабее. Так же доказывают и остальные равносильности: две ленты заменяют одной, двустороннюю ленту — односторонней, большой алфавит — двоичным.

Осталось направление «машина Тьюринга выполняет Python». Его доказывают цепочкой, и все звенья вы уже прошли. Интерпретатор Python — программа на C. Её компилятор переводит в машинный код (глава 33), машинный код исполняет процессор (глава 32), а процессор с памятью — это конечная таблица переходов плюс массив ячеек. Машина Тьюринга может хранить на ленте память процессора парами «адрес: значение» и, бегая по ленте, выполнять его команды одну за другой. Получится мучительно медленно, но получится.

Систему, которая умеет выполнять любую машину Тьюринга, называют полной по Тьюрингу. Python, C, Brainfuck, λ-исчисление, процессор «Искры-8» — полны. Конечный автомат и регулярные выражения из прошлой главы — нет: скобки и палиндромы им не по силам. Чтобы стать полной, системе нужны три вещи: неограниченная память, способ выбирать действие по прочитанному и способ повторять. Убери любую — и полнота пропадает.

Жизнь на клетчатой бумаге

Всё, что было до сих пор, придумано нарочно: машину Тьюринга — чтобы вычислять, Brainfuck — ради самого маленького компилятора на свете. Но полнота находится и там, где вычислительной машины не видно вовсе. Самый знаменитый пример появился в 1970 году на клетчатой бумаге: несколько правил о соседях, ничем не напоминающих процессор.

Правила «Жизни» помещаются в две строки. Мёртвая клетка, у которой ровно три живых соседа, оживает. Живая клетка, у которой два или три живых соседа, живёт дальше, остальные умирают — от одиночества или тесноты. Всё обновляется одновременно: новое поколение считается целиком по старому, как регистры по такту в главе 31. Такое устройство — сетка клеток, у каждой конечное число состояний, одинаковое правило по соседям — называют клеточным автоматом. Убедимся, что Конвей свои пятьдесят долларов проиграл: посчитаем живые клетки ружья Госпера.

Каждые 30 поколений — ровно на пять клеток больше: столько в одном планере. Ружьё стреляет без конца, и узор растёт неограниченно. Функция step при этом не перебирает бесконечную доску: соседей она считает только вокруг живых клеток, ведь ожить может лишь клетка рядом с живой. Это словарь из главы 8 в роли счётчика.

Планер можно считать сигналом: поток планеров из ружья — это последовательность единиц, пропущенный планер — ноль. Два планера, столкнувшиеся под прямым углом в подходящий момент, уничтожают друг друга без следа. На этом строится вентиль НЕ: второе ружьё стреляет поперёк входного потока. Где во входе планер есть, он сбивает планер второго ружья; где дырка, планер второго ружья пролетает дальше. Из похожих столкновений собираются И и ИЛИ, а из них, как в главе 29, — всё остальное.

Дальше дело инженерное, хотя и долгое. Второго апреля 2000 года Пол Ренделл закончил машину Тьюринга внутри «Жизни», собранную из ружей, планеров и узоров, накопленных любителями за тридцать лет. Машина маленькая — три состояния и три символа, — и один её шаг занимает 11 040 поколений. Но её устройство можно расширить, и в 2010 году Ренделл собрал версию, в которой работает универсальная машина, а в 2011-м — с лентой, которая сама достраивается по мере надобности. «Жизнь» полна по Тьюрингу: четыре правила о соседях на клетчатой бумаге вычисляют всё, что вычисляет ваш компьютер.

Полны нечаянно

«Жизнь» в этом смысле не одинока. Стоит в системе появиться неограниченной памяти, развилке и повторению, и она почти наверняка полна, нравится это её авторам или нет. Ниже галерея: попробуйте угадать про каждый экспонат, полон ли он, прежде чем перевернуть карточку.

Несколько экспонатов стоят отдельного рассказа. Клеточный автомат «Правило 110» — одномерная «Жизнь», где клетка смотрит только на себя и двух соседей. В 1985 году Стивен Вольфрам предположил, что он полон по Тьюрингу, а Мэтью Кук это доказал; правда, фирма Вольфрама, где Кук работал, через суд задержала публикацию, и статья вышла только в 2004 году. Шаблоны C++ задумывали для обобщённых контейнеров, а в 2003 году Тодд Велдхёйзен показал, что на них можно вычислять что угодно ещё во время компиляции. Стивен Долан из Кембриджа доказал, что из всех команд x86 хватает одной — пересылки mov, — а Кристофер Домас написал компилятор, который превращает программы на C в одни mov.

Дальше всех от компьютеров, пожалуй, Magic: The Gathering, карточная игра. В 2019 году Алекс Черчилль, Стелла Бидерман и Остин Херрик собрали из обычных турнирных карт позицию, в которой ходы обоих игроков вынуждены, а розыгрыш выполняет заданную машину Тьюринга: первый игрок выигрывает тогда и только тогда, когда машина останавливается. Запомните эту формулировку — она понадобится в следующей главе.

Что значит «полный» на деле

Во-первых, полнота ничего не говорит об удобстве и скорости: Brainfuck полон, а машина Ренделла делает один шаг за 11 тысяч поколений. «Полна по Тьюрингу» значит «на ней можно всё», а не «на ней удобно хоть что-нибудь».

Во-вторых, и это важнее, за полноту приходится платить. Если язык полон, программа на нём может работать вечно, и, как мы увидим в следующей главе, заранее этого в общем случае не узнать. Поэтому полные по Тьюрингу системы приходится ограничивать снаружи. Компилятор GCC прерывает подстановку шаблонов на глубине 900 — в документации прямо сказано, что ограничение нужно, чтобы ловить бесконечную рекурсию. TypeScript, у которого система типов тоже полна, выдаёт ошибку 2589: «Type instantiation is excessively deep and possibly infinite» — «подстановка типов слишком глубока и, возможно, бесконечна». В Ethereum каждый шаг программы-контракта стоит «газа», и выполнение обрывается, когда газ кончился.

Бывает и обратный ход: если вычислять что угодно не требуется, язык делают нарочно неполным. Регулярное выражение без обратных ссылок — конечный автомат, и движок, который исполняет его автоматом, как RE2 от Google, отвечает за время, линейное от длины строки; движок с перебором, как re в Python, такой гарантии не даёт — вспомните аварию Cloudflare из прошлой главы. Язык Starlark, на котором пишут конфигурации сборки Bazel, запрещает рекурсию и while: циклы ходят только по готовым конечным коллекциям, и программа на нём заканчивается. Выбирая формат конфига или язык шаблонов, спросите, полон ли он, — и что будет, когда кто-нибудь напишет в нём бесконечный цикл.

Задачи

Три задачи. В первых двух ответ — таблица машины в строке TABLE, в том же формате, что в главе: «состояние символ -> запись сдвиг новое_состояние», по правилу на строку, после # — комментарий. Тесты прогоняют таблицу на симуляторе курса: вход записан на ленте с клетки 0, головка стоит на клетке 0, начальное состояние — состояние первого правила, пробел — _. Таблицу удобно собрать в игре и нажать там «Скопировать таблицу». В третьей задаче симулятор пишете вы сами.

Куда дальше

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

По дороге нам встречались вопросы: остановится ли эта таблица, выиграет ли первый игрок в позиции «Магии», будет ли узор в «Жизни» расти вечно. Это точные вопросы с ответом «да» или «нет», и ответ у каждого есть. Но симулятор может только ждать: остановилась машина — «да», а если нет, то, может быть, остановится через минуту. В 1930 году Давид Гильберт был уверен, что неразрешимых задач нет. Любой ли точный вопрос имеет ответ, который найдёт машина? Об этом следующая глава: там у нас будет собеседник, уверенный, что умеет отвечать на вопрос об остановке.