Anzeige
Erschienen in:
2022 | OriginalPaper | Buchkapitel
3. Loop Programs
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 loop programs were introduced by Meyer and Ritchie (Computational complexity and program structure, Technical Report RC-1817, IBM, 1967) as a program theoretic counterpart to the number theoretic introduction of the set of primitive recursive functions \(\mathcal {P}\mathcal {R}\). This programming formalism among other things connects the definitional (or structural) complexity of primitive recursive functions with their (run time) computational complexity, but this latter phenomenon will be addressed in Chap. 15. In the present chapter we will offer an easy informal proof that \(\mathcal {P}\mathcal {R}\) is an incomplete formalism for the concept of “computable function”.