Два примера обобщенной вычислимости

Г.А. Баженова

Омский государственный университет, кафедра информационных систем
644077, Омск, пр. Мира, 55-А

Получена 26 декабря 1998 г.

В статье [1] было введено понятие обобщенной вычислимости (над произвольной алгебраической системой). Оно на самом деле является обобщением классического понятия вычислимости для натуральных чисел (формализованного с помощью машин Тьюринга, а также через понятие частично-рекурсивной функции и многими другими способами). Естественно возникает вопрос, какие же результаты классической теории остаются верными и для обобщенной вычислимости, а какие нет. Например (см. []), как и в классической теории, доказано существование универсальных машин. С другой стороны, в обобщенной теории не существует однозначного аналога рекурсивно перечислимого множества, так как эквивалентные в классической теории определения рекурсивно перечислимого множества становятся неэквивалентными в обобщенной. В данной статье мы приводим два примера того же сорта: пример, показывающий, что известная теорема Майхилла в общем случае неверна, то есть 1-эквивалентные множества могут не быть рекурсивно изоморфными, а также пример, когда m-полное множество не является 1-полным. Первый пример интересен потому, что он удовлетворяет сильным дополнительным ограничениям (примеры без этих ограничений строятся легко).

Определения всех используемых нами понятий из области обобщенной вычислимости содержатся в [1]. Если A - алгебраическая система, то через HL(A) обозначается ее списочная надстройка.

Определение. Пусть A - произвольная алгебраическая система, HL(A) - ее списочная надстройка. Пусть X,YНHL(A) - произвольные множества. Будем говорить, что множество X m-сводится к множеству Y, если существует такая всюду на HL(A) определенная BSS-вычислимая функция f :HL(A)®HL(A), что для любого tОHL(A) имеем f(t)ОYЫtОX. Если существует такая функция с дополнительным условием инъективности, то множество X 1-сводится к множеству Y.

Множество PНHL(A) называется m-полным, если множество остановки любой BSS-машины "от одной переменной" над HL(A) m-сводится к P и если P само является множеством остановки. Аналогично, множество остановки P 1-полно, если любое множество остановки к нему 1-сводится.

Множества X,YНHL(A) называются 1-эквивалентными, если X 1-сводится к Y и Y 1-сводится к X. Множества X,Y называются рекурсивно изоморфными, если существует такая биекция f: HL(A)®HL(A), что f(X)=Y и f, f ^-1 BSS-вычислимы.

Пример 1. Рассмотрим алгебраическую систему A=(A,a⁽¹⁾,b⁽¹⁾), где основное множество A состоит из трех попарно не пересекающихся счетных множеств C={c_i, i=0, 1, ј}, E={e_i, i=0, 1, ј} и D={d_j, jОZ}, а одноместные функциональные символы a и b интерпретируются так:
a(c_i) = c_i+1, a(d_j) = d_j+1, a(e_i) = e_i+1, b(d_j) = d_j-1, b(c_i) = c_{max(i-1, 0)}, b(e_i) = e_{max(i-1, 0)}.

Рассмотрим множества S₁ = {c_i, d_j, e_l | i, j нечетны, l четно }, S₂ = {c_i, d_j, e_l | i, j четны, l нечетно }. Эти множества 1-эквивалентны над HL(A), то есть существуют всюду определенные BSS-вычислимые над HL(A) инъективные функции f, g : HL(A)®HL(A) такие, что

f(x) О S₁ Ы x О S₂,
g(x) О S₂ Ы x О S₁.

(На самом деле можно положить f(x) = g(x) = a(x), x О A и f(x) = g(x) = x, x П A. По обобщенному тезису Черча (см. [1]) эта функция вычислима. Остальное без труда проверяется.)

Однако эти множества не являются рекурсивно изоморфными, более того, не существует BSS-вычислимой биекции h : HL(A)®HL(A) такой, что h(S₁) = S₂. (Мы даже не требуем вычислимости h^-1.)

Действительно, предположим, что такая биекция h существует. Очевидно, что h(d₁) = d_a, где a - некоторый четный индекс. Из результатов [1] следует, что существует такое счетное множество бескванторных формул сигнатуры системы HL(A) F={j_i(x), iОI} и такое множество термов той же сигнатуры {T = t_i(x), iОI }, что для каждой пары различных индексов i, jОI в HL(A) истинна формула "xj_i(x)®Шj_j(x) и для каждого x для некоторого индекса i истинно j_i(x), и для такого x значение функции h совпадает со значением терма t_i(x).

