23. Машина останавливается. Алан Тьюринг
По словам коллеги Тьюринга по Блетчли-парку Джека Гуда, Алан страдал сенной лихорадкой. Он ездил в контору на велосипеде, и каждый июнь вынужден был надевать респиратор, чтобы защититься от пыльцы. С велосипедом у него тоже что-то было не в порядке, и время от времени цепь слетала. Поэтому Тьюринг всегда возил с собой банку масла и тряпку, чтобы привести себя в порядок после очередной починки.
Со временем, устав от бесконечного надевания цепи, он решил подойти к проблеме рационально. Он начал подсчитывать, сколько раз успевают провернуться педали велосипеда от одной поломки до следующей. Это число оказалось замечательно стабильным. Сравнив его с числом звеньев в цепи и числом спиц в колесе велосипеда, он пришел к выводу: цепь слетает всякий раз, когда цепь и колесо находятся в некоторой определенной конфигурации. После этого он постоянно вел подсчет оборотов, чтобы заранее знать, когда цепь соберется слететь в очередной раз; тогда он предпринимал некий маневр, который позволял ему удержать цепь на месте. Ему больше не нужно было возить с собой масло и тряпку. Со временем он выяснил и подлинную причину: такой эффект давала слегка погнутая спица в сочетании с поврежденным звеном цепи.
Это был триумф рациональности, но любой другой на месте Тьюринга просто отдал бы велосипед в мастерскую, где мастер быстро обнаружил бы неисправность. С другой стороны, тем, что он этого не сделал, Тьюринг сэкономил на ремонте – и сделал так, что никто, кроме него самого, не мог ездить на его велосипеде. Как и во многих других случаях, у него были свои соображения; просто они не походили на соображения всех остальных.
Отец Алана Тьюринга Юлиус работал в Индийской гражданской службе. Его мать Этель (урожденная Стоуни) была дочерью главного инженера Мадрасских железных дорог. Супруги хотели, чтобы их дети воспитывались в Англии, поэтому переехали в Лондон. Алан был младшим из двух сыновей. В шесть лет он поступил в школу в прибрежном городке Сент-Леонард, где директор сразу же обратила внимание на необычайно умного мальчика.
В 13 лет Алан поступил в Шерборнскую школу – независимую «публичную» школу, как замысловато именуются в Англии частные платные школы, в которых обучаются преимущественно дети из богатых семей. Как в большинстве подобных школ, упор в ней делался на классические дисциплины. У Тьюринга был плохой почерк, он не отличался хорошей грамотностью, да и в любимом своем предмете – математике – предпочитал собственные ответы тем, что требовали учителя. То ли несмотря на это, то ли благодаря этому он выигрывал все математические конкурсы. Кроме того, ему нравилась химия, но и здесь он предпочитал искать собственный путь. Его классная руководительница писала: «Если ему суждено заниматься исключительно наукой, он напрасно теряет время в частной школе».
Чистая правда.
Школа была не в курсе, что в свободное время Тьюринг читает статьи Эйнштейна о теории относительности и книгу Артура Эддингтона о квантовой теории «Природа физического мира». В 1928 г. Алан сдружился с Кристофером Моркомом, который учился на класс старше и разделял его интерес к науке. Однако не прошло и двух лет, как Морком умер. Тьюринг был безутешен, но продолжал упрямо учиться – и выиграл возможность изучать математику в Кембриджском Королевском колледже. Там Алан продолжал читать учебники, намного опережавшие учебный план – или вообще не входившие в него. В 1934 г. он закончил колледж.
Тьюринг был неисправимо неряшлив. Даже если он надевал костюм, то костюм этот редко был отглажен. Говорят, что иногда он подвязывал брюки галстуком или просто бечевкой. Его смех звучал громко и неприятно. У него был дефект речи, не то чтобы заикание, а внезапные паузы в речи, когда он некоторое время мог тянуть «э-э-э-э-э…», подыскивая подходящее слово. Он не слишком придирчиво относился к бритью, и к концу дня у него на лице обычно видна была легкая щетина. Тьюринга часто изображают нервным, социально не адаптированным чудиком, но на самом деле он был довольно популярен и легко осваивался в любой компании. Его очевидная эксцентричность происходила в основном от оригинальности не того, о чем он думал, а того, как он думал. Работая над задачей, Тьюринг находил такие ее аспекты, о существовании которых никто даже не подозревал.
Через год после выпуска Тьюринг учился в аспирантуре по основаниям математики у Макса Ньюмана; именно там он узнал о программе Гильберта и о ее разрушении Гёделем. Тьюринг понял, что Гёделева теорема о неразрешимости на самом деле говорит об алгоритмах. Вопрос разрешим, если существует алгоритм получения ответа на него. Разрешимость конкретной задачи можно доказать, отыскав такой алгоритм. Понятие неразрешимости глубже, и работать с ним сложнее: необходимо доказать, что таких алгоритмов не существует. Бесполезно и пытаться, если у вас нет точного определения алгоритма. Гёдель, по существу, разобрался с этим вопросом, рассматривая алгоритм как доказательство в рамках аксиоматической системы. Тьюринг же начал размышлять о том, как формализовать алгоритмы в целом.
В 1935 г. он стал членом Королевского колледжа за независимое открытие центральной предельной теоремы в теории вероятностей, которая обеспечивает некоторое логическое обоснование широкому использованию «колоколообразной кривой», или нормального распределения, в статистическом анализе. Однако в 1936 г., с публикацией основополагающей статьи «О вычислимых числах применительно к Entscheidungsproblem» (проблеме разрешимости), на передний план вышли его мысли о теоремах Гёделя. В этой статье Тьюринг доказал теорему о неразрешимости для формальной модели вычислений, которую сегодня называют машиной Тьюринга. Он доказал, что ни один алгоритм не может решить заранее, остановится ли расчет с получением ответа. Его доказательство проще, чем Гёделево, хотя оба они требуют предварительных ухищрений для организации контекста.
Хотя мы говорим о машине Тьюринга, название это относится к абстрактной математической модели, представляющей идеализированную машину. Тьюринг называл ее а-машиной, где «а» означает «автоматическая». Машину эту можно представить в виде ленты, разделенной на последовательные ячейки, которые могут либо быть пустыми, либо содержать какой-нибудь символ. Лента – это память машины, она ничем не ограничена, но конечна. Если вы подошли к концу, добавьте еще несколько клеток. Некая головка, размещенная над начальной ячейкой, считывает находящийся в ней символ. Затем она сверяется с таблицей, в которой размещены правила перехода (программа, заданная пользователем), записывает в клетку какой-нибудь символ (заменяя им то, что было там до этого) и сдвигает ленту на одну ячейку вперед. Затем, в зависимости от таблицы и символа, машина либо останавливается, либо выполняет инструкции, которые таблица предписывает для символа в ячейке, на которую она передвинулась.
Вариантов существует множество, но все они эквивалентны между собой в том смысле, что могут вычислять одно и то же. Мало того, эта рудиментарная машина способна, в принципе, вычислять все то же, что и цифровой компьютер, сколь угодно быстрый и продвинутый. К примеру, машина Тьюринга, использующая символы 0–9 и, возможно, еще несколько символов, может быть запрограммирована на вычисление числа π до любого заданного числа десятичных знаков, причем машина запишет их в последовательные ячейки ленты и после этого остановится. Такой уровень общности может показаться удивительным для столь простого устройства, но все тонкости вычислений изначально зашиты в таблице с правилами перехода, которые могут быть очень сложными, – в точности как все действия компьютера зашиты в программном обеспечении, которое на нем работает. Однако простота машины Тьюринга, помимо всего прочего, делает ее очень медленной в том смысле, что даже простое вычисление требует гигантского числа шагов. Она совершенно непрактична, но из-за простоты отлично подходит для разбора теоретических вопросов об ограничениях, связанных с вычислениями.
Первая важная теорема Тьюринга доказывает существование универсальной машины Тьюринга, при помощи которой можно смоделировать любую конкретную машину. Программа конкретной машины зашифрована на ленте универсальной машины еще до начала вычислений. Правила перехода сообщают универсальной машине, как следует переводить эти символы в инструкции и исполнять их. Архитектура универсальной машины – важный шаг по направлению к реальному компьютеру, где программа размещается в памяти. Мы не строим для каждой задачи новый компьютер с жестко, на уровне «железа», заданной программой – ну разве что для каких-то совершенно особых задач.
Вторая его важная теорема – вариация на тему теорем Гёделя; она доказывает, что задача останова для машины Тьюринга неразрешима. В этой задаче требуется найти алгоритм, который мог бы решить, получив на вход программу для машины Тьюринга, остановится ли машина когда-нибудь, получив ответ, или будет работать до бесконечности. Предложенное Тьюрингом доказательство, что такого алгоритма не существует – то есть что задача останова неразрешима, – предполагает его существование, а затем применяет результирующую машину к ее собственной программе. Однако она при этом хитроумно преобразуется таким образом, что модель останавливается в том, и только том случае, если первоначальная машина этого не делает. Это приводит к противоречию: если модель останавливается, то она не останавливается; если она этого не делает, то она это делает. Мы видели, что доказательство Гёделя в конечном итоге кодирует утверждение вида «это утверждение ложно». Доказательство Тьюринга проще и больше напоминает карточку, на двух сторонах которой написано:
Утверждение на другой стороне этой карточки истинно.
Утверждение на другой стороне этой карточки ложно.
Каждое утверждение за два шага приводит к отрицанию самого себя.