Berechenbarkeit
← Einsatz von Rekursion | ● | Zeiger und Adressen →
Es gibt rekursive Funktionen, die sich prinzipiell nicht iterativ darstellen lassen, d.h. iterativ im Sinne einer einfachen for-Schleife mit einer bekannten Anzahl von Durchläufen.
Man sagt, dass diese Funktionen nicht primitiv-rekursiv sind.
Ein Beispiel dafür ist die Ackermannfunktion a(n,m):
Diese Funktionen haben jedoch keine praktische Relevanz, sondern spielen hauptsächlich in der theoretischen Informatik eine Rolle, wo es um die prinzipielle Berechenbarkeit von Funktionen geht. Die Ackermann Funktion ist in diesem Zusammenhang das klassische Beispiel für eine prinzipiell berechenbare aber nicht primitiv-rekursiv berechenbare Funktion.
Ebenso gibt es prinzipiell nicht berechenbare Funktionen. Das klassische Beispiel hierfür ist der soganannte Fleißige Biber (Busy Beaver).