Wyraźne wyrażenie mu-rekurencyjne dla funkcji Ackermana

Czy mógłbyś wskazać, jak zbudować funkcję Ackermana (tak naprawdę interesuje mnie wersja zaproponowana przez Rózsa Pétera i Raphaela Robinsona) za pomocą standardowych operatorów rekursywnych? Próbowałem oryginalnych prac Pétera i Robinsona, ale praca Pétera używa języka innego niż angielski, a prace Robinsona „Recursion and Double Recursion” i „Primitive Recursive Functions” również nie pomagają: pierwszy z nich wydaje się bardziej trafny, ale ma takie zastosowania nazywany operatorem podwójnej rekurencji w celu zdefiniowania funkcji Ackermana, dlatego w tym przypadku poszukuje się wyraźnej definicji operatora w kategoriach mu-rekurencyjnych.

Najbliżej odpowiedzi udzielił P. Smith w „Wprowadzenie do twierdzeń Godela” (CUP, 2007) (29.4 Funkcja Ackermanna-Petera jest μ-rekurencyjna), ale wymyślił: „uczynienie argumentu wodoszczelnym jest ładnym nużący, choć nie trudny. Nie trzeba niczego się uczyć, opisując tutaj szczegóły: więc nie zrobimy tego. ”

Próbowałem też książki Rózsy Péter „Funkcje rekurencyjne” (1967, prasa akademicka). Podano tam wiele wariantów dla operatorów rekurencyjnych. Zwykle jeden redukuje się do drugiego. Uważam, że istnieje pewien rodzaj operatora rekurencji, który pasuje do definicji funkcji Ackermana i sekwencji kroków, które redukują ją do prymitywnych operatorów redurcji i minimalizacji, ale nie byłem w stanie zbadać całej drogi.

computability Artem Pelenitsyn
źródło

W rzeczywistości nie jest to tak trudne, jak mogłoby się początkowo wydawać. Sztuczka polega na tym, aby operator

szukał obliczenia funkcji Ackermana, tj. Tabeli wartości aż do danych wejściowych, a następnie sprawdził, czy tabela odpowiada definicji funkcji. Potrzebne jest kodowanie / dekodowanie skończonych sekwencji i sprawdzanie tabeli. Kodowanie / dekodowanie jest wyraźnie zdefiniowane w wielu podręcznikach, sprawdzanie może być wykonane przez ograniczony uniwersalny kwantyfikator na prostej relacji między wpisami tabeli. Ograniczony uniwersalny kwantyfikator można wyrazić jako ograniczone mnożenie,

μ

$\mu$

Kaveh

w podręcznikach można również znaleźć wyraźną definicję ograniczonego mnożenia w odniesieniu do

rekurencji.

μ

$\mu$

Kaveh

@Kaveh tak, ta sama idea zaimplementowana w „Wprowadzenie do twierdzeń Godela” P. Smitha. Podano tam kodowanie i zastosowanie operatora minimalizacji. Trudna część polega na tym, jak wygenerować „tabelę”, jak ją nazwiesz. Smith to pominął. Wygląda więc na to, że będę musiał się nad tym zastanowić, zamiast czekać tutaj na rozwiązania;) Przynajmniej dziękuję za aprobatę ogólnego podejścia.

Artem Pelenitsyn

Tabela jest tylko skończoną sekwencją, w której wpisy są indeksowane przez wynik funkcji parowania.

gdzie

μ c : \forall x < L e n (c) \forall y, z < x, x =< y, z >\to c_{< y, z >} = R (c, x, y)

$\mu c: \forall x<Len(c) \forall y,z<x , x=<y,z> \to c_{<y,z>} = R(c,x,y)$

R (c, x, y)

$R(c,x,y)$ oznacza rh równania dla

A c k (x, y)

$Ack(x,y)$

Kaveh

Odpowiedzi:

Złamanie funkcji Ackermanna aż do operatorów elementarnych byłoby naprawdę dość długie, ale oto szkic:

Zauważ, że obliczając rekurencyjnie , w dowolnym punkcie obliczeń masz do czynienia z wyrażeniem postaci $A(m,x)$ $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$ $p$ $(\pi_1,\pi_2)$ $p(z,p(k,p(m_k,\dots,p(m_2,m_1)\dots)$ $p(z,0)$ $k=0$

$e(p(z,0)) = p(z,0)$

$e(p(z,p(k,p(0,c)))) = p(z+1,p(k-1,c))$

$e(p(0,p(k,p(m+1,c)))) = p(1,p(k,p(m,c)))$

. $e(p(z+1,p(k,p(m+1,c)))) = p(z,p(k+1,p(m+1,p(m,c))))$

Następnie otrzymujesz n-krokową funkcję oceny za pomocą prymitywnej rekurencji:

i . $E(0,m,x) = p(x,p(1,m))$ $E(n+1,m,x) = e(E(n,m,x))$

Na koniec owinąć rekurencję $\mu$ $E$ $p(z,0)$ $z$ $A(m,x)$

Klaus Draeger
źródło

Dzięki! Jeszcze jedno pytanie (być może dość naiwne, przepraszam): definicje podobne do dopasowania wzorca (f (0) = ..., f (n + 1) = ...) są szeroko stosowane, ale wątpię, czy są naprawdę dozwolone przez definicja funkcji mu-rekurencyjnej. Czy oni są?

Artem Pelenitsyn

f (x, y)

$f(x,y)$

f (0, y) = g (y)

$f(0,y)=g(y)$

f (x + 1, y) = h (x, y)

$f(x+1,y) = h(x,y)$

A (x, y)

$A(x,y)$

π_{1}, π_{2}

$\pi_1,\pi_2$

e

$e$

e (s) = f_{1} (π_{1} (s), π_{2} (s))

$e(s)=f_1(\pi_1(s),\pi_2(s))$

f_{1} (z, 0) = p (z, 0)

$f_1(z,0)=p(z,0)$

f_{1} (z, m + 1) = f_{2} (z, π_{1} (m + 1), π_{2} (m + 1))

$f_1(z,m+1)=f_2(z,\pi_1(m+1),\pi_2(m+1))$ , where

f_{2} \dots

$f_2\dots$ you get the idea.

Klaus Draeger

This is a variant of the idea posted by Kaveh, but I am posting anyway since it allows you to sweep many nasty details under the rug without actually doing any handwaving.

The key fact is that the graph of the Ackermann function is primitive recursive. It's not that hard to find a very crude primitive recursive bound $B(m,n,w)$ on the code for the table of Ackermann values needed to verify that $A(m,n) = w$ . Don't try to get sharp bounds — the cruder the easier! Something like $B(m,n,w) = 2^{mw^w}$ should be good enough, but that depends on your choice of coding scheme. Since the verification of the table values can be described by a bounded formula, it is primitive recursive.

Once you have a primitive recursive definition for the graph $G(m,n,w)$ of the Ackermann function, simply define $A(m,n) = \mu w\,G(m,n,w)$ .

Sadly, this strategy doesn't work for all functions defined by double (or multiple) recursion. The reason it works for the Ackermann function — as you will see when trying to figure out a good $B(m,n,w)$ — is that it grows very monotonically. For the general case, you must use Kaveh's idea and have $\mu$ look for the appropriate table of values. This is basically the same reason why the Kleene's Normal Form Theorem needs to do a projection after applying the $\mu$ operator.

François G. Dorais
źródło

Hi François. It's nice to see you on cstheory.

Kaveh

Hi Kaveh. Nice to finally get to answer something here!

François G. Dorais