Тьюринг пытался найти ответ на вопрос, поставленный в 1928 году немецким математиком Давидом Гильбертом: возможно ли найти алгоритм, позволяющий в любой математической системе определять, верно ли в этой системе то или иное утверждение или нет. В итоге Тьюринг доказал, что существуют системы — и одна из них арифметика, — в которых невозможно, пользуясь единым методом, определить истинность утверждения.
В научной работе, посвященной этой проблеме, Тьюринг придумал воображаемую машину — это был отличный образец того, что ученые именуют «мысленным экспериментом». Машина состояла из бесконечной ленты, разделенной на ячейки, и головки, которая, действуя по принципу головки магнитофона, могла записывать в ячейки символы и стирать их.
В своей работе Тьюринг описывает изменения в ячейках, производимые так называемым компьютером, или вычислителем (в те времена слово «компьютер» означало человека, а не предмет):
«Вычисление обычно осуществляется путем записи неких символов на бумаге. Представим себе, что эта бумага поделена на клеточки, как тетрадка по арифметике… Поведение компьютера в любой момент времени определяется символами, которые он воспринимает, и его состоянием в данный конкретный момент»[18].
Простейший репертуар символов состоит из 0 и 1, и к этому репертуару прилагается таблица инструкций. Такая таблица может включать в себя, например, следующие правила:
Если головка находится над ячейкой, содержащей 0, то 0 стирается и на его место записывается 1, после чего лента сдвигается вправо.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента сдвигается влево.
Если головка находится над ячейкой с символом 0, то 0 стирается и на его место записывается 1, после чего лента сдвигается влево.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента сдвигается вправо.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента остается на месте.
Эти инструкции (всего лишь часть полной таблицы правил) можно коротко выразить так:
(0,1, П), (1,1, Л), (0,1, Л), (1,1, П) и (1,1, Н)
Таблица инструкций используется снова и снова, пока машина от некоего начального состояния (определенного набора символов) не перейдет к конечному состоянию. При должном применении правил начальное состояние ленты — скажем, двоичное отображение числа 27 — может прийти к конечному состоянию — 729, — нужно только воспользоваться набором инструкций для умножения чисел на самих себя.
Умозрительно изобретя «машину Тьюринга», которая способна решить некую одну задачу с помощью набора инструкций, предназначенного именно для этой задачи, ученый продемонстрировал, что можно изобрести «универсальную машину Тьюринга», способную имитировать все остальные «машины Тьюринга». Набор правил для такой машины эквивалентен программному обеспечению современных компьютеров, которое позволяет использовать их самыми различными способами.
Хотя эта «машина Тьюринга» так и не была создана в действительности, Тьюринг вовсю трудился над производством других, уже вполне реальных устройств для решения задач. Одна из важнейших задач, которую Тьюринг пытался решить и которая остается нерешенной по сей день, — это математическое выражение, названное «гипотезой Римана», оно касается распределения простых чисел среди натуральных.
В 1939 году Тьюринг получил грант на сборку машины, которая состояла из тридцати сцепленных между собой шестеренок с разными количествами зубцов, соответствующими определенным логарифмам. У каждой шестерни была своя гиря, подвешенная на том или ином расстоянии от центра, шестерни были взаимно соединены в группы и приводились в движение большим рычагом.
Биограф Тьюринга Эндрю Ходжес (р. 1949) писал:
«Летом 1939 года в комнате [Тьюринга] чаще всего можно было найти нечто вроде головоломки из шестерней, распределенных по всему полу… Алан пытался, но самым жалким образом не мог объяснить, для чего все это нужно. Если движение шестерней и было как-то связано с закономерностью распределения простых чисел, которых по мере приближения к бесконечности становится все меньше, то совершенно не ясно, как именно».
Потерпев неудачу при создании машины Римана, Тьюринг, однако, внес существенный вклад в разработку одного из самых важных в истории вычислительной техники приборов — машины для расшифровки кода «Энигма», которым Германия пользовалась в ходе Второй мировой войны. Эта работа, как принято считать, помогла закончить войну на два года раньше и принесла Тьюрингу орден Британской империи.
π = 3
Все мы слышали о числе «пи», обозначаемом на письме греческой буквой π, но немногие из нас осведомлены о его занятных свойствах.
Происхождение этого числа лишено всякой загадочности. Еще самые первые математики, включая древних египтян, индийцев, шумеров и греков, открыли, что любые окружности имеют одно и то же соотношение длины и диаметра. Будь то окружность размером с мелкую монетку или с орбиту планеты Плутон, соотношение всегда одно и то же — примерно 3,14, то есть длина окружности всегда в три с небольшим раза превышает ее диаметр.
Знание этого соотношения может пригодиться, если вы вдруг решите начертить на земле окружность определенной длины, например 10 метров, а под рукой у вас будут только колышек, веревка и кусок мела. Длина веревки должна быть чуть меньше 1/6 от длины окружности, то есть в нашем случае 1,6 метра, поскольку радиус, как известно, равен половине диаметра.
По мере совершенствования методов измерения значение числа π становилось все более точным. Древние египтяне для его выражения использовали дробь 25/8, шумеры — 256/81, а сейчас, когда ученым больше не нужно ходить с рулеткой вокруг огромных кругов и можно воспользоваться компьютерными вычислениями, значение числа π определено с точностью до 1 240 000 000 000 знаков после запятой — на вид это случайная последовательность цифр от 0 до 9. Число π начинается с 3,1415 и продолжается еще на 1 239 999 999 996 знаков. И, как и в случае с Вавилонской библиотекой из одноименного рассказа Хорхе Борхеса, это число, если продлить его до бесконечности, содержит любую комбинацию цифр, какую бы вы ни задумали. Моя дата рождения, например, начинается с цифры с порядковым номером 36 764 575, а моя фамилия, если принять латинскую А за единицу, В — за двойку и так далее, начинается с цифры под номером 82 062 313.
А теперь о странностях. Обычно числа не длятся таким вот образом. Если измерить мой рост с максимально возможной точностью, получится число 180,236 128 639 сантиметра. То есть количество знаков после запятой в нем конечно. А если бы я попытался добавить еще цифр, они все были бы нулями. Если мы переведем египетские 25/8 в десятичную дробь, то получим 3,125, и все. Вы, конечно, можете записать его как 3,125 000 000 000 плюс еще триллион нулей, но этим не добьетесь ничего, только руку перетрудите. Даже и через миллиард знаков никаких новых цифр, кроме нулей, там не появится.
Наше загадочное π принадлежит к классу иррациональных чисел. Такое название этим числам дано не потому, что они ведут себя иррационально, а лишь потому, что их нельзя представить в виде ratio[19] — обыкновенной дроби, в которой и числитель, и знаменатель являются целыми числами. Замечательное π также входит в более узкую группу среди рациональных чисел, называемую трансцендентными числами, то есть оно не удовлетворяет никакому алгебраическому уравнению с целыми коэффициентами. И хотя нам пока известно не так много представителей этой группы чисел, на самом деле их больше, чем всех знакомых нам других чисел — целых чисел, дробей и прочего.
Для людей с нематематическим складом ума все это может показаться слишком сложным и потому отпугивающим, особенно когда дело касается таких привычных явлений реального мира, как окружности. Мысль о том, что число, которое невозможно записать с абсолютной точностью, присутствует повсюду: в монетах, которыми мы расплачиваемся, в Солнце, которым любуемся, в баранке руля, которую сжимаем в руках, — никак не укладывается в голове.
Вот почему в американском штате Индиана в 1897 году один член Генеральной ассамблеи штата решил наконец покончить с этой проблемой, официально приравняв значение числа — π к чему-то более разумному, можно сказать, рациональному. Тейлор Рекорд, представитель от округа Пози, внес законопроект с целым списком значений π, куда более простых и привычных, чем иррациональное. Документ гласил: «Поскольку существовавшее до сих пор правило не действует… его следует признать несостоятельным и ведущим к ошибкам при попытках применить его на практике». Жителям Индианы предоставлялось право выбрать значение. Два самых незамысловатых были 4 и 3,2, однако на фоне стремления к упрощению довольно странно было видеть в списке квадратный корень из 2×16/7, то есть около 3,23.
