|
|
|
| Untersuchte Arbeit: Seite: 91, Zeilen: re.Sp. 19-32 |
Quelle: Wikipedia Ackermannfunktion 2012 Seite(n): 0, Zeilen: 0 |
|---|---|
| Zunächst entstand der Begriff der primitiv rekursiven Funktion. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt, und dass sich die Dauer der Berechnung im Voraus abschätzen lässt.
Dies trifft auf in der Tat auf nahezu alle in der Praxis vorkommenden Funktionen zu. Noch im Jahre 1926 vermutete David Hilbert (Abb. 5.4), dass jede berechenbare Funktion primitiv-rekursiv sei. Allerdings konnte Ackermann im gleichen Jahr eine Funktion konstruieren, die diese Vermutung widerlegte, und veröffentlichte sie 1928. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv. |
Entstehungsgeschichte
1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt und dass sich die Dauer der Berechnung im Voraus abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu. Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv. |
|
|