BuK/IIm12/BuK-Übung09

Wiki-Quelltext dieser Seite.

== WHILE-berechenbarkeit der Ackermann-Peter-Funktion ==

Weisen sie nach, dass die Ackermann-Peter-Funktion (AP-Funktion) WHILE-berechenbar ist.

Die AP-Funktion ist definiert durch:

 AP(0, y) = y + 1
 AP(x, 0) = AP(x - 1, 1), x > 0
 AP(x, y) = AP(x - 1; AP(x, y - 1)), x, y > 0

=== Beweis: ===

Der konstruktive Beweise setzt zunächst Voraus, das die AP-Funktion in einer Turing-Vollständigen Sprache implementiert wird. Da Racket eine Turing-Vollständigen Sprache ist, kann diese hierfür verwendet werden.

<code id="simareic_ap_funktion">
(define AP
  (lambda (x y)
  (if (= x 0)
      (+ y 1) 
      (if (= y 0)
          (AP (- x 1)1) 
          (AP (- x 1) (AP x (- y 1)))
          )
      )))
</code>

<run id="simareic_ap_funktion">
(AP 3 2)
</run>