Как доказать рекурсивность функции Аккермана

Lokomotiv59

что она частично рекурсивна:
A(0, y+1) = y
A(x+1, 0) = A(x, 1)
A(x+1, y+1) = A(x, A(x+1, y
Надо доказать, что функция получается подстановкой, примитивной рекурсией (по 1-й переменной
операциями минимизации из константы 0, s(x)=x+1, функции проекции на x_m набора (x_1, ... ,x_n)

Waleri58

а для A(0, 0) мы вылезем в отрицательные значения первого аргумента?
а любые значения A(x, y) , где x > 1, y >= 0 , похоже, будут выражаться через
A(0, A(1, 0 = A(0, 0)
или я чего-то туплю?
я так понимаю, что определение функции Аккермана очень похоже на то, что написано здесь, но что-то там должно быть не так...

Lokomotiv59

ах да, забыл написать, что A(0,0) = 1

Waleri58

а ещё диагональ функции Аккермана должна быстро расти, а тут вроде она равна единце, надо проверить, во всяком случае... мне кажется, что так, хотя, может, туплю...

luherstag

Есть теорема, не помню как называется, что любая вычислимая функция частично рекурсивна. Доказывается через моделирование машины Тьюринга, реализующей эту функцию. Строится примитивно-рекурсивная функция от n "состояние машины через n шагов". Затем оператором минимизации ловится момент, когда машина останавливается.

Lokomotiv59

Вот мне бы еще и эту теорему... или ссылку на нее... кандмин на носу блин
Честно пытался заботать по Мальцеву, но ниасилил. По Клини та же фигня. Тяжело книжки написаны.

luherstag

Может в Яблонском есть, точно не помню.

natunchik

Как ни странно, в английской википедии очень много и понятно было написано про это всё, когда я последний раз зачем-то смотрел. Точно было доказательство не примитивной рекурсивности как раз для Аккермана (но, кажется, не в статье про неё, а в статье про примитивную рекурсию может где-то и алгоритм построения частичной рекурсии валяется.

Waleri58

там скорее всего доказывается, что она растёт быстрее любой примитивно рекурсивной

Lokomotiv59

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

Waleri58

вот, в этой книге вроде должно доказываться.
http://lib.mexmat.ru/books/66

natunchik

http://en.wikipedia.org/wiki/Mu-recursive_function#Equivalen...
Там как бы план и есть ссылки.

Lokomotiv59

всем спасибо, разобрался кажись.
Оставить комментарий
Имя или ник:
Комментарий: