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

МТ= (Γ, Σ, Ь, 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 года Тьюринг совершил новую поездку в США, чтобы помочь американским военным взломать немецкие шифры. Во время поездки он познакомился с Клодом Шенноном, создателем теории информации и автором определения энтропии.