Recursion theory : its generalisations and applications : proceedings of Logic Colloquium '79, Leeds, August 1979 / edited by F.R. Drake and S.S. Wainer.

Includes bibliographical references.

Print version record.

Recursion theory - now a well-established branch of pure mathematics, having grown rapidly over the last 35 years - deals with the general (abstract) theory of those operations which we conceive as being `computable' by idealized machines. The theory grew out of, and is usually still regarded, as a branch of mathematical logic. This book is a collection of advanced research/survey papers by eminent research workers in the field, based on their lectures given at the Leeds Logic Colloquium 1979. As such it provides an up-to-date view of current ideas and developments in the field of recursion theory as a whole. The individual contributions fit together naturally so as to provide an overview of all the main areas of research in the field. It will therefore be an important and invaluable source for advanced researchers and research students in mathematics and computer science (particularly in Europe, USA and USSR).

Degrees of Generic Sets1. INTRODUCTION; 2. PRELIMINARIES ON FORCING, GENERICITY, AND CATEGORY; 3. CONSEQUENCES OF CLASSICAL CONSTRUCTIONS; 4. MARTIN'S CATEGORY THEOREM; 5. RELATIVE RECURSIVE ENUMERABILITY OF I-GENERIC DEGREES; 6. CUPPING AND COMPLEMENTATION THEOREMS; 7. OPEN QUESTIONS; REFERENCES; The Degrees of Unsolvability: Some Recent Results; INTRODUCTION; 1. LOCAL STRUCTURE THEOREMS; 2. DECIDABILITY; 3. HOMOGENEITY; 4. AUTOMDRPHISMS; 5. DEFINABILITY; REFERENCES; GENERALISATIONS; Some Constructions in a-Recursion Theory; 1 PRELIMINARIES

2 a-FINITE INJURY PRIORITY ARGUMENTS AND THE SACKS SPLITTINGTHEOREM3. A CONE OF WELL ORDERED a-DEGREES; 4. MINIMAL PAIRS OF a-R.E. DEGREES; REFERENCES; The Recursion Theory of the Continuous Functionals; INTRODUCTION; BASIC DEFINITIONS AND RESULTS; THE MODULUS OF A SEQUENCE; COROLLARY (Normann-Wainer [18]); THE PROJECTIVE HIERARCHY; FINAL REMARKS; REFERENCES; Three Aspects of Recursive Enumerability in Higher Types; ABSTRACT; 1. INTRODUCTION; 2. MACHINERY; 3. INADMISSIBLE FORCING; 4. LIMITS OF RECURSIVE ENUMERABILITY; 5. COUNTABLE E-CLOSED ORDINALS; 6. POST'S PROBLEM

7. LOGIC ON E-CLOSED SETSREFERENCES; APPLICATIONS; Computing in Algebraic Systems; INTRODUCTION; 1. FINITE ALGORITHMIC PROCEDURES; 2. THE FAP-COMPUTABLE FUNCTIONS IN THE LARGE; 3. ALGEBRAIC INFLUENCES ON FAP-COMPUTATION; 4. LOCAL FAPCS-ENUMERATION, SEARCH AND PAIRING; 5. COUNTING AND STACKING: VARIETIES AND LOCAL FINITENESS; 6. TOPOLOGICAL ALGEBRAS; REFERENCES; Applications of Classical Recursion Theory to Computer Science; Introduction; Programming Tools; Complexity; Inductive Inference; Summary; Acknowledgements; References

""Natural"" Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach1 INTRODUCTION; 2 SUBRECURSIVE PROGRAMMING LANGUAGES; 3 COMPLEXITY MEASURES; 4 SUBRECURSIVE COMPLEXITY: A BEGINNING; 5 RELATIONSHIPS BETWEEN THE COMPLEXITIES OF RELATED PROGRAMS; 6 A PROOF TECHNIQUE FOR SUBRECURSIVE COMPLEXITY; 7 OTHER SUBRECURSIVE COLLECTIONS OF FUNCTIONS J; 8 CONCLUSIONS AND QUESTIONS; 9 ACKNOWLEDGMENTS; REFERENCES; Complexity Theory with Emphasis on the Complexity of Logical Theories; LECTURE 1. BASIC COMPLEXITY THEORY

English.

eBooks on EBSCOhost EBSCO eBook Subscription Academic Collection - Worldwide