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.
Índice
1 Definição
2 Equivalência com outros modelos de computabilidade
3 Teorema da forma normal
4 Simbolismo
5 Links Externos
6 Referências
7 Bibliografia
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{displaystyle n,}e cada k{displaystyle k,}
:
f(x1,…,xk)=n{displaystyle 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)=deff(x)=x+1{displaystyle S(x){stackrel {mathrm {def} }{=}}f(x)=x+1,}
- S(x)=deff(x)=x+1{displaystyle S(x){stackrel {mathrm {def} }{=}}f(x)=x+1,}
Função projeção Pik{displaystyle P_{i}^{k}}(também chamada de Função Identidade Iik{displaystyle I_{i}^{k}}
): Para todos números naturais i,k{displaystyle i,k,}
tal forma que 1≤i≤k{displaystyle 1leq ileq k}
:
Pik=deff(x1,…,xk)=xi{displaystyle P_{i}^{k}{stackrel {mathrm {def} }{=}}f(x_{1},ldots ,x_{k})=x_{i}}.
Operador de Composição ∘{displaystyle circ ,}(também chamado de operador de substituição): Dada uma função m-ária h(x1,…,xm){displaystyle h(x_{1},ldots ,x_{m}),}
e funções m k-ária g1(x1,…,xk),…,gm(x1,…,xk){displaystyle g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1},ldots ,x_{k})}
:
h∘(g1,…,gm)=deff(x1,…,xk)=h(g1(x1,…,xk),…,gm(x1,…,xk)){displaystyle hcirc (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 ρ{displaystyle rho ,}: Dada a função k-ária g(x1,…,xk){displaystyle g(x_{1},ldots ,x_{k}),}
e função k+2 -ária h(y,z,x1,…,xk){displaystyle h(y,z,x_{1},ldots ,x_{k}),}
:
- ρ(g,h)=deff(y,x1,…,xk)wheref(0,x1,…,xk)=g(x1,…,xk)f(y+1,x1,…,xk)=h(y,f(y,x1,…,xk),x1,…,xk){displaystyle {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}}}
- ρ(g,h)=deff(y,x1,…,xk)wheref(0,x1,…,xk)=g(x1,…,xk)f(y+1,x1,…,xk)=h(y,f(y,x1,…,xk),x1,…,xk){displaystyle {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 μ{displaystyle mu ,}: Dada uma função total (k+1)-ária f(y,x1,…,xk){displaystyle f(y,x_{1},ldots ,x_{k}),}
:
- μ(f)(x1,…,xk)=z⟺def ∃y0,…,yzsuch thatyi=f(i,x1,…,xk)for i=0,…,zyi>0for i=0,…,z−1yz=0{displaystyle {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}&>0quad {rm {for}} i=0,ldots ,z-1\y_{z}&=0end{aligned}}}
- μ(f)(x1,…,xk)=z⟺def ∃y0,…,yzsuch thatyi=f(i,x1,…,xk)for i=0,…,zyi>0for i=0,…,z−1yz=0{displaystyle {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}&>0quad {rm {for}} i=0,ldots ,z-1\y_{z}&=0end{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 ≃{displaystyle simeq }
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){displaystyle U(y)!}
- f(x1,…,xk)≃U(μyT(y,e,x1,…,xk)){displaystyle 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 |
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:
- S(a) = a'
- U11(a) = a
- U23( b, c, a ) = c
- 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 |
- Stanford Encyclopedia of Philosophy entry
Referências
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.
