Computability in Combinatory Spaces

Inhaltsverzeichnis

• I. Computational Structures and Computability on them.
• 1. Computational structures.
• 2. Computability of partial functions with respect to a given computational structure.
• 3. On a procedure for generating the unary partial recursive functions.
• 4. On the interconnection between programmability in a FP - system and ?- computability.
• 5. Computability of multiple-valued functions with respect to a given computational structure.
• 6. The recursively enumerable binary relations considered as multiple-valued functions.
• 7. On the notions of prime and search computability.
• 8. Computability in the case of unproductive termination taken into account.
• II. Combinatory Spaces.
• 1. The notion of combinatory space.
• 2. The companion operative space of a combinatory space.
• 3. Iteration in combinatory spaces.
• 4. On least fixed points in partially ordered sets.
• 5. The companion operative space of an iterative combinatory space.
• 6. Left-homogeneous mappings and least fixed points connected with them.
• 7. Some formal systems for the theory of iterative combinatory spaces.
• III. Computability in Iterative Combinatory Spaces.
• 1. Explicit and fixed-point definability in partially ordered algebras.
• 2. Computable elements and mappings in iterative combinatory spaces.
• 3. Representation of the partial recursive functions in iterative combinatory spaces.
• 4. The First Recursion Theorem for iterative combinatory spaces.
• 5. Application of the First Recursion Theorem to some concrete iterative combinatory space.
• 6. Normal Form Theorems for computable elements and mappings in iterative combinatory spaces.
• 7. Universal computable elements in iterative combinatory spaces.
• 8. A notion of search computability in iterative combinatory spaces.
• 9. On the formalization of the proof of theFirst Recursion Theorem.
• References.
• Additional Bibliography.
• Index of Names.
• Index of Definitions.