Ordinal Computability: An Introduction to Infinitary Machines (De Gruyter Series in Logic and Its Applications)

__Ordinal Computability__ discusses models of computation obtained by generalizing classical models, such as Turing machines or register machines, to transfinite working time and space. In particular, recognizability, randomness, and applications to other areas of mathematics are covered. Cover......Page 1 Ordinal Computability: An Introduction to Infinitary Machines......Page 4 Contents......Page 6 1. Introduction......Page 10 2. Machine models of transfinite computability......Page 18 3. Computability strength......Page 86 4. Recognizability......Page 166 5. Randomness......Page 204 6. Degree theory......Page 228 7. Complexity......Page 248 8. Applications and interactions......Page 266 9. Philosophical aspects......Page 286 Bibliography......Page 322 Index......Page 332

Ordinal Computability discusses models of computation obtained by generalizing classical models, such as Turing machines or register machines, to transfinite working time and space. In particular, recognizability, randomness, and applications to other areas of mathematics are covered.

The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.