Эндрю Ходжес - Игра в имитацию Страница 44

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

Механизация Канторова процесса не представляла особой сложности. Трудность состояла в другом необходимом условии, а именно — в создании таблиц в их «алфавитном порядке» для вычислимых чисел. Предположим, что таблицы зашифрованы в виде дескриптивных чисел. На деле они не могли использовать все целые числа. В действительности разработанная Аланом система зашифровывала бы даже самые простые таблицы в виде громаднейших чисел. Но это не имело бы никакого значения. Существенным образом это оставалось вопросом механистического характера, чтобы по очереди обрабатывать целые числа и пропускать те, что не соответствовали указанной таблице. Действительно серьезная проблема представлялась не такой очевидной. Вопрос был следующим: в случае с предоставленной (скажем) 4589-ой и должным образом описанной таблицей, как можно было с уверенностью сказать, что в ходе ее выполнения получится 4589-ая по счету цифра? Или то, что она произведет вообще какие-нибудь цифры? Ведь устройство могло двигаться вперед и назад в непрерывно повторяющемся цикле операций, не производя ни единой новой цифры. В таком случае машина Кантора застрянет на одном действии и никогда не сможет завершить свою работу.

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

Дескриптивные числа, которые производили числа с бесконечным десятичным рядом, Алан назвал «удовлетворительными числами». Так он показал, что не существует особого способа определить «неудовлетворительное число». Ему удалось точно установить пример того, в существовании чего Гильберт сомневался — неразрешимой проблемы.

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

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

Однако это была не просто математическая уловка или его логическая изобретательность. В ходе решения проблемы он сумел создать нечто новое — саму идею своих машин. И следовательно, оставался один вопрос: действительно ли включало его описание такой машины то, что могло считаться «определенным методом»? Достаточно ли было такого набора действий: считывания и записи информации, перемещения и остановки считывающего устройства? Было крайне важно, чтобы это в действительности было так, поскольку в обратном случае всегда будет таиться подозрение, что некоторое расширение функций устройства позволило бы ему решить больший ряд проблем. Чтобы ответить на эти вопросы, Алану пришлось продемонстрировать способность его машин вычислять любое математическое число. Он также показал, что его машина могла обладать программой производства каждого доказуемого утверждения в рамках представления Гильберта о математике. Также он предоставил работу с всесторонним изучением вопроса, которая по праву считалась одной из наиболее захватывающих математических исследований, в котором он смог объяснить определение на примере того, какой процесс происходит в сознании человека, когда производит вычисление, записывая его на бумаге:

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

«Бесконечное число символов» не соответствовало ничему в реальности. Есть немало оснований возразить тому, что существует бесконечное число символов, поскольку такая арабская цифра, как 17 или 999999999999999 обычно рассматривается в качестве одного символа. Подобным образом в любом европейском языке слова рассматриваются как отдельные символы (хотя китайский язык, например, стремится обладать счетным бесконечным множеством символов).