ные классы во все.\ ассоциативных исчислениях просто рекурсивными? Ясно, что если в каком-нибудь ассоциативном исчислении проблема тождества решается положительно, то все смежные классы в этом исчислении рекурсивны.

Пользуясь близостью элементарных преобразований слов в ассоциативных исчислениях к преобразованиям машинных слов в машинах Поста - Тьюринга, Пост [51 и М а р к о в [2] почти одновременно заметили, как можно построить ассоциативное исчисление, обладающее нерекурсивными смежными классами и потому имеющее неразрешимую проблему тоилдества. Мы сейчас изложим один из простейших способов построения ассоциативных исчислений, элементарные преобразования которых непосредственно имитируют преобразования машинных слов : в машинах Тьюринга.

- Пусть задана машина Тьюринга с символами ао, . . . . . ., йуп, состоянияАШ до, д, . . ., д и совокупностью S команд. Строим ассоциативное исчисление А (£) следующим образом. Алфавит А (£) состоит из символов Оо, а,. . . . . ., ап, до, Qi, • Чп и дополнительного символа v. Определяющие соотношения исчисления А (£) выписываются при помощи команд %. Ниже слева указаны команды из Z, а справа выписаны соответствующие формальные равенства, которые вносятся в список определяющих соотношений для 4 (£):

qafli gpaj дйг = драу, (5)

qao-i q(,L ai-qai = драа,- (/с = О, 1, . . ., m),

даЯ,- дрЛ 7аа; = Я:?,;- (7)

Добавляя к этим соотпошениям еще соотношение

aov = V, (8)

получим полный список определяющих соотношений исчисления А (£).

Теорема 2. Пусть машина Тьюринга % имеет символы «о, fli,. . ., UjnU состояния д, д, . . ., д, А {%) - построенное въиие ассоциативное исчисление с определяющими соотношениями (5)-(8), а, 6, с, & - произвольные слова в алфавите а, а, . . ., а, иг которых слово Ь либо пусто, либо оканчивается буквой, отличной от а. Для того чтобы в исчислении А {%) было истинно соотношение

необходимо и достаточно, чтобы машина Z из конфигурации agwO-ib через конечное число тактов работы и без надстраивания ячеек слева переходила в конфигурацию

Достаточность условий совершенно очевидна. Действительно, пусть

щагЬ -> mi ->... m, = сдоаЬСо

- последовательные конфигурации, принимаемые работающей машиной Z. По условию, конфигурация т+у возникает из конфигурации Ш/,- путем выполнения некоторой команды из совокупности %. Эта команда имеет один из видов (5) - (7). Рассмотрим самый сложный случай: пусть слово ха-ц переходит в слово m;,+i в результате выполнения команды вида (7), сопровождаемой надстраиванием ячейки справа. Это значит, что = лдаО-i, т+у = = aagpuo. В слове mv заменяем согласно (8) букву v словом av, затем, заменяя в слове \щаои согласно (7) подслово QaUi через Яг-др, получим слово nr+ii;, т. е. из Щ Ш+1 следует тг; = m+xV, что и требовалось.

Докажем теперь необходимость условий теоремы 2. Пусть

ЩгогЬи = ро -> Pi - . . . ~> Р; = cgoUpbv (9)

- слова, получаемые последовательно элементарными преобразованиями, отвечающими соотношениям (5) - (8). Не меняя начального и конечного слов цепочки (9), мы хотим ее преобразовать в такую цепочку, для которой доказываемое утверждение будет очевидным.

Из формы элементарных преобразований (5)-(8) следует, что в преобразуемом слове они не меняют ни числа вхождений буквы v, ни числа вхождений каждой буквы вида да- Поэтому каждое слово в цепочке (9) имеет вид

где 6ft - некоторые слова в а.лфавите «о, • • •, <hn-Пусть в двух последовательных преобразованиях р Pt+i -> Pa-+2 из (9) второе преобразование есть правое

У-преобразованпе v av. Тогда в более подробной записи

этот участок цепочки (9) имеет вид

dgabv -> й"дрЬ"г. -> a"gpb"aoi;

и потому вместо цепочки (9) можно рассматривать цепочку ... -> aqv -> dqabaov -> (Cqaov -> . .. (10)

Переход от цепочки (9) к цепочке (10) условимся называть СДВИГОМ правого и-преобразования f влево.

Аналогично, если в отрезке -ц fj+i ?;.+2 преобразование f f i.+x есть левое и-преобразовапие ~->

V, то этот отрезок имеет вид

aqabaoV-.aqav-.dqfyv и вместо цепочки (9) можно рассматривать цепочку

...~>aqabaov->a"qb"aoV~>a"qfib"v~>... (И)

Переход от (9) к (И) будем называть сдвигом левого у-пре-образования fj. f+i вправо.

Сдвигая в цепочке (9) все правые у-преобразования влево, а все левые -преобразования вправо достаточное число раз, получим цепочку вида

-> cqattpbalv ->...-> cqodphv,

где участок

адщЯгЬаоЬ -> t)i -> • •. -> t)s = (12)

преобразований вида (8) ун<е не содержит.

Последнее слово цепочки (12) содержит заключительный символ до, не входяш;ий в левые слова соотношений (5)-(7). Поэтому преобразование l)s-i l)s не может быть правьш. Допустим, что цепочка (12) содержит правые преобразования. Пусть J);,- - последнее правое

