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

Глория Оригги

Философ (Национальный центр научных исследований, Париж); редактор книги Text-e: Text in the Age of the Internet («Е-текст, или Текст в эпоху Интернета»)

«Есть многое на свете, друг Горацио, что вашей философии не снилось»[86], – говорит Гамлет своему приятелю. Изящное резюме, которое преследует нас в жизни. Один из самых замечательных научных экспериментов всех времен и народов подводит нас к тому же печальному выводу: некоторые математические проблемы попросту неразрешимы.

В 1936 году британский математик Алан Тьюринг придумал самую простую и изящную вычислительную машину на свете, устройство (которое он позже описал в своей статье 1948 года «Разумная машина»), наделенное

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

Итак, перед нами абстрактная машина, порожденная гением для того, чтобы справиться с неразрешимой проблемой – проблемой разрешения. Вот формулировка этой проблемы. Возможно ли для каждой логической формулы, существующей в какой-либо теории, за конечное число шагов определить, верна ли данная формула для данной теории?

Ну так вот, Тьюринг демонстрирует, что это невозможно. Проблема разрешения (Entscheidunsproblem) была хорошо знакома тогдашним математикам. Она занимала десятую строчку в перечне проблем, которые Дэвид Гильберт в 1900 году представил математической общественности, тем самым обрисовав основную часть повестки математических исследований на ХХ век. В классической формулировке задается вопрос, существует ли механический процесс, способный за конечное число шагов определить, верна ли формула или можно ли вычислить значение функции. Тьюринг начал с вопроса: «А что такое механический процесс?» и дал ответ: механический процесс – такой, который может осуществить машина. Очевидно, не так ли?

Затем он разработал машину для операций со всеми возможными формулами в логике первого порядка и со всеми возможными рекурсивными функциями натуральных чисел, с учетом доказанной Гёделем (в его теореме о неполноте) логической эквивалентности между множеством формул логики первого порядка и множеством натуральных чисел. И в самом деле, на основе простой дефиниции Тьюринга можно описать функцию при помощи записанных на ленту нулей и единиц, затем дать машине список простых команд (сдвинь ленту влево, сдвинь ленту вправо, стоп) так, чтобы она записала «демонстрацию» функции и затем прекратила работу.

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