переведут пару (З"" -5, 5) в пару [l -5, 1). Применяя к последней паре снова весь цикл преобразований 1-6, получим пару {2~"-Ъ, 1) и т. д. После исчерпания всех четверок мы получим пару (2-5, 7), которую приказы

переработают в окончательную пару (2-", 0).

Итак, преобразуя сначала 2*" в 2, затем 2 в 2" и, наконец, 2-" в 2="), получим операторный алгоритм с программой вида (4), преобразуюш;ий 2 в 2W.

Теорема 2 доказана. Указанное в ней кодирование значений X mf [х) л виде 2" и 2( в каком-то смысле неизбежно, так как, например, Барздинь [1] показал, что невозможен операторный алгоритм с программой вида (4), который бы перерабатывал х в х. Поэтому, если мы хотим иметь операторные алгоритмы, перерабатывающие xuf [х) для любой частично рекурсивной функции /, то к списку приказов (4) мы должны присоединить приказы иного вида. В частности, из теоремы 2 неносредственно вытекает, что для каждой частично рекурсивной функции f (х) существует операторный алгоритм, пере-

из приказов вида (4) и приказов

В. самом деле, согласно теореме 2 существует алгоритм, перерабатывающий 2" в 2/(=) и имеющий программу

состоящую пз приказов вида (4). Тогда цепочка приказов О:

будет перерабатывать х в f (х).

Понятие операторного алгоритма легко обобщить. Напрпмер, можно рассматривать приказы впда

означающие, что, исходя из заданного числа х, следует найти W (х) и затем перейти к выполнению над числом W (х) приказа с номером ф {х), если w {х) определено, и перейти к выполнению над х приказа с номером ф (х), если W (х) не определено. Однако при всех этих обобщениях легко доказывается, что класс вычислимых функций остается совпадающим с классом частично рекурсивных функций.

Весьма интересный класс алгоритмов, перерабатывающих графы, был определен и исследован Колмогоровым и Успенским [1]. Как пишут авторы, эти алгоритмы были получены при попытке воспроизвести в абстрактном определении наибольшее число черт, присущих работе вычислителя, действующего согласно заданной ему программе. Класс функций, вычислимых при помощи алгоритмов Колмогорова - Успенского, оказался снова совпадающим с классом всех частично рекурсивных функций.

Дополнения и примеры

1. В п. 14.2 отмечено, что каждая словарная частично рекурсивная функция F (х), заданная в алфавите А, вычислима при помощи нормального алгоритма в подходящем расширении алфавита А. Показать, что F (х) вычислима посредством нормального алгоритма уже в алфавите {qq, А}, отличающемся от А лишь одной донолнительной буквой а, 4 (М а р к о в [2], Нагорный [1]).

2. Невозможно задать нормальный алгоритм в алфавите А, который перерабатывает произвольное слово х в алфавите А в его удвоение х)С (Нагорный [1]).

3. Какие функции вычислимы онераторныъш алгоритмами, программы которых содержат лишь приказы вида

и стои-приказ?

4. Согласно теореме 2 из и. 14.2 для каждой частично рекурсивной функции / (i) с\тцествует операторный алгоритм, перерабатывающий 2- в 2 причем ирогражш этого алгоритма состоит лпшь из приказов указанного в теореме частного впда. Показать, что нп один алгоритм этого тппа не может перерабатывать х в (Барздинь [1]).

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

где д (х) - X - [l/iP, и стоп-приказа.

Рпс. 3

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

15.1. Общие йшоголенточные машпны. /г-ленточная машина Тьюринга состоит из механического устройства (автомата) 4п А; лент, разбитых на ячейки (рис. 3). Каждая ячейка может находиться в одном нз фиксированного конечного множества состояний. Эти возможные состояния условимся обозначать символами ао, а, . . ., а„„ совокупность которых будем называть внешним алфавитом машины. Клетки в состоянии ао, как п ранее, будут называться пустыми. По предположению, автомат А в каждый момент времени находится в одном из конечного множества состояний до, gi, . . ., gn- Состояния gi, go называются соответственно начальным и заключительным. Машина работает в дискретном врел1ени, так что можно говорить о «состоянпи машпны», «состоянии автомата», «состояниях ячеек лент» в момент t = О, в момент f = 1 п т. д. Предполагается, что в каждый момент времени машпна «обозревает» одну ячейку каждой ленты. По оире-

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

ащ . . . aiiUi

4l:v

- i;o одному слову для каждой ленты.

В зависимости от внутреннего состояния д автомата А II состояний а;, . . ., аг,.„ обозреваемых в данный момент ячеек машина £ переходит в следующую конфигурацию посредством таких действий: а) заменяет состояние каждой воспринимаемой ячейки новым состоянием (которое может совпадать и со старым); б) каждую ленту передвигает на одну ячейку влево, вправо или оставляет неподвижной; в) переводит внутреннее состояние д автомата Л в новое состояние qj. Считается, что если автомат А в какой-то момент времени приходит в заключительное состояние до, то машина Z останавливается и в последующие моменты времени конфигурация машины не меняется.

