Resolução dos exercícios do terceiro capítulo do livro Computability, Complexity, and Languages. Fundamentals of Theoretical Computer Science.

Pág. 43, questão 1. Let C be a PRC class, and let g1, g2, g3, g4 belong to C. Show that if:

  • h1(x,y,z) = g1(z,y,x),
  • h2(x) = g2(x,x,x), and
  • h3(w,x,y,z) = h1(g3(w,y),z, g4(2,g4(y,z)))

then h1, h2, h3, also belong to C.

Resposta: Colocando as funções na forma canônica:

  • h1(x,y,z)=g1(z,y,x)=g1(u33(x,y,z),u23(x,y,z),u13(x,y,z))
  • h2(x)=g2(x,x,x)=g2(u11(x),u11(x),u11(x))
  • h3(w,x,y,z)=h1(g3(w,y),z, g4(2,g4(y,z)))=h1(g3, (w,y),u44(w,x,y,z), g3, (w,x,y,z))

onde g3, (w,x,y,z) = g3(u14(w,x,y,z), u34(w,x,y,z),) g4, (w,x,y,z) = g4(dois(w,x,y,z), g4,, (w,x,y,z)) dois(w,x,y,z) = s(s, s, (w,x,y,z)) s, (w,x,y,z) = s(n, (w,x,y,z), n’(w,x,y,z))=n(u44(w,x,y,z)) g4,, (w,x,y,z) = g4(u44(w,x,y,z),u44(w,x,y,z))

Pág. 43, questão 2. Show that the class of all total functions is a PRC class.

Resposta: Seja φ o conjunto de todas as funções totais. Primeiro temos que mostrar que as funções iniciais pertencem a φ.

  1. s(x) = x+1 é uma função total, portanto pertence φ .
  2. n(x) = 0 é uma função total, portanto pertence φ.
  3. uin(x1,..,xn)=xi1 ≤ i ≤ n é uma função total portanto pertence a φ.

Como na composição de funções totais obtemos uma função total e o mesmo acontece com a recursão, então φ pertence a PRC. (*incompleto*)

Pág. 43, questão 3. Let n ≥ 0 be some given number, and let C be a class of total functions of no more than n variables. Show that C is not a PRC class.

Resposta: Em uma classe de funções totais com não mais que n variáveis eu não consigo fazer a projeção uin+1(x,x,y,z).

Pág. 44, questão 4. Let C be a PRC class, let h belong to C, and let f(x) = h(g(x)) and g(x) = h(f(x)) Show that f belongs to C if and only if g belongs to C.

Resposta: Para provar que f ∈ C ↔ g ∈ C vamos em duas partes:

  1. f ∈ C → g ∈ C: Por hipótese vamos admitir que f ∈ C. Sabemos que g(x) = h(f(x)), e como g(x) foi construída usando uma operação de composição/recursão sob duas formulas que pertencem a C então g(x) também pertence a C, já que uma classe PRC é fechada para composição.
  2. f ∈ C ← g ∈ C: Por hipótese vamos admitir que g ∈ C. Da mesma maneira, sabemos que f(x) = h(g(x)), e como f(x) foi construída usando uma operação de composição/recursão sob duas formulas que pertencem a C então f(x) também pertence a C.

Pág. 44, questão 5. Prove Corollary 3.4 directly from Theorems 1.1, 2.2, 2.2 and the proof of Theorem 3.1.

Resposta: O corolário 3.4 diz que toda função primitiva recursiva é computável. Uma função é primitiva recursiva se ela pode ser obtida das funções iniciais através de um número finito de aplicações de composição e recursão. Pelo teorema 3.1 sabemos que as funções iniciais são computáveis. Os teoremas 2.1 e 2.2 mostram como construir os programas que para funções obtidas por composição ou recursão de outras funções computáveis. Suponha que eu tenha uma função f que é primitiva recursiva. Pela definição, f pode ser obtida das funções iniciais por um número finito de aplicações de composição e recursão. Para escrever um programa de f, eu uso o seguinte procedimento:

  • Para cada aplicação de recursão ou composição eu utilizo os teoremas 2.1 ou 2.2 para escrever o programa.
  • Quando eu precisar escrever o programa de uma função inical, eu uso o procedimento descrito na prova do teorema 3.1.

Pág. 47, questão 1. Give a detailed argument that xy, p(x), and xy are primitive recursive.

Resposta: Escrevendo essas funções na forma recursiva canônica de forma a mostrar que elas são definidas através de composição e recursão prova que elas são recursivas primitivas.

Pág. 47, questão 2. Show that for each k, the function f(x) = k is primitive recursive.

