Saltar para o conteúdo

função μ-recursiva

Origem: Wikipédia, a enciclopédia livre.

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.

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 e cada :
    .
    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:
  3. Função projeção (também chamada de Função Identidade ): Para todos números naturais tal forma que :
    .
  4. Operador de Composição (também chamado de operador de substituição): Dada uma função m-ária e funções m k-ária :
    .
  5. Operador de recursão primitiva : Dada a função k-ária e função k+2 -ária :
  6. Operador de Minimização : Dada uma função total (k+1)-ária :

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 pode ser usado para comparar funções μ-recursivas parciais. Isto é definido para todas as funções parciais f e g de modo que : 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 e tal que para qualquer função μ-recursiva com variáveis livres k existe um e tal que:

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)

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) ]

Ligações externas

[editar | editar código-fonte]

Referências

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