Тьюринг. Компьютерное исчисление

В августе 1936 года Алан Тьюринг направил для публикации в Proceedings of the London Mathematical Society статью под названием «О вычислимых числах, с приложением к проблеме разрешимости». Мы уже говорили о ней, так как именно в этой работе впервые упоминалась машина Тьюринга. Также в статье даются определения понятиям «вычислимое» и «невычислимое» и представлены фундаментальные идеи математики и информатики. По воле случая в том же году Алонзо Чёрч опубликовал в журнале American Journal of Mathematics статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером.

Месяц спустя, в сентябре 1936 года, Тьюринг отправился в США. Там он планировал получить докторскую степень и провести два года в Институте перспективных исследований в престижном Университете Принстона. Под руководством Алонзо Чёрча Тьюринг обратился к теме, странной даже сегодня — использованию в математике интуиции. Не теряя времени на философские объяснения, скажем, что интуиция может быть определена как продукт здравого смысла. То есть речь шла о предвосхищении или ментальном видении, которое помогает нам при рассуждениях прийти к умозаключению. Учитывая, что в ходе рассуждений мы связываем факты в логическую цепь, интуиция представляет собой дополнительный компонент, необходимый для разрешения задачи.

Математическое рассуждение схематично можно рассматривать как упражнение в комбинировании двух факторов — интуиции и изобретательности.

Алан Тьюринг, «Логические системы, основанные на ординалах»

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

В этот период Тьюринг начал проявлять интерес к возможности создания своей машины, но эта цель так и не была достигнута. Именно во время пребывания в США проявился интерес ученого к hardware и, следовательно, к возможности создания с использованием электронных схем и электромеханических компонентов того, что еще недавно было не более чем интеллектуальным упражнением. И вновь, как и в случае появления идеи о машине Тьюринга на логическом уровне, мы сталкиваемся с тем, что ученый начал думать о реализации своей машины в эпоху, когда еще не было компьютеров. Он создал машину для умножения с использованием электромагнитных реле, которая позволяла умножать двоичные числа (то есть числа, которые можно представить с использованием только двух знаков: 0 и 1).

В 1938 году еще один гениальный исследователь той эпохи, американский ученый венгерского происхождения Джон фон Нейман предложил Тьюрингу временную должность в Принстонском университете. Однако тот отверг это предложение и летом того же года вернулся в Королевский колледж. По возвращения он занялся созданием аналогового механизма для оценки так называемой гипотезы Римана.

В августе 1939 года Тьюринг получил предложение работать в Блетчли-парке над расшифровкой перехваченных сообщений нацистов.

Глава 2

Машины против кода.

Тьюринг как криптограф

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