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

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

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

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

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