преобразование в ней, отвечаюш;ее соотношению {и) {и = = 5, 6, 7). Слово I);..!.! пусть содержит подслово gaflj. Преобразование р.+х j)v+2 по предположению левое. Но среди соотношений (5)-(7) есть лишь одно соотношение, левая часть которого есть gai- Следовательно, это соотношение должно совпадать с упомянутым соотношением {и). Таким образом, преобразованпя t);,+i и J)i+2

взагошо обратны, Г)у: = 1),+2 ы цепочку (12) можно сократить до цепочкп

t)o . . . -t)j- t)l+3

(13)

Продолжая этот процесс дальше, получпм цепочку вида (12), в которой все преобразованпя левые, отвечаюпще

I оитиошеипям (5)-(7). Но ведь эти соотношения были так подобраны, чтобы, выполняя левое преобразование, отвечающее одному из указанных соотношений, над какой-нибудь конфигурацией m машины S, мы получали конфигурацию го следующего состояния машины £. Следовательно, машина £, начав работать в конфигурации адшйгЬао, закончит работу в конфигурации cqoujal-Последняя буква слова & отлична от а. Поэтому машина £, начав работать в конфигурации agab, закончит работу в конфигурации вида СдоЯрЬяо, что и требовалось.

Теорема 3 (Пост, Марков). Существует ассоциативное исчисление с алгоритмически неразрешимой проблемой равенства.

В и. 6.3 построена частично рекурсивная функция Е {х), принимающая лишь значения О, 1 и не имеющая рекурсивных доопределений. Пусть Mi (i = О, 1) - совокупность решений уравнения Е (х) = г. В п. 6.3 показано, что множества 31 i рекурсивно перечислимы, но не рекурсивны. Обозначим через £ машину Тьюринга с символами О, 1 и подходящими состояниями до, д, . . ., д„, правильно вычисляющую функцию Е (х), т. е. переходящую из конфигурации giOl" в конфигурацию вида goOlO после конечного числа тактов работы без надстраивания ячеек слева. Согласно теореме 2 это означает, что в ассоциативной системе А (£) для любого натурального х qiPlv = goGiv-xeMi

