§ 7. НЕОБХОДИМОСТЬ УТОЧНЕНИЯ ПОНЯТИЯ АЛГОРИТМА

Из сказанного выше видна та глубокая связь, которая существует между алгоритмами и автоматическими вычислительными машинами.

Очевидно, всякий процесс, отдельные шаги которого последовательно осуществляются автоматически

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

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

Это можно проиллюстрировать на примере алгоритма Евклида. Простейшая задача нахождения общего наибольшего делителя двух чисел может оказаться неосуществимой для вычислителя, решающего ее «вручную», если для решения этой задачи потребуется больше бумаги и чернил, чем имеется в распоряжении вычислителя. Аналогично этому алгоритм Евклида в данной конкретной задаче может оказаться неосуществимым для машины, если для его осуществления потребуется больший объем памяти, чем тот, которым располагает машина.

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

Говоря же о возможности осуществления алгоритма в машине, имеют в виду потенциальную возможность неограниченного увеличения объема памяти в машине.

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

Однако при всем подчеркивании общности этих понятий ни одно из них еще не было нами пока точно

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

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

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

Построить алгоритм, позволяющий для любого уравнения вида

произвольное натуральное число) найти все его корни.

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

Уже приведенные примеры в какой-то мере характеризуют естественное стремление математиков создавать все более и более мощные алгоритмы, решающие по возможности все более и более широкие классы задач (задачи весьма общего типа). Разумеется, в этом отношении задача о решении любого уравнения вида еще не представляет собою предела, дальше которого нельзя идти. Более того, если мы хотим быть последовательными в своем безудержном стремлении расширять класс задач, для которых желательно иметь единый разрешающий алгоритм, то мы неизбежно должны прийти к постановке следующей проблемы:

Построить алгоритм, позволяющий решать любую математическую задачу.

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

Эта проблема имеет свою историю. Еще великий немецкий математик и философ Лейбниц (1646-1716 гг.) мечтал о создании всеобщего метода, позволяющего эффективно решать любую задачу. Хотя такого всеобщего алгоритма ему и не удалось найти, Лейбниц все

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

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

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

Пользуясь терминологией, введенной ранее при рассмотрении ассоциативных исчислений, можно сказать, что всякая такая формула представляет собою слово в некотором специальном алфавите, содержащем наряду с употребительными в математике знаками вроде букв, скобок и т. д., еще и другие специальные знаки, изображающие логические операции, например, отрицание, логическую сумму и т. д. Однако главная аналогия с ассоциативными исчислениями заключается в том, что сам процесс логического вывода из какой-нибудь посылки следствия может быть описан в виде процесса формальных преобразований слов, очень схожих с допустимыми подстановками в ассоциативном исчислении. Это позволяет говорить о логическом исчислении, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой сколь угодно сложный формально-логический вывод. Примером такого допустимого преобразования является вычеркивание в формуле двух рядом стоящих знаков отрицания; скажем, «ненекрасивый» может быть преобразовано в

«красивый» (интересно сравнить это допустимое преобразо вание с подстановкой в ассоциативном исчислении примера 4).

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

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

Решение понимается в смысле алгоритма, дающего ответ на любой из вопросов такого типа (любые

Нетрудно теперь сообразить, что создание такого алгоритма позволило бы получить общий разрешающий метод для автоматического решения самых разнообразных задач из всех математических теорий, которые построены аксиоматически. Действительно, справедливость какого-либо утверждения (например, формулировка какой-нибудь теоремы) в такой теории понимается как его логическая выводимость из системы аксиом, взятой в качестве посылки Но тогда, применяя алгоритм распознавания выводимости, можно было бы установить, справедливо ли это утверждение 5 в рассматриваемой теории или нет. Более того, в случае утвердительного ответа можно было бы эффективно найти в логическом исчислении соответствующую дедуктивную цепочку, а по ней восстановить цепь умозаключений, составляющих доказательство рассматриваемого утверждения. Фактически, предполагаемый алгоритм решил бы единым эффективным методом почти все сформулированные и еще не решенные до сегодняшнего дня математические проблемы. Это обстоятельство делает понятным не только заманчивость построения такого «всеобщего алгоритма», а значит и построения соответствующей «всемогущей машины», но и трудности такого построения.

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

в частности, относится и проблема Гильберта о диофантовых уравнениях (см. § 1), а также ряд других задач, о которых будет сообщено ниже.

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

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

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

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

формул в радикалах для уравнений степени выше четвертой, продолжавшиеся до начала XIX века, оказались безуспешными, пока, наконец, был установлен следующий замечательный результат:

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

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

выработано несколько определений понятия алгоритм. Однако впоследствии выяснилось, что все эти определения равносильны между собой и, следовательно, определяют одно и то же понятие; это и есть современное точное понятие алгоритм.

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

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

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