Fundamentals of Generalized Recursion Theory
Published on 18. August 2011
328 pages
978-0-08-096031-9 (ISBN)
Description
Fundamentals of Generalized Recursion Theory
More details
Other editions
Additional editions
Melvin Fitting
Fundamentals of Generalized Recursion Theory
Book
10/1981
Elsevier
€86.60
Article exhausted; check different version
Content
- Front Cover
- Fundamentals of Generalized Recursion Theroy
- Copyright Page
- Contents
- Introduction
- Chapter 1. Recursion and ?-recursion Theories
- 1. Introduction
- 2. Structures
- 3. Elementary formal systems
- 4. Examples
- 5. Remarks
- 6. Informal motivation
- 7. Enumeration operators
- 8. Informal motivation
- 9. ?-elementary formal systems
- 10. Basic structural properties
- 11. Recursion and ?-recursion theories
- 12. The least fixed point theorem
- 13. Inductive definability
- 14. R -definability
- Chapter 2. Production Systems
- 1. Introduction
- 2. Production systems
- 3. Elementary results
- 4. Reducibility
- 5. Pointwise generated functions
- 6. Production systems with equality
- 7. Closure under least fixed point
- 8. A Kleene-Post result
- Chapter 3. Embeddings
- 1. Introduction
- 2. Codings
- 3. Pre-embeddings
- 4. Embeddings and co-embeddings
- 5. Theory assignments
- 6. Examples
- 7. The category of production systems
- Chapter 4. Combining Production Systems
- 1. Introduction
- 2. Combining domains and codings
- 3. Symmetric monoidal categories
- 4. A few technical results
- 5. Combining structures
- 6. Recursion theories, for example
- 7. Combining production systems
- 8. Combining embeddings
- 9. Monoidal subcategories in Prod
- 10. Separability
- 11. A few results about separability
- 12. Injections and co-embeddings
- Chapter 5. Effective Embeddings
- 1. Introduction
- 2. Effective embeddings
- 3. Results about effective embeddings
- 4. Reflexivity
- 5. An "effective" symmetric monoidal category
- 6. Extensions
- 7. Isomorphisms
- Chapter 6. Indexed Recursion and ?-recursion Theories
- 1. Introduction
- 2. Elaborating a structure
- 3. Recursion and ?-recursion theories
- 4. S completeness
- 5. Elementary formal systems and S completeness
- 6. Separability
- 7. Reflexivity
- 8. Sequence codings
- 9. Adding letters
- 10. Copies and extensions
- 11. Universal machines
- 12. Operator indexing
- 13. Input and output place-fixing theorems
- 14. Indexing revisited
- 15. Relational indexing
- 16. Finite codes
- Chapter 7. Indexed Relational Systems
- 1. Introduction
- 2. Immediate consequences
- 3. Fixed point theorems
- 4. Rice's theorem
- 5. Creative sets
- 6. Kleene-Mostowski systems
- 7. The Rice-Shapiro theorem
- Chapter 8. Indexed Production Systems
- 1. Introduction
- 2. Indexed production systems
- 3. The output place-fixing property
- 4. The input place-fixing property
- 5. Pointwise generated functions, again
- 6. D-finiteness
- 7. Rogers' form for operators
- 8. Effective pairing
- 9. Non-compact operators
- 10. All the D-finiteness assumptions together
- 11. The least fixed point theorem
- 12. Metacompactness
- 13. Semi-hyperregularity
- 14. Compact cores
- 15. The least fixed point theorem, again
- Chapter 9. Admissible Set Recursion Theories
- 1. Introduction
- 2. Admissible sets
- 3. Terminology
- 4. Elementary formal systems over admissible sets
- 5 . Basic results
- 6. Examples
- 7. Enumeration operators generalized
- 8. Structural properties
- 9. More examples
- 10. Pre-embeddings and embeddings
- 11. Combining augmented F-structures
- 12. More monoidal subcategories in Prod
- 13. Extensions, again
- 14. Indexed relational systems
- 15. Indexed production systems
- 16. Remarks on a-recursion theory
- Chapter 10. Effective Operators of Higher Types
- 1. Introduction
- 2. Operators with several inputs
- 3. Effective type 2 operators
- 4. Properties of effective type 2 operators
- 5. Effective type 3 operators
- 6. Examples of effective type 3 operators
- 7. The least fixed point theorem, again
- 8. Higher types
- 9. Indexing
- 10. Conclusion
- Appendix
- Bibliography
- Index
