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

• Название: Игра в имитацию
• Автор: Эндрю Ходжес
• Жанр: Биографии и Мемуары
• Год: 2015
• ISBN: 978-5-17-089741-4

О загадочной, «зашифрованной» судьбе великого криптографа снят фильм «Игра в имитацию», который получил главную награду Кинофестиваля в Торонто в 2014 году. В роли Тьюринга — Бенедикт Камбербэтч, прославившийся своей ролью в телесериале «Шерлок». А его несостоявшуюся невесту Джоан Кларк сыграла Кира Найтли.

Национальный совет кинокритиков США и Американский институт киноискусства включили «Игру в имитацию» в топ 10 фильмов 2014 года. Также фильм получил пять номинаций на премию «Золотой глобус».

Настало время миру узнать о Тьюринге.

---

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

Но чтобы представить ясный результат работы, оставалось еще многое сделать. С одной стороны, в его доводах было нечто парадоксальное. Сама уловка Кантора казалась тем самым «определенным методом». Диагональное число имело достаточно четкое и ясное описание, так почему его нельзя было вычислить? И как могло нечто, полученное в результате механистических действий, быть невычислимым? И что бы пошло не так при попытке вычислить его?

Предположим, некто попытался создать «машину Кантора», чтобы произвести подобное диагональное невычислимое число. В общих чертах работа устройства начиналась бы с пустой ленты и записи единицы в пустой ячейке. Затем оно бы произвело первую таблицу, выполнило ее, остановившись на первой записанной цифре и прибавив к ней единицу. После этого считывающее устройство снова начало работу с числом 2, произвело вторую таблицу и выполнило ее до второй записанной цифры, записало результат, добавив единицу. Эти действия выполнялись бы непрерывно и, когда устройство считало бы число 1000, машина произвела бы тысячную таблицу, выполнила ее до тысячной цифры в последовательности, прибавила единицу и записала результат.

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

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

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

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

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

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

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

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

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