Funkcja Ackermanna.

[Molas.]

Funkcja Ackermanna określona jest następująco \(\displaystyle{ (i,j,k qslant 1}\) i naturalne\(\displaystyle{ )}\):

\(\displaystyle{ A(1,j,k)=j+k}\)
\(\displaystyle{ A(i+1,j,1)=j}\)
\(\displaystyle{ A(i+1,j,k+1)=A(i,j,A(i+1,j,k))}\)

Udowodnij, że \(\displaystyle{ A(3,j,k)=j^{k}}\), oblicz \(\displaystyle{ A(4,2,3).}\)

[Qń]

\(\displaystyle{ A(1,j,k)=j+k}\) (*)
\(\displaystyle{ A(i+1,j,1)=j}\) (**)
\(\displaystyle{ A(i+1,j,k+1)=A(i,j,A(i+1,j,k))}\) (***)

Znajdźmy najpierw wzór na \(\displaystyle{ A(2,j,k)}\). Mamy:
\(\displaystyle{ A(2,j,k) =(***)=A(1,j,A(2,j,k-1))=(*)=A(2,j,k-1) +j}\)
Ponieważ zaś \(\displaystyle{ A(2,j,1)=(**)=j}\), prosta indukcja pokazuje, że \(\displaystyle{ A(2,j,k)=kj}\) (****).

Mamy dalej:
\(\displaystyle{ A(3,j,k)=(***)=A(2,j,A(3,j,k-1))=(****)=jA(3,j,k-1)}\)
Ponieważ zaś \(\displaystyle{ A(3,j,1)=(**)=j}\), prosta indukcja pokazuje, że \(\displaystyle{ A(3,j,k)=j^k}\), czego należało dowieść.

Policzmy jeszcze na koniec \(\displaystyle{ A(4,2,3)}\). Jest:
\(\displaystyle{ A(4,2,1)=2}\)
\(\displaystyle{ A(4,2,2)=A(3,2,A(4,2,1))=A(3,2,2)=2^2=4}\)
\(\displaystyle{ A(4,2,3)=A(3,2,A(4,2,2))=A(3,2,4)=2^4=16}\)

Q.