совокуиности пар <а (i), р (i)> (t = О, 1, . . .), где а, fj - подходящие примитивно рекурсивные функции. Обозначим через v (х) выражение 2 и введем частичную функцию W (х), полагая

= 32;, если exoa;7oc(exia;),

не определено, если exoa; = a(exia;).

Функция W (х) частично рекурсивна с рекурсивной областью определения. Легко убедиться, что операторный алгоритм, имеющий проградгму:

w{x)

вычисляет как раз функцию / (х). В самом деле, выполнив над произвольным числом х приказ 1, получим пару (2-, 2). Если X Ф а (0), то, выполнив над 2* приказ 2, получим пару {2-3, 2). Если х Ф а {!), то, выполнив над 2••3 приказ 2, получим пару (2=-3, 2.) и т. д. Процесс продолжается до тех пор, пока, наконец, получится пара (2-3", 2), для которой х = а (п). Так как w (2-•3") не определено, то над числом 2*-3" теперь надо выполнить приказ 3, в результате которого получим пару {?г, 4). Выполнив над п приказ 4, получим пару (Р (п), 0). Так как х = а (п), то (п) = f (х) и, следовательно, алгоритм перерабатывает х в f (х), что и требовалось.

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

Теорема 2 (Минский [1]). Для каждой частично рекурсивной функции i [х) существует операторный алгоритм, программа которого состоит из приказов вида

для любого X перерабатывающий 2 в 2<).

Иными словами, любая частично рекурсивная функция / [х) вычислима при помощи подходящего алгоритма программа которого состоит из приказов вида (4), при условии, что значения аргумента и функции кодируются числами 2", 2(. Из доказательства теоремы будет видно, что в ее формулировке числа 3, 5 можно заменить любыми другими взаимно простыми нечетными числами.

Прежде всего покажем, как для любой машины Тьюринга £ с внешним алфавитом {О, 1} можно построить программу операторного алгоритма, выполняющего, грубо говоря, ту же работу, что и машина £. Мы можем предполагать, что в процессе работы машина % не надстраивает ленты слева. Пусть qo, q, . . ., q - внутренние состояния машины £. Мгновенное состояние всей машины £ описывается машинным словом

у = brbr-i . . . boqiOoay . . . а (bx, = О, 1), (5)

которое мы условимся кодировать парой чисел (2"•3 i), где

а = ао -Ь ai-2 --. . . . + as-2, b = bo + Ьу2 + . . . + Ьг-2Г

В зависимости от i и ао машина £ перейдет из конфигурации р в конфигурацию f. Пусть конфигурация кодируется парой {2-3, ]). Число 2°.3* зависит от чисел 2-3, i, ао, а число / зависит лишь от i и ао. Поэтому полагаем / = h (i, ао).

Но чпсло ао само есть функция числа z = 2"-3 :

ао =

0, если exoz четно,

1, если exoZ нечетно.

Следовательно, с и d будут зависеть от z = 2°-3 и г, п мы можем ввести для каждого i = 1, . . ., п две частичные функцпп Wio, н/ц, полагая по определению

то (z) "41 (Z)

= 2-3, если ex6z четно,

не определено, еслп ехо z нечетно,

=i2=3, если exflS нечетно,

не определено, если exoZ четно.

стоп

Пара приказов

переводит указанную выше пару чисел (2-3, i), отвечаю-щих конфигурации j, в пару чисел (2=-3, /), отвечаюш;их конфигурации f. В частности, если машина £ перерабатывает какую-нибудь начальную конфигурацию

bbr-i . . . boqiaoux . . . в заключительную конфигурацию

ddu-i . . . daqacac-x . . . с,,

(9) (10)

то алгоритм А с программой (8) переработает число 2-3 в число 2-3, где а, b выражаются формулами (6), а с, d вычисляются по таким же формулам для (10).

Приказы программы (8) содержат более сложные функции, чем те, которые указываются теоремой 2. Наша задача состоит в том, чтобы каждый приказ из программы (8) заменить равносильной ему серией приказов впда (4).

Рассмотрим приказ i:

. Нам задана пара чисел

