Primitive und partielle Rekursion Flashcards
1
Q
primitiv-rekursive Funktionen - Definition
A
2
Q
primitiv-rekursive Funktion und und totalität.
A
Alle primitiv-rekursiven Funktionen sind total.
3
Q
Mächtigkeit von primitiv-rekursiv und LOOP-berechenbar
A
Eine Funktion ist LOOP-berechenbar genau dann, wenn sie durch eine primitiv-rekursie Funktion dargestellt werden kann.
4
Q
μ- bzw. partielle Rekursion - Definition
A
μ(g) ist womöglich nicht total!
5
Q
Mächtigkeit von μ-rekursiv und Turing/WHILE/GOTO-berechenbar
A
μ-rekursiv und Turing/WHILE/GOTO-berechenbar ist gleich Mächtig (logisch Äquivalent)
6
Q
Kleene’sche Normalform - Theorem
A
