Expresión explícita mu-recursiva para la función de Ackerman

¿Puede indicar cómo construir la función Ackerman (en realidad estoy interesado en una versión propuesta por Rózsa Péter y Raphael Robinson) a través de operadores mu-recursivos estándar? Probé documentos originales de Péter y Robinson, pero el papel de Péter usa un idioma diferente al inglés y los documentos de Robinson "Recursion and Double Recursion" y "Primitive Recursive Functions" tampoco ayudan: el primero de ellos parece más relevante, pero es útil. llamado operador de doble recursión para definir la función de Ackerman, por lo que en este caso se busca la definición explícita del operador en términos mu-recursivos.

P. Smith se acerca más a la respuesta en "Una introducción a los teoremas de Godel" (CUP, 2007) (29.4 La función de Ackermann-Peter es μ-recursiva), pero se le ocurre lo siguiente: "hacer que el argumento sea hermético es bastante tedioso aunque no difícil. No hay nada que aprender de explicar los detalles aquí: así que no lo haremos ”.

También probé el libro de Rózsa Péter "Funciones recursivas" (1967, Academic press). Hay muchas variantes para operadores de recursión que se ofrecen allí. Por lo general, uno se reduce a otro. Creo que hay un tipo de operador de recursión que se ajusta a la definición de la función de Ackerman y la secuencia de pasos que lo reducen a operadores primarios de reducción y minimización, pero me encontré incapaz de investigar todo el proceso.

computability Artem Pelenitsyn
fuente

En realidad, esto no es tan difícil como puede parecer al principio. El truco consiste en dejar que el operador busque un cálculo de la función Ackerman, es decir, la tabla de valores hasta la entrada, y luego verifique que la tabla siga la definición de la función. Lo que se necesita es codificar / decodificar secuencias finitas y verificar la tabla. La codificación / decodificación se define explícitamente en muchos libros de texto, la verificación puede realizarse mediante un cuantificador universal acotado sobre una relación simple entre las entradas de la tabla. El cuantificador universal acotado puede expresarse como multiplicación acotada,

μ

$\mu$

Kaveh

y una definición explícita de multiplicación acotada en términos de -recursion también se puede encontrar en los libros de texto.

μ

$\mu$

Kaveh

@Kaveh sí, la misma idea implementada en "Una introducción a los teoremas de Godel" de P. Smith. Las codificaciones y la aplicación del operador de minimización se dan allí. La parte difícil es cómo generar la "tabla" como la nombre. Smith lo esquió. Así que parece que tendré que pensarlo mejor en lugar de esperar soluciones aquí;) Al menos, gracias por su aprobación del enfoque general.

Artem Pelenitsyn

La tabla es solo una secuencia finita donde las entradas se indexan por el resultado de una función de emparejamiento.

donde

μ 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)$ es la rhs de la ecuación para

A c k (x, y)

$Ack(x,y)$

Kaveh

Respuestas:

Romper la función de Ackermann hasta los operadores elementales realmente sería bastante largo, pero aquí hay un bosquejo:

Tenga en cuenta que cuando calcula recursiva, en cualquier punto del cálculo está tratando con una expresión de la forma . una función de emparejamiento biyectivo con inversa , podemos codificar este estado como $A(m,x)$ $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$ $p$ $(\pi_1,\pi_2)$ (solo en caso de que ). Luego podemos definir la función de evaluación de un paso, dado un estado: $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))))$

Luego obtiene la función de evaluación de n pasos usando recursividad primitiva:

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

$\mu$ $E$ $p(z,0)$ $z$ $A(m,x)$

Klaus Draeger
fuente

¡Gracias! Una pregunta más (tal vez bastante ingenua, lo siento): las definiciones similares a la coincidencia de patrones (f (0) = ..., f (n + 1) = ...) se usan ampliamente, pero dudo que realmente estén permitidas por el definición de función mu-recursiva. ¿Son ellos?

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

bastante si desea desglosar esto en el conjunto básico de operaciones.

π_{1}, π_{2}

$\pi_1,\pi_2$

Klaus Draeger

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$

Esta es una variante de la idea publicada por Kaveh, pero estoy publicando de todos modos, ya que le permite barrer muchos detalles desagradables debajo de la alfombra sin hacer ningún movimiento manual.

$B(m,n,w)$ $A(m,n) = w$ $B(m,n,w) = 2^{mw^w}$ debería ser lo suficientemente bueno, pero eso depende de su elección del esquema de codificación. Dado que la verificación de los valores de la tabla puede describirse mediante una fórmula acotada, es primitiva recursiva.

$G(m,n,w)$ $A(m,n) = \mu w\,G(m,n,w)$

$B(m,n,w)$ $\mu$ $\mu$

François G. Dorais
fuente

Hola françois Es bueno verte en teoría.

Kaveh

Hola kaveh ¡Es bueno finalmente poder responder algo aquí!

François G. Dorais