[z / x]= g(x) = my y£z ( х(y+1)>z ).
В описании этой ф-и используется не предикат равенства (как в определении обратной функции), а предикат “>”. Это связано с тем, что целая часть от деления — функция, “не совсем обратная” умножению; точнее, обратная ему только в тех точках, где z делится нацело на x.
§ 7. Функции Аккермана
Возникает вопрос: все ли вычислимые функции можно описать как примитивно-рекурсивные? Чтобы показать, что ответ на этот вопрос является отрицательным, построим пример вычислимой функции, не являющейся примитивно-рекурсивной. Идея примера в том, чтобы, построив последовательность функций, каждая из которых растет существенно быстрее предыдущей, сконструировать с ее помощью функцию, которая растет быстрее любой примитивно-рекурсивной функции.
Начнем с построения последовательности функций j0, j1, j2. Положим
j0(а, x)=a+x; j1(а, x)=ax; j2(а, x)=ax.
Эти функции связаны между собой следующими рекурсивными соотношениями:
j1(а, 1)=a; j1(а, x+1)=а+ax=j0(а, j1(а, x));
j2(а, 1)=a; j2(а, x+1)=а ax=j1(а, j2(а, x)).
Продолжим эту последовательность, положив по определению (n>=1).
jn+1(а, 0)=1;
jn+1(а, 1)=a; (5.6)
jn+1(а, x+1)= jn(а, jn+1(а, x)).
Эта схема имеет вид примитивной рекурсии, следовательно, все функции jn примитивно-рекурсивные. Растут они крайне быстро; например,
j3(а, 1)=a; j3(а, 2)= j2(а, а)=aа; j3(а, 3)= j2(а, aа)=
...
Зафиксируем теперь значение а: пусть а=2. Получим последовательность одноместных фнкций j0(2, x), j1(2, x)... Определим теперь функцию В(n, x), которая перечисляет эту последовательность: В(n, x)= jn(2, x), т. е. В(0, x)= j0(2, x)=2+x; В(1, x)= j1(2, x)=2x и т. д., а также диагональную функцию А(x)= В(x, х).
[3, гл. III, § 5]
Функции В(n, x) называются функциями Аккермана, а функция А(x) — диагональной функцией Аккермана.
[2, § 5.3]
Из соотношений (5.6) следует, что
В(0, x) = j0(2, x) = 2+x;
В(n+1, 0) = jn+1(2, 0) = sg n =
(5.7)
В(n+1, x+1) = jn+1(2, x) = jn(2, jn+1(2, x)) = В( n, В(n+1, x) ).
Эти соотношения позволяют вычислить значения функций В(n, x) и, следовательно, А(x), причем для вычисления функции в данной точке нужно обратиться к значению функции в предшествующей точке — совсем как в схеме примитивной рекурсии. Однако здесь рекурсия ведется сразу по двум переменным (такая рекурсия называется двойной, двукратной, или рекурсией 2-й ступени), и это существенно усложняет характер упорядочения точек, а следовательно, и понятие предшествования точек также усложняется.
Примеры.
1. В(3,3) = В( 2, В(3,2) ), а так как В(3,2) = j3(2, 2)= j2(2, 2)=22=4, то вычислению В(3,3) должно предшествовать вычисление В(2,4).
2. В(3,4) = В( 2, В(3,3) ), а так как В(3,3) = j3(2, 3)= j2(2, 4)=16, то вычислению В(3,4) должно предшествовать вычисление В(2,16).
Важно отметить, что это упорядочение не определено заранее, как в схеме примитивной рекурсии, где n всегда предшествует n+1, а выясняется в ходе вычислений; поэтому схему двойной рекурсии (в отличие от рассмотренной ранее одномерной рекурсии) не всегда удается свести к схеме примитивной рекурсии.
[3, гл. III, § 5]
Свойства функции В(n, x)
1. В(n, x) ³ 2x (n³2; x=1,2...)
Так как В(2, x) = 2x, то для n=2 это соотношение верно. Далее применяем индукцию по n. Пусть для некоторого n=k³2 соотношение (1) истинно при всех значениях х³1. Согласно (5.7) и (5.6) имеем В(k+1, 1) = jk+1(2, 1) = 2 ³ 21.
Пусть теперь для какого-то х³1 выполняется неравенство В(k+1, x) ³ 2x. Тогда
В(k+1, x+1) = В( k, В(k+1, x) ) ³ 2 В(k+1, x) ³
³ 2x+1.
На последнем этапе доказательства мы воспользовались тем, что 2m ³ m+1для всех натуральных m.
2. В(n, x+1) > В(n, x) (n, x=1,2...)
При n=1: В(1, x+1) = j1(2, x+1) = 2x+2, В(1, x) = j1(2, x) = 2x, 2x+2>2x.
Пусть для некоторого n=k³1 соотношение (2) истинно. В силу (5.7) и св-ва (1)
В(k+1, x+1) = В( k, В(k+1, x) ) ³ 2 В(k+1, x) > В(k+1, x).
На последнем этапе доказательства мы воспользовались тем, что 2m > m для всех натуральных m.
3. В(n+1, x) ³ В(n, x+1) (n ³ 1, x ³ 3)
В силу (5.7) и св-в (1) и (2)
В(n+1, x) = В( n, В(n+1, x-1) ) ³ В( n, 2x-1) ³ В(n, x+1).
На последнем этапе доказательства мы воспользовались тем, что 2m-1 ³ m+1 для всех натуральных m ³ 3.
4. В(n+1, x) > В(n, x) (n ³ 1, x ³ 3)
В(n+1, x) ³ ***св-во(3)*** В(n, x+1) > ***св-во(2)*** В(n, x)
[2, § 5.3]
Теорема. Диагональная функция Аккермана А(x) растет быстрее, чем любая примитивно-рекурсивная функция, и, следовательно, не является примитивно-рекурсивной.
Чтобы доказать эту теорему, надо показать, что для любой одноместной примитивно-рекурсивной функции f(х) найдется такое n, что для любого х ³ n выполняется неравенство
А(x)> f(х).
Этап I. Функция f(x1, ..., xn) называется В-мажорируемой, если существует такое число mÎNÈ{0}, что для любых x1, ..., xn, удовлетворяющих условию max(x1, ..., xn)>1, выполняется неравенство: f(x1, ..., xn) < B( m, max(x1, ..., xn) ). На первом этапе доказательства покажем, что все примитивно-рекурсивные функции В-мажорируемы.
а) Для простейших функций 0, х+1, Imn их В-мажорируемость очевидна.
б) Рассмотрим оператор суперпозиции Smn, причем для простоты выкладок ограничимся случаем n=1, m=2, т. е. функцией f(x)= h( g1(x), g2(x) ). (1)
Пусть функции h, g1, g2 В-мажорируемы с числами mh, m1 и m2 соответственно. Выберем в качестве m максимальное из чисел mh, m1 и m2. Тогда по определению В-мажорируемости и свойствам функции В(n, x)
h(x1, x2) < B( m, max(x1, x2) );
g1(x) < B(m, x) < B(m+1, x);
g2(x) < B(m, x) < B(m+1, x).
и, следовательно, с учетом (5.7) и св-ва (3)
f(x)= h( g1(x), g2(x) ) < B( m, max(g1(x), g2(x)) ) < B( m, B(m+1, x) ) = B(m+1, x+1) £ B(m+2, x), т. е.
f(x) B-мажорирума.
в) Рассмотрим теперь оператор примитивной рекурсии, ограничившись для простоты схемой 1*-2*:
f(0)=с; (1*)
f(х+1)= h(х, f(х ) ). (2*)
Пусть функция h B-мажорируема, т. е. h(x1, x2) < B( mh, max(x1, x2) ) при max(x1, x2)>1. Докажем индукцией по х, что f(x) B-мажорируема.
Учитывая условие в определении В-мажорируемости, индукцию надо начинать с х=2. Пусть f(2)=с2. Из свойств функции В(n, x) следует, что В(x+1,2) > В(x,2); поэтому найдется такая величина m2, что В(m2,2) > с2 = f(2). Положим m = max(m2, mh)+1. Очевидно, что f(2) < В(m, 2).
Пусть теперь f(k) < В(m, k). Тогда f(k+1)= h(k, f(k ) ) < B( mh, max(k, f(k )) ).
Если max(k, f(k ))=k, то
f(k+1) < B( mh, k ) (***(mh < m) + св-во (4)***) < B( m, k ) (*** св-во (2)***) < B( m, k+1).
Если же max(k, f(k ))= f(k ), то
f(k+1) < B( mh, f(k ) ) < *** предположение + св-во (2)***
< B( mh, В(m, k) ) < ***(mh £ m-1) + св-во (4)***
£ B( m-1, В(m, k) ) = В(m, k+1).
Из пп. “а”-”в” следует, что все примитивно-рекурсивные функции В-мажорируемы.
Этап II. Пусть f(x) - примитивно-рекурсивная функция. Тогда она В-мажорируема, т. е. для некоторого m и х ³ 2 выполняется неравенство: f(x) < B(m, x); поэтому
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)