Карл Зигмунд - Точное мышление в безумные времена. Венский кружок и крестовый поход за основаниями науки

Альфред Тарский (1901–1983) был частым гостем в Вене, где вел бесконечные дискуссии с Гёделем, Поппером и Карнапом. Именно в тот период Тарский разработал формальное определение понятия истинности. Например, утверждение «Фидо лает» истинно тогда и только тогда, когда Фидо действительно лает. В этом примере утверждение высшего уровня — то есть «Следующее утверждение истинно» — применяется к утверждению низшего уровня — то есть «Фидо лает». Формально этот акт связывания двух разных лингвистических уровней требует метаязыка вроде того, что разрабатывал в те годы Рудольф Карнап.

В дальнейшем, когда Тарский жил в США, он, к своему огорчению, утратил титул величайшего логика своего времени — эта честь, несомненно, принадлежала Курту Гёделю — зато остался «величайшим логиком в здравом уме » [466] 466 Fefferman and Fefferman, 2004. , как он частенько говаривал.

Влияние Алана Тьюринга было даже сильнее, чем Тарского, и его открытия сформировали все грани современного мира. Однако в середине тридцатых годов представлялось, что абстрактные рассуждения Тьюринга несказанно далеки от любого практического применения.

В 1931 году теорема Гёделя о неполноте пролила свет на безумное на первый взгляд обстоятельство, что любая система аксиом, достаточно богатая, чтобы вместить в себя теорию чисел, должна содержать истинные утверждения, не имеющие формальных доказательств, причем таких утверждений бесконечно много. Это обескураживает, однако еще остается надежда, что существует механическая процедура, позволяющая определить, истинно или ложно то или иное утверждение, относящееся к теории чисел. Можно представить себе, что такой механизм определения истины позволит полностью обойти понятие формальной доказуемости. Может быть, есть какой-то характерный признак, который таится во всех этих последовательностях символов, выражающих математические истины, и отсутствует во всех остальных последовательностях? Может быть, есть какой-то способ распознать наличие или отсутствие этого признака? Может быть, это можно как-то сделать?

Давид Гильберт в своей знаменитой парижской лекции в 1900 году сформулировал этот важнейший вопрос, затрагивающий самую суть природы математики, и назвал его Entscheidungsproblem — проблема разрешения. Алан Тьюринг постоянно ломал себе голову над этим вопросом Гильберта — задача попросту не давала ему покоя.

Разумеется, Тьюринг впитал идеи Курта Гёделя и блестяще применил их к миру вычислительных машин (которых в то время еще не существовало), чтобы исследовать глубочайшую проблему, которую поставил Гильберт в 1900 году. Но для этого Тьюрингу сначала надо было ответить на другой вопрос: что такое общая вычислительная процедура, она же алгоритм ? С этой целью он изобрел набор рудиментарных машин, которые впоследствии получили название «машины Тьюринга». Эти машины могли производить разные вычисления. Например, машина Тьюринга одного типа складывала два данных числа (и больше ничего не умела). Машина другого типа перемножала два данных числа (и все). Третий тип определял, простое число или нет, и так далее и тому подобное. Такие гипотетические машины, если бы их и в самом деле создали, не имели бы никакого практического применения, более того, были бы удручающе громоздкими и немыслимо медленными, но работали бы с гарантией, а больше от них в этом абстрактном контексте ничего и не требовалось.

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

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

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

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

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

Когда Тьюринг тщательно разбирал все следствия подобной бесконечной регрессии (подобно зеркалам, отражающим друг друга, колесам внутри колес и змеям, кусающим собственный хвост…), он открыл, что у всех возможных машин Тьюринга есть фундаментальные ограничения, в частности невозможно создать машину, которая всегда могла бы предсказать, остановится когда-нибудь данная машина Тьюринга или нет. Это открытие было равносильно доказательству, что проблема разрешения Гильберта не имеет решения. Это был результат, значение которого для математики, логики и теории вычислений, пожалуй, трудно описать. Его следствия сказываются на всех аспектах современного мира компьютеров.

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