Resposta: Seja f i(x) = i. A função f(x) que sempre retorna a constante zero é primitiva recursiva e é: f 0(x) = 0. Por hipótese de indução vamos supor que para uma constante w menor que k, f w(x) é primitiva recursiva. Vamos então definir f k(x) como: f k(x) = f w(x) + 1 Como a função de soma é primitiva recursiva, f k(x) também é primitiva recursiva já que foi composta através da composição de outras duas funções primitivas recursivas.

Pág. 47, questão 3. Prove that if f(x) and g(x) are primitive recursive functions, so is f(x) + g(x).

Resposta: Por hipótese, seja s(x,y) a função x+y, que é uma função recursiva primitiva. Podemos escrever f(x)+g(x) através de s como s(f(x),g(x)). Como f(x), g(x) e s(x,y) são funções recursivas primitivas então f(x)+g(x) também são pois as funções recursivas primitivas são fechadas para composição.

Pág. 47, questão 4. Without using x + y as a macro apply the constructions in the proofs of Theorems 1.1, 2.2, and 3.1 to give an F program that computes x.y. Pág. 47, questão 5. For any unary function f(x), the nth iteration of f, written f n, is

fn(x) = f(…f(x)…),

where f is composed with itself n times on the right side of the equation. (Note that f 0(x) = x.) Let lf(n, x) = f n(x). Show that if f is primitive recursive, then lf is also primitive recursive.

Resposta: Vamos provar que se f é uma função primitiva recursiva então lf também é primitiva recursiva. Então por hipótese, vamos supor que f é uma função primitiva recursiva. lf (0,x) =f(x) A função lf (0,x) é primitiva recursiva já que f é primitiva recursiva por hipótese. Por indução em n supomos que lf é primitiva recursiva até n-1. Podemos definir lf como: lf (n,x) = f(lf (n-1,x)) Logo lf é primitiva recursiva já que foi definida com a composição e recursão de funções primitivas recursivas.

Pág. 47, questão 6.* (a) Let E(x) = 0 if x is even, E(x) = 1 if x is odd. Show that E(x) is primitive recursive.

Resposta: E(0) = 0 E(x) = ~E(x-1) E(x) foi construída usando somente operações que são primitivas recursivas através composição e recursão, logo E(x) também é primitiva recursiva.

(b) Let H(x) = x/2 if x is even, (x – 1)/2 if x is odd. Show that H(x) is primitive recursive.

Resposta: H(x) = E(x/2)·x/2+E((x-1)/2)·(x-1)/2 (se eu tivesse divisão)

Pág. 47, questão 7.* Let f(0) = 0, f(1) = 1, f(2) = 22, f(3) = 33^3 = 327, etc. In general, f(n) is written as a stack n high, of n‘s as exponents. Show that f is primitive recursive.

Resposta: p(x,1) = x p(x,y) = xp(x,y-1) Fica claro que p é primitivo recursivo pois é definida apenas através de funções primitivas recursivas usando composições e recursões. Podemos definir agora f como: f(0) = 0 f(x) = p(x,x) Pelo mesmo argumento anterior, f é primitiva recursiva.

Pág. 48, questão 8. Let k be some fixed number, let f be a function such that f(x + 1) < x + 1 for all x, and let

h(0) = k h(t+1) = g(h(f(t+1))) Show that if f and g belong to some PRC class C, then so does h. [Hint: Define f ‘(x)=mint≤xf ‘(x)=0. See Exercise 5 for the definition of f’(x).] Pág 48, questão 9. Let g(x) be a primitive recursive function and let f(0,x)=g(x), f(n+1,x)=f(f,f(f,x)). Prove that f(n,x) is primitive recursive. Pág 51, questão 1. Let us call a predicate trivial if it is always TRUE or always FALSE. Show that no nontrivial predicates belong to COMP (see Exercise 4.10 for the definition of COMP). Pág 54, questão 1. Let f(x)=2 if x is a perfect square; f(x) =2x+1 otherwise. Show that f is primitive recursive.

Resposta: Seja R o predicado que retorna 1 quando x é um quadrado perfeito e 0 caso contrário: R(x)=(∃w)x(w·w = x) É fácil ver que R é primitivo recursivo. Vamos construir agora f(x) a partir de R através de uma composição: f(x) = 2·x + R(x)

Pág 54, questão 1. Let σ(x) be the sum of the divisors of x if x≠0; σ(0) = 0 [e.g., σ(6) = 1+2+3+6 = 12]. Show that σ(x) is primitive recursive.

Resposta: σ(x) = Σxi=1(i|x) · i Como σ(x) está definida através de composições de funções primitivas recursivas, então pela própria definição de funções primitivas recursivas, σ(x) é também uma função primitiva recursiva.

Pág 54, questão 3. Let π(x) be the number of primes that are ≤ x. Show that π(x) is primitive recursive.

Resposta: π(x) = Σxi=1prime(i) Analogamente à questão anterior, π(x) é uma função primitiva recursiva.

continua em tdc-trabalho2 parte 2