xeMiqM=v(:[qoOVv] (i = 0, 1),

где [j] обозначает совокупность слов исчисления А (£), эквивалентных слову г. Алфавитный номер (п. 11.1) слова qiOVv будет некоторой общерекурсивной функцией ф (х). Обозначая через Pj (г = О, 1) совокупность алфавитных номеров слов из класса [gpOlV], получим

ze3/i?9(x)ePi {i = 0, 1). (14)

Мы видим, следовательно, что нерекурсивное множество -li"o «i-СБОДится к лшожеству Ро. Поэтому йшожество Рд не рекурсивно и в исчислении А (S) проблема эквивалентности произвольного слова слову gou алгоритмически неразрешима.

На самом деле соотношения (14) дают несколько больше, чем утверждает теорема 3. РГменно, соотношения (14)

означают, что пара множеств М, 311 m-сводится к паре! Ро, Ру. Так как пара Жо, иг.-универсальна, а множества Ро, Pi рекурсивно неречислимы, то пара Ро, Pi также т-универсалъна. Следовательно, ассоциативное исчисление А (£) обладает парой эффективно неотделимых смежных классов [0] и \qdv\.

Выше мы строили ассоциативное исчисление с неразрешимой проблемой равенства, совершенно не заботясь о том, насколько сложным это исчисление окажется. В нервом приближении можно принять, что сложность исчисления характеризуется числом порождающих и числом определяющих соотношений. Простейшие замечания (см. задачу 12 § 13) показывают, что если существует ассоциа-. тивное исчисление с неразрешимой проблемой равенства, имеющее р порождающих и I определяющих соотношений, то существует и ассоциативное исчисление с неразрешимой проблемой равенства, имеющее то же число I определяющих соотношений и лишь 2 порождающих. Возникает задача нахождения ассоциативного исчисления с неразрешимой проблемой равенства и наименьшим числом определяющих соотношений. Есть основания полетать (см. А д я н [3]), что ассоциативные исчисления с одним определяющим соотношением имеют разрешимую проблему равенства. С другой стороны, Ц е й т и н [1] показал, что ассоциативное исчисление с порождающими а, Ь, с, d, е и семью определяющими соотношениями

ас = са, ad = da, be ~ сЪ, bd = db, еса = се, edb = de, сса ~ ссае имеет неразрешимую проблему равенства слов. Ассоциативное исчисление, имеющее неразрешимую проблему равенства и менее селш определяющих соотношений, пока неизвестно*).

Ассоциативное исчисление называется групповым (иногда - инверсивным) исчислением, если его порождающие можно разбить на пары ау,Ьу,...,ар, bp так, чтобы среди определяющих соотношений заведомо встречались соотношения aii = А, . . ., Upbp = А, где А - пустое слово. Полугруппа, определяемая групповым исчислением, является группой, в которой элементы [aJ и [Ь;] взаимно обратны.

*) Ю. В. Матпясевпч (ДАН СССР, т. 173, 6) построил ассоциативное исчисление с тремя определяющпмп соотноишния.мн, имеющее неразреи]и.му1о ггробле.му равенства слов.- Примеч. ред.

Задание групп при помощи групповых исчислений, т. е. при помощи порождающих и лпределяющих соотношений, играет большую роль как в самой теории групп, так и в некоторых ее важных приложениях. Поэтому уже в начале XX столетия в теории групп стала известной проблема равенства слов. Однако она оказалась весьма трудной и решение ее было получено только в 1952 г. Новиковым [1]. Другие ее решения позже были найдены Буном [1], Бриттоном [1], Хигме-н о м [1]. Все эти решения достаточно сложны и нотому здесь не излагаются.

Конечно, в связи с ассоциативными и групповыми исчислениями возникло много различных проблем алгоритмического характера. Общий обзор их дан в работах Маркова [2], Адяна [2], а также Р а б и н а [1]. Как правило, решение этих проблем осуществляется тем пли иным сведением их к проблеме равенства слов в некотором вспомогательном ассоциативном или групповом исчислении с заведомо неразрешимой проблемой равенства слов.

13.2. Тождественно истинные формулы исчисления предикатов 1-ir ступепн. Основным формальным логическим языком является исчисление предикатов 1-й ступени. Наша цель - доказать теорему Чёрча о том, что совокупность всех тождественно истинных формул исчисления предикатов 1-й ступени , нерекурсивна. Напомним некоторые определения.

Рассматривается особое двухэлементное лдаожество 8, элементы которого называются «истиной» и «ложью» и обозначаются соответственно И и JT. На множестве е определяются операции конъюнкции &, дизъюнкции \/, импликации и отрицания I обычным образом: а & b пмеет значение И для а = И, Ь = Иша&Ъ=Л для остальных значений а, Ь; далее ,

а\/ Ъ = Л а b = Л, ЪЛа = И,Ъ = Л,

-1а-= И а = Л.

Если 3£ - произвольное непустое множество, то д-местная функция Р {ху, . . ., Хп), определенная на 31 со значениялш в {И, Л}, называется п-местным предикатом на М. Для двуместных предикатов Р вместо записи Р (х, у) обычно употребляют более короткую запись хРу. На-