Теорема 2. Проблема вхождения для множества слов f& разрешима на машинах Тьюринга тогда и только тогда, когда Ъ рекурсивно.

В самом деле, пусть существует машина £ со свойствами а), б). Обозначим через F (р) словарную функцию, вычисляемую машиной Z (в смысле и. 12.2). Обозначим через ЭЗо совокупность всевозможных слов в алфавите В. Согласно а), б) функция F (р) всюду определена на и S5 есть совокупность решений уравнения F {х) = \, лел<ащих в S5o. Следовательно, множество ЭЗ рекурсивно.

Обратно, пусть совокупность S5 рекурсивна. Определяем на So функцию / (5), полагая ее равной 1 на 35 и Л вне Ъ. Так как эта функция рекурсивна, то найдется машина Тьюринга £, правильно вычисляющая функцию / (j), а это и значит, что £ удовлетворяет требованиям

j... Пусть Ш - произвольная машина Тьюринга. Говорят, что проблема остановки машины Ш разрешима на машинах Тьюринга, если на машинах Тьюринга разрешима проблема вхождения для множества Шп, т. е. если множество ?й?пп рекурсивно. Так как ш-универсальные множества нерекурсивны, то из приведенных определений следует, что проблема остановки универсальной машины Тьюринга неразрешима на машинах Тьюринга.

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

1. Доказать теорему 2 пз п. 12.3 о синтезе машин Тьюринга для произвольного внешнего алфавита.

2. Определенные в п. 12.1 машины Тьюринга могут сдвигать ленту на 1 шаг влево пли вправо, оставляя содержимое ячеек не-изменныш, пли 1шгут изменять состояние восприппмаелюп ячейки, оставляя ленту неподвижной. Можно расширить этот список операций. Л1ашина Тьюринга называется стандартной, еслп она п ири сдвиге лепты может предварительно изменить состояние воспрпии.маемой ячейкп. Программа стандартной машины может быть записана в виде совокупности предписаний вида qa\

qijT, где формула дЧ - а1-Т , папример, означает, что машина, находясь во внутреннем состоянии н воспринимая символ Hj, заменяет этот символ символом я;, переходит во внутреннее состояние q и сдвигает ленту на 1 шаг влево (если Т, то сдвигает вправо, еслп То, то оставляет неподвижной). Так как уже на машинах, определенных в п. 12.1, все частично рекурсивные функции вычислимы, то онп будут вычислимыми и на стандартных. Показать, что псе функции, вычислили на стандартных машинах, частично рекурсивны.

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

(а = О, 1; е = О, ±1),

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

5. Пусть задана машина Тьюринга % с внешним алфавитом «о, а-х, . . ., йдаИ внутренними состояниями q, q, . . ., q. Системой кодов условимся называть пару словарных функций cod [f, J)), dec [f, о), удовлетворяющих следующим условиям: а) обе функции общерекурсивны и определенны в объединенном алфавите {«о, . . . • • м а"; Зо, • • Чп}\ б) если t) - слово в алфавите {яр, • • ., ащ), то cod [х, X)) - некоторое машинное слово, если же о - заключительное машинное слово, то dec (х, \)} - слово в алфавите {а, . . ., От). Говорят, что машина £ вычисляет частичную словар-пую функцию / {х), заданную в алфавите {cj, . . ., а„} при коде с индексом П, если машина, начав работать в конфигурации cod (п, X), или остановится в конфигурации J, для которой dec (п, J) = / (х), либо будет работать вечно, еслп / (х) не определено.

Машина Z называется строго универсальной, если для нее существует такая система cod {х, i)), dec {х, ))), что каждая частично рекурсивная числовая функция / (г) вычислима на 2! при коде с подходящим индексом.

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

6. Каждая машина Тьюринга имеющая лишь одно внутрен-пее состояние, отличное от заключительного, имеет рекурсивное .гнoжecтвo Sifin и потому не может быть универсальной (Ш е н-U о н [1]).

7. Используя простое множество, иостроенное в и. 8.3, показать, что из нерекурспвностп множества следзет универсальность машины Z-

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

