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

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

записать новый (заданный) символ в пустую ячейку, или оставить уже записанный символ в неизменном виде, или стереть символ и оставить ячейку пустой;

остаться в прежней конфигурации или сменить ее на другую (заданную) конфигурацию;

переместиться на ячейку влево, или вправо, или остаться в текущей позиции.

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

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

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

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

Полная таблица, описывающая это действие, будет выглядеть следующим образом:

Просканированный символ

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

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

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

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

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

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