função μ-recursiva

Em lógica matemática e ciência computacional, as funções μ-recursivas são uma classe de funções parciais de números naturais para números naturais que são “computáveis” num sentido intuitivo. De fato, na teoria da computação é mostrado que as funções μ-recursivas são precisamente as que podem ser computadas por máquinas de Turing. As funções μ-recursivas são intimamente relacionadas às funções recursivas primitivas, e sua definição indutiva se baseia nestas funções recursivas primitivas. No entanto, nem toda função μ-recursivas é uma função primitiva recursiva – o mais famoso exemplo é a função de Ackermann.

Outras classes equivalentes de funções são as funções λ-recursivas e as funções que podem ser computadas através dos algoritmos de Markov.

O conjunto de todas as funções recursivas é conhecido como R (Complexidade R) na teoria da complexidade computacional.

Definição

As funções μ-recursivas (ou funções μ-recursivas parciais) são funções parciais que recebem tuplas finitas de números naturais e retornam um único número natural. Elas são a menor classe de funções parciais que inclui as funções iniciais e é fechada sob a composição, recursão primitiva e o operador μ.

A menor classe de funções incluindo as funções iniciais e fechadas sob composição e recursão primitiva (i.e. sem minimização) é a classe de funções recursivas primitivas. Enquanto todas as funções primitivas recursivas são totais, isto não é verdadeiro nas funções parciais recursivas, por exemplo, a minimização da função sucessor é indefinida. O conjunto de funções recursivas totais é um sub-conjunto das funções parciais recursivas e é um super-conjunto das funções primitivas recursivas; funções como a Função de Ackermann podem ser provadas como sendo totalmente recursivas, e não primitivas.

As primeiras três funções são chamadas de “iniciais” ou “básicas”: (Na seguinte subscrição por Kleene (1952) p. 219. Para saber mais sobre alguns dos vários simbolismos encontrados na literatura, ver Simbolismo abaixo.)

1. Função constante: Para cada número natural $n\,$ e cada $k\,$:

   $f(x_{1},\ldots ,x_{k})=n\,$.
   Definições alternativas usam composições da função sucessor e usa uma função zero, que sempre retorna zero, no lugar da função constante.

2. Função sucessor S:

   $S(x){\stackrel {\mathrm {def} }{=}}f(x)=x+1\,$

3. Função projeção $P_{i}^{k}$ (também chamada de Função Identidade $I_{i}^{k}$): Para todos números naturais $i,k\,$ tal forma que $1\leq i\leq k$:

   $P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$.

4. Operador de Composição $\circ \,$ (também chamado de operador de substituição): Dada uma função m-ária $h(x_{1},\ldots ,x_{m})\,$ e funções m k-ária $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$:

   $h\circ (g_{1},\ldots ,g_{m}){\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))\,$.

5. Operador de recursão primitiva $\rho \,$: Dada a função k-ária $g(x_{1},\ldots ,x_{k})\,$ e função k+2 -ária $h(y,z,x_{1},\ldots ,x_{k})\,$:

   ${\begin{aligned}\rho (g,h)&{\stackrel {\mathrm {def} }{=}}f(y,x_{1},\ldots ,x_{k})\quad {\rm {where}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(y+1,x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,\end{aligned}}$

6. Operador de Minimização $\mu \,$: Dada uma função total (k+1)-ária $f(y,x_{1},\ldots ,x_{k})\,$:

   ${\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z&{\stackrel {\mathrm {def} }{\iff }}\ \exists y_{0},\ldots ,y_{z}\quad {\rm {such\ that}}\\y_{i}&=f(i,x_{1},\ldots ,x_{k})\quad {\rm {for}}\ i=0,\ldots ,z\\y_{i}&>0\quad {\rm {for}}\ i=0,\ldots ,z-1\\y_{z}&=0\end{aligned}}$

Intuitivamente, minimização busca – começando a busca a partir de 0 e prosseguindo para cima—o menor argumento que causa a função retornar para zero; se não existir tal argumento, a busca nunca termina.

O operador de igualdade forte $\simeq$ pode ser usado para comparar funções μ-recursivas parciais. Isto é definido para todas as funções parciais f e g de modo que :$f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})$ se e somente se para qualquer escolha de argumentos ou ambas as funções são definidas e seus valores são iguais ou ambas as funções são indefinidas.

Equivalência com outros modelos de computabilidade

Na equivalência de modelos de computabilidade, uma paralela é desenhada entre Máquinas de Turing que não terminará para certas entradas e um resultado indefinido para aquela entrada na função parcial recursiva correspondente. O operador de pesquisa ilimitada não é definível pelas regras de recursão primitiva como aqueles que não fornecem um mecanismo para “loops infinitos” (valores indefinidos).

