Reflexive structures. An introduction to computability theory
Church's thesisclasses closed under recursive operationsclosure propertiescomputabilityenumeration hierarchyenumeration propertiesfunctional reflexive structurefunctions and predicates on natural numbershyperenumerationindexing functionsinductionminimal fixed point theory of continuous functionalsreflexivity propertiesstack algorithm
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Abstract and axiomatic computability and recursion theory (03D75)
The book under review bears the subtitle ``Introduction to computability theory. The included material as well as the organization of the topics prevent the full achievement of this goal. A beginner would hardly develop the natural intuition about computability when reading this book. It is also difficult to imagine that he could directly pass to the study of more advanced related books. That this book, however, is very interesting resides exactly in its originality which unfortunately generates these flaws at the same time. The approach is related to general recursion theory and many ideas are derived from there. The main concern is the study of closure properties under certain finitary or infinitary operators of structures possessing reflexivity properties (usually in the form of universal or indexing functions). These structures are dealt with in a reasonably general setting, avoiding the introduction of abstract axiomatic domains. Thus the first chapter introduces functions and predicates on natural numbers which are exclusively discussed in this book. The main finitary rules for obtaining meaningful classes of functions are defined (substitution, bounded sum and product, existential and universal bounded quantification, bounded and unbounded minimalization and others). Closure properties of these operations are investigated. The second chapter treats recursion, which is considered from two different points of view: via the minimal fixed point theory of continuous functionals and via the well-known stack algorithm. A paragraph explains Church's thesis and some classical results are shown to hold true in the general setting of classes closed under recursive operations (like Myhill's theorem stating that equivalence under 1-1 recursive functions implies recursive isomorphism). The third chapter explores enumeration properties introduced via unbounded quantification, existential and universal. This chapter also investigates the enumeration hierarchy (a generalization of the arithmetic hierarchy), includes a discussion on induction, viewed as a restricted kind of recursion, and a paragraph dedicated to nondeterministic computation. The fourth chapter defines the concept of functional reflexive structure as the class of functions containing some simple initial functions, being closed under basic operations and possessing a certain effective indexing property. Once again some classical theorems are stated in this general context (the existence of universal interpreters, the recursion theorem, the Friedberg completeness criterion, e.g.). Then, reflexivity is extended to sets, and some emerging properties, like productivity, are discussed. Finally, the fifth chapter investigates topics similar to those in the previous two chapters, considering hyperenumeration in place of enumeration. The structure of the book respects the classical canons of a textbook. Each paragraph is completed with a set of problems and a short ``Notes section which draws parallels between the topics in the paragraph and the corresponding issue in classical recursive function theory. The notation is inevitably rich and the lack of a notation index is unfortunate. To sum up, the book is interesting and can be read in parallel with a standard introductory textbook in computability, or it can be used as an intermediate step toward a study of general recursion theory.
- scientific article; zbMATH DE number 732055
- scientific article; zbMATH DE number 841091
- Computational reflection in the calculus of constructions and its application to theorem proving
- scientific article; zbMATH DE number 5778850
- scientific article; zbMATH DE number 2047478
- Towards a theory of recursive structures
- Towards a theory of recursive structures
- Computable structures and the hyperarithmetical hierarchy
- scientific article; zbMATH DE number 1344955
- Computable Structure Theory
This page was built for publication: Reflexive structures. An introduction to computability theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3994786)