Эта странная математика

Глава 5. Фантастическая машина Тьюринга

Можно создать одну-единственную машину, которую можно использовать для вычисления любой вычислимой последовательности[18].

Алан Тьюринг

У компьютеров, пожалуй, больше общего с инженерным делом, чем с математикой, и когда речь идет об аппаратной части и программировании, с этим не поспоришь. Но теория алгоритмов – теоретическая информатика – наука самая что ни на есть математическая. Наш путь через лабиринты странной математики компьютеров к дальним пределам возможностей вычисления начинается почти столетие назад, задолго до того, как зажегся огонек первого электронного мозга.

В 1928 году немецкий математик Давид Гильберт, известный своим обыкновением ставить перед коллегами вопросы, на которые не было готового ответа[19]

, сформулировал задачу, названную им Entscheidungsproblem, или “проблемой разрешимости”. В задаче спрашивалось: всегда ли можно найти поэтапную процедуру, позволяющую за конечный промежуток времени определить, является математическое утверждение истинным или ложным? Гильберт надеялся на положительный ответ, но не прошло и десяти лет, как эта надежда рухнула.

Первый удар нанесла статья, опубликованная в 1931 году логиком австрийского происхождения Куртом Гёделем (о его работе мы еще поговорим подробнее в последней главе), изучавшим аксиоматические системы – наборы аксиом, или правил, принимаемых за самоочевидную истину, из которых выводятся теоремы. Гёдель показал, что в любой логически непротиворечивой системе аксиом, которая достаточно велика, чтобы включать в себя все правила арифметики, существуют истинные утверждения, чью истинность невозможно доказать средствами самой этой системы. Вывод, получивший название теорем Гёделя о неполноте, означал, что всегда будут существовать математические истины, которые невозможно доказать. Открытие стало потрясением для многих ученых, но оно еще не ставило крест на вопросе разрешимости математических утверждений, или, другими словами, на возможности найти алгоритм (последовательность шагов), способный гарантированно определить, является ли утверждение доказуемым, а если является – истинно оно или ложно. Крест на этом вопросе будет поставлен несколько позже, во многом благодаря молодому англичанину Алану Тьюрингу, который помог вынести окончательный вердикт по

Entscheidungsproblem.

В жизни Тьюринга смешались триумф и трагедия: триумф гения, одного из основателей теории вычислительных систем, приблизившего окончание Второй мировой войны, и трагедия человека, на себе испытавшего отношение общества той поры к гомосексуалам. В раннем возрасте у него открылся удивительный талант к математике и естественным наукам. Проявился он уже в Шерборнской школе в графстве Дорсет, которую Тьюринг начал посещать в 1926 году в возрасте тринадцати лет. В школе Тьюринг крепко сдружился с другим талантливым учеником, своим одноклассником Кристофером Моркомом. Внезапная смерть Моркома в 1930 году глубоко потрясла Тьюринга. Он целиком посвятил себя занятиям математикой, а из-за потери друга стал проявлять острый интерес к природе человеческого разума и возможности жизни духа после смерти тела, надеясь, что ответ на этот вопрос сможет дать квантовая механика.

Во время учебы в Кембридже Тьюринг прослушал курс логики, из которого он узнал об Entscheidungsproblem.

Убежденный в неправоте Гильберта, он решил посвятить этой проблеме отдельную научную работу. Тьюринг считал, что алгоритм, позволяющий определить, возможно ли доказать конкретное математическое утверждение, существует не всегда. Для работы над проблемой разрешимости ему требовался способ реализации алгоритмов: некое идеализированное устройство, умеющее выполнить любой заданный ему логический набор команд. Таким устройством стала придуманная им воображаемая “a-машина” (где буква а означала “автоматическая”), которая вскоре получила название “машина Тьюринга”, – чистая абстракция, он даже не предполагал воплощать ее в реальности. Конструкция ее была нарочито примитивной, а работала бы такая машина мучительно медленно. Она изначально создавалась исключительно как упрощенная до предела математическая модель вычислительной машины.

Машина Тьюринга состоит из бесконечно длинной ленты, разделенной на ячейки, каждая из которых может быть пустой или содержать 1 либо 0, и головки чтения-записи. Головка считывает по одной ячейке за шаг и выполняет определенное действие в зависимости от содержимого ячейки, внутреннего состояния головки и текущей команды в ее протоколе или программе. Команда может иметь, например, следующий вид: “Если вы находитесь в состоянии 18 и обозреваемая ячейка содержит 0, то замените его на 1, передвиньте ленту на одну ячейку влево и переключитесь в состояние 25”.