BuK/IIm12/Studenten/siclsche/Thema9

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Weisen Sie nach, dass die AP-Funktion WHILE-berechenbar ist.
$$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$$

== Aufgabe 2 ==
Folgende Klassen sollen dargestellt werden:
* Turing-berechenbare Funktionen
* WHILE-berechenbare Funktionen
* GOTO-berechenbare Funktionen
* partiell berechenbare Funktionen
* total berechenbare Funktionen
* LOOP-berechenbare Funktionen
* AP-Funktion



[[Bild:Siclsche_Mengendiagramm.png|500 px]]

== Kreativaufgabe: LOOP-, WHILE, GOTO-Grammatik ==
Entwickeln Sie jeweils zu LOOP-, WHILE- und GOTO-Programmen eine entsprechende, reduzierte Grammatik. Überprüfen Sie anhand eines Beispiels ob die von Ihnen entwickelten Grammatiken korrekt sind.

Verwenden Sie AtoCC.