Question

A função de Ackerman, que leva N²
em N é uma função que cresce muito rapidamente.
Ela é dada por:
A(0, y) = 1 para todos y ∈ N
A(1, 0) = 2
A(x, 0) = x + 2 para x ≥ 2

A(x + 1, y + 1) = A (A(x, y + 1), y) para todos x ∈ N, y ∈ N
a) Encontre uma equação f(x) que descreva A(x, 1) para todo x ≥ 1
b) Encontre uma equação g(x) que descreva A(x, 2) para todo x ≥ 1
c) Calcule o valor de A(4, 3).

PRECISO DA REPOSTA HJ, ME AJUDEM

Answer 1

Temos as informações

( I )  A(0,y) = 1   para todo y

( II ) A(1,0) = 2

( III ) A(x,0) = x+2 para x ≥ 2

( IV) A(x + 1, y + 1) = A (A(x, y + 1), y)  para todo x,y.

a)

Já sabemos que A(0,1) = 1. Ou seja, f(0) = 1.

Usando y = 0 em ( IV ) temos:

A(x+1, 1) = A( A(x,1), 0)

f(x+1) = A( f(x), 0)    (V)

Para x = 0 temos

f(1) = A ( f(0), 0) = A(1,0) = 2

Logo, para x > 0 teremos f(x) ≥ 2. Usando  ( III ) na equação (V) teremos:

f(x+1) = f(x) + 2

Portanto:

f(x) = 2x se x ≥ 1

b)

Já sabemos que A(0,2) = g(0) = 1

Usando dessa vez y = 1 na equação ( IV ) temos:

A(x+1, 2) = A( A(x,2), 1)

g(x+1) = A( g(x), 1)

g(x+1) = f(g(x))  

Usando a expressão obtida no item anterior para f temos:

g(x+1) = 2g(x)

Logo:

g(x) = 2ˣ

c)

A(0,3) = 1

Usando (IV) para x = 0 e y = 2 temos:

A(1,3) = A ( A(0,3), 2) = A(1,2) = g(1) = 2

Usando (IV) para x = 1 e y = 2 temos:

A(2,3)  = A (A(1,3),2) = A(2,2) = g(2) = 4

Usando (IV) para x = 2 e y = 2 temos:

A(3,3) = A ( A(2,3),2) = A(4,2) = g(4) = 16

Usando (IV) para x = 3 e y = 2 temos:

A(4,3) = A (A(3,3),2) = A(16,2) = g(16) = 2¹⁶