Самая важная машина, которой никогда не было
Одним из основоположников современной вычислительной техники стал британский математик Алан Тьюринг. А прославился он отчасти благодаря так называемой «машине Тьюринга», которая существовала исключительно умозрительно — в воображении ученого и его научных трудах. Тем не менее нынешние компьютеры работают во многом на базе гениальных догадок Тьюринга и небольшой группки его единомышленников, чьи главные открытия пришлись на 1930-е годы.
Тьюринг пытался найти ответ на вопрос, поставленный в 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 года в комнате [Тьюринга] чаще всего можно было найти нечто вроде головоломки из шестерней, распределенных по всему полу… Алан пытался, но самым жалким образом не мог объяснить, для чего все это нужно. Если движение шестерней и было как-то связано с закономерностью распределения простых чисел, которых по мере приближения к бесконечности становится все меньше, то совершенно не ясно, как именно».
Потерпев неудачу при создании машины Римана, Тьюринг, однако, внес существенный вклад в разработку одного из самых важных в истории вычислительной техники приборов — машины для расшифровки кода «Энигма», которым Германия пользовалась в ходе Второй мировой войны. Эта работа, как принято считать, помогла закончить войну на два года раньше и принесла Тьюрингу орден Британской империи.
