Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

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

В 1928 году немецкий математик Давид Гильберт, известный своим обыкновением ставить перед коллегами вопросы, на которые не было готового ответа [19] В 1900 году на II Международном конгрессе математиков в Париже Гильберт сформулировал 23 проблемы, которые считал важнейшими в математике. Эти задачи, называемые проблемами Гильберта, оказали существенное влияние на математику XX века. На настоящий момент полностью решены 12 из них (если не считать нескольких, в которых формулировка оказалась слишком расплывчатой для создания математического утверждения). – Прим. науч. ред . , сформулировал задачу, названную им Entscheidungsproblem , или “проблемой разрешимости”. В задаче спрашивалось: всегда ли можно найти поэтапную процедуру, позволяющую за конечный промежуток времени определить, является математическое утверждение истинным или ложным? Гильберт надеялся на положительный ответ, но не прошло и десяти лет, как эта надежда рухнула.

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

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

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

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

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

Простой пример: прибавление к цепочке из n единиц еще одной, или, другими словами, превращение n в n + 1. Входные данные в этом случае – последовательность единиц и за ней пустая ячейка либо, если n = 0, просто пустая ячейка. Головке дается первая команда: перейти к первой непустой ячейке – или, если известно, что на ленте нет вообще никаких данных, начать с любой ячейки – и считать ее содержимое. В случае, если в ячейке стоит 1, дается команда оставить ее как есть и перейти на одну ячейку вправо, не переключаясь в другое состояние; если же ячейка пустая, дается команда записать в ней 1 и остановиться. Дописав к цепочке цифр единицу, головка может, в зависимости от полученной команды, либо остановиться, либо вернуться в исходную позицию – например, для того чтобы начать процесс заново и дописать к цепочке еще одну единицу. Как вариант, после размещения головки над последней в цепочке единицей может быть введено какое-либо иное состояние, после чего головка начнет выполнять новый набор команд.