Модель машины Тьюринга, построенная Майком Дэйви в соответствии с оригинальной идеей Алана Тьюринга.
Как уже упоминалось, свое изящное устройство Тьюринг придумал специально для того, чтобы дать ответ на проблему разрешимости, сформулированную Гильбертом, что он и сделал в своей статье 1936 года, озаглавленной “О вычислимых числах применительно к Entscheidungsproblem”. Если ввести в универсальную машину Тьюринга произвольные входные данные, она может либо остановиться, либо продолжать работать бесконечно. Тьюринг задался вопросом: возможно ли определить, остановится она или нет? Можно, конечно, запустить ее на неопределенное время и посмотреть, что произойдет. Но если после долгого ожидания вы решите досрочно прекратить эксперимент, не дождавшись результата, то так и не узнаете, остановилась бы машина сразу после этого этапа, гораздо позже либо продолжала бы работать бесконечно. Разумеется, для конкретных случаев просчитать результат можно, как мы в силах выяснить, остановится ли когда-нибудь простая машина Тьюринга. Однако Тьюринг хотел знать, существует ли общий алгоритм, способный для любых входных данных определить, остановится машина или нет. Эта задача получила название “проблема остановки”, и Тьюринг доказал, что такого алгоритма не существует. Далее, в заключительной части своей статьи, он показал, что отсюда следует вывод о неразрешимости Entscheidungsproblem. А это значит, что мы можем быть абсолютно уверены: никакая самая совершенная компьютерная программа не сумеет – во всех случаях – определить, завершит ли когда-нибудь свою работу какая-либо иная программа.
За месяц до выхода исторической статьи Тьюринга американский ученый-логик Алонзо Чёрч, его научный руководитель, независимо опубликовал собственную статью, в которой делал тот же вывод, но для доказательства использовал совершенно другой метод – лямбда-исчисление. Так же как и машина Тьюринга, лямбда-исчисление представляет собой универсальную вычислительную модель, но скорее программную, а не аппаратную; она оперирует “комбинаторами” – функциями, которые применяются к другим функциям. И Чёрч, и Тьюринг, пользуясь каждый своим методом, пришли, в сущности, к одному и тому же результату, получившему название “тезис Чёрча – Тьюринга”. Суть его в том, что человек способен высчитать или оценить количественно (такую мелочь, как ограниченность ресурсов, мы при этом в расчет не берем) только то, что вычислимо с помощью машины Тьюринга или равнозначного ей устройства. “Вычислимость” означает, что машина Тьюринга, если подать ей на вход программу (в двоичном представлении), способна работать до тех пор, пока не остановится, дав на выходе ответ (в таком же двоичном представлении). Основной вывод, следующий из тезиса Чёрча – Тьюринга, заключается в том, что общего решения Entscheidungsproblem не существует.
Хотя Тьюринг изобрел свою машину для решения математической задачи, он фактически заложил основу для создания цифровых компьютеров. Все современные компьютеры, по сути, делают то же самое, что и машины Тьюринга, а сам подход также используется для измерения эффективности наборов машинных команд и языков программирования. Высшая оценка эффективности компьютерной программы, ее “полнота по Тьюрингу”, означает, что программа способна смоделировать любую машину Тьюринга, использующую одну ленту.
Пока еще никому не удалось придумать метод вычислений, который может больше, чем машина Тьюринга. Последние разработки в области квантовых компьютеров, на первый взгляд, указывают на существование способа выйти за пределы возможностей машины Тьюринга. Но на самом деле при наличии достаточного времени даже квантовый компьютер можно эмулировать с помощью любого обычного (классического) компьютера. Да, некоторые типы задач квантовый компьютер сможет решить гораздо более эффективно, чем его классический эквивалент, но в конечном итоге все, на что он способен, выполнимо и на простом устройстве, придуманном Тьюрингом. Это говорит о том, что существуют задачи, для которых мы никогда не сумеем путем вычислений получить общий, гарантированно точный во всех случаях ответ (хотя для конкретных случаев такое возможно).
Есть в математике и другие вещи и явления, которые на первый взгляд не имеют ничего общего с машинами Тьюринга, но на поверку оказываются их эквивалентами (эмулирующими их). Один из примеров – игра “Жизнь”, придуманная английским математиком Джоном Конвеем. Идея игры пришла ему в голову, когда он заинтересовался проблемой, которую в 1940-х годах исследовал венгерско-американский математик и один из основоположников компьютерной науки Джон фон Нейман: возможно ли выдумать гипотетическую машину, способную производить точные копии самой себя? Фон Нейман доказал, что это возможно, создав математическую модель такой машины, где использовались разбитая на прямоугольные клетки область и набор очень сложных правил. Конвей задался вопросом, нельзя ли доказать то же более простым способом, – и придумал игру “Жизнь”. В игре Конвея используется (теоретически) бесконечное поле, разбитое на квадратные клетки, каждая из которых может быть окрашена либо в черный, либо в белый цвет. Игра начинается с произвольного узора из черных клеток и развивается по двум правилам:
1. Черная клетка остается черной, если ровно 2 или 3 из восьми соседних клеток тоже черные.
2. Белая клетка превращается в черную, если ровно 3 соседние клетки – черные.
Вот и все. И хотя освоить игру “Жизнь” может даже ребенок, она обладает всеми теми же возможностями, что и универсальная машина Тьюринга – а стало быть, что и любой когда-либо созданный в истории человечества компьютер. Впервые удивительная игра Конвея была представлена широкой аудитории в колонке Мартина Гарднера “Математические игры” в октябрьском выпуске журнала Scientific American за 1970 год. Гарднер познакомил своих читателей с основными фигурами в игре: “блоком” – квадратом размером 2 × 2 клетки, который по правилам игры никогда не изменяется, и “мигалкой” – прямоугольником размером 1 × 3 клетки, ориентация которого чередуется между горизонтальной и вертикальной, а центр остается неподвижным. “Планер” представляет собой фигуру из пяти клеток, передвигающуюся по диагонали на одну клетку за каждые четыре хода.
Поначалу Конвей думал, что, как бы ни располагались клетки в начале игры, их бесконечное “размножение” невозможно – любая конфигурация в конце концов стабилизируется, превратится в осциллятор или просто исчезнет, “умрет”. В той статье Гарднера 1970 года объявлялось, что Конвей предлагает премию в 50 долларов первому, кто докажет или опровергнет эту гипотезу. Не прошло и нескольких недель, как приз получила группа из Массачусетского технологического института под руководством математика и программиста Билла Госпера, одного из основателей сообщества хакеров. Так называемое “ружье Госпера” циклически “выстреливает” нескончаемую череду планеров со скоростью одна штука за тридцать поколений. Помимо того, что это увлекательное зрелище, “ружье Госпера” представляет интерес и с точки зрения теории: оно играет важнейшую роль в построении компьютеров на основе игры “Жизнь”, поскольку испускаемые им планеры можно принять за аналог потока электронов в компьютере. В реальной жизни, правда, эти потоки надо как-то контролировать, чтобы компьютер мог выполнять свое предназначение – вычислять. Как раз эту функцию выполняет логический вентиль.
