rekursja - ackermann
: 8 sty 2011, o 20:57
Niech
\(\displaystyle{ \psi (m,n= \left\{ \begin{array}{lll} n+1 \ dla \ m=0 \\ \psi(m-1,1) \ dla\ n=0, m>0 \\ \psi(m-1, \psi(m,n-1)) \ dla \ m>0, n>0}\end{array} \right .}\)
Pokazać, że \(\displaystyle{ \psi(m,n) \in Rek}\)
Gdzie
Klasa funkcji rekurencyjnych \(\displaystyle{ Rek}\) jest najmniejszą klasa zawierająca funkcje inicjujące i zamknięta na rekursję prostą, złożenie i \(\displaystyle{ \mu}\) - rekursję
\(\displaystyle{ \psi (m,n= \left\{ \begin{array}{lll} n+1 \ dla \ m=0 \\ \psi(m-1,1) \ dla\ n=0, m>0 \\ \psi(m-1, \psi(m,n-1)) \ dla \ m>0, n>0}\end{array} \right .}\)
Pokazać, że \(\displaystyle{ \psi(m,n) \in Rek}\)
Gdzie
Klasa funkcji rekurencyjnych \(\displaystyle{ Rek}\) jest najmniejszą klasa zawierająca funkcje inicjujące i zamknięta na rekursję prostą, złożenie i \(\displaystyle{ \mu}\) - rekursję