Berechenbarkeitstheorie/Alternative Berechnungsmodelle

Wiki-Quelltext dieser Seite.

<language>Scheme</language>

== 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)=F_0(F_1(3,1), F_1(3,1)+1+1)$