1.3. Необходимость математического понятия алгоритма

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

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

Дальнейший процесс развития вычислительных методов содействовал утверждению, что решение любой математической проблемы должно быть алгоритмическим. Такой мысли придерживались выдающиеся математики Р.Декарт, Г.Лейбниц, Д.Гильберт. Декарт развивал аналитическую геометрию с намерением сделать ее доступной для изучения алгебраическими методами, и тем самым достичь более полной алгоритмизации геометрии. Лейбниц также занимался уточнением и решением алгоритмических проблем. Ему принадлежит первая попытка создать автоматически действующую машину для решения таких задач, но попытка закончилась неудачно. Гильберт активно стимулировал алгоритмические исследования. В частности, среди 23 знаменитых проблем Гильберта, есть десятая: дано алгебраическое уравнение f(x₁,…,x_n) = 0 с целыми коэффициентами. Необходимо найти метод, с помощью которого за конечное число операций можно было бы установить, имеет ли это уравнение решения в целых числах. Метод, про который идется в этой проблеме, понимают ныне как алгоритм. В то время теория алгоритмов еще не была создана и речь могла идти лишь о позитивном решении этой проблемы. Тем не менее в 1970 г. советский математик Ю.В. Матиясевич доказал, что такого алгоритма не существует.

К началу 20 в. стали усложняться объекты, с которыми оперировали алгоритмы (появилась необходимость выполнять операции над векторами, матрицами, множествами, функциями и т. д.). Возникли проблемы, связанные с трактовкой элементарности тех или иных шагов алгоритма, понимаемого на интуитивном уровне. Другие проблемы были связаны с оценкой конечности и однозначности алгоритма. Возникла мысль, что не для всяких математических задач вообще можно найти процедуру решения, которая явилась бы алгоритмом, то есть появилась идея о том, что существуют алгоритмически неразрешимые проблемы. Для решения указанных проблем необходимо было дать точное определение алгоритма.

Возникает вопрос: так ли уж важно и необходимо иметь точное определение алгоритма, если и без него возможно составление и применение алгоритмов (причем, даже без употребления самого термина)? Тем более, что интуитивное понятие алгоритма хотя и не обладало строгостью, но было настолько ясным, что практически до 20 в. не возникало ситуаций, когда математики разошлись бы в суждениях относительно того, является ли алгоритмом тот или иной конкретный процесс. Положение существенно изменилось в начале 20 в., когда были сформулированы такие проблемы, алгоритмическое решение которых было не очевидным.

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

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

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

Впервые вера в универсальность алгоритмических методов была подорвана в 1931 г. работой К.Геделя, в которой было показано, что есть такие математические проблемы, которые не могут быть решены с помощью алгоритмов из некоторого точно определенного класса алгоритмов. Поэтому до уточнения понятия “алгоритм” в математике были распространены две точки зрения.

1. Все проблемы алгоритмически решены. Но алгоритм для решения некоторых из них пока не найден, потому что не достаточно способов в современной математике для его построения. Построение искомых алгоритмов – дело будущего.

2. Существуют классы задач, для решения которых вообще не существует алгоритма. То есть некоторые проблемы нельзя решать механически с помощью формальных соображений и вычислений.

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

Так возникла необходимость в точном определении понятия «любой алгоритм», т.е. максимально общем определении, под которое подходили бы все мыслимые виды алгоритмов. В 20-е гг. XX в. построение определения алгоритма стало одной из центральных математических проблем. Определение это, с одной стороны, должно было соответствовать сущности интуитивного понятия алгоритма, а с другой стороны, быть формально строгим. Попытки формулировки такого понятия привели к появлению в 30-х гг. XX века теории алгоритмов как самостоятельной науки, которая вместе с математической логикой изучает основные средства математики – методы доказательств, способы построения аксиоматических теорий, свойства математических процедур и пр. Когда же в 40-е – 50-е гг. началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использованием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Любая программа есть ни что иное, как запись алгоритма на языке, который может «понять» исполнитель – компьютер. Таким образом, с практической точки зрения также представляется важным уточнение понятия алгоритма.

Действительно, одно дело – доказать существование алгоритма, а совсем другое – доказать его отсутствие. Для этого необходимо знать точно, что такое алгоритм, и что такое “алгоритмически нерешенные проблемы”. Начиная с 1935 года, был предложен ряд таких уточнений. Математики согласились на том, что уточненные понятия адекватно выражают интуитивное представление об алгоритме. Для этого есть ряд оснований:

1. Доказано, что все известные на этот час уточненные понятия алгоритма эквивалентные между собой.

2. Все алгоритмы в точном понимании являются алгоритмами в интуитивном понимании.

3. Все известные алгоритмы в интуитивном понимании можно “перемоделировать” алгоритмами в точном понимании.

Доказать адекватность интуитивного и точного понятия алгоритмов невозможно потому, что не существует точного определения алгоритма в интуитивном понимании. Вместе с тем эта адекватность широко используется как гипотеза. Первым такую гипотезу в 1936 году высказал Алонзо Черч. Ныне она известна как гипотеза Черча. Эта гипотеза не может быть доказана математическими методами, так как она сформулирована на основании практического опыта и ее правильность подтверждается практикой. Аналогичная ситуация имеет место, например, в физике: законы Ньютона подтверждается практикой и не имеют математического доказательства.

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