Teorema da recursividade de Kleene

Em teoria da computabilidade, o teorema da recursão de Kleene é um par de resultados fundamentais sobre a aplicação de funções computáveis para suas próprias descrições. Os teoremas foram inicialmente provados por Stephen Kleene em 1938.

Os dois teoremas da recursão podem ser aplicados para construir pontos fixos de certas operações sobre funções computáveis, para gerar quines, e para construir funções definidas através de definições recursivas.

O segundo teorema da recursão

O Segundo teorema da recursão está intimamente relacionado à definição das funções computáveis que usam Recursividade. Por ser mais conhecida que o primeiro teorema da recursão, este é, algumas vezes, apenas chamada de teorema da recursão. Sua declaração refere-se à numeração de Gödel φ das funções recursivas parciais, no qual a função correspondente a um índice e é $\varphi _{e}$.

O segundo teorema da recursão. Se F é uma função computável total então existe um índice e tal que $\varphi _{e}\simeq \varphi _{F(e)}$.

Aqui $\varphi _{e}\simeq \varphi _{F(e)}$ significa que, para cada n, ou ambos $\varphi _{e}(n)$ e $\varphi _{F(e)}(n)$ estão definidos, e seus valores são iguais, ou senão ambos estão indefinidos.

Exemplo

Suponha que g e h são funções computáveis totais que são usadas na definição recursiva para uma função f:

$f(0,y)\simeq g(y),\,$

$f(x+1,y)\simeq h(f(x,y),x,y),\,$

Essa definição recursiva pode ser convertida em uma função computável F(e) t que pega um índice para um programa e e retorna um índice F(e) tal que

$\varphi _{F(e)}(0,y)\simeq g(y),\,$

$\varphi _{F(e)}(x+1,y)\simeq h(\varphi _{e}(x,y),x,y).\,$

Nesse contexto, um ponto fixo de F é um índice e tal que $\varphi _{e}\simeq \varphi _{F(e)}$; a função computada por tal e vai ser a solução para as equações recursivas originais. O teorema da recursividade estabelece a existência de tal ponto fixo, assumindo que F é computável, e é algumas vezes chamada de teorema do ponto fixo (de Kleene) por essa razão. O teorema não garante que e é um índice para o menor ponto fixo das equações recursivas; este é o papel do primeiro teorema da recursividade descrito a seguir.

Prova do segundo teorema da recursão

A prova usa uma função computável h, como definida a seguir. Dado um número natural x, h tem como saída o índice da função parcialmente computável que executa a seguinte computação:

Dada uma entrada y, primeiro tente computar $\varphi _{x}(x)$. Se a computação retornar como saída e, então compute $\varphi _{e}(y)$ e retorne seu valor, se existir algum.

Desta forma, para todo x, se $\varphi _{x}(x)$ para, então $\varphi _{h(x)}=\varphi _{\varphi _{x}(x)}$, e se $\varphi _{x}(x)$ não para então $\varphi _{h(x)}\,$ também não para; isso é denotado $\varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}$. A função h pode ser construída a partir da função parcialmente computável $g(x,y)=\varphi _{\varphi _{x}(x)}(y)$ e o teorema teorema s m n: para cada x, $h(x)$ é o índice de um programa que computa a função $y\mapsto g(x,y)$.

Para completar a prova, seja F alguma função computável total, e construa h como acima. Seja e um índice da composição $F\circ h$, que é uma função computável total. Então $\varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}$ por definição de h. Contudo, como e é um índice de $F\circ h$, $\varphi _{e}(e)=(F\circ h)(e)$, e portanto $\varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}$. Por transitividade de $\simeq$, isso significa que $\varphi _{h(e)}\simeq \varphi _{F(h(e))}$. Por isso $\varphi _{n}\simeq \varphi _{F(n)}$ para $n=h(e)$.

Aplicação para quines

Uma interpretação informal para o Segundo teorema da recursão é que qualquer função computável parcial pode adivinhar um índice para si próprio.Isso segue do seguinte corolário do teorema (Cutland 1980: p. 202).

Corolário. Para qualquer função recursiva Q(x,y) existe um índice p tal que $\varphi _{p}\simeq \lambda y.Q(p,y)$.

O corolário é provado deixando $F(p)$ ser uma função que gera um índice para $\lambda y.Q(p,y)$.

O corolário mostra que para qualquer função computável Q de dois argumentos existe um programa que pega um argumento e avalia Q com o índice desse próprio programa como o primeiro argumento e o dado argumento como segundo. Note que esse programa é também capaz de gerar seu índice a partir de informação embutida no programa; ele não precisa de nenhum recurso externo para achar o índice.

Um exemplo clássico é a função Q(x,y) = x. O índice correspondente p, nesse caso, produz uma função computável que tem como saída seu próprio índice quando aplicado a qualquer valor (Cutland 1980: p. 204). Quando expresso como programas de computadores, tais índices são conhecidos como quines.

O exemplo que se segue em Lisp ilustra como o p no corolário pode ser efetivamente produzido a partir da função Q. A função s11 no código é a função do nome produzido por teorema s m n.