9. Обычно прпнтшется (см. Шеннон [1]), что «сложность» машины Тьюринга равна произведению чпсла символов ее внешнего алфавита на чпсло вщ-тренних состоянпй, отличных от заключительного. Значительный интерес вызвала задача построения унь нереальных машин 1шшгмальноп сложности. К началу 1963 г. по. следниъш результата™ в этом направленпи была теорема Вата,

предписания вида

аЧ ais ai ?p"io, ai 9aзf = ±1).

4. Стандартная машина Тьюринга с внешним алфавитом 0,1 пазывается нестирающей, если она способна выполнять лпшь пред-ипсания вида

н а б е [1] о существовании универсальной машины с пятью снмволалш и шестью состояния5ш и теорема Трпттера [1]о существовании универсальной машпны с четырьмя спмволаьш и 1иестью состояниями (отличными от заключительного).

10. Пусть / {ху, . . ., Xs) - общерекурсивная функция и 2 - машина Тьюринга с внешним алфавитом {О, 1, а} и внутренние со-(;тояипя1ш qQ, qy, . . ., g„, а - символ пустой ячейки, - заключительное состояние. Условимся говорить, что машина S! вычис-ляэт функцию /, если для любых натуральных Ху, . . ., xs

qa {xila . . . a{.r.,}„ - . . . ga {/ (xy, . . Xs)} . . . a,

где {.TJj - двоичная запись числа x. Мы предполагаем, что машина может в процессе вычислении надстраивать пустые ячейки, но предполагаем также, что машина не может отбрасывать никаких ячеек. Поэтому длина машинных слов в процессе вычислений не убывает и заключительные слова - это слова макстшльной длины. Пусть If {ху, . . ., Xs) - длина заключительного слова, получившегося прп вычислении значения / {х, . . ., Xs) на машине К, jTnenbnieHHaH на 1. Это длипа ленты, необходимой машине Z для вычисления / (,г, . . ., г).

Как измерять «сложность» вычислимой функции? Один из возможных ответов па этот вопрос указан Р и ч и [1]. Рекурсивные функции разбиваются на классы Fg а FyCl ... по мере возрастания их слонностп следующим образом. В класс Fq относим все линейные функцип. Далее для каждого I в класс Fi.i относим те функцип / (ху, . . ., Xs), для которых существует вычисляющая их машина Тьюринга Z такая, что If 6 Fi. В статье Ричи показано, что объединение всех классов Fi в -точности совпадает с классом функций, элементарных в смысле Кальмара - Чиллага (Кальмар [1]) (см. задачи 4, 5 из § 6). Пусть (г) = 2, {х) = (i)); (х)). Тогда л\>1 Ё Fi, ii Fi п потому классы Fi различны.

Аналогичная пдея для разбиения функций в классы по степеням сложности была развита также К л и в о м [2].

§ 13. Приложения

Изложенная выше теория машин Тьюринга позволяет просто решить ряд алгоритлшческих проблем алгебры, логики, арифметики н других областей математики. Некоторые из этих проблем в качестве иллюстрации будут рассмотрены в данном параграфе. Приложения к теории чисел будут изложены в § 16.

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

Совокупность элементов, рассматриваемая вместе с некоторой определенной на ней бинарной ассоциативной операцией, называется ассоциативной системой или полу-

группой. Например, полугруппой является совокупность всех натуральных чисел вместе с операцией сложения или вместе с операцией умножения.

Основную операцию в произвольной полугруппе обычно называют умножением и обозначают точкой. Вместо а-Ь обычно пишут аЬ. Так как распределение скобок в произведениях нескольких сомножителей: {{аЬ) с) d, а (Ь (cd)) на величину этих произведений в полугруппах не влияет, то при записи таких произведений скобки опускают.

Согласно п. 1.3 система элементов с, . . ., с.р некоторой полугруппы К называется системой порождающих для ©, если каждый элемент с полугруппы (£ может быть представлен в форме

с = Cic,. . .Ci (tft = 1, 2, . . ., р),

где множители могут и повторяться. Например, числа вида 2"* образуют полугруппу относительно умножения с одним порождаюпщм элементом 2.

В качестве другого примера рассмотрим совокупность всех непустых слов какого-нибудь алфавита С = {с, . . . . . ., Ср}. Эта совокупность является полугруппой относительно обычной операции умножения слов: а-Ь = аЬ. Однобуквенные слова . . ., с, очевидно, будут иорож-даюпщми для этой полугруппы, называющейся свободной полугруппой с свободными порождающими с, . . ., Ср.

В алгебре важное место занимает способ задания полугрупп посредством определяющих соотношений. Сущность его состоит в следующем.

Задаем некоторый алфавпт С = [с, . . ., Ср) и конечную совокупность формальных равенств вида

Ci = bi, Сг = Ьз, .. ., Сг = bi.

где = - особый знак, а q, bi, . . ., Q, bi - произвольные слова в алфавите {су, . . ., Ср). В течение некоторого времени словадш далее будем называть лпшь слова в а.л-фавите {су, . . ., Ср} и делать специальные оговорки в противном случае.

Левым элежнтарны.ч преобразованием некоторого слова с, отвечающим соотношению с, = Ь,, будем называть подстановку в слово с слова Ь; вместо какого-нпбудь вхождения слова С;. Аналогично, правым элементарным преобразованием, отвечающим соотношению с- = Ь-, пазы-

вается подстановка в слово с слова с, вместо какого-нибудь вхождения слова Ь; в с.

Если слово с содержит несколько вхождений слова С;, то над с можно выполнить по произволу одно из нескольких левых элементарных преобразований, отвечающих соотношению С; = Ь,-. Если с,- не входит в с, то над с соответствующие левые элементарные преобразования не выполнимы.

Левые и правые элементарные преобразования, отве-чаюпще определяющим равенствам (1), называются просто элементарными преобразованиями. Условимся писать с Ь, если слово b получается каким-либо элементарным преобразованием из с, и условимся писать с = Ь, если существуют такие слова fi, . . ., то

с-?1-> . . .->?г->Ь, (2)

или если с = Ь.

Новое определение отношения = не противоречит определяющим соотношениям (1), так как в силу (1) Cj

-V £); и потому С; == Ь;.

Из приведенных онределений неносредственно видно, что отношение = рефлексивно, транзитивно, симметрично и согласовано с операцией умножения, то есть

f = f 1 & t) = Di =Ф JJ) = (3)

