1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 37
Текст из файла (страница 37)
Отметим, что а [лл91 доказан результат о равноеилъиости класса я-ленточных автоматов классу унарних схем с я независимыми ячейками: с яомощью специального моделирования автоматов схемами проблемы пустоты, тоталъносги н эквивалентности для автоматов можно, з евою очередь, свести к соответствующим проблемам для слом.
Заметим также, что класс схем Янова представляет собой класс унарных схем с одной независимой ячейкой, поэтому схемы Икова можно моделировать одколенточными автоматами методом, описанным в работе [ИЯ1. Летнчевский [331 показал разрешимость подкласса консерв»- тинных схем, в которых все операторы невырожденни, а условные операторы содержат один и тот же набор переменных, составленный иэ всех переменных памяти схемы. Петросян [52, 531 обобщил этот результат на случай, когда каждый условный оператор содержит один и тот же набор переменных, составленный иэ поременных некоторой выделенной подпамяти схемы.
Гедлевский [9, [01 доказал разрешимость эквивалентности в следующем классе схем: все предикатние символи одноместны н аргументом всех условных операторов является выделенная переменная х, а все присваивания переменной х имеют внд х:= : = ~ (х,...), т. е. первим аргументом служит переменная х. Перечисленные классы схем Летичевекого, Петросяна и Годлевского являются подклассами класса сквозных схем.
Описанный в атой главе алгоритм распознавания эквнвалентности сквозных схем бил построен Сабелъфельдом [691. Непомнящий [48, 49, 4251 довольно подробно исследовал различные базисы схем, близкие к «граничным» случаям е двумя переменными, когда добавление или удаление одного оператора кардинально меняет статуе основных проблем.
Он построил неразрешимый класс схем, который в начале этой главы был назван классом У и который уже неразрешимого класса Э'< из гл. 5. Удаление любого оператора из бааиеа класса Э' превращает его э разрешимый класс. В этих же работах показана разрешимость проблемы пустоты для классов У«и 7«. Годлевский [91 и Петросян [521 доказали неразрешимость проблемы пустоты в классе схем над базисом ([х, у), [[<и, а<«>), (р<«>), [т: = У (х), у:= У (у), х:= а, у:= а, р (х, у), стон (х, у))).
Непомнящий доказал [491, что проблема пустоты остаетея неразрешимой для класса схем над бааисом 31 = ((х, у), [1<я, а<«<), [р<«<), [х:= У (х), у:= ) (у), х:= у, у:= а, р (», у), стоп (х, у))), но разрешима в классах схем над базисом, получающимся иэ базиса 169 л«г ааменой оператора у:= а на оператор у:= х или х:= а. В [49) был выделен замечательный граничный случай класса схем иад баэисом ((х, у), (о(«>, Р1>, К(о), (Ф11), (х:= у(х), у:=- а(у), (х:= := о, у:= а), р (х), р(у), стон (х, у))), в котором проблема тотальности раарешима, а проблемы пустоты и функциональной эквивалентности неразренпамы.
Здесь (х:= а, у:= а) — так нааываемый груллогой оператор прис«алганов, который присваивает аначения переменным х и у «одновременноэ, Если говорить о сложности алгоритмов, решающих основные проблемы в разрешимых классах схем, то адесь мы отметим только, что почти все они настолько сложны,что не может быть никакой речи о их прямом практическом испольэованин. Исключение составляют, пожалуй, только алгоритмы распоанавания откошеннй, блиаких к отношению изоморфизма (где верхняя оценка сложности имеет порядок О (яб (л)), см. гл.
3) и логике-термали ной эквивалентности (где доказана полиномиальная верхняя оценил сложности). О сложности распоанавання функщаональной аквиаалентности даже в таком уэком классе, каким являются простые ациклические схемы Янова, можно сказать, что к проблеме распоанавания аквнвалентности для схем етого класса сводится КР-полная проблема выполннмости формул (бескванторной) алгебры логики. 470 ГЛАВА 8 РЕКУРСИВНЫЕ СХЕМЫ В этой главе излагаются элементы теории рекурсивных схем, которые моделируют рекурсивные методы программирования (рекурсивные языки и такие ионструкцни, как рекурсивные процедуры в языках вроде Алгол-68 или Паскаль). Основное внимание уделяется проблеме взаимной транслвции рекурсивных в стандартных схем. $1. Класс рекурсивных схем 1Л.
Рекурсквиое программвреванне. Среди упомянутых выше методов формализации понятия вычислимой функцви метод Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего используются абстрактные «машнныэ, описанные в точных математических терминах. Другой подход (метод Черта — Клини) основан на понятии рекурсивной функции. Рекурсивная фуницня задается с помощью рекурсивных определений. Рекурсивное определение позволяет связать искомое значение функции для заданных аргументов с известными значениями той же функции при некоторых друтих аргументах.
Эта связь устанавливается с помощью универсального механизма рекурсии, задающего механическую процедуру поиска эначенив функция. Двум подходам к определенвю вычислимых функций соответствуют два метода программирования этих функций — операторное я рекурсивное программирование. При операторном методе программа представляет собой явно выписанную последовательность описаний действий ппютетической вычислительной машины (последовательность операторов, команд и т. и.). Язык Фортран — типичный представитель операторных языков. С другой стороны, рекурсивная программа — это совокупность рекурсивных .определений, задающих рекурсивную функцию, для которой аргументами служат начальные данные программы, а значением — результат выполнения программы.
Известный язык рекурсивного программирования — язык Лисп— предназначен для обработки символьной информации. В других, языках комбинируют оба метода программирования. Так, Паскаль — операторный язык с возможностью рекурсивного программирования, предоставляемой механизмом рекурсивных процедур и функций.
Известным прнмером рекурснвно определяемой функции является факторнальная функция РАСТ: Л-~ К, где К вЂ” множество целых неотрнцательных чнсел: 1, если х=О, РАСТ (х) = ххРАСТ(к — 1), если х >О. Операторные программы, вычисляющие значеннн етой функцик, прнведены в гл. 4. Эту >не функцию можно запрограммировать в некотором рекурсивном языке, базирующемся на механизме ре- курсивных функцвй языка Паскаль: РАСТ (я), РАСТ (л) = если л = 0 то 1 иначе х х РАСТ (л — 1), где а — некоторое целое неотрицательное число. Выполнение етой программы для некоторого значения а (пусть а = 4) может быть осуществлено следующим образом.
В обе частя рекурсивного определения вместо х подставляется 4, после чего вычисляется правая часть определення. Вычисление правой части начинается с вычисления логического выражения. Если его аначенне 1 (нстнна), то вычисляется левое функциональное выражение (стоящее после то), а если его значение 0 (ложь) — вычисляется правое выражение (стоящее после нначе). Вычисление функционального выражения сводится к его упрощению, т. е.
выполненню всех возможных вычислений. Если в упрощенном выраженнк остается вхождение символа определяемой функция РАСТ, то осуществляется переход к новому шагу выполнения программы, На атом шаге вхождение РАСТ(ш), где т — значение внутри скобок после упрощения, заменяется левым (т = 0) нлп правым (т ) 0) функцноналышм выраженном, в котором все вхождения л заменены на т. Упрощения продолжаются до тех пор, пока не будет получено выражение, не содержащее РАСТ (в нашем случае это выражение — число). РАСТ (4) = есля 4 = 0 то 1 вязче 4 х РАСТ (4 — 1) = =4х РАСТ (3) = 4 Х (если 3 = 0 то 1 вначе 3 х РАСТ (3 — 1)) =4 Х 3 х РАСТ(2) = =12х (еслк 2 = О то 1 япаче 2 х РАСТ(2 — 1)) = = 12 х 2 х РАСТЯ = 24 х (еслп 1 = 0 то 1 яначе 1 ~ РАСТ(1 — 1)) = = 24 х 1 х РАСТ(0) = 24 х (еслп 0 = =Ото 1 нначе О х РАСТ(0 — 1)) = 24 Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов (начальвых значеннй переменных), но может и продолжаться бесконечно, В последнем случае значение функции не определено.
Еще один популярный пример — рекурсивная программа, вычисляющая аначення функции Аккермана А: М'-~- Ф: 112 А (а, Ь), А (х, у) = если х = 0 то у + 1 иначе В (х, у), В(х,у) =если у=Ото А (х — 1,1) иначе С(х,у), С (х, у) = А (х — 1, А (х, у — 1)). Эта программа состоит из главного вызова А (а, Ь) и трех определений функций. Первое определение описывает функцию Аккермана А череа вспомогательную функцию В, которая задана, в свою очередь, с помощью функгсзй А и С. Последняя также определена через функцию А. Здесь каждое определение, взятое отдельно, само на себя не ссылается, но имеет место взаимная рекурсия, когда каждая из фуннцнй А, В, С косвенно определена через саму себя.
Выполнение этой программы для а = Ь = 1 выглядит следующим образом (некоторые мелкие упрощения не выписаны): А (1, 1) = если 1 = 0 то 2 иначе В (1, 1) = В (1, 1) = если 1=0 то А(0,1)вначеС (1, 1)=С(1, Ц=- =А (О, А (1, 0))= А (О, (если 1 = 0 то 1 иначе В (1, 0))) = А (О, В (1, 0)) = А (О, (еслв 0 = О то А (О, 1) иначе С(1, 0)) =А (О, Й(0, 1)) = =4 (О, (если 0 = 0 то 2 иначе В (О, 1))) = А (О, 2) = = если 0 = 0 то 2 + 1 вваче В (О, 2) = 3. Отметим, что в этом примере функциональное выражение содержит несколько вхождений символов определяемых функций (например, А (О, А (1, 0))). Использованное нами правило подстановки в этом случае требует, чтобы замещалось левое из самых внутренних вхождений (в случае упомянутого терка — вхождение А (1, 0)). Операторный н рекурсивный методы программирования имеют гвен достоинства и недостатки, обсуждать которые — не наша задача (см.
например, ставшую классической работу Дж. Бзкуез [84), обратившего внимание на преимущества функционального стиля программирования). Но чтобы подготовить почву для ташло обсуждения, полезно формализовать оба метода. Стандартные схемы являются моделями операторных программ. Сейчас е ы введем рекурсивные схемы, которые служат абстракциями рекурсивных программ, а в последующих параграфах проведем ".равнение этих моделей. 1.2. Определевве рекурсивной схемы. Так же, как и стан- ~:,зртные схемы, рекурсивные схемы определяются в некотором базисе. Веяний базис ренуреиенмх сеем, как и базис стандартных "хем, включает четыре счетных множества символов: переменные, функциональные еимеслм, иредикатнме еимеелм, енеииальнме символы. Множества переменных н предикатных символов ничем не отличаются от соответствующих множеств в базисе стандартных схем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
