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

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

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

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

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

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

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

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

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

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

Вопрос поэтики

Ричард Форман

Драматург и режиссер, основатель Театра онтологической истерики

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

1. Почти не помню подробностей (в конце концов, я же не ученый), но помню, как читал о теории Поля Дирака насчет моря отрицательной энергии, из которого (из дыры, из ничего) вдруг возникает позитрон – одна из фундаментальных частиц нашего мира. Надеюсь, у меня есть право поделиться этим воспоминанием и я не выставил себя на посмешище, дав неверную интерпретацию упомянутой теории. В каком-то смысле это и неважно. Потому что этот образ, подпитываемый этим объяснением, побудил меня предпринять более активные поиски нового типа театра, где (если прибегать к своего рода отрицательной теологии) я пытался и до сих пор пытаюсь затянуть зрителей в пустоту, а не скармливать им то, что они и без того чувствуют и знают о «реальном» мире.

2. Вскоре после этого (все описываемое происходило в 1950‑е годы), встретившись с философом Ортегой-и-Гассетом, я испытал настоящее потрясение от его объяснения, согласно которому человек – не «цельная личность» (в мире, где это понятие вскоре станет расхожим штампом, применяемым ко всем подряд), а нечто иное. Согласно его знаменитой формулировке, «я – это я сам плюс мои обстоятельства»: иными словами, человек – существо разделенное, расщепленное, раздробленное.

Почему же ортегианские обстоятельства заставили меня увлечься диракианским объяснением? Возможно, тут есть какая-то связь с тем, что вырос я в элитарном Скарсдейле, ненавидя его, но скрывая, что чувствую себя не в своей тарелке и мне весьма неудобно получать хорошие отметки в старших классах. Дирак подарил мне мощную поэтическую метафору, которая позволила мне воображать, будто некий недостижимый источник (море отрицательной энергии) является реальной почвой, на которой все мы втайне стоим – и черпать отвагу в том факте, что мир вокруг меня не замечает глубинной реальности вещей, а значит, мое отчуждение в известном смысле оправданно.