Машины Тьюринга: объяснение

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

Лента из ячеек с единицами и пустыми клетками и головка чтения-записи над одной из ячеек с подписью её состояния
Лента из ячеек с единицами и пустыми клетками и головка чтения-записи над одной из ячеек с подписью её состояния

Вопрос Тьюринга

В 1928 году Давид Гильберт спросил, существует ли механическая процедура, которая для каждого математического утверждения решает, можно ли его доказать: Entscheidungsproblem. Чтобы ответить на этот вопрос, кто-то должен был точно сказать, что такое механическая процедура. В своей статье 1936 года On Computable Numbers («О вычислимых числах») Тьюринг представил себе конторского служащего, работающего карандашом на бумаге, и свёл его работу к самым мелким шагам: посмотреть на один символ, изменить его, перейти к соседнему символу и запомнить немного о том, чем занимаешься. Так появилась машина Тьюринга.

Машина Bombe (слева) и портрет Алана Тьюринга (справа)
Машина Bombe (слева) и портрет Алана Тьюринга (справа)

Машина

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

Программы как таблицы правил

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

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

Самая важная идея Тьюринга состояла в том, что саму таблицу правил можно записать на ленту. Универсальная машина Тьюринга читает описание любой другой машины и её вход, а затем имитирует её шаг за шагом. Поэтому одна фиксированная машина может выполнять любую программу: на этом принципе основан каждый компьютер с хранимой программой, где программное обеспечение — просто данные в памяти. Любую систему, способную имитировать универсальную машину Тьюринга, называют полной по Тьюрингу; таковы все языки программирования, игра «Жизнь» Конвея и клеточный автомат «Правило 110».

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

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

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

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

Усердные бобры

В 1962 году Тибор Радо превратил проблему остановки в игру: среди всех машин с n состояниями и символами 0 и 1, которые останавливаются, если запустить их на пустой ленте, какая запишет больше всего единиц и сколько шагов может сделать такая машина? Эти числа, значения усердного бобра, растут быстрее любой вычислимой функции, потому что способ их вычислять решил бы проблему остановки. Известные значения — 6, 21 и 107 шагов для двух, трёх и четырёх состояний; для пяти состояний чемпион Хайнера Марксена и Юргена Бунтрока делает 47 176 870 шагов — это значение в 2024 году доказали участники онлайн-проекта bbchallenge с помощью проверенного компьютером доказательства. Для шести состояний известны машины, которые работают больше шагов, чем можно записать в обычной нотации.

Попробуйте сами

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

Часто задаваемые вопросы

Строили ли машину Тьюринга на самом деле?

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

Чем различаются числа шагов 14 и 21 для трёх состояний?

Есть два вопроса об усердных бобрах: наибольшее число записанных единиц и наибольшее число сделанных шагов. Для трёх состояний машина в симуляторе записывает максимальные шесть единиц за 14 шагов, а другая машина с тремя состояниями делает максимальный 21 шаг, но оставляет только пять единиц. Для двух, четырёх и пяти состояний одна машина побеждает в обоих.

Означает ли полнота по Тьюрингу мощность?

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

Почему компьютер не может просто запустить программу и посмотреть, остановится ли она?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть симулятор машины Тьюринга