Alternative Berechnungsmodelle
Aus ProgrammingWiki
Theorie der rekursiven Funktionen
Primitiv-rekursive Funktionen
Sudan-Funktion
Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) - wie Ackermann ebenfalls ein Schüler von David Hilbert - hat 1927 eine total berechenbare jedoch nicht primitiv rekursive Funktion publiziert. Sie ist folgendermaßen definiert.
$\begin{eqnarray*} F_0(x,y) &=& x+y \\ F_{n+1}(x,0) &=& x,\ n\geq 0 \\ F_{n+1}(x,y+1) &=& F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0 \end{eqnarray*}$
Beispiel: $F_1(3,2)=16$
$\begin{eqnarray*} F_1(3,2) &=& F_0(F_1(3,1), F_1(3,1)+1+1) \\ F_1(3,1) &=& F_0(\underbrace{F_1(3,0)}_{3}, \underbrace{F_1(3,0)}_{3}+0+1) \\ &=& F_0(3,4) = 3+4 = 7\\ F_1(3,2) &=& F_0(7,9)=7+9=16 \\ \end{eqnarray*}$
Berechnen Sie $F_1(3,3)=35, F_1(3,4)=74$ und $F_2(2,1)=27$ mit Hilfe der folgenden Prozedur. Beachten Sie das Aufrufmuster: Zur Berechnung von $F_n(x,y)$ lautet der zugehörigen Aufruf (f n x y).
