BuK-Übung09

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2012-05-29T16:17:33+00:00. Aktuelle Version

Weisen Sie nach, dass die AP-Funktion

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

WHILE-berechenbar ist.


Nach den Sätzen, dass jede Turing-berechenbare Funktion auch WHILE-berechenbar und jede WHILE-berechenbare Funktion auch Turing-berechenbar ist, wird mit der Angabe eines Programmes für die Ackermann-Peter-Funktion in einer Turing-Vollständigen Sprache auch die WHILE-Berechenbarkeit der AP-Funktion gezeigt.