штрихованными буквами {например, (qca) = CiCj}. Обозначим через ф систему продукций с алфавитом D и базисными продукциями

cjW-c-W

Wc], - Wcj

{i = 1, (7 = 1,

, I), ,P)-

Для любых двух слов х, ri в алфавите С отношение f --I) истинно в системе подстановок © тогда и только тогда, когда оно истинно в системе продукций «р.

В самом деле, неносредственно ясно, что если слово t) в С получается из слова f подстановкой йг Ьг, то X} можно ползить из J совокупностью продукций вида (4). П оэтому из 5 9 в © следует f i) в ф.

Обратно, пусть для некоторых слов , t) в алфавите С имеем 5 \- t) в ?р. Тогда найдется конечная цепочка слов

?2, в алфавите D такая, что в цепочке

5 = ?о, ?1, . . ., ft, fm = ?)

каждое слово fj+i получается из предыдущего слова f посредством какой-то из продукций (4). Индукцией по i легко убеждаемся сначала, что каждое слово f; имеет вид fj = Mi или ?г - {ii, где t),-, j; - слова в алфавите С. Полагаем {щ)* = = Просматривая продукции

(4), сразу н{е видим, что для каждого i либо (fj)* == = либо получается из (f)* одной из под-

становок (2), что и требовалось.

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

Б самом деле, пусть А (£) - ассоциативное исчисление с алфавитом {О, 1, до, gi, . • . gn, v} = С, в котором неразрешима проблема равенства слову ди. Такое исчисление было построено в п. 13.1. Обозначим через ?р систему продукцией с алфавитом D = {О, 1, до, • . ., д О, 1, до, . . ., дп, v}, получаемую из ассоциативного исчисления процессом, описанным в теореме 2. Тогда совокупность тех слов в алфавите С, которые выводимы продукциями из слова gov, будет совпадать с совокупностью всех слов, эквивалентных счову goi в псчисленип А (£). Так как последняя совокуппость нерекурспвна, то нере-

курсивна и совокупность всех слов в алфавите Х), выводимых продукциями из qoV.

14.2. Нормальные алгоритмы. Фиксируем какой-нибудь алфавит А и пусть символы и • не входят в А. Следуя Маркову, формулы вида

йЬ, а-Ь, (1)

где й, Ь - какие-нибудь слова (возможно и пустые) в алфавите А, будем называть соответственно простыми и заключительными формулами подстановок. Слово й будет называться левым, а слово Ь - правым словом формулы.

Произвольная конечная последовательность формул подстановок называется схемой. Нормальным алгоритмом с данной схемой % в алфавите А называется следующее предписание для переработки слов в алфавите А.

