Resumo do capítulo 2 do livro Computability, Complexity, and Languages. Fundamentals of Theoretical Computer Science.

Composição:

  • Forma canônica:
    h(x1,…, xn) = f(g1(x1,…, xn),…, gk(x1,…, xn))
  • Se h é obtida pelas funções (parcialmente) computáveis f, g1,…, gk usando composição, então h é (parcialmente) computável.

Recursão:

  • Forma canônica:
    h(x1,…, xn,0)=f(x1,…, xn)
    h(x1,…, xn,t+1) = g(t, h(x1,…, xn,t), x1,…, xn)
  • Se h é obtida pelas funções (parcialmente) computáveis f e g, então h é (parcialmente) computável.

Classes PRC:

  • Funções iniciais:
    s(x)=x+1
    n(x)=0
    uni(x1,…, xn)=xi, 1 ≤ i ≤ n
  • Uma classe de funções é PRC se as funções iniciais pertecem a ela e ela éfechada para a composição e recursão.
  • A classe de funções computáveis é uma classe PRC.
  • Uma função é primitiva recursive se ela pode ser obtida a partir das funções iniciais usando um número finito de composições e recursões.
  • A classe de funções primitivas recursivas é PRC.
  • Uma função é primitiva recursiva se e somente se ela pertence a toda classe PRC.
  • Toda função primitiva recursiva é computável.

Exemplos de funções primitivas recursivas:

  • x+y
  • x*y
  • x!
  • xy
  • p(x) = x-1 se x≠0; p(x)=0 se x =0.
  • x ∸ y =0 se y ≥ x, senão x – y
  • |x-y|
  • α(x)=1, se x==0. α(x)=0, caso contrário.

Predicados primitivos recursivos:

  • x=y
  • x≤y
  • x<y
  • Se P(x1,…, xn) ,g, h pertencem a uma mesma classe PRC então
    f(x1,…, xn) = g(x1,…, xn) se P(x1,…, xn) ou f(x1,…, xn) =h(x1,…, xn) se caso contrário,
    também pertence a classe.

Quantificadores:

  • Se f(t, x1,…, xn) pertence a uma classe C, PRC, então:
    g(y, x1,…, xn)=∑t=0y f(t, x1,…, xn)
    e
    h(y, x1,…, xn)=∏t=0y f(t, x1,…, xn)
    também pertencem a C.
  • Se P(t,x1,…, xn) é um predicado que pertence a alguma classe PRC, então os predicados:
    (∀t)≤yP(y, x1,…, xn) e (∃t)≤yP(t, x1,…, xn) pertencem a mesma classe PRC.
  • y|x (y é divisor de x) é um predicado primitivo recursivo.
  • Prime(x) é um predicado primitivo recursivo.

Minimalização:

  • Se P(y, x1,…, xn) pertence a alguma classe PRC e f(t, x1,…, xn) = mint≤yP(y, x1,…, xn) então f também a PRC.
  • ⌊x/y⌋ é primitivo recursivo.
  • R(x,y) é primitivo recursivo (resto).
  • pn é primitivo recursivo (n-éssimo número primo).
  • Se P(y, x1,…, xn) é um predicado computável e se g(x1,…, xn) = minyP(y, x1,…, xn) então g é parcialmente computável.

Funções de pareamento de número de Gödel

  • <x,y> = 2x(2y+1)-1. Para cada par <x,y>=z existe somente um z que satisfaz a equação.
  • Se <x,y>=z então definimos x=l(z) e y=r(z), l e r são funções primitivas recursivas.
  • Seja a seguinte sequência [a1,..., an]=∏in piai

    • , para cada n a função [a] é primitiva recursiva.

  • c