Thema9

Aus ProgrammingWiki
< BuK < IIm12 < Studenten < siclsche
Archivierte Version vom 2013-05-30T08:22:10+00:00. Aktuelle Version

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

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.