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

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

Рис. 32.

Перейдем к рассмотрению тыоринговых машин с многомерной

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

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

вычислима на машине с двумерной памятью, то она вычислима и на обычной машине с одномерной лептой. Это утверждение справедли­

о полуленте. Именно программу машины 9)2 с /е-мерной лентой можно перестроить в программу машины 93с' с обычной лентой, которая в определенном смысле имитирует работу машины 9Л. Однако реали­ зация этой идеи в данном случае несколько сложнее.

§ 13. ОСНОВНАЯ ГИПОТЕЗА ТЕОРИИ АЛГОРИТМОВ

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

120

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

Мы рассмотрим здесь два вопроса, возникающих в связи

сформулировкой гипотезы:

1.В чем заключается значение этой гипотезы для тео­ рии алгоритмов?

2.В чем заключается обоснование гипотезы?

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

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

121

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

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

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

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

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

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

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

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

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

Например, вместо схемы рис. 12 возникает одномерная строка символов

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

II I I Ы-

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

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

Конечно, можно было выбрать другие буквы, отличные от Л, П, Н, и для обозначения сдвигов (влево, вправо, от­ сутствие сдвига), однако при этом должно быть четко ого­ ворено, какой именно буквой такой сдвиг обозначается. Здесь сказывается тот факт, что каждая из трех букв обо­ значает вполне определенное действие, которое не заменимо другим.

Учитывая эти обстоятельства, заменим в строке Q каж­ дую отдельную букву некоторой последовательностью из единиц и нулей (кодовой группой) так, чтобы различные буквы заменялись различными кодовыми группами, но одна и та же буква заменялась бы всюду, где бы она ни встре­ чалась, одной и той же кодовой группой. В результате такой замены, например, строка Q перейдет в некоторую строку Q'. Для того чтобы по й ' можно было восстановить Q, способ

128