Expression mu-récursive explicite pour la fonction Ackerman

Pouvez-vous s'il vous plaît indiquer comment construire la fonction Ackerman (en fait, je suis intéressé par une version proposée par Rózsa Péter et Raphael Robinson) via des opérateurs mu-récursifs standard? J'ai essayé des papiers originaux de Péter et Robinson, mais le papier de Péter utilise une langue différente de l'anglais et les papiers de Robinson «Recursion and Double Recursion» et «Primitive Recursive Functions» n'aident pas non plus: le premier semble plus pertinent, mais est appelé opérateur de double récursion pour définir la fonction Ackerman, donc dans ce cas, une définition explicite de l'opérateur en termes mu-récursifs est recherchée.

Le plus proche de la réponse est P. Smith dans «Une introduction aux théorèmes de Godel» (CUP, 2007) (29.4 La fonction Ackermann-Peter est μ-récursive), mais il propose ce qui suit: «rendre l'argument étanche est assez fastidieux mais pas difficile. Il n'y a rien à apprendre de l'énoncé des détails ici: nous ne le ferons donc pas. »

J'ai également essayé le livre de Rózsa Péter «Fonctions récursives» (1967, Presse académique). Il existe de nombreuses variantes pour les opérateurs de récursivité qui y sont données. Habituellement, l'un se réduit à l'autre. Je crois qu'il existe un type d'opérateur de récursion qui convient à la définition de la fonction Ackerman et à la séquence d'étapes qui la réduisent à des opérateurs de récursion et de minimisation primitifs, mais je me suis trouvé incapable d'enquêter sur toute la voie.

computability Artem Pelenitsyn
la source

En fait, ce n'est pas aussi difficile que cela puisse paraître au premier abord. L'astuce consiste à laisser l' opérateur

rechercher un calcul de la fonction Ackerman, c'est-à-dire le tableau des valeurs jusqu'à l'entrée, puis vérifier que le tableau suit la définition de la fonction. Ce qu'il faut, c'est encoder / décoder des séquences finies et vérifier la table. L'encodage / décodage est explicitement défini dans de nombreux manuels, la vérification peut être effectuée par un quantificateur universel borné sur une relation simple entre les entrées du tableau. Le quantificateur universel borné peut être exprimé comme une multiplication bornée,

μ

$\mu$

Kaveh

et une définition explicite de la multiplication bornée en termes de

récursivité peut également être trouvée dans les manuels.

μ

$\mu$

Kaveh

@Kaveh oui, la même idée implémentée dans «Une introduction aux théorèmes de Godel» de P. Smith. Les codages et l'application de l'opérateur de minimisation y sont donnés. La partie délicate est de savoir comment générer la «table» comme vous le nommez. Smith l'a sauté. Il semble donc que je devrai y réfléchir plus dur au lieu d'attendre des solutions ici;) Au moins merci pour votre approbation de l'approche générale.

Artem Pelenitsyn

Le tableau est juste une séquence finie où les entrées sont indexées par le résultat d'une fonction d'appariement.

où

μ 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)$ est le rhs de l'équation pour

A c k (x, y)

$Ack(x,y)$

Kaveh

Réponses:

Décomposer la fonction Ackermann jusqu'aux opérateurs élémentaires serait vraiment assez long, mais voici un schéma:

Notez que lors du calcul récursif de , à tout moment du calcul, vous avez affaire à une expression de la forme . une fonction d'appariement bijective avec inverse , on peut coder cet état comme $A(m,x)$ $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$ $p$ $(\pi_1,\pi_2)$ (juste dans le cas ). On peut alors définir la fonction d'évaluation en une étape, étant donné un état: $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))))$

Vous obtenez ensuite la fonction d'évaluation en n étapes en utilisant la récursion primitive:

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

Enfin, enroulez -récursion autour de pour trouver le point où nous arrivons à un état de la forme - sera . $\mu$ $E$ $p(z,0)$ $z$ $A(m,x)$

Klaus Draeger
la source

Merci! Une autre question (peut-être assez naïve, désolée): les définitions de correspondance de motifs (f (0) = ..., f (n + 1) = ...) sont largement utilisées, mais je doute qu'elles soient vraiment définition de la fonction mu-récursive. Sont-ils?

Artem Pelenitsyn

Ce type de distinction de cas (par exemple, définir

par

) n'est qu'un cas spécial de récursion primitive qui n'utilise pas réellement la valeur précédente. Dans le calcul de

, vous utiliseriez en plus des fonctions auxiliaires et les inverses

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

un peu si vous voulez décomposer cela en un ensemble d'opérations de base.

π_{1}, π_{2}

$\pi_1,\pi_2$

Klaus Draeger

Par exemple, vous pouvez traduire la définition de

par

, où

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

, où

vous avez l'idée.

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

C'est une variante de l'idée affichée par Kaveh, mais je poste quand même car elle vous permet de balayer de nombreux détails désagréables sous le tapis sans réellement faire de la main.

Le fait clé est que le graphe de la fonction Ackermann est récursif primitif. Il n'est pas si difficile de trouver une borne récursive primitive très grossière sur le code de la table des valeurs d'Ackermann nécessaire pour vérifier que . N'essayez pas d'obtenir des limites précises - le plus grossier est le plus facile! Quelque chose comme $B(m,n,w)$ $A(m,n) = w$ $B(m,n,w) = 2^{mw^w}$ devrait être suffisant, mais cela dépend de votre choix de schéma de codage. Puisque la vérification des valeurs de table peut être décrite par une formule bornée, elle est récursive primitive.

Une fois que vous avez une définition récursive primitive pour le graphique de la fonction Ackermann, définissez simplement $G(m,n,w)$ $A(m,n) = \mu w\,G(m,n,w)$ .

Malheureusement, cette stratégie ne fonctionne pas pour toutes les fonctions définies par double (ou multiple) récursivité. La raison pour laquelle elle fonctionne pour la fonction Ackermann - comme vous le verrez en essayant de trouver un bon - est qu'elle croît de façon très monotone. Pour le cas général, vous devez utiliser l'idée de Kaveh et faire rechercher par la table de valeurs appropriée. C'est essentiellement la même raison pour laquelle le théorème de forme normale de Kleene doit faire une projection après avoir appliqué l' opérateur . $B(m,n,w)$ $\mu$ $\mu$

François G. Dorais
la source

Salut François. Je suis ravi de vous voir sur cstheory.

Kaveh

Salut Kaveh. Ravi de pouvoir enfin répondre à quelque chose ici!

François