Отношение = будем.для краткости называть эквивалентностью. Совокупность всех слов, эквивалентных данному слову с, обозначим через [с] и назовем смежным классом но модулю =. Ввпду изложенного соотношение v s j) равносильно «точному» равенству [f] = [j)].

Вводпм теперь операцию умножения смежных классов, полагая по определению

[?]•[•)]-[?»)]. (4)

В силу (3) так определенная операция умножения является однозначной на совокупности всех смежных классов. Поскольку для произвольных слов л, Ь, С па (4) следует

([a][b])[c] = [alj.c] = [a]([b][c]),

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

Для любого слова с = Cifi . . . ci из (4) следует [с] = . . . Ci ] = [cij. . . [ci ].

Поэтому элементы [с], . . ., [ср\ образуют порождающую систему для полугруппы и полугруппа ©ц) обычно называется полугруппой, заданной порождающими с, . . . . . ., CpU определяющими соопгношениями (1). Полугруппы, задаваемые этим путем, называются конечно определенными полугруппами пли ассоциативными исчислениями.

Говорят, что слово с представляет элемент [с] полугруппы ©(1). Так как основной способ задать элемент полугруппы - это задать его представителя, то естественно возникает следующая основная

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

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

Небольшое изучение вопроса приводит к выводу, что, во всяком случае, справедлива

Теорема 1.5 каждом ассоциативном исчислении совокупность пар эквивалентных слов рекурсивно перечислима.

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

Из теоремы 1 непосредственно следует, что в каждом ассоциативном исчисленип каждый смежный класс рекурсивно перечислим. Спрашивается, а не будут лп все смеж-

9 А. и. Мялъпе»