(2-3, г), кодируюш;ая некоторую конфигурацию (5) машпны £. В соответствии с формулой (7) мы должны прежде всего узнать, четно а илп нет. Для этого niimCiM серию приказов

:4 i.l

1.1:

i.2:

:2 i.3 i.4

В результате этих приказов пара (2°-3, i) преобразу-етсяв пару {3o->/, i.3), еслианечетно, пвпару {35/-, i.4), еслп а четно. В первом случае нам надо далее перейти к паре {2°-3, i*). Очевидно, мы достигнем этого

Bo втором случае нам надо от пары {3-5°-/, i.4) перейти к паре (2=-3, /), которая кодирует машинное слово 5, непосредственно следующее за f. Чтобы найти f, надо обратиться к программе машины £. Так как обозреваемая ячейка ао находится в состоянии О, то рассматриваем ту из команд

qfi -> qe, qfi -> qjL, qfi -> qjR,

которая содержится в программе £. Пусть, например, это команда qfi qjR. Тогда

f = bX-x . . . boOqjai . . . Us

и кодирующей парой является пара {2/-3, j).

Чтобы перейти к этой паре от пары {3-5°-/, i.4), пишем приказы

i.4:

в результате которых из пары (3-5"/, i.4) получим пару (2/2.3 i.8). Приказами

i.lO

i.9:

переводим пару (2-/2•3 i.8) в пару (2/2.5 i.lO). Затем приказалш

i.lO:

i.ll

i.ll:

переводим пару {2"-- 5, i.lO) в требуемую пару {2"/ • 3, j).

Итак, мы указали, как постропть серию новых приказов i, i.l, . . ., i.ll, равносильную старому приказу г, в случае, когда машина £ выполняет команду доО- qjR. Ясно, что тем же способом соответствующие серии приказов можно построить п в тех случаях, когда машина £ вместо команды дО qjR выполняет команду qfi -> qjL или команду дО -> де.

Наконец, тем же способом строится и серия новых приказов, заменяющая старый приказ е номером i*.

Рассмотрим операторный алгоритм А с программой

приказами i.3:

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

равносилен паре приказов У-

а приказ вида у: у:

равносилен приказам

у.2:

имеющим уже стандартную форму, требуемую теоремой 2. То же относится и к приказам

После всех указанных замен у нас получится операторный алгоритм В, программа которого состоит из приказов вида, требуемого теоремой 2. Из построения видно, что новый алгоритм В об.ладает тем же основным свойством что и алгоритм А, а именно, если машина £ из какой-нпбудь начальной конфигурации (9) переходит через конечное число тактов работы в заключительную конфигурацию (10), то алгоритм В перерабатывает число 2°-3 в число г-З*.

Пусть теперь нам задана какая-нибудь частично рекурсивная функция / (х). В соответствии с п. 12.3 строим машину Тьюринга £, имеющую внешний алфавит {О, 1} и перерабатывающую машинное слово qyOi в слово goOl-. Обозначим через В операторный алгоритм, отвечающий машине £ и имеющий программу вида (4). Так как упомянутые машинные слова кодируются парами

(22»*1-2, 1), (22/М-1-2 0),

то алгоритм В перерабатывает чпсло] 2-" в чпсло 22!(.х)--1-о Мы сначала изменим алгоритм В так, чтобы он переводил 2- в Z-

, 3:

4 5

, 5:

перерабатывает число 2 в число 2--, а алгоритм D, имеющий программу!

, 3:

перерабатывает 2 в 2*. Таким] образом, алгоритм CBD перерабатывает 2" в 2-\

Нам остается построить программы алгоритмов, пере-рабатыз. ющих 2 в 2* и соответственно 2 в 2". Приказы

. 3:

переведут пару (2, 1) в пару (2-5, 4), а приказы 4:

переведут (2-5-, 4) сначала в пару (2•5=" 4), затем в пару (2* •б"-, 4) и через х циклов] получим) требуемую пару (2 0).

С другой стороны, еслп задана пара (2-, 1), то приказы

Легко видеть, что алгоритм С, имеющий программу 1: