Expresse cada uma das funções abaixo em termos de
ou
usando apenas + , - e ○ (Por exemplo, a resposta para o item a) é
).
(Nota:
sempre significa
; esta convenção é adotada porque
pode ser escrita mais simplesmente como
.)
Passo 1
O enunciado pede para escrever f(t)=2(2t) em termos dos construtores primitivos (projeção P, sucessor s e recursão S) usando só +, - e composição ○.
Passo 2
Primeiro vamos criar zero como função Z definindo Z = - ○ (P^1_1, P^1_1), pois Z(x)=x−x=0.
Em seguida a constante 1 é C1 = s ○ Z, já que C1(x)=s(Z(x))=0+1=1.
Em seguida a constante 1 é C1 = s ○ Z, já que C1(x)=s(Z(x))=0+1=1.
Passo 3
Precisamos de uma função que dobre o segundo argumento: D = + ○ (P^2_2, P^2_2), pois D(x,y)=y+y.
Passo 4
Definimos exp2 por recursão primitiva: exp2 = S(C1, D). Assim exp2(0)=1 e exp2(t+1)=D(t,exp2(t))=exp2(t)+exp2(t)=2⋅exp2(t), ou seja exp2(t)=2^t.
Passo 5
Finalmente, f = exp2 ○ exp2 dá f(t)=exp2(exp2(t))=2(2t).
Resposta
f = (S(C1, +\circ(P_22,P_22)))\circ(S(C1, +\circ(P_22,P_22)))