2) Проблема конфигураций. Дана машина Минского М. Указать алгоритм, позволяющий узнать для любой заданной конфигурации {х, 0; д), существует ли начальная конфигурация {а, 0; i), которая через конечное число тактов работы переходит в конфигурацию (х, 0; до)-

Обе проблемы решаются отрицательно. В самом деле, пусть / (х) - частично рекурсивная функция, область определения которой не рекурсивна. Строи.м двухленточную машину Минского М, перерабатывающую 2 в 2/С) . Если бы существовал алгоритм, решающий проблему остановки машины М, то этот алгоритм решал бы и проблему вхождения числа х в область определения функции / (х), так как х входит в область определения / тогда и только тогда, когда машина М, начиная работать в конфигурации (2, 0; gi), останавливается через конечнор число тактов работы.

Аналогично, пусть / {х) - примитивно рекурсивная функция, совокупность значений которой не рекурсивна. Строим двухленточную машину Минского М, перерабатывающую 2 в 2<-". Как и выше, легко убеждаемся, что для М не разрешима проб.яема конфигураций.

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

(с = 2, 3, 5).

В свою очередь, с помощью теоремы 2 можно еще сократить этот список приказов, правда, сложнпв кодирование. Покажем, что имеет место

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

Пусть М - двухленточная машина Мпнского с внут-реннпми состоянпямп до, Qi, g„, переходящая пз кон-фпгурацпп (2-, 0; д{) в конфпгзфацпю (2М, 0; до), еслп f {х) определено, п работающая вечно в противном случае.

Машина М может двигать одновременно или обе ленты, ИЛИ только одну. Покажем сначала, что М можно заменить такой машиной М, которая ири каждом такте работы непременно либо двигает обе ленты на 1 шаг вправо, либо двигает только одну ленту (l-io или 2-ю) на 1 шаг влево. Действительно, пусть (1) - программа машины М. Если эта программа содержит приказ

giOOgaTJ-x, (19)

то вводим дополнительные внутренние состояния д, дц и вместо приказа (19) пишем приказы

qtOOqiJiTx, gnabgiJoT-i{a,b = Q,i), (20)

giab-> даТ(,Т-х.

Аналогично ностунаем и с другими приказами из программы (1). Ясно, что новая машина М с внутренними состояниями gi, дц и приказами вида (20) будет по-прежнему из конфигурации (2-, 0; д,) переходить в конфигурацию (2(>, 0; до) и в то же время будет сдвигать ленты в соответствии с наложенными требованиями. Обозначим внутренние состояния машины М через до, gi, . . ., gn, g„+i, . . ., д,. Программа машины М - это совокупность команд вида

gtQQgRy.i (yi = О, -1, 1),

дгЮ -> giRii,

QiOi gviMi ii = О, 1; i = i, . . ., s), (21)

gtli-gciRvi,

где R-i означает сдвиг обеих лент вправо, R - сдвиг влево 1-й ленты, Ri - сдвиг влево 2-й ленты.

Условимся конфигурацию (о, Ь; gi) изображать парой {2-Ъ, gi). Тогда сдвпг обеих лент вправо будет в.чечь деление первого числа пары на б, а сдвпг одной пз лент влево будет влечь умножение этого числа на 2 п.чи 3. Исходя из программы (21), легко сразу написать и программу операторного алгорпт.л1а А, который число 2-3 и указание i перерабатывает в число 2-3 и указание /, если машина М из конфигурации (2-3, gi) переходит неносредственно в конфигурацию {2-Ъ, д). Для этого часть приказов алгоритма А защмеруем числами О, 1, . . ., s, а часть - парами чпсел г/ и далее поступп-м следующим способом. Берем для какого-нибудь i четверку команд (21)

из программы машины М и пусть Xj = -1. Чтобы из числа 2-3 с помощью команд (21) получить число 2=-3, надо узнать, нет ли среди чисел а, Ъ нулей. Для этого делим 2-3 на 6. Если делится без остатка, то согласно первой команде четверки (21) частное и будет требуемым числом. Если 2-3 на 6 не делится, то среди чисел а, Ъ есть равное О и потому надо воспользоваться одной из последующих команд систеьш (21). Итак, в программу алгоритма А вносим приказ

05,-

(22)

который дает требуемую пару {2-Ъ, q.), если 2-3 делится на 6, и отсылает к приказу i. О, если 2"-3 на 6 не делится. Если в последнем случае число 2-3-3 делится на 6, то а О, 6 = О и мы должны воспользоваться второй из команд (21). В соответствии с этим в программу А вносим приказы

i.O:

i.2: X 2

i.l:

i.3:

(po = 2, pi = 3),

(23)

дающие искомую пару (2=-3, др.), если а > О, и дающие пару (2".3+1, i.4) в противном случае. Приказы

i.4:

(24)

переводят пару (2«.ЗЬ+1, i.4) в пару (2"•3 i.6), где а = - 0. Если Ь > О, то должны воспользоваться 3-й из команд (21) и нотому в программу А добавляем приказы

i.G:

i.8:

1.1:

i.9:

i.lO

(25)

приводящие при &> Окпаре (2=-3*, q) и прп 6 = 0 к паре (2°+1, i.lO). Наконец, приказы

i.lO:

(26)

и для случая a = Ъ = Q дадут требуемую пару (2=-3, q).

Аналогичным путем пишутся приказы (22) - (26) и для = О, 1. Объединяя приказы, построенные указанньш образом для г = 1, 2, . . ., S, и присоединяя к ним начальный стон-приказ, ползучим программу операторного алгоритма А, имеющую требуемый теоремой 3 вид. По условию машина М из конфигурации (2=, 0; qi) преобразуется в конфигурацию (2(=, 0; q) или в новом кодировании из конфигурации (2, q преобразуется в конфигурацию (2*\ до)- Отсюда следует, что алгоритм А с программой, построенной по правилам (22) - (26), перерабатывает число 2" в число 22\

15.3. Однородные продукции. ТАГ-системы. В п. 14.1 было введено понятие системы продукций, определяемой алфавитом С = = {ci, cj, . . ., cri) и системой базисных продукций

diW Шг (i = 1, . . ., s). (Р)

Чтобы при помощи этой системы Р определить понятие Р-вы-числимых частичных числовых функций, надо каким-то образом кодировать числа в алфавите С. Мы примем такое соглащение. Пусть алфавит С системы Р содержит символы а, ai, Ло, Ау, Во, By и произвольное число других символов. Фиксируем, кроме того, еще произвольное натуральное положительное число w и будем произвольное натуральное число х кодировать словом АуССВу. Будем говорить, что частичная числовая функция / (ж) вычисляется системой продукций Р, если система Р перерабатывает слово AyuBy в слово Ада1Вд~ для тех х, для которых / (ж) определено, и система Р без конца преобразует слово АуаВ~ для тех х, для которых / (х) не определено.

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

По определению, однородная система продукций (плп ТАГ-си-сте.ча) Т задается своим алфавитом С = {оу, а, . , а), положительным натуральным числом w, называющимся шагом систешл, и особыш! элементарнБвга преобразованпями

где bi, . . ., Ъ,п - какпе-нпбудь слова в алфавите С.

Т-продукцией над какпм-нпбудь словом Х, записанным в алфавите С, называется следзчощий процесс: в последовательности (Т) ищем слово Ь;, отвечающее начальной букве uj слова х- Затем отбрасываем в х первые w букв и к остатку справа приписываем слово 6;. Если длина слова): меньще w, то Г-продукцпя называется невыполнимой над X или непримени.чой к у.

Однородные системы продукций можно рассматривать как обычные системы продукций впда (Р), подчиненные требованиям:

1) все начальные слова й,, . . ., us системы (Р) имеют одну и ту же длину w;

2) слова бц . . ., bs в продукциях (Р) зависят лишь от начальных букв слов Й1, . . ., us,

3) среди слов Й1, . . ., Os системы (Р) содержится любое слово длины S над заданным алфавитом.

Чтобы однородную систему продукций, заданную шагом w и. элемептарньвга преобразоваииянш (Т), записать в виде системы (Р) обычных продукций, достаточно каждое преобразование Oj hi в цепочке (Т) заменить последовательностью всевоз5юлшых продукций впда uiWWbi, где а - произвольное слово длины w - 1 в заданном алфавите.

В однородной системе продукций с шагом w слова, к которым продукции не применимы, имеют длину, меньшую w. Чтобы избавиться от этого недостатка, введем eni;e понятие однородной системы продукций с заключительной буквой.

Система продукций в алфавите {oq, о,, . . ., а} называется однородной системой продукций шага w с заключительной буквой Ор, если совокупность ее продукций можно представить в виде

Ьг.....«т-

(То)

(буква слева не встречается), где 6, . . ., Ь„, - непустые слова в алфавите Oq, а,, . . ., o„j.

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

Теорема 1 (Минский [1]). Для каждой частично рекурсивной функции f (,т) существует однороднаясистема продукций с заключительной буквой Ад и шагом w, для каждого х перерабатывающая слово А-аВ в слово Л QCoв~ при / (.г) определенном и работающая вечно при f [х] неопределенном.

Для каждой ограниченной частично рекурсивной функции f (х) существует однородная система продукций {без заключительной

буквы) шага w > 2 перерабатывающая слово AiaB~ в слово

4

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

где имеет одно из значений >< 2, X 3. X 5, :30. Чпсло w = 30 примем в качестве шага искомой системы npofljKnnu. Алфавит этой системы будет состоять из основных отав 4о, а, А,, а,. . . ., As. Oj, попарно отвечающих приказам (1), и ряда дртгпх 65-кв bj, bi„, Bi, Bij, Ci (i, / = 0, 1, . . .).

Процесс переработки заданного числа 2- посредством алгоритма (1) распадается на шаги так, что после какого-то к-то шага получается чпсло Z (променчуточный результат) и номер i приказа, который должен быть выполнен над числом s прп след}тоще.ч шаге

вычислений. Если i=0, то процесс вычислений обрывается и z-результат переработки 2 посредством алгоритма (1). С парой чисел (z, i) сопоставим слово 4ia?S"" и постараемся построить систему продукций Т так, чтобы эта система преобразовывала слово AiaBf в слово AjajBP-, если алгоритм (1) преобразует пару (z, i) в пару

Для каждого i (1 < i < s) может быть 2 случая: t,i= х с, t,i = : W. Рассмотрим пх отдельно.

1-й случай: i:

Пишем следующие однородные продукции:

Ai Bit, . . . Siit-i, ai bf, Bi- bf,

BioCfA, b,-.al, C,-.Bl-\

br(«-i)cf(r = l,..., Ш-1). (2)

Посмотрим, BO что переведут этп продукции слово Aia\B-. Представляя z в впде z = to -f г, О < г < ш, и предполагая, что 1г ф О, пз (2) непосредственно получаем

H«r5rBio...Bi.-ir""V

Легко убеждаемся, что пол5гченное соотношение

верно и для случая 1г = 0.

2-й случай: i:

Пишем продукции

Ai-Big. . . Bi,. j, fli

. CrA„aL

"а-

(г=1,...,ш-1).

BiCf, В.,

Для того чтобы найтп, во что этп продукцпп npeo6pa3540T слово yliOBf", представим г снова в форме г = to- -Ь г (О < г < w). Согласно (3)