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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

Точнее говоря, сама машина не обладала бы никакими знаниями о десятичных числах или десятичных разрядах. Она могла лишь производить последовательность цифр. Последовательность, которая могла быть произведена одной из его машин, Алан назвал «вычислимой последовательностью». Тогда вычислимая бесконечная последовательность, перед которой стояла десятичная запятая, могла определить «вычислимое число» между 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-м десятичном разряде, и так далее. Таким образом, число не могло входить в список. А поскольку список содержал все рациональные числа, диагональное число не могло быть рациональным.

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