Expressão mu-recursiva explícita para a função Ackerman

Você pode apontar como criar a função Ackerman (na verdade, estou interessado em uma versão proposta por Rózsa Péter e Raphael Robinson) por meio de operadores mu-recursivos padrão? Tentei artigos originais de Péter e Robinson, mas o artigo de Péter usa um idioma diferente dos artigos de inglês e Robinson: "Recursão e dupla recursão" e "Funções primitivas recursivas" também não ajudam: o primeiro deles parece mais relevante, mas é tão útil. chamado operador de recursão dupla para definir a função Ackerman; portanto, neste caso, é buscada uma definição explícita do operador em termos mu-recursivos.

Mais próximo da resposta está P. Smith em “Uma introdução aos teoremas de Godel” (CUP, 2007) (29.4 A função Ackermann-Peter é μ-recursiva), mas ele apresenta o seguinte: “tornar o argumento à prova d'água é bastante tedioso, embora não seja difícil. Não há nada a ser aprendido explicando os detalhes aqui: então não vamos. ”

Também experimentei o livro de Rózsa Péter, “Funções recursivas” (1967, Academic press). Existem muitas variantes para operadores de recursão fornecidas lá. Normalmente, um reduz a outro. Acredito que exista um tipo de operador de recursão que se ajuste à definição da função Ackerman e sequência de etapas que a reduza a operadores de redursão e minimização primitivos, mas não consegui investigar o caminho todo.

computability Artem Pelenitsyn
fonte

Na verdade, isso não é tão difícil quanto pode parecer à primeira vista. O truque é permitir que o operador

μ

$\mu$ procure um cálculo da função Ackerman, ou seja, a tabela de valores até a entrada e, em seguida, verifique se a tabela segue a definição da função. O que é necessário é codificar / decodificar seqüências finitas e verificar a tabela. Codificação / decodificação são definidas explicitamente em muitos livros, a verificação pode ser feita por um quantificador universal limitado em uma relação simples entre as entradas da tabela. O quantificador universal limitada pode ser expressa como a multiplicação limitada,

Kaveh

e uma definição explícita de multiplicação limitada em termos de

recursão também pode ser encontrada nos livros didáticos.

μ

$\mu$

Kaveh

@ Kaveh sim, a mesma idéia implementada em “Uma introdução aos teoremas de Godel”, de P. Smith. As codificações e a aplicação do operador de minimização são fornecidas lá. A parte complicada é como gerar a "tabela" como você escolhe. Smith pulou. Parece que vou ter que pensar mais sobre isso em vez de esperar por soluções aqui;) Pelo menos, obrigado por sua aprovação da abordagem geral.

Artem Pelenitsyn

A tabela é apenas uma sequência finita em que as entradas são indexadas pelo resultado de uma função de emparelhamento.

em que

μ 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)$ é o rhs da equação para

A c k (x, y)

$Ack(x,y)$

Kaveh

Respostas:

Quebrar a função Ackermann até os operadores elementares seria realmente muito demorado, mas aqui está um esboço:

Observe que ao calcular recursivamente, em qualquer ponto do cálculo, você está lidando com uma expressão da forma . uma função de emparelhamento bijetivo com inverso , podemos codificar esse estado como $A(m,x)$ $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$ $p$ $(\pi_1,\pi_2)$ (apenas no caso ). Em seguida, podemos definir a função de avaliação em uma etapa, considerando um 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))))$

Você obtém a função de avaliação n-step usando recursão primitiva:

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

Finalmente, envolva a recursão em torno de para encontrar o ponto em que chegamos ao estado da forma - será . $\mu$ $E$ $p(z,0)$ $z$ $A(m,x)$

Klaus Draeger
fonte

Obrigado! Mais uma pergunta (talvez bastante ingênua, desculpe): definições semelhantes à correspondência de padrões (f (0) = ..., f (n + 1) = ...) amplamente utilizadas, mas duvido que sejam realmente permitidas pelo definição de função mu-recursiva. São eles?

Artem Pelenitsyn

Este tipo de caso distinção (por exemplo, que definem

por

) é apenas um caso especial de recursão primitiva que realmente não usa o valor anterior. No cálculo de

, você usaria adicionalmente funções auxiliares e os inversos

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

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

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

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
fonte

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