Grenzen der LOOP-Berechenbarkeit Flashcards
1
Q
Sind alle totalen Funktionen Loop-berechenbar?
A
Nein
2
Q
Totale und Loop-berechenbare Funktionen - Theorem
A
3
Q
Ackermannfunktion - Theorem
A
Die Ackermannfunktion ist nicht LOOP-berechenbar.
4
Q
Wie wird gezeigt, das die Ackermannfunktion nicht LOOP-berechenbar ist?
A
Wir zeigen, das die Ackermannfunktion schneller wächst als jede LOOP-berechenbare Funktion.
5
Q
Ackermannfunktion (Variante Rosza Peter) - Formel
A
6
Q
Ist die Ackermannfunktion total?
A
Ja
7
Q
Ist die Ackermannfunktion LOOP-berechenbar?
A
Nein
8
Q
Ist die Ackermannfunktion WHILE-berechenbar?
A
Ja