- A survey of infinite time Turing machines
- Lecture Notes in Computer Science
- Pages (from-to)
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time, thereby providing a natural model of infinitary computability, with robust notions of computability and decidability on the reals, while remaining close to classical concepts of computability. Here, I survey the theory of infinite time Turing machines and recent developments. These include the rise of infinite time complexity theory, the introduction of infinite time computable model theory, the study of the infinite time analogue of Borel equivalence relation theory, and the introduction of new ordinal computational models. The study of infinite time Turing machines increasingly relies on the interaction of methods from set theory, descriptive set theory and computability theory.
- go to publisher's site
- Proceedings title: Machines, computations, and universality: 5th international conference, MCU 2007, Orléans, France, September
10-13, 2007: proceedings
Place of publication: Berlin
Editors: J. Durand-Lose, M. Margenstern
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.