# 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.)
* 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.
* Função sucessor S:
    $S(x){\stackrel {\mathrm {def} }{=}}f(x)=x+1\,$
* 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}$.
* 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}))\,$.
* 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}}$
* 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$_{13}$$^7$ ( r, s, t, u, v, w, x ) = 13
       e.g. const$_{13}$ ( 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$$^n$( x ) = id$_i$$^n$( x ) = x$_i$
    e.g. U$_3$$^7$ = id$_3$$^7$ ( 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$_1$(x), ... , f$_m$(x) )
       h(x) = S$_m$$^n$(g, f$_1$, ... , f$_m$ )
De maneira semelhante, mas sem o sub e o expoente, B-B-J mostram:
       h(x')= Cn[g, f$_1$ ,..., 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$_1$$^1$(a)
      * Passo indutivo: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U$_2$$^3$( b, c, a )
          R$^2$ { U$_1$$^1$(a), S [ (U$_2$$^3$( b, c, a ) ] }
          Pr{ U$_1$$^1$(a), S[ (U$_2$$^3$( 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:
   * S(a) = a'
   * U$_1$$^1$(a) = a
   * U$_2$$^3$( b, c, a ) = c
   * g(b, c, a) = S(U$_2$$^3$( b, c, a )) = c'
5. Passo base: h( 0, a ) = U$_1$$^1$(a) Passo indutivo: h( b', a ) = g( b, h( b, a ), a ) Ele chega em:
       a+b = R$^2$[ U$_1$$^1$, S$_1$$^3$(S, U$_2$$^3$) ]