Teorema da forma normal

Um teorema da forma normal devido a Kleene diz que para cada k existem funções recursivas primitivas $U(y)\!$ e $T(y,e,x_{1},\ldots ,x_{k})\!$ tal que para qualquer função μ-recursiva $f(x_{1},\ldots ,x_{k})\!$ com variáveis livres k existe um e tal que:

$f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))$

O número e é chamado um índice ou número de Gödel para a função f. Uma consequência deste resultado é que qualquer função μ-recursiva pode ser definida usando uma única instância do operador μ aplicado a uma (total) função recursiva primitiva.

Minsky (1967) observa (assim como Boolos-Burgess-Jeffrey (2002) pp. 94–95) que U definido acima é em essência o μ-recursivo da Máquina de Turing universal: Para a construção de U é escrever a definição de uma função recursiva geral U(n, x) que interpreta corretamente o número n e computa apropriadamente a função de x. Para construir U diretamente envolveria essencialmente a mesma quantidade de esforço, e essencialmente, as mesmas ideias, assim como temos investido na construção da máquina de Turing universal. (itálico em original, Minsky (1967) p. 189)

Simbolismo

Um número de simbolismos diferentes é usado na literatura. Uma vantagem de usar o simbolismo é a derivação de uma função por distribuição dos operadores um dentro do outro é mais fácil de escrever de forma compacta. Nos exemplos seguintes, vamos abreviar a sequência dos parâmetros x1, ..., xn as x: Função constante: Kleene utiliza " Cqn(x) = q " e Boolos-Burgess-Jeffry (2002) (B-B-J) utiliza a abreviação " constn( x) = n ":

e.g. C₁₃⁷ ( r, s, t, u, v, w, x ) = 13

e.g. const₁₃ ( r, s, t, u, v, w, x ) = 13

Função sucessor: Kleene utiliza x' e S for "sucessor". Como "sucessor" é considerada primitiva, a maioria dos textos usa o apóstrofo como mostrado a seguir:

S(a) = a +1 =_def a', onde 1 =_def 0', 2 =_def 0 ' ', etc.

Função identidade: Kleene (1952) utiliza " Uin " para indicar a função identidade sobre as variáveis xi; B-B-J utiliza a função identidade idin sobre as variáveis x1 a xn:

U_iⁿ( x ) = id_iⁿ( x ) = x_i

e.g. U₃⁷ = id₃⁷ ( r, s, t, u, v, w, x ) = t

Operador de Composição (Substituição): Kleene utiliza em negrito Snm (não confundir com o S para “sucessor”!). O sub-expoente "m" refere ao mº da função "fm", enquanto que o expoente “n” refere-se à nº variável "xn": Se é dado h( x )= g( f₁(x), ... , f_m(x) )

h(x) = S_mⁿ(g, f₁, ... , f_m )

De maneira semelhante, mas sem o sub e o expoente, B-B-J mostram:

h(x')= Cn[g, f₁ ,..., f_m](x)

Recursão primitiva: Kleene utiliza o símbolo " Rn(passo de base, passo de indução) " onde n indica o número de variáveis, B-B-J usam " Pr(passo de base, passo de indução)(x)". Dado:

• Passo base: h( 0, x )= f( x ), e
• Passo indutivo: h( y+1, x ) = g( y, h(x,y),x )

Exemplo: definição da recursão primitiva de a + b:

• Passo base: f( 0, a ) = a = U₁¹(a)
• Passo indutivo: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U₂³( b, c, a )

R² { U₁¹(a), S [ (U₂³( b, c, a ) ] }

Pr{ U₁¹(a), S[ (U₂³( b, c, a ) ] }

Exemplo: Kleene dá um exemplo de como realizar a derivação recursiva de f(b,a) = b+a (note a reversão das variáveis a e b). Ele começa com 3 funções iniciais:

1. S(a) = a'
2. U₁¹(a) = a
3. U₂³( b, c, a ) = c
4. g(b, c, a) = S(U₂³( b, c, a )) = c'

5. Passo base: h( 0, a ) = U₁¹(a) Passo indutivo: h( b', a ) = g( b, h( b, a ), a ) Ele chega em:

a+b = R²[ U₁¹, S₁³(S, U₂³) ]

Ligações externas

• Stanford Encyclopedia of Philosophy entry

Bibliografia

• Stephen Kleene (1952) Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
• Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
• Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

On pages 210-215 Minsky shows how to create the µ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.