Expliziter mu-rekursiver Ausdruck für die Ackerman-Funktion

Können Sie bitte erläutern, wie Sie die Ackerman-Funktion (eigentlich interessiert mich eine von Rózsa Péter und Raphael Robinson vorgeschlagene Version) über standardmäßige mu-rekursive Operatoren erstellen können? Ich habe Originalarbeiten von Péter und Robinson ausprobiert, aber Péters Arbeit verwendet eine andere Sprache als Englisch und Robinsons Arbeiten „Rekursion und doppelte Rekursion“ und „Primitive rekursive Funktionen“ helfen ebenfalls nicht weiter wird als doppelter Rekursionsoperator bezeichnet, um die Ackerman-Funktion zu definieren. In diesem Fall wird also nach einer expliziten Definition des Operators in mu-rekursiven Begriffen gesucht.

Der Antwort am nächsten kommt P. Smith in „Eine Einführung in Godels Theoreme“ (CUP, 2007) (29.4 Die Ackermann-Peter-Funktion ist μ-rekursiv), der jedoch Folgendes vorschlägt: „Das Argument wasserdicht zu machen ist hübsch langweilig, aber nicht schwierig. Es gibt nichts zu lernen, wenn man die Details hier ausdrückt: Also werden wir es nicht tun. “

Ich habe auch Rózsa Péters Buch „Rekursive Funktionen“ ausprobiert (1967, Academic Press). Es gibt dort viele Varianten für Rekursionsoperatoren. In der Regel reduziert man auf andere. Ich glaube, dass es eine Art von Rekursionsoperator gibt, die für die Definition der Ackerman-Funktion und der Folge von Schritten geeignet ist, die sie auf primitive Redursions- und Minimierungsoperatoren reduzieren, aber ich war nicht in der Lage, den gesamten Weg nach unten zu untersuchen.

computability Artem Pelenitsyn
quelle

Eigentlich ist das gar nicht so schwer, wie es zunächst scheinen mag. Der Trick besteht darin, den Operator nach einer Berechnung der Ackerman-Funktion, dh der Wertetabelle bis zur Eingabe, suchen zu lassen und dann zu überprüfen, ob die Tabelle der Definition der Funktion entspricht. Was benötigt wird, ist das Codieren / Decodieren endlicher Sequenzen und das Überprüfen der Tabelle. Kodierung / Dekodierung sind in vielen Lehrbüchern explizit definiert, die Überprüfung kann durch einen begrenzten Universalquantifizierer über eine einfache Beziehung zwischen den Einträgen der Tabelle erfolgen. Der begrenzte Universalquantifikator kann als begrenzte Multiplikation ausgedrückt werden

μ

$\mu$

Kaveh

und eine explizite Definition der begrenzten Multiplikation im Sinne von Rekursion findet sich auch in Lehrbüchern.

μ

$\mu$

Kaveh

@Kaveh ja, die gleiche Idee wurde in P. Smiths "Eine Einführung in Godels Theoreme" umgesetzt. Dort werden die Codierungen und die Anwendung des Minimierungsoperators angegeben. Der knifflige Teil ist, wie man die "Tabelle" so erzeugt, wie man sie nennt. Smith ließ es aus. Es scheint also, als müsste ich etwas genauer darüber nachdenken, anstatt hier auf Lösungen zu warten. Zumindest danke ich Ihnen für Ihre Zustimmung zu der allgemeinen Vorgehensweise.

Artem Pelenitsyn

Die Tabelle ist nur eine endliche Folge, bei der die Einträge durch das Ergebnis einer Paarungsfunktion indiziert werden. wobei ist der rhs der Gleichung für .

μ 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)$

A c k (x, y)

$Ack(x,y)$

Kaveh

Antworten:

Das Aufbrechen der Ackermann-Funktion bis hinunter zu den Elementaroperatoren wäre wirklich ziemlich langwierig, aber hier ist eine Skizze:

Man beachte , dass bei der Berechnung rekursiv, an einem beliebigen Punkt der Berechnung man mit einem Ausdruck der Form handelt . Bei einer gegebenen bijektive Paarungsfunktion mit invers , wir können diesen Zustand als kodieren (nur für den Fall ). Wir können dann die einstufige Bewertungsfunktion definieren, wenn ein Zustand gegeben ist: $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))))$ .

Sie erhalten dann die n-Stufen-Auswertungsfunktion unter Verwendung der primitiven Rekursion:

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

Schließlich wickeln Sie -recursion um , um den Punkt zu finden, an dem wir zu einem Zustand der Form - wird . $\mu$ $E$ $p(z,0)$ $z$ $A(m,x)$

Klaus Draeger
quelle

Vielen Dank! Noch eine Frage (vielleicht ziemlich naiv, sorry): Mustervergleichsähnliche Definitionen (f (0) = ..., f (n + 1) = ...) werden häufig verwendet, aber ich bezweifle, dass sie wirklich von den zugelassen werden Definition der mu-rekursiven Funktion. Sind sie?

Artem Pelenitsyn

Diese Art der Fallunterscheidung (zum Beispiel die Definition von durch und ) ist nur ein Sonderfall der primitiven Rekursion, die den vorherigen Wert nicht verwendet. Bei der Berechnung von würden Sie zusätzlich Hilfsfunktionen und die Inversen ziemlich wenn Sie dies auf die Grundmenge von Operationen herunterbrechen wollten.

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$

Klaus Draeger

Beispielsweise könnten Sie die Definition von als , wobei und , wobei Sie die Idee bekommen.

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))$

f_{2} \dots

$f_2\dots$

Klaus Draeger

Dies ist eine Variante der von Kaveh geposteten Idee, aber ich poste sie trotzdem, da Sie so viele unangenehme Details unter den Teppich kehren können, ohne tatsächlich mit der Hand zu winken.

Entscheidend ist, dass der Graph der Ackermann-Funktion primitiv rekursiv ist. Es ist nicht so schwer, eine sehr grobe primitive rekursive Bindung im Code für die Tabelle der Ackermann-Werte zu finden, die zur Überprüfung von erforderlich ist . Versuchen Sie nicht, scharfe Grenzen zu ziehen - je gröber, desto einfacher! Etwas wie sollte gut genug sein, aber das hängt von Ihrer Wahl des Codierungsschemas ab. Da die Überprüfung der Tabellenwerte durch eine begrenzte Formel beschrieben werden kann, ist sie primitiv rekursiv. $B(m,n,w)$ $A(m,n) = w$ $B(m,n,w) = 2^{mw^w}$

Sobald Sie eine primitive rekursive Definition für den Graphen der Ackermann-Funktion haben, definieren Sie einfach . $G(m,n,w)$ $A(m,n) = \mu w\,G(m,n,w)$

Leider funktioniert diese Strategie nicht für alle Funktionen, die durch doppelte (oder mehrfache) Rekursion definiert sind. Der Grund, warum es für die Ackermann-Funktion funktioniert - wie Sie sehen werden, wenn Sie versuchen, ein gutes herauszufinden - ist, dass es sehr monoton wächst. Für den allgemeinen Fall, müssen Sie Kaveh Idee und haben verwenden sucht die entsprechende Wertetabelle. Dies ist im Grunde der gleiche Grund, warum der Normalformsatz von Kleene nach Anwendung des Operators eine Projektion durchführen muss . $B(m,n,w)$ $\mu$ $\mu$

François G. Dorais
quelle

Hallo François. Es ist schön, dich auf cstheory zu sehen.

Kaveh

Hallo Kaveh. Schön, hier endlich mal was zu beantworten zu bekommen!

François G. Dorais