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

Точнее говоря, сама машина не обладала бы никакими знаниями о десятичных числах или десятичных разрядах. Она могла лишь производить последовательность цифр. Последовательность, которая могла быть произведена одной из его машин, Алан назвал «вычислимой последовательностью». Тогда вычислимая бесконечная последовательность, перед которой стояла десятичная запятая, могла определить «вычислимое число» между 0 и 1. Это означало, что любое вычислимое число между 0 и 1 могло быть определено в виде таблицы с конечным числом действий. Для Алана оставалось важным, чтобы вычислимые числа всегда были представлены в виде бесконечной последовательности цифр, даже если все цифры после определенного момента были нулями.

Теперь все эти таблицы с конечным числом действий можно было расположить в некотором роде по алфавитному порядку, начиная с самой простой и заканчивая наиболее большой и сложной. Их можно было представить в виде списка или посчитать; и это означало, что все вычислимые числа также можно было представить в виде списка. Разумеется, выполнить на практике подобное было достаточно сложно, но идея была довольно ясной: квадратный корень из трех в таком случае будет значиться 678-м в списке, а логарифм числа π — 9369-м. Такая мысль казалась потрясающей, поскольку в такой список могло войти любое число, полученное в результате выполнения арифметических действий, например, вычисления корня уравнения, или используя математические функции, например, синусы и логарифмы, — любое число, которое могло возникнуть в сфере вычислительной математики. И в тот самый момент, когда он пришел к этой мысли, он узнал ответ на третий вопрос Гильберта. Возможно, именно это он неожиданно понял, остановившись отдохнуть на лугу в Гранчестере. И полученному ответу он был обязан прекрасному математическому устройству, которое все это время ожидало своего часа.

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

1/2 1/3 1/4 2/3 1/5 1/6 2/5 3/4 1/7 3/5 1/8 2/7 4/5 1/9 3/7 1/10…

Но Кантор не остановился на достигнутом и изобрел особый математический трюк, который получил название «диагональный метод Кантора» и мог быть использован в качестве доказательства существования иррациональных чисел. Для этого рациональные числа представлялись в виде бесконечных разложений десятичной дроби, и соответственно список всех подобных чисел между 0 и 1 начинался бы следующим образом:

5000000000000000000.…

3333333333333333333.…

2500000000000000000.…

6666666666666666666.…

2000000000000000000.…

1666666666666666666.…

4000000000000000000.…

7500000000000000000.…

1428571428571428571.…

6000000000000000000.…

1250000000000000000.…

2857142857142857142.…

8000000000000000000.…

1111111111111111111.…

4285714285714285714.…

1000000000000000000.…

……

……

Суть математической уловки Кантора состояла в том, чтобы рассмотреть диагональное число, начинающееся

5306060020040180.…

а затем изменить каждую его цифру, например прибавив к каждой по единице, за исключением изменения 9 на 0. В таком случае бесконечный десятичный ряд будет начинаться следующим образом:

6417171131151291.…

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

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

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

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

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

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