; Q pode ser mudado para qualquer função de dois argumentos.
(setq Q '(lambda (x y) x))
(setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y))))
(setq n (list 'lambda '(x y) (list Q (list s11 'x 'x) 'y)))
(setq p (eval (list s11 n n)))

; O resultado da seguinte expressão deve ser o mesmo.
; φ_p(nil)
(eval (list p nil))

; Q(p, nil)
(eval (list Q p nil))

O primeiro teorema da recursão

O primeiro teorema da recursão está relacionado com pontos fixos determinados operadores de enumeração, que são um análogo computacional de definições indutivas. Um operador de enumeração é um conjunto de pares (A,n) onde A é um (código para um) conjunto finito de números e n é um único número natural. Frequentemente, n vai ser visto como um código para um par de números naturais ordenados, particularmente quando funções são definidas através de operadores de enumeração. Tais operadores são de central importância para o estudo da redução por enumeração.

Cada operador de enumeração F determina uma função de conjuntos de números naturais em conjuntos de naturais dado por

$\Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.$

Um operador recursivo é um operador de enumeração que, quando dado de uma função recursiva parcial, sempre retorna um gráfico de uma função recursiva parcial.

Um ponto fixo de um operador de enumeração Φ é um conjunto F tal que Φ(F) = F. O primeiro teorema da enumeração mostra que pontos fixos podem ser efetivamente obtidos se o próprio operador de enumeração for computável.

Primeiro teorema da recursão. As seguintes afirmações são sustentadas.

1. 1. Para operador de enumeração computável F existe um conjunto recursivamente enumerável F tal que F(F) = F e F é o menor conjunto com essa propriedade.
2. 2. Para qualquer operador recursivo ? existe uma função computável parcial f tal que ?(f) = f e f é a menor função computável parcial com essa propriedade.

Exemplo

Como o segundo teorema da recursão, o primeiro teorema da recursão pode ser usado para obter funções que satisfazem sistemas de equações recursivas. Para aplicar o primeiro teorema da recursividade, as equações recursivas precisam primeiramente ser remodeladas como operadores recursivos.

Considere as equações recursivas para a função fatorial f:

f(0) = 1,

f(n+1) = (n + 1) · f(n).

TO operador recursivo correspondente Φ vai ter informação que diz como obter o valor de f a partir de valores anteriores. Contudo, o operador recursivo vai de fato definir o gráfico de f. Primeiro, Φ vai conter o par $(\varnothing ,(0,1))$. Isso indica que f(0) é inequivocamente 1, e assim o par (0,1) está no gráfico de f.

Após isso, para cada n e m, Φ vai conter o par $(\{(n,m)\},(n+1,(n+1)\cdot m))$. Isso indica que, se f(n) é m, então f(n + 1) é (n + 1)m, logo o par (n + 1, (n + 1)m) está no gráfico de f. Diferentemente do caso base f(0) = 1, o operador recursivo necessita de alguma informação sobre f(n) antes de definir o valor para f(n + 1).

O primeiro teorema da recursão (em particular a parte 1) afirma que existe um conjunto F tal que Φ(F) = F. O conjunto F vai consistir inteiramente de pares ordenados de números naturais, e vai ser o grafo da função fatorial f, como desejado.

A restrição para equações recursivas que podem ser remodeladas como operadores recursivos asseguram que as equações recursivas realmente definem o último ponto fixo. Por exemplo, considere o conjunto de equações recursivas:

g(0) = 1,

g(n + 1) = 1,

g(2n) = 0.

Não existe nenhuma função g que satisfaça essas equações, porque elas implicam g(2) = 2 e também implicam g(2) = 0. Desta forma não existe nenhum ponto fixo g que satisfaça essas equações recursivas. É possível fazer um operador de enumeração correspondente a essas equações, mas ele não vai um operador recursivo.

Esboço da prova do primeiro teorema da recursão

A prova da parte 1 do primeiro teorema da recursão não é obtida através da iteração do operador de enumeração Φ começando com um conjunto vazio. Primeiramente, a sequência F_k é construída, para $k=0,1,\ldots$. Seja F₀ o conjunto vazio. Procedendo indutivamente, para cada k, faça F_{k + 1} ser $F_{k}\cup \Phi (F_{k})$. Finalmente, F é considerado como sendo $\bigcup F_{k}$. O resto da prova consiste na verificação que F recursivamente enumerável e é o último ponto fixo de Φ. sequência F_k usada na prova corresponde a cadeia de Kleene na prova do teorema do ponto fixo de Kleene.

A segunda parte do primeiro teorema da recursividade segue a partir da primeira parte. A suposição de que Φ é um operador recursivo é usado para mostrar que o ponto fixo de Φ é um gráfico de uma função parcial. O ponto chave é que se o ponto fixo F não é o gráfico de uma função, então existe algum k tal que F_k não é o gráfico da função.

Referências

• Cutland, N.J., Computability: An introduction to recursive function theory, Cambridge University Press, 1980. ISBN 0-521-29465-7
• Kleene, Stephen, "On notation for ordinal numbers," The Journal of Symbolic Logic, 3 (1938), 150–155.
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1