função μ-recursiva

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde dezembro de 2011).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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[editar | editar código-fonte]

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 \le i \le 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{align} 
             \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{align}
  6. Operador de Minimização \mu\,: Dada uma função total (k+1)-ária f(y, x_1, \ldots, x_k)\,:
    \begin{align}
          \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{align}

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 idéias, assim como temos investido na construção da máquina de Turing universal. (itálico em original, Minsky (1967) p. 189)

Simbolismo[editar | editar código-fonte]

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. C137 ( r, s, t, u, v, w, x ) = 13
e.g. const13 ( 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:

Uin( x ) = idin( x ) = xi
e.g. U37 = id37 ( 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( f1(x), ... , fm(x) )

h(x) = Smn(g, f1, ... , fm )

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

h(x')= Cn[g, f1 ,..., fm](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 = U11(a)
  • Passo indutivo: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U23( b, c, a )
R2 { U11(a), S [ (U23( b, c, a ) ] }
Pr{ U11(a), S[ (U23( 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. U11(a) = a
  3. U23( b, c, a ) = c
  4. g(b, c, a) = S(U23( b, c, a )) = c'

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

a+b = R2[ U11, S13(S, U23) ]

Links Externos[editar | editar código-fonte]

Referências

Bibliografia[editar | editar código-fonte]

  • 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.