Алгоритм Евклида — это лишь одна из многих, часто классических, алгоритмических процедур, встречающихся в математике повсеместно. Но, вероятно, не лишним будет отметить, что, несмотря на значительный исторический возраст отдельных алгоритмов, точная формулировка универсального определения алгоритма появилась только в двадцатом веке. В 1930-х годах было предложено несколько альтернативных формулировок этого понятия, из которых наиболее емкая и убедительная — и, к тому же, наиболее значимая в историческом плане — опирается на понятие машины Тьюринга. Поэтому нам будет полезно рассмотреть некоторые свойства этих «машин».

Прежде всего следует помнить, что «машина» Тьюринга принадлежит области «абстрактной математики» и ни в коем случае не является физическим объектом. Это понятие было введено в 1935–1936 годах английским математиком и кибернетиком Аланом Тьюрингом, внесшим огромный новаторский вклад в развитие компьютерной науки (Тьюринг [1937]). Тьюринг рассматривал задачу весьма общего характера (известную как проблема алгоритмической разрешимости), которая была поставлена великим немецким математиком Давидом Гильбертом частично в 1900 году на Парижском Конгрессе математиков (так называемая «десятая проблема Гильберта»), и более полно — на международном конгрессе 1928 года в Болонье. Проблема, поставленная Гильбертом, состояла ни больше, ни меньше как в отыскании универсальной алгоритмической процедуры для решения математических задач или, вернее, ответа на вопрос о принципиальной возможности такой процедуры. Кроме того, Гильберт сформулировал программу, целью которой было построение математики на несокрушимом фундаменте из аксиом и правил вывода, установленных раз и навсегда. Но к тому моменту, когда Тьюринг написал свою великую работу, сама идея этой программы уже была опровергнута поразительной теоремой, доказанной в 1931 году блестящим австрийским логиком Куртом Геделем. Мы рассмотрим теорему Геделя и ее значение в четвертой главе. Проблема Гильберта, которую исследовал Тьюринг (Entscheidungsproblem), не зависит от какого-либо конкретного построения математики в терминах аксиоматической системы. Вопрос формулировался так: существует ли некая универсальная механическая процедура, позволяющая, в принципе, решить все математические задачи (из некоторого вполне определенного класса) одну за другой?

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

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

Концепция Тьюринга

Попробуем представить себе устройство, предназначенное для выполнения некоторой (конечноопределенной) вычислительной процедуры. Каким могло бы быть такое устройство в общем случае? Мы должны быть готовы к некоторой идеализации и не должны обращать внимания на практические аспекты — мы на самом деле рассматриваем математическую идеализацию «машины». Нам нужно устройство, способное принимать дискретное множество различных возможных состояний, число которых конечно (хотя и может быть очень большим). Мы назовем их внутренними состояниями устройства. Однако мы не хотим, чтобы объем выполняемых на этом устройстве вычислений был принципиально ограничен. Вспомним описанный выше алгоритм Евклида. В принципе, не существует предельной величины числа, после которой алгоритм перестает работать. Этот алгоритм, или некая общая вычислительная процедура, будет тем же самым независимо от того, сколь велики числа, к которым он применяется. Естественно, для очень больших чисел выполнение процедуры может занять много времени и может потребоваться огромное количество «черновиков» для выполнения пошаговых вычислений. Но сам по себе алгоритм останется тем же конечным набором инструкций, сколь бы большими ни были эти числа.

Значит, несмотря на конечность числа внутренних состояний, наше устройство должно быть приспособлено для работы с входными данными неограниченного объема. Более того, устройство должно иметь возможность использовать внешнюю память неограниченного объема (наши «черновики») для хранения данных, необходимых для вычислений, а также уметь выдавать окончательное решение любого размера. Поскольку наше устройство имеет только конечное число различных внутренних состояний, мы не можем ожидать, что оно будет «хранить внутри себя» все внешние данные, равно как и результаты своих промежуточных вычислений. Напротив, оно должно обращаться только к тем данным и полученным результатам, с которыми оно работает непосредственно в настоящий момент, и уметь производить над ними требуемые (опять же, в данный момент) операции. Далее, устройство записывает результаты этих операций — возможно, в отведенной для этого внешней памяти — и переходит к следующему шагу. Именно неограниченные объемы входных данных, вычислений и окончательного результата говорят о том, что мы имеем дело с идеализированным математическим объектом, который не может быть реализован на практике (рис. 2.3).

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

На самом деле память устройства, которая выше была названа «внешней», можно рассматривать как внутренний компонент современного компьютера. Но это уже технические детали — рассматривать часть объема для хранения информации как внутреннюю или внешнюю по отношению к устройству. Одним из способов проводить такое деление между «устройством» и «внешней» частью могло бы стать использование понятий аппаратного (hardware) и программного (software) обеспечения вычислений. В этой терминологии внутренняя часть могла бы соответствовать аппаратному обеспечению (hardware), тогда как внешняя — программному обеспечению (software). Я не буду жестко придерживаться именно этой классификации, однако, какую бы точку зрения мы не заняли, не вызывает сомнений, что идеализация Тьюринга достаточно точно аппроксимируется современными электронными компьютерами.

Тьюринг представлял внешние данные и объем для хранения информации в виде «ленты» с нанесенными на нее метками. Устройство по мере необходимости могло обращаться к этой ленте, «считывать» с нее информацию и перемещать ее вперед или назад в ходе выполнения операций. Помимо этого, устройство могло ставить новые метки на ленту и стирать с нее старые, что позволяло использовать одну и ту же ленту и как внешнюю память (то есть «черновик»), и как источник входных данных. На самом деле, не стоило бы проводить явное различие между этими двумя понятиями, поскольку во многих операциях промежуточные результаты вычислений могут играть роль новых исходных данных. Вспомним, что при использовании алгоритма Евклида мы раз за разом замещали исходные числа (А и В) результатами, полученными на разных этапах вычислений. Сходным образом та же самая лента может быть использована и для вывода окончательного результата («ответа»). Лента будет двигаться через устройство туда-сюда до тех пор, пока выполняются вычисления. Когда, наконец, все вычисления закончены, устройство останавливается, и результат вычислений отображается на части ленты, лежащей по одну сторону от устройства. Для определенности будем считать, что ответ всегда записывается на части ленты, расположенной слева от устройства, а все исходные числовые данные и условия задачи — на части ленты, расположенной справа от него.