Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

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

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

Ч А С ТЬ II Машины Тьюринга

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

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

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

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

60

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

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

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

Поэтому можно сформулировать еще более общую задачу.

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

*) Точнее, для любого натурального числа k найти десятичные приближения корней по недостатку и по избытку с точностью до 1/10*.

62

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

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

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

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

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

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

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

63

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

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

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

Вопрос о логической выводимости предложения 5 из по­ сылки R в указанном логическом исчислении становится вопросом о существовании дедуктивной цепочки, ведущей

64

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

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

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

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

7.3. Формулировка определения «алгоритма». Очевид­ но, утверждение об алгоритмической неразрешимости не­ которого класса задач, т. е. о невозможности указать со­ ответствующий разрешающий алгоритм, является не про­