книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

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

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

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

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

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

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

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

60

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

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

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

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

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

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

62

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

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

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

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

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

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

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

63

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

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

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

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

64

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

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

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

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

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

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

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

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

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

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

66

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

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

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

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

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

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

§ 8. МАШИНА ТЬЮРИНГА

Отличительные особенности машины Тьюринга по сравнению с электронными машинами, описанными в § 5, 6, заключаются в следующем:

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

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

2. В машине Тьюринга часть памяти*' изображается в виде неограниченной с обеих сторон ленты, разбитой на

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

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

8.1. Определение машины Тьюринга. Перейдем к по­ дробному описанию машины Тьюринга.

*) А именно, так называемая внешняя память.

68

1. Машина располагает конечным числом знаков (сим­

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

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

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

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

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

69