Anzeige
Erschienen in:
2022 | OriginalPaper | Buchkapitel
4. The Ackermann Function
verfasst von : George Tourlakis
Erschienen in: Computability
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The “Ackermann function” was proposed, of course, by Ackermann. The version here is a simplification by Robert Ritchie.
It provides us with an example of a recursive function that is not in \(\mathcal {P}\mathcal {R}\). Unlike the example in Chap. 3, which provided an alternative such function by diagonalisation, the proof that the Ackermann function is not primitive recursive is by a majorisation argument. Simply, it is too big to be primitive recursive!
But this function is more than just intuitively computable! It is computable —no hedging —as we will show by showing it to be a member of \({\mathcal {R}}\).
Another thing it does is that it provides us with an example of a function \(\lambda \vec x.f(\vec x)\) that is “hard to compute” (in the sense \(f\notin \mathcal {P}\mathcal {R}\)) but whose graph —\(\lambda y\vec x.y=f(\vec x)\)— is nevertheless “easy to compute” (\({}\in \mathcal {P}\mathcal {R}_{*}\)). (Here the colloquialisms “easy to compute” and “hard to compute” are aliases for “primitive recursive” and “not primitive recursive”, respectively. This is a hopelessly coarse rendering of easy/hard and a much better gauge for the runtime complexity of a problem is on which side of O(2n) it lies. However, our gauge will have to do for now: All I want to leave you with is that for some functions it is easier to compute the graph —to the quantifiable extent that it is in \(\mathcal {P}\mathcal {R}_{*}\)— than the function itself, meaning that the latter fails to be primitive recursive.)