Lista de Exercícios 6 -AOC2

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
 Teoria da Computação
Lista de Exercícios 6
Prof​a​ Simone André da Costa 
 
 
Exercícios do Capítulo 3 - Uma introdução à Teoria da Recursão 
1. 
a. Para , qual resultado de ?(n, ) mj m = n2 + 2 + 3 (3, )j 5 
b. Desejamos computar o valor da função Comp para certosh = j,[ p , ]31 p
3
2
 
 
argumentos. Qual é o valor de no caso dessa função ? Qual é o valor dem h 
 neste caso? Portanto quantos argumentos irá ter?k h 
c. Qual é o valor de = ​Comp ?(3, , 8)h 5 3 j, (3, , 8)[ p , ]31 p
3
2
 
 5 3 
 
2. 
a. Desejamos computar o valor da função Comp para certosh = Soma,[ p , ]43 p
4
4
 
 
argumentos. Qual é o valor de no caso dessa função ? Qual é o valor dem h 
 neste caso? Portanto quantos argumentos irá ter?k h 
b. Qual é o valor de = ​Comp ?(3, , , 2)h 5 0 2 Soma, (3, , , 2)[ p , ]43 p
4
4
 
 5 0 2 
c. Para . Desejamos computar o valor da função Pr(n, ) mj m = n2 + 2 + 3 h = j,[
Comp Qual é a função que serve de neste caso? Qual é aSoma,[ p , ]].43 p
4
4
 
 f 
função ? Neste , qual será o valor de ? (Dica: Note que é o número deg h k k 
argumentos de .)f 
d. Qual é o resultado de alterando apenas o último argumento, ?h (3, , )h 5 0 
? ? ?(3, , )h 5 1 (3, , )h 5 2 (3, , )h 5 3 
 
3. 
a. Se , qual resultado de ?(n , , )j 1 n2 n3 = n1 · n2 + n3 (6, , )j 0 7 
b. Desejamos computar o valor da função ​Comp para certosSoma,[ j, ]p33
 
 
argumentos. Qual é o valor de no caso dessa função ? Qual é o valor dem h 
 neste caso? Portanto quantos argumentos irá ter?k h 
c. Qual é a função que serve de neste caso? Qual é a função ? E a ?f g1 g2 
d. Qual e o valor de = ​Comp ? Qual é o valor de(6, , )h 0 7 Soma,[ j, ](6, , )p33 0 7
 
 
 = ​Comp ? (Esses valores particulares são(6, , 4)h 1 1 Soma,[ j, ](6, , 4)p33 1 1
 
 
úteis para o exercício 4 abaixo.) 
 
4. 
a. De novo, para como antes. Desejamos computar o(n , , )j 1 n2 n3 = n1 · n2 + n3 
valor da função ​Pr Comp aplicando argumentossucc,[ Soma,[ j, ]]p33
 
 
pequenos. Qual é o valor de ​dessa função Pr Compf h = succ,[
? Qual é o valor de neste caso? E o ?Soma,[ j, ]]p33
 
 k g 
b. Qual é o valor de = ​Pr​[​succ​, ​Comp ?(6, )h 0 Soma, (6, )[ j, ]]p33
 
 0 
c. Qual é o valor de = ​Pr​[​succ​, ​Comp ?(6, )h 1 Soma, (6, )[ j, ]]p33
 
 1 
d. Qual é o valor de = ​Pr​[​succ​, ​Comp ?(6, )h 2 Soma, (6, )[ j, ]]p33
 
 2 
 
5. 
Calcule as expressões seguintes. Em todos os casos a resposta deve ser um 
número natural. 
a. Comp p , , ucc] (9)[ 22 C
1
0 s
 
 
b. (8, 5, 3, 9, , )p62 4 2 7 1 1 
c. Comp Comp Compsucc,[ succ,[ succ, ]]] (9)[ C10
 
 
d. Pr Comp,[p22 succ , ]](6, 5, )[ p
4
4 3 2 
 
6. 
Explique por que ​Comp ​de fato não nomeia nenhuma função.p , , ucc][ 32 C
1
0 s 
 
7. 
Calcule as expressões seguintes. Em todos os casos a resposta deve ser um 
número natural. Assumindo que é uma função de multiplicação bináriaultm 
usual definida por . Também assuma que é umault(n, )m m = n · m omas 3 
função de adição ternária de números naturais, isto é. 
.oma (n, , )s 3 m k = n + m + k 
a. Comp succ, ] (7, 4, )[ p31
 
 1 8 
b. Comp (7, 4, )[mult, , ]p32 p
3
2
 
 1 8 
c. Comp Compsucc,[ (7, 4, )[mult, , ]p32 p
3
2
 
 1 8 
d. Pr (7, )[succ, ]soma 3
 
 2 
 
8. 
Desejamos verificar que várias outras funções úteis são recursivas primitivas. 
Preencha as lacunas abaixo de maneira a completar as demonstrações de que 
as funções em questão são recursivas primitivas. Claro, nós utilizaremos 
livremente funções que já se provou serem recursivas primitivas. 
a. Proposição.​ A função ​ant​ definida por 
 
é recursiva primitiva. Note que ​ant​ é a função antecessor usual exceto que o 
antecessor de 0 agora é não −1, mas o próprio 0. 
Prova​. A função ​ant​ pode ser definida por 
(i)​ ​ant​(0) = 0 
(ii)​ ​ant​(​m​ + 1) = (m, ant(m))p21 
Mas isso mostra que ​ant​ é recursiva primitiva, já que na primeira equação 0 
pode ser escrito como . Tomando ​k​ = 0 no esquema B da definição 3.3,()C00 
nós temos que ​ant​ é Pr[​ ​, ​ ​]. 
b. Proposição.​ A função definida por 
 
é recursiva primitiva. Note que ​monus​ é como a subtração usual, exceto que 
valores negativos são bloqueados: ​monus​(4, 7) é igual a 0. Às vezes será 
conveniente escrever ​monus​(​n​, ​m​) como ​n​ − ​m​. 
Prova​. Nós temos as seguintes equações de recursão: 
(i)​ ​monus​(​n​, 0) = ​n 
(ii)​ ​monus​(​n​, ​m​ + 1) = nt(monus(n, m))a 
Estas podem ser reescritas como 
(i)​ ​monus​(​n​, 0) = ​ ​(​n​) 
(ii)​ ​monus​(​n​, ​m​ + 1) = nt(p (n, m, monus(n, m)))a 33 
 = Comp ant, p ](n, m, monus(n, m))[ 33 
o que mostra que ​monus​ é Pr[​ ​, ​ ​]. Portanto, ​monus​ é 
recursiva primitiva. 
c. Proposição.​ A função (unária) ​sinal​ definida por 
 
é recursiva primitiva. 
Prova​. Note que ​sinal​(​n​) = ​monus​(1, ​monus​(1, ​n​)). (Verifique isso para 
 
 e , por exemplo.) Mas tudo à direita aqui é recursivo primitivo. 0n = 3n = 
Já que 1 é , isso dá(n)C11 
sinal​(​n​) = ​monus (n), monus((C11 n)), 
 = ​monus (C (n), n), monus((p21
1
1 n)), 
 ​= Comp[​ ​, ​ ​, ​ ​] C (n), n)( 11 
 ​= Comp[​ ​, ​ ​, ​ ​] C (n), p (n))( 11 11 
 ​= Comp[Comp[​ ​, ​ ​, ​ ​] C , p ](n), 11 11 
 
9. 
Mostre que a função unária é recursiva primitiva.(n)f = n2