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)=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 <tt>(f n x y)</tt>.

<code id="4fd985fd76323">
(define f
  (lambda (n x y)
    (cond
      ((= n 0) (+ x y))
      ((= y 0) x)
      (else
       (f (- n 1) (f n x (- y 1)) (+ (f n x (- y 1)) y))))))
</code>
<run id="4fd985fd7638d">(f 1 3 2)</run>