Пусть задано произвольное слово j в алфавите А. Полагаем по определению fo = J и говорим, что слово fo получается из слова f после нуля шагов переработки. Пусть для некоторого натурального п нам уже известно слово fn, полученное из f после п шагов переработки. Тогда {п + 1)-й шаг переработки будет состоять в следующих действиях. В схеме % ищем первую формулу подстановок (1), левая часть которой й есть подслово слова f„, ц затем в f„ вместо первого вхождения а подставляем правое слово Ь этой формулы. Возникшее в результате подстановки слово обозначается через f„+i. Если использованная для получения f„+i формула подстановок была простой, то говорим, что fn+i есть слово, получающееся из f после п -{- 1 шагов переработки. Если же указанная формула подстановок была заключительной, то слово f„+i называется результатом переработки слова f посредством алгоритма 51 и обозначается символом 5f (f).

Может случиться, что в схеме % не окажется ни одной формулы подстановок, левое слово которой входит в качестве подслова в слово г„. В этом случае мы полагаем 5,141 = fп н также говорим, что f„+i есть результат переработки слова f посредствод! алгоритма 9(. В обоих последних слзлаях говорят, что процесс переработки слова обрывается после {п -Ь 1)-го шага. Если процесс переработки слова f нп на каком шаге не обрывается, то говорят, что рез5м[ьтат переработки слова f посредством алгоритма не определен. В этом последнем случае символу Ш (г) приписывается неопределенное значение.

В формулах подстановок (1) слова а, 6 могут быть пустыми. В связи с этим возникает вопрос, что значит в данное слово 5 подставить Ь вместо первого вхождения в X пустого слова а = Л? По определению полагают, что результатом указанной подстановки является слово Ьр. Например, нормальный алгоритм % со схемой, состоящей лишь из одной формулы Л • а, каждое слово f перерабатывает в слово aj.

Выше определено понятие нормального алгоритма в алфавите Л. Если алгоритм 31 задан в некотором расширении алфавита Л, то говорят, что 31 есть нормальный алгоритм над А. Одноместная частичная словарная функция F (f), заданная в алфавите А, называется нормально вычислимой, если существует нормальный алгоритм 31 над алфавитом А такой, что для каждого слова f в алфавите А выполнено равенство F {$) = йИ (?).

В частности, алгоритм со схемой Л • Л вычисляет функцию F (?) = J, а алгоритм со схемой Л Л вычисляет нигде не определенную функцию.

В качестве более содержательного примера рассмотрим словарную функцию в алфавите {О, 1}, заданную формулой F (г) = ja. Пусть 3( - нормальный алгоритм в более широком алфавите {О, 1, 2}, имеющий схему

20 02, 21 12, 2 -а, Л 2.

Возьмем какое-нибудь слово в алфавите {О, 1}, например, слово ОНО = i". После первого шага мы получим слово 20110. Каждый следующий шаг переработки будет сдвигать символ 2 на одно место вправо и после 5-го шага мы будем иметь слово 01102, которое после использования заключительной формулы даст слово 0110 а = ра.

Таким образом, алгоритм над алфавитом {О, 1} с указанной схемой вычисляет функцию ja, заданную в алфавите {О, 1}.

Мы не будем рассматривать более сложные примеры, так как легко устанавливается следующая общая

Теорема 1 (Детловс [1]). Класс нормально вычислимых частичных функций, заданных в произвольном алфавите А, совпадает с классом всех одноместных частично рекурсивных словарные функций в алфавите А.

Для доказательства достаточно сравнить определенпе нормального алгоритма с определением алгоритма Тьюринга при помощи программы подстановок. В самом деле, пусть F (г) - произвольная частично рекурсивная сло-

варная функция, заданная в алфавите А. Согласно п. 12.3 существует машина Тьюринга £, имеющая внешний алфавит {ао} U А (ао - новый, не входящий в А символ) п вычисляющая функцию F (х).

Пусть до, Qi, . . ., g„ - внутренние состояния £ и ф - программа подстановок для £. Заменяя входящие в $ формулы вида дадф-к формулами qiaj-у- -доа, получим схему некоторого нормального алгоритма 91 в алфавите J. Q {ао, до, . . ., Qn)- Сравнивая описания работы машины £ и операций, предписываемых алгоритмом 31, непосредственно видим, что для каждого слова х в алфавите А ф (?) = Э( (5). Таким образом, каждая частично рекурсивная словарная функция нормально вычислима.

Обратно, пусть задан нормальный алгоритм со схемой 31 в алфавите А. Пусть символ до не входит-в А. Заменяя точки в формулах 3( символом до, присоединяя в начале формулу до до ив конце формулу Л до, получим программу подстановок (в смысле п.12.2). В п. 12.2 доказано, что частичная словарная функция F (5), заданная в алфавите А и вычисляемая с помощью указанной программы подстановок, является частично рекурсивной. Так как ясно, что функцип F (5) и 31 (5) совпадают, то мы приходим к выводу, что каждая нормально вычислимая функция частично рекурсивна.

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

IV а Р

где i - номер приказа, w - символ фикспрованноп одноместной частичной функции, а, р -номера некоторых приказов. Выполнить приказ (1) над числом х - значит найти число W [х) и далее перейти к выполнению над w (х) приказа с номером а; еслп же w (х) не определено, то перейти к выполнению над числом х приказа с номером [3.

292 гл. VI. ВАРИАНТЫ МАШИН и АЛГОРИТМОВ

Например, выполнив над числом 24 приказ i:

получим число 4 и указание выполнять далее над 4 приказ с номером 7. Выполнив же упомянутый приказ над числом 23, получим снова число 23 и указание выполнять над 23 приказ с номером 13.

Помимо приказов вида (1), будет нужен eni;e приказ

стон

который означает,, что вычисления следует остановить и что число, над которым следует выполнить приказ (2), есть результат вычислений.

Результат выполнения приказа (1) над числом х мы будем изображать нарой (z, у), где z - полученное число, у - номер приказа, который должен выполняться далее над Z.

Программой операторного алгоритма называется последовательность приказов вида

где Wi {x), . . ., Ws {x) - заданные частичные функции,

Pi, . . ., «5, Ps - какие-то натуральные числа из последовательности О, 1, . . ., S.

Пусть задано произвольное чпсло х. Переработать х согласно указанной программе - это значит выполнить над X последовательность следзющпх действий:

1-й шаг: находим и\ (х). Если Wi {х) определено, то результатом первого шага будет пара чпсел {w, {х), а,). Если Wi {х) не определено, то результатом первого шага будет пара (х, РО.

2-й шаг: пусть пара (х,, у) есть результат предыдуш;его шага. Выполняем над х, приказ с номером у из программы (3), т. е. находим Wy (х). Еслп Wy {xi) определено, то результатом 2-го шага будет пара {wy (xi), ссу). Еслп же Wy {хх) не определено, то результатом 2-го шага будет пара {хх, pv) и т. д.

Если на п-м шаге получится пара вида (а, 0), то по определению на этом процесс обрывается и число а называется результатом переработки первоначально числа х

согласно программе (3). Если же пара вида (а, 0) ни на каком шаге не возникает, то результатом переработки х будет «неоиределенное значение».

В дальнейшем мы вседа будет иринисывать номер О приказу «стон» и номер 1 начальному приказу. Остальные /ке приказы иногда будем нумеровать не только натуральными числами, но и нарами чисел, и сш1Волами какого-нибудь алфавита. Важно лишь одно: если программа содержит приказ

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

Говорят, что операторный алгоритм А с ирограммов (3) вычисляет частичную функцию / (х), если алгоритл! А иерерабатывет каждое натуральное число х в f (х). В частности, если / (х) не определено, то процесс переработки X согласно программе (3) должен быть бесконечным.

Природа функций, вычислимых посредством оператор-пых алгоритмов, зависит, конечно, оттого, какие функции Wi входят в записи приказов. Простейшим фактом в этом направлении является

Теорема 1. Для того чтобы частичная функция / [х) была вычислима с помощью операторного алгоритма, программа которого (3) содержит лишь частично рекурсивные функции Wi {х) с рекурсивной областью определения, необходимо и достаточно, чтобы j [х) была частично рекурсивной.

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

вычисляет нигде не определеннзю функцию / {х).

Пусть частично рекурсивная функция / (у) имеет непустой график. Тогда этот график можно представить в вид€