Expresse cada uma das funções abaixo em termos de S, P ou s usando apenas + , - e ○ (Por exemplo, a resposta para o item a) é P circ s ).
f(t)=2^2^t (Nota: a^b^c sempre significa a^(b^c); esta convenção é adotada porque (a^b)^c pode ser escrita mais simplesmente como a^b c.)

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.

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)))

Exercícios relacionados