Глава 2

Алгоритмы и машины Тьюринга

Основы алгоритмов

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

В дальнейших рассуждениях я буду иногда прибегать к математическим выражениям. Вероятно, некоторых читателей эти выкладки напугают и даже заставят отложить книгу в сторону. Если вы как раз такой читатель, то я прошу вашего снисхождения и рекомендую вам последовать совету, данному мной в Обращении к читателю вначале книги! Доказательства, которые здесь встретятся, не потребуют владения математическим аппаратом, выходящим за пределы школьного курса, но чтобы в них детально разобраться, все же понадобятся интеллектуальные усилия. На самом деле, большинство рассуждений изложено весьма подробно, и если внимательно им следовать, можно добиться глубокого понимания. Однако, даже беглый просмотр доказательств позволяет ухватить основную идею. С другой стороны, если вы являетесь экспертом в этой области, то я опять вынужден принести свои извинения. Но я осмелюсь предположить, что даже в этом случае вам будет небесполезно ознакомиться с моими рассуждениями, в которых почти наверняка найдется что-то интересное и для вас.

Слово «алгоритм» происходит от имени персидского математика IX века Абу Джафара Мухаммеда ибн Мусы аль-Хорезми, написавшего около 825 года н. э. руководство по математике «Kitab al-jabr wa’l-muqa-bala», которое оказало значительное влияние на математическую мысль того времени. Современное написание «алгоритм», пришедшее на смену более раннему и точному «алгоризм», своим происхождением обязано, скорее всего, ассоциации со словом «арифметика»[39]. (Примечательно, что и слово «алгебра» происходит от арабского al-jabr, фигурирующего в названии вышеупомянутой книги.)

Примеры алгоритмов были, однако, известны задолго до появления книги аль-Хорезми. Один из наиболее известных — алгоритм Евклида — процедура отыскания наибольшего общего делителя двух чисел, восходит к античности (примерно 300 лет до н. э.). Давайте посмотрим, как он работает. Возьмем для определенности два числа, скажем, 1365 и 3654. Наибольшим общим делителем двух чисел называется самое большое натуральное число, на которое делится каждое из этих чисел без остатка. Алгоритм Евклида состоит в следующем. Мы берем одно из этих чисел, делим его на другое и вычисляем остаток: так как 1365 входит дважды в 3654, в остатке получается 3654 ―

2 х 1365 = 924.

Далее мы заменяем наши два исходные числа делителем (1365) и полученным остатком (924), соответственно, производим с этой парой ту же самую операцию и получаем новый остаток:

1365 — 924 = 441.

Для новой пары чисел — а именно, 924 и 441, — получаем остаток 42. Эту процедуру надо повторять до тех пор, пока очередная пара чисел не поделится нацело. Выпишем эту последовательность:

3654:1365

дает в остатке 924

1365:924

дает в остатке 441

924:421

дает в остатке 42

441:42

дает в остатке 21

42:21

дает в остатке 0

Последнее число, на которое мы делим, а именно 21, и есть искомый наибольший общий делитель.

Алгоритм Евклида является систематической процедурой, которая позволяет найти этот делитель. Мы только что применили эту процедуру к двум конкретным числам, но она работает и в самом общем случае с произвольными числами. Для очень больших чисел эта процедура может занять много времени, и будет выполняться тем дольше, чем больше сами числа. Но в каждом конкретном случае выполнение процедуры в конце концов заканчивается, приводя за конечное число шагов к вполне определенному ответу. На каждом этапе мы точно представляем себе действие, которое должно быть выполнено, и точно знаем, когда получен окончательный результат. Более того, всю процедуру можно описать конечным числом терминов, несмотря на то, что она может применяться к любым, сколь угодно большим натуральным числам. («Натуральными числами» называются неотрицательные[40] целые числа 0,1,2,3,4,5,6,7,8,9,10,11….) На самом деле нетрудно изобразить (конечную) блок-схему, описывающую логическую последовательность операций алгоритма Евклида (рис. 2.1).

Нужно заметить, что на схеме эта процедура не до конца разбита на простейшие составляющие, поскольку мы неявным образом предположили, что нам уже «известно», как выполнять необходимую базовую операцию получения остатка от деления двух произвольных натуральных чисел А и В. Эта операция, в свою очередь, также алгоритмична и выполняется при помощи хорошо знакомой нам со школы процедуры деления. Эта процедура, на самом деле, сложнее, чем все остальные части алгоритма Евклида, но и она может быть представлена в виде блок-схемы. Основное затруднение здесь возникает из-за использования привычной «десятичной» записи натуральных чисел, что вынуждает нас выписывать все таблицы умножения, учитывать перенос и т. п. Если бы для представления некоторого числа n мы использовали последовательность из n каких-нибудь одинаковых знаков, например, пяти звездочек (*****) для обозначения пятерки, то определение остатка свелось бы к совершенно элементарной алгоритмической операции. Для того чтобы получить остаток от деления А на В, достаточно просто убирать из записи числа А последовательность знаков, представляющих В, до тех пор, пока на некотором этапе оставшееся число знаков в записи А не станет недостаточным для выполнения следующего шага. Эта последовательность знаков и даст требуемый ответ. Например, желая получить остаток от деления 17 на 5, мы просто будем последовательно удалять ***** из *****************, как это показано ниже:

*****************

************

*******

* *,

и в результате получим, очевидно, 2, так как следующее удаление уже станет невозможно. Блок-схема изложенного выше процесса нахождения остатка от деления путем последовательных вычитаний приведена на рис. 2.2.

Чтобы придать блок-схеме алгоритма Евклида завершенный вид, мы должны подставить схему отыскания остатка в соответствующий блок справа в центре предыдущей схемы. Такая подстановка одного алгоритма в другой — распространенная в компьютерном программировании процедура. Алгоритм вычисления остатка, изображенный на рис. 2.2, служит примером подпрограммы, иначе говоря, это алгоритм (как правило, уже известный), вызываемый и используемый по мере надобности в ходе выполнения основного алгоритма.

Безусловно, обозначение числа n просто набором из n звездочек чрезвычайно неэффективно, когда речь заходит о больших числах. Именно поэтому обычно используют более компактную запись, например, стандартную (десятичную) систему. Однако оставим в стороне эффективность операций и обозначений и уделим все внимание вопросу о том, какие операции в принципе могут выполняться алгоритмически. Действие, которое поддается алгоритмизации в одной записи, сохранит это свойство и в любой другой. Эти два случая различаются только техническими нюансами и сложностью выполнения алгоритма.