Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

Математик Алан Тьюринг, считающийся одним из создателей компьютеров.

Чёрч и Тьюринг в своих доказательствах использовали созданные ими модели: первый применял лямбда-исчисление, второй — разработанную им машину. Оба дали формальное определение алгоритму и использовали в своих доказательствах арифметические задачи. Существование арифметических задач, для которых решения отсутствуют, означало бы, что решить любую произвольную задачу также невозможно. Однако работа Тьюринга была намного более доступной и понятной.

Он свел проблему разрешения к проблеме остановки и доказал, что она неразрешима с помощью его машины: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу в какой-то момент или нет. Чёрч и Тьюринг не соперничали; напротив, оба осознавали, что их модели, несмотря на формальные различия, были одинаково мощными, и объединили усилия.

* * *

КАК РАБОТАЕТ МАШИНА ТЬЮРИНГА ?

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

Формально машина Тьюринга определяется на основе кортежа из семи элементов. Кортеж — это упорядоченная последовательность элементов, то есть перечень ограниченного числа объектов. Кортежи используются для описания математических объектов, имеющих структуру. Обозначим кортеж, который будет обрабатывать наша машина Тьюринга, как

МТ= (Γ, Σ, Ь, Q, q 0, f, F).

Его элементы определяются следующим образом.

• Γ— алфавит, символы которого записываются на ленте.

• Σ Γ— алфавит, символы которого подаются на вход машины. Множество возможных входных символов является подмножеством символов, которые могут быть записаны на ленте. На ленте также будут находиться символы, записанные самой машиной.

• b Γ, Ь Σ: Ьопределяет пустое пространство. Это символ, не принадлежащий множеству входных символов. Изначально лента содержит конечное число символов Σ; оставшаяся часть ленты (которая является бесконечной) заполнена символами Ь.

• Q— множество состояний.

• q 0 Q— начальное состояние.

• f— функция перехода. Для данного состояния и элемента, записанного на ленте, эта функция определяет новое состояние, записывает символ на ленте и перемещает считывающее устройство влево ( I), вправо ( D) или же оставляет неподвижным ( Р). Таким образом, функция fявляется функцией вида f: Qx Γ—> Q x Γх { I, D, Р}.

F Q— множество конечных состояний.

* * *

В апреле 1936 года американский математик Алонзо Чёрч из Принстонского университета опубликовал работу о проблеме разрешения. Чёрч пришел к тому же выводу, что и Тьюринг, доказав, что не все в математике является вычислимым.

В своем доказательстве он использовал лямбда-исчисление, разработанное им совместно с коллегой Стивеном Клини, которое радикально отличалось от машины Тьюринга. Тьюринг опубликовал свое решение проблемы разрешения в августе того же 1936 года. Это была его знаменитая статья «О вычислимых числах в приложении к проблеме разрешения», в которой были переформулированы результаты Курта Гёделя(1906–1978) о пределах доказуемости и вычислений, а также содержались ссылки на работу Чёрча. Вместо того чтобы спорить, кто совершил открытие первым, в сентябре того же года Тьюринг переходит на работу в Принстонский университет, чтобы написать диссертацию о проблеме разрешения под руководством Чёрча. Он защитил диссертацию в 1938 году, получил степень доктора и вернулся в Кембридж. Этот удачный союз талантов принес немалую выгоду всему человечеству.

* * *

БЛЕТЧЛИ-ПАРК И ЭНИГМА

Легендарное шифровальное подразделение Великобритании Блетчли-парк располагалось в графстве Бакингемшир в 80 километрах от Лондона. Во время Второй мировой войны наиболее авторитетные английские ученые работали в Блетчли-парке над взломом немецких шифров. Это подразделение располагалось в одноименном викторианском поместье (сегодня музей криптографии). В Блетчли-Парке был расшифрован код шифровальной машины «Энигма». Эта машина содержала шифровальный механизм, состоящий из вращающихся роторов и колец, который позволял вооруженным силам нацистской Германии расшифровывать и зашифровывать сообщения. Усилия британских ученых по взлому шифра «Энигмы» не пропали даром: считается, что прочтение предположительно секретных сообщений немцев позволило приблизить окончание войны на несколько лет.

* * *

Эти значимые события, касающиеся наиболее теоретической области науки, происходили в один из самых драматичных моментов современной истории. Политическая ситуация в Европе накалялась, и мир двигался к войне. Опасаясь, что Англия вступит в войну с Германией, Тьюринг во время работы над диссертацией начал заниматься криптографией. Британское правительство в 1939 году пригласило его работать в Блетчли-парке вместе с другими исследователями. Перед ними стояла задача взломать секретный шифр немецкой армии — код «Энигмы». Благодаря своим знаниям Тьюринг смог взломать шифр немецких воздушных сил в середине 1941 года, однако в феврале 1942 шифр был усложнен, и сообщения немцев снова стало невозможно прочесть.

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