Alternative Berechnungsmodelle

Aus ProgrammingWiki
< Berechenbarkeitstheorie
Archivierte Version vom 2012-06-14T06:24:28+00:00. Aktuelle Version

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:

$\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}, F_1(3,0)+0+1) \\
          &=& F_0(3,4) = 3+4 = 7\\
 F_1(3,2) &=& F_0(7,9)=7+9=16 \\

\end{eqnarray*}$