Найдем такой индекс bОI, что в списочной надстройке истинна формула j_b(d₁). По этой формуле можно (даже эффективно) построить бескванторную формулу y(x) сигнатуры системы A такую, что для любого элемента uОA y(u) Ы j_b(u) (см. [1]). Аналогичным образом можно по терму t_b(x) построить некоторый терм t^ў(x) сигнатуры {a,b} так, что для всех uОA t_b(u) = t^ў(u). (Конечно, это возможно потому, что для некоторого A'u = d₁ t_b(u) = d_a также принадлежит A.) В дальнейшем мы будем считать сам терм t_b термом сигнатуры {a,b}.

Далее, формулу y можно представить как результат подстановки в некоторую формулу x(X₁,ј,X_k) исчисления высказываний вместо переменных X_i некоторых атомарных формул Y_i(x) сигнатуры {a,b}. Найдется такое натуральное N, что если Y_j(x) имеет вид ((Ш)a^r₁ b^s₁јa^r_l b^s_l(x) = a^z₁ b^v₁ -a^z_l b^v_l(x) ), то суммы е¹_{u = 1} s_u, е^l_u = 1 v_u не превосходят N. Далее, пусть t_b(x) = a^p₁ b^q₁јa^p_m b^q_m(x). Обозначим s₁=е^m_u = 1 p_u, s₂=е^m_u = 1 q_u. Тогда для любого d_i t_b(d_i) = a^s₁ - s₂(d_i), если s₁ > s₂, t_b(d_i) = b^s₂ - s₁(d_i), если s₁<s₂, t_b(d_i) = d_i, если s₁=s₂. Можно записать это короче: t_b(d_i) = d_i+s₁-s₂. (Отсюда следует, что a = 1+s₁-s₂, t_b(d_i) = d_i+a -1.)

Будем считать, что s₂ < N. Но тогда для всех i і N + 1 значения термов t_b(c_i), t_b(e_i) вычисляются по полностью аналогичным формулам. В частности, t_b(c_i) = c_i + a -1, t_b(e_i) = e_i + a -1. Повторяя эти рассуждения для термов, входящих в формулы Y_j, получаем также, что для любого элемента c_i, i і N + 1, (соответственно e_i, i і N + 1) каждая формула Y_j(c_i) (соответственно Y_j(e_i)) принимает то же значение, что Y_j(d₁). Отсюда следует истинность j_b(c_i), j_b(e_i), i і N + 1. Значит, h(c_i) = t_b(c_i) = c_i + a -1, h(e_i) = e_i + a -1. Теперь заметим, что должно быть h(S₁ЗC) = CЗS₂, а также h(S₁ЗE) = EЗS₂. Из последнего условия в силу симметрии системы следует h(S₂ЗC) = CЗS₁. (В этом месте доказательства мы используем наличие множества E. Иначе условие h(C) = C не обязано выполняться, и рекурсивный изоморфизм существует.) Мы видим, что функция h устанавливает биективное соответствие между множеством M = {c_i, i і N + 1 } и множеством P = {c_i, i і N + a}, а также между множеством C и им самим, а тогда она устанавливает биективное соответствие и между конечными множествами C \ M и C \ P, но они имеют разную мощность. Действительно, первое из них содержит N + 1 элемент, а второе N + a элементов, а число a четно. Полученное противоречие говорит о том, что множества S₁ и S₂ не являются рекурсивно изоморфными.

Замечание. Отметим, что предыдущий пример удовлетворяет следующим дополнительным условиям: во-первых, множества значений сводящих функций f,g рекурсивны, во-вторых, (частичные) обратные к f,g функции также BSS-вычислимы.

Пример 2. Рассмотрим следующую алгебраическую систему A: основное множество A почти произвольно, потребуем лишь, чтобы оно содержало по крайней мере два элемента. Сигнатура - пустое множество. Докажем, что существует множество P Н HL(A), которое m-полно, но не 1-полно.

Напомним, что, согласно [1], существует так называемая универсальная функция U(x,y): HL(A) ґ HL(A) ® HL(A), под которой понимается (частичная) BSS-вычислимая функция такая, что для любой BSS-машины M от одной переменной найдется некоторый элемент хОHL(Ж) такой, что для любого yОHL(A) M(y) = U(x,y). В качестве P возьмем множество всех таких списков из двух элементов (x,y) + HL(Ж), что U(x,y) определено. Ясно, что это - множество остановки. Далее, пусть S₀ - множество остановки некоторой машины M₀. Докажем, что S₀ m-сводится к P. Пусть v - произвольный элемент списочной надстройки HL(A). Опишем некоторую эффективную процедуру "кодирования" элемента v списком из HL(Ж). Прежде всего, выпишем (без повторений) носитель элемента v: a₁,ј,a_n. Теперь определим по индукции функцию c_v : HL({a₁,ј,a_n}) ® HL(Ж) следующим образом:

1) c_v(u) = (0, i), если u есть праэлемент a_i;
2) c_v(u) = (0, 0), если u есть пустой список nil;
3) c_v(u) = (1, c_v(w₁),ј,c_v(w_r)), если u есть список (w₁,ј,w_r).
(Здесь 0, 1 - "натуральные числа" - см. [1]).

Теперь положим C(v) = c_v(v). По тезису Черча функция C(v) BSS-вычислима. Более того, если M - некоторая BSS-машина, то существует BSS-машина M ^ў, которая вход C(v) перерабатывает в C(M(v)), если M(v) определено, и не останавливается, получив на входе C(v), иначе. (Конечно, мы используем здесь то, что сигнатура системы A пустая, и M ^ў должна лишь имитировать выполнение списочных операций). В частности, по машине M₀ построим соответствующую M₀^ў. Далее, найдем "номер" x О HL(Ж) такой, что для всех yОHL(A) M₀^ў(y) совпадает с U(x,y). Рассмотрим функцию f : HL(A)®HL(A), f : v®(x, C(v)). Очевидно, что vОS₀ Ы f(v)ОP. Значит, P m-полно.

Докажем, что P не является 1-полным (от противного). Действительно, множество K = HL(A) - множество остановки. Поэтому, если P 1-полно, то существует такая всюду определенная BSS-вычислимая инъективная функция f, что f (HL(A)) = P. Но если a № b - некоторые элементы A, то перестановка a :A ® A, a(a)=b, a(b)=a, a(d)=d, d № a,b, может быть продолжена до автоморфизма j алгебраической системы HL(A), при котором все элементы HL(Ж) остаются неподвижными. Легко видеть, что, поскольку f вычислима, для всех x из HL(A) f(j(x)) = j(f(x)). Но тогда (так как P Н HL(Ж)) f(j(x)) = f(x). В частности, f(a) = f(b). Но это противоречит инъективности f. Значит, P не 1-полно.

Литература