Говорят, что машина £ выполняет (или может выполнять) команду

qiucc-l- .>а. -ngj-e.v. • • -ЧкУк (Уь • • •. Tfr = - 1. 0. 1).

1(2)

еслп, находясь во внутреннем состоянии д и воспринимая ячейки в состояниях ад,, . . ., Оа, машина £ заменяет qi на qj и указанные состояния состояниями ар ,. . ., ар., после чего сдвигает лентысоответственно в направлениях Ту, . . ., Ту Ту, То означают соответственно сдвиг

на одну ячейку влево, вправо и оставление лен неподвижной). Как и в случае одноленточных машин, предполагается, что в необходимых сл5чаях машина может перед сдвигами надстраивать ленты пустыми ячейками.

Задать программу машпны £ - это значит для каждого слова

qia.

Оа,. (j = 1,

п; tti.

«А- = О, 1,

задать какую-нибудь команду вида (2).

§ 15. Многоленточные машины и ТАГ-системы

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

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

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

Ясно, что, зная программу машины £, мы можем путем серии указанных операций для любой конфигурации (1) машины в заданный момент времени вычислить ее конфигурацию В любой из носледу10П];их моментов времени. Иначе говоря, каждая А;-ленточная машина Тьюринга . определяет алгоритм для переработки систем машинных слов вида (1).

Пусть / {х-х, . . ., Xs) какая-нибудь частичная функция от S неременных. Говорят, что / нормально вычислима на {s -f- А-)-ленточной машине Тьюринга £ с внешним алфавитом {О, 1, «2, . . ., а}, если для любых натуральных щ, . . ., Hs машина £, начав работать в конфигурации

ЮЛхО, . . ., 10"=~giO, gil, . . ., gl (Юда = gla), по истечении конечного времени перейдет в конфигурацию

Ю*".....доО ... О, до 10 ... О, . . ., доЮ ... О

при условии, что / {п-х, . . ., Us) определено, и будет работать вечно, т. е. не переходя во внутреннее состояние до, в противном случае. При этом, как и в случае однолен-точных машин, можно предполагать, что в продолжение всей работы машина не надстраивает ячеек слева ни на одной ленте.

Теорема 1. Для того чтобы частичная функция / (х-х, . . ., Xs) была вычислима на (s -f- к)-ленточной машине Тьюринга с внешним алфавитом {О, 1, а, . . ., {т - любое натуральное число), необходилю и достаточно, чтобы / была частично рекурсивной.

Мы не будем излагать подробное доказательство этой теоремы. Заметим лишь, что вычислимость частично рекурсивных функций на {s -г А)-ленточной машине есть прямое следствие вычпслимости этих функций на однолен-точной машине, а обратное утверждение есть непосредственное следствие теоремы о частичной рекурспвностп функций, вычислимых при п0м01цп нормальных алгоритмов (п. 14.2).

15.2. Машпны Минского. Способность менять состояния ячеек ленты - существенная черта машин Тьюринга. Однако для многоленточных машин эта способность перестает быть необходимой. А именно, Л е м б е к [Ц показал, что каждая частично рекурсивная функция вычис лшма на машине с достаточным чистом лент так, что машина не меняет состояния ячеек лент и не надстраивает левых ячеек. Почтп одновременно Минский [1] но-

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

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

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

g-ai ... Us -> QaTa • Та.

(i = 1, . . ., re; ая, = О, 1; a = О, 1, . . ., п; «х == О, 1, -1),

которые способна выполнять данная машина. Так как 1 есть состояние самой левой ячейки, то в командах (1) пз «г, = 1 должно следовать неравенство

Этим условием и ограничивается произвол в задании команд (1).

Теорема 1. Для каждой частично рекурсивной функции / (х) существует трехленточная машина Минского, вычисляющая эту функцию, т. е. переходящая us конфигурации 10-~giO, gil, gjl в конфигурацию IQ/M-i goO, gol, gol, если / {x) определено, и работающая вечно, если f (х) не определено.

Условимся изображать четверкой чпсел {а, Ъ, с; i) ту конфигурацию трехленточной машины Минского, которая характеризуется машинными словами 10"g;0, lOgjO, lOgjO. Напомним, что lOgO есть слово glO. Таким образом, числа а,Ъ,с равняются просто д.чинам концов лент, находящихся слева от воспрпнпмае.мых машиной ячеек, а i - номер (или символ) внутреннего состояния машпны.

Согласно теореме 2 из п. 14.3 стцествует операторный алгоритл! А, перерабатывающий 2" в 2(-") и имеющий

1 А. И. 1\Гальпев