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

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

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

В чем же заключается обоснование этой столь важной гипотезы?

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

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

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

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

122

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

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

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

Общин смысл теорем замкнутости заключается в том, что класс алгоритмов, которые в принципе можно «переложить» па язык тыоринговых программ, замкнут относительно всех употребительных приемов образования новых алгоритмов из алгоритмов уже имеющихся; иначе говоря, коль скоро для исходных алгоритмов возможно задание посредством тыоринговых программ, то это возможно и для результи­ рующих более сложных алгоритмов. В § 10 это было строго доказано для таких важных приемов, как последовательная и параллельная композиция, разветвление и повторное применение алгоритмов. Разумеется, список таких приемов можно было бы продолжить. Однако для всех подобных при­ емов, которые известны, можно строго доказать аналогич­ ные теоремы. Более того, опыт подсказывает, что в точности так же обстоит дело для всех приемов, которые можно пред­ видеть в настоящее время.

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

вычисляют одну и ту же функцию. Как уже говорилось, многие математики предприняли исследования с целые вы-

123

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

шиной Тьюринга достаточно подробно рассмотрена п дру­ гая модель вычислительной машины —так называемый ав­ томат Неймана (§21—23); ранее же, в § 4, на примере алго­ ритма приведения для одного ассоциативного исчисления было иллюстрировано понятие нормального алгоритма, сформулированное А. А. Марковым. Соответственно можно говорить о тыоринговых, неймановых и марковских алго­ ритмах (программах); этот список можно было бы еще про­ должить. Оказывается, однако — и в этом как раз и за­ ключается содержание теорем равносильности — что все эти, а также и другие известные классы (типы) алгоритмов равносильны. Это означает, что при фиксации двух таких

равносильный ему алгоритм 2 в классе Д"2. Обычно дока­ зательство теоремы равносильности состоит в описании процедуры, строящей по заданному алгоритму (по заданной

§ 10, можно сказать, что эта процедура есть программиру­ ющий алгоритм, перерабатывающий программы класса К\ в программы класса /( 2 . Идея имитации (моделирования) уже была проиллюстрирована нами при сравнении машин Тьюринга с полулентой и обычных машин Тьюринга.

Как уже отмечалось в § 11, среди алгоритмических про­ блем особое место занимают те, в которых требуется найти алгоритм для вычисления всех значений некоторой функ­ ции. Теорема равносильности для каких-нибудь классов алгоритмов /\\ и К2 имеет и тот смысл, что класс функций, вычислимых посредством алгоритмов из 1\х, в точности сов­ падает с классом функций, вычислимых алгоритмами из К2- Следовательно, функции, вычислимые по Тьюрингу, или по Маркову, или по Нейману, или в смысле любого другого

124

функциями; как было показано в § 11, класс вычислимых функции совпадает с классом рекурсивных функций. Ко­ нечно, этот факт нельзя считать случайным; он является очень весомым доводом в пользу основной гипотезы.

ЧАСТЬ I I I Алгоритмические проблемы

§ 14. УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА

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

14.1.Алгоритм подражания . Для того чтобы лучше

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

125

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

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

вобозреваемой ячейке.

Ук а з а н и е 4. Замените букву из обозреваемой ячейки первой буквой из обозреваемой тройки.

Ук а з а н и е 5. Если в обозреваемой тройке второй буквой является !, то остановитесь: процесс окончен.

Ук а з а н и е 6. • Если в обозреваемой тройке второй буквой является И, то замените букву, подписанную под обозреваемой ячейкой, третьей буквой из обозреваемой тройки.

Ук а з а н и е 7. Если в обозреваемой тройке второй буквой является Л , то сотрите букву, подписанную под обозреваемой ячейкой, и левее ее запишите третью букву из обозреваемой тройки.

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

Ук а з а н и е 9. Переходите к указанию 1.

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

*> То есть в функциональной схеме.

126

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

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

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

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

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

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

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

127