Дальнейший ход преобразований зависит от делимости z на ш. Пусть Z делится на w и, следовательно, г = 0. В этом случае согласно (4) имеем далее

Если же г > О, то (5) продолжается следзаош;им образом:

Итак, еслп алгоритм (1) преобразует иару (г, i) в пару (и, /), то продукции (2) - (4) прообразуют слово AiafSV- в слово AjajBj. Наконец, для i = О добавляем продукцию

Во Д ао (6)

и называем букву Ло заключительной.

Обозначим через 2" однороднзчо систему продукций с заключительной буквой 0, построенную для програшш (1) в соответствии с правилами (2)-(4), (6). Пусть х - произвольное число. Берем слово AialB~. Выполняя над ним продукции Т, мы будем сначала получать слова, начинающиеся одной из вспомогательных букв Bi, Bij, Ci, bi, biQ. Первое слово, начинающееся одной из букв 0, Ау, . . ., As, будет AialB", где число z п номер i суть результаты выполнения приказа с номером 1 над числом 2-. Выполняя над словом 4ioS]°"i продукции Т, снова получим сначала слова, начинающиеся вспоьюгательными букваьш, а за ни1ш получится слово AjaV-Bj~, где пара {и, /) является результатом выполнения приказа с номером i над числом z пт. д. Если / (ж) не определенно, то процесс будет длиться без конца. Если же f (х) определенно, то

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

Для доказательства второго утверждения воспользуемся замечанием, сделанным в п. 14.3 по поводу теоремы 2, согласно которому в формулировке этой теоремы число 5 можно заменить любым числом р > 1, не деляпщмся пп на 2, нп на 3.

Пусть / (.г) - частично рекурсивная ф-нкцпя, значения которой не превосходят некоторого числа I. Тогда значения 2= будут меньше чпсла р = б, не делящегося ш1 на 2, нп на 3. Согласно упомянутому замечанию найдется операторный алгоритм, перера-батыБающий 2* в 2\ программа которого содержит лишь прп-казывида Si «г Pi , где принимает значения х2, X 3, х р,: 2-3-

•р. Вьппе показано, каким образом можно построить однородщто систему прод5т;цпп Т с заключительной буквой Ад, имеющлто шаг

Ш = 6/) и перерабатывающую слово jQS"! в слово Адав~-

Присоединяя к продукциям (2)-(4), (6) системы Т еще продукцию обратим Т в однородную систему продукций без заключительного

„X W-1 j,2l(=)r,W-l

.цемента, которая преобразует слово yljoj iJi всловоЛоЛц В . ] [о теперь последнее слово не является заключительным и согласно (7), (6) далее имеем

Aoaf-Bf%--.al

Поскольку длина слова о меньше шага продукций w, то оно теперь и будет результатом переработки начального слова.

С каждой системой продукций Т (не обязательно однородной) Пост связал следуюпще две основные алгоритмггаеские проблемы.

1) Проблема остановки. Рекурсивна или нет совокупность <В всех тех слов, начиная с которых процесс Т-продукций обрывается через конечное число ш,агов1

2) Проблема выводимости. Для каждого ли слова % является рекурсивной совокупность ©,j[ всех тех слов, которые можно получить из % конечным числом Т-продукций"}

Пост показал, что существуют такие системы продукций, для которых обе проблемы имеют отрицательное решение (см. п. 13.1) . Однако вопрос о том, существуют ли однородные системы продукций с отрицательно решаемой проблемой остановки, он оставил открытым {ТАГ-проблема). Решение этой более специальной проблемы непосредственно следует из предшествующих результатов.

Теорема 2 (Пост - Минский). Существует такая система Т однородных продукций, для которых совокупность @ тех слов, начиная с которых процесс Т-продукций обрывается, является нерекурсивным множеством.

Рассмотрим какое-ш1будь рекурсивно перечпслимое нерекурсивное множество натуральных чисел S и обозначим через / (ж) функцию, равную О в точках S и не определенную вне S. П>ункция / (ж) частично рекурсивна. Согласно теореме 1 найдется

однородная система продукции Т, перерабатывающая Ayaf В в Яо, если ж 6 S, и дающая бесконечный процесс в случае ж $ 5. Обозначим через SO? совокупность всех слов вида Ауо В~

и через Ж/ coBOKjTiHOCTb слов вида Ауа В, где г; 6 S. Согласно и. 11.1 совокупность 93? рекурсивна, а совокупность Ш?/ (вместе с множеством S) нерекурспвна. Но Щ = © П SK, поэтому и совокупность нерекурсивна.

Теорема 3. Существует такая cucme.ua однородныхпродукций Т и такое с.юво S(, что совокупность всех слов ©щ, по.гу-чае.иых из 91 конечным числом Т-продукций, яв.г.яется нерекурсивной.

Пусть g (ж) - общерекурсивная ф-нкция, принимающая различные значения при различных значениях aprjenra и имеющая нерекурспвную совоктгность S значений. Вводим hobjto функцию / (ж), полагая

ns{n)) = g(n+i) (« = 0, 1, ...).

Областью определения функции f (х) служит множество S, а график ее состоит из пар <g (п), g {п + 1)> и потому он рекурсивно перечислим. Следовательно, функция / {х) частично рекурсивна. Рассмотрим программу (1) операторного алгоритма, вычисляющего функцию / {х). Пусть и - последовательность продукции, построенных, исходя из программы (1), с помощью правил (2)-(5). Вместо продукции (6) добавляем к U продукции, получающиеся согласно правилу (2) для приказа

Х1 1

Обозначим через V получившуюся таким путем расширенную систему продукций. Система V однородна. Берем слово ЛоВ-"". Из (2)-(5) и (8) получаем

AiafB-.

AiafB-.

.-.4<""BrV..., (9)

причем в последовательности (9) начинаются буквой лишь явно выписанные слова. Пусть а = lajB", - совокупность слов, ползгчаемых пз о конечным числом F-продукцпй (т. е. всех слов последовательности (9)), §( - совокупность слов впда Aio, B]""• и аз - совокупность слов вида Аа, В" (ц £ S). Так как совокупность S( рекурсивна, й нерекурспвна и й = §( П ©а т° ®а рекурсивна, что и требовалось.

Теоремы 2 и 3 доказаны наш для однородных продукций шага 30. Если воспользоваться теоремой 3 п. 15.2 и вместо програишы (1) рассматривать программы, составленные -лпшь из приказов впда

(10)

перерабатывающих 2" в 2 , то продукции, полученные изпро-граммвида (10) согласно правилам (2)-(5), (8), будут иметь шаг, равный 6. Все рассуждения, прпведшпе нас к теоремам 2 п 3, остаются в силе и для кодпрования 2- , 2-\ Таким образом, существуют системы однородных продукций шага, равного 6, удовлетворяющие условиям указанных теорем..

Ясно, что однородных систем продукции шага 1. для которых былп бы верны утвержденпя теорем 2 или 3, нет. Однако, Ван X а о [2], изменив систему кодированпя, построил такую однород-HJTO систему продукций, шаг KoTopoii равен 2 и для которой проблема остановки не разрешима. Более того, в системе Вана Хао Д.ЧПНЫ всех слов Ь,, . . ., Ьт в преобразоваш!Ях по превышают 3.

Дополнения, примеры п задачи

1. Частичная фзнкция / (ж) тогда и только тогда вычислима на двухленточной машине Мпнского в обычной кодировке, когда / х) вычислима прп помощи операторного алгоритма, програ»ша

и стоп-приказа (Барздинь [1]).

2. В а и X а о [1] рассматривает нестирающие машины Тьюринга, которые могут менять состояния пустых ячеек, но не могут изменять состояний непустых ячеек. Иначе говоря, машина Тьюринга с внешним алфавитом (О, 1} называется нестирающей, если она выполняет лишь команды вида

9,0 q.aT, g,l q.\T (а = О, 1; е = О, +1).

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

3. Если в однородно!! системе продукций шага w длины всех правых слов bi определяющих продукций не меньше w пли длина каждого из этих слов не больше ш, то проблемы остановки и выводимости решаются положительно.

4. Пусть однородная система продукций имеет шаг 1 и прп этом некоторые пз правых слов bi определяющих продукций могут быть пустыми. Тогда условия предыдущей задачи не выполняются. Тем не менее и в этом слухае проблема остаповкп решается поло-ло1тельно (Ван Хао [2]).

5. Рассмотрим следующие «упрощенные» приказы. Приказ

Х2 пусть означает: умножить данное чпсло на 2 и перейти к следующему по порядку приказу. Аналогично определим приказ Приказ

:6 а

пусть означает: разделить данное чпсло на 6 п перейти к выполнению приказа с номером а; еслп же данное число на 6 не делится, то nepciiTii к выполненпю над данным числом следующего по порядку приказа. Напрпмер, серия зрощеипых приказов

равносильна приказу Х2 а : умножпть данное чпсло на 2 п затем

иерейтп к выполнению приказа с номером а. Аналогично этому серия упрощенных приказов

равносильна приказу

. С помощью теоремы Зп. 15.2 пока-

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

которого состоит лпшь из приказов вида

программа этого алгоритма состоит лишь из стоп-приказа и упрощенных приказов вида

6. Алгоритм в предыдущей задаче перерабатывает числа. Нетрудно описать соответствующие операторные алгоритмы, перерабатывающие слова в надлежащем алфавите. Например, рассмотрим

алфавит, состоящий из цифр О, 1, 2, 3, 4, 5, 6. Обозначим через i

приказ: приписать к данному слову справа цифру i (О < i < 6) и затем перейти к выполнению над пол5енным словом следующего по порядку приказа. Через

обозначим приказ: в данном слове выбросить первую цифру, перейти далее к выполнению приказа с номером аь если отброшенная цифра есть i, и перейти к стон-приказу, если данное слово пусто. Например, серия приказов

перерабатывает любое слово апа . . . в алфавптеО, 1, 2, 3, 4, 5 в слово аобабягб . . . as6 п в указание выполнять приказ с номером а. Далее, условимся каждое натуральное чпсло >г > 1 кодировать словом agOi . . . flg, где

п = ао-Ьагб4-.. .-]-а,-б (0<aj<5; а>1), т. е. кодировать «обратной» июстсричной заппсыо га. Тогда приказ

: 6 а р будет равпосплен приказу

выполненному над «обратной» шестерпчной записью данного чпсла. На основе теоремы 3 п. 15.2 (см. пpeдыдцJo задачу) показать, что для каждой частично рекурсивной фзнкцпп / (х) стцествует операторный алгоритм А, перерабатывающий слова в алфавите О, 1, . . . . , 6, программа которого состоит пз приказов впда

и который обратную шестеричнто запись произвольного числа вида22 перерабатывает в обратную шестеричную запись числа 2" 7. Рассмотрим слова в двоичном алфавите О, 1. Приказ

(i = О, 1) пусть означает: приписать i справа к данному слову и перейти к следующему приказу. Приказ пусть означает: вы-

черкнуть первчо цифру и перейти к приказу с номером а;, если вычеркнутая цифра есть i (i = О, 1); если данное слово пустое, то остановиться Беря обратную шестеричную запись натурального числа и заменяя в ней цифры О, 1, . . ., 5 их двоичными разложениями, получим так называемую обратную двоично-шестеричную запись числа. Например, обратная двоично-шестеричная запись числа 2 есть 010011011. Показать, что для каждой частично рекурсивной функции / {х) существует алгоритм, перерабатывающий слова в алфавите (О, 1} с программой, состоящей лишь из приказов вида

который перерабатывает обратную двоично-шестеричную запись числа 2- в такую уке запись числа 2

8. Приказ

пусть означает: вычеркнуть первую букву,

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

(без стоп-приказа) и для

\ сс

лишь из приказов впда

которого совокупность слов, перерабатываемых в пустое слово, является креативной (Шепердсон и Стургпс [1]).

Именно этот результат используется для построения универсальной машпны Тьюринга с спмволалш ад, а, о,, а и внутренниьш состояниями дд, д, . . ., дд, пока «наименьшей» пз известных универсальных машин Тьюринга (Т р и т т е р [1]).

9. Каково лшнимальное значение га, для которого существует универсальная машпна Тьюринга с символами О, 1 и состояниялш дд, ду, . .., ?п? Каковы ьшшшальные л, для которых С5тцествует такая машпна Z, что нерекурсивно, креативно, просто, максимально?

10. Согласно Б ю х и [1] регулярной системой над алфавитом {су, . . ., Стп) называется система, определяемая указанным алфавитом и спстемой базисных преобразований впда

aiW~.biW {i=i,...,s).

где ui, bi - фикспрованные слова в ртомянутом алфавите.

Бюхи показал, что совокупность слов ЗГ тогда п только тогда порождается конечной спстемой слов прп помопщ преобразований вида (.А), когда М порождается конечной системой слов при