Student talks on infinitary computability

Posted on November 29, 2012 by Joel David Hamkins

Students in my Infinitary Computability course will give talks on their term papers. Talks will be held at the CUNY Graduate Center, Room 3307, 9:30-11:30.

Monday, December 3rd

Miha Habič will speak on “Cardinal-Recognizing Infinite Time Turing Machines”, in which he develops the theory of infinite time Turing machines that are given information about when they have reached cardinal time.
Erin Carmody will speak on “Non-deterministic infinite time Turing machines”, in which she develops the theory of non-deterministic ITTM computation.
Alexy Nikolaev will speak on “Equivalence of ITTMs, and their simultation on a finite time computer,” in which we proves the equivalence of various formalizations of ITTMs.

Monday, December 10th

Manuel Alves will speak on infinite time computable model theory.
Syed Ali Ahmed will speak on the relation between Büchi automata and infinite time Turing machines, including $ω$ -regular languages and generalizations to longer transfinite strings.

Ansten Mørch-Klev

Posted on August 13, 2012 by Joel David Hamkins

Ansten Mørch-Klev earned his M.Sc. degree under my direction at Universiteit van Amsterdam in July, 2007. For his thesis, Ansten undertook to investigate the infinite-time analogue of Kleene’s $O$ , the natural extension of Kleene’s concept to the case of infinite time Turing machines. The result was a satisfying and robust theory, which revealed (as predicted by Philip Welch) the central importance of the eventually writable ordinals in the theory of infinite time computability. This work eventually appeared as: Ansten Mørch-Klev, “Infinite time analogues of Kleene’s $O$ ,” Archive for Mathematical Logic, 48(7):2009, p. 691-703, DOI:10.1007/s00153-009-0146-2.

Ansten Mørch Klev

web page | DBLP | google scholar

Ansten Mørch-Klev, “Extending Kleene’s O Using Infinite Time Turing Machines, or How With Time She Grew Taller and Fatter”, M.Sc. thesis for Institute of Logic, Language and Computation, Universiteit van Amsterdam, July, 2007. ILLC publication

Abstract. We define two successive extensions of Kleene’s $O$ using infinite time Turing machines. The first extension, $O^{+}$ , is proved to code a tree of height $λ$ , the supremum of the writable ordinals, while the second extension, $O^{+ +}$ , is proved to code a tree of height $ζ$ , the supremum of the eventually writable ordinals. Furthermore, we show that $O^{+}$ is computably isomorphic to $h$ , the lightface halting problem of infinite time Turing machine computability, and that $O^{+ +}$ is computably isomorphic to $s$ , the set of programs that eventually writes a real. The last of these results implies, by work of Welch, that $O^{+ +}$ is computably isomorphic to the $Σ_{2}$ theory of $L_{ζ}$ , and, by work of Burgess, that $O^{+ +}$ is complete with respect to the class of the arithmetically quasi-inductive sets. This leads us to conjecture the existence of a parallel of hyperarithmetic theory at the level of $Σ_{2} (L_{ζ})$ , a theory in which $O^{+ +}$ plays the role of $O$ , the arithmetically quasi-inductive sets play the role of $Π_{1}^{1}$ , and the eventually writable reals play the role of $Δ_{1}^{1}$ .

A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020

Posted on April 8, 2012 by Joel David Hamkins

In Fall 2012 I will teach a graduate course on infinitary computability theory in the Computer Science program at the CUNY Graduate Center. This course will be aimed at graduate students in computer science and mathematics who are interested in infinitary computational processes.

Infinitary computability, CSC 85020, Mondays, 9:30 – 11:30 am
CS course listings | this listing

This course will explore all the various infinitary theories of computability, including infinite time Turing machines, Blum-Shub-Smale computability, Büchi automata, ordinal register machines and others. The focus will be on introducing the computability models and comparing them to each other and to standard concepts of computability. In the early part of the course, we shall review the standard finitary computational models, before investigating the infinitary supertask analogues.

Students wishing to prepare for the course should review their understanding of Turing machines and the other theoretical machine models of computation.

Some of my articles on infinitary computability | Student talks on their infinitary computability term papers

Effective Mathemematics of the Uncountable

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=EMU]

Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students, and a source of interesting new approaches for researchers in computability theory and related areas.

Many of the authors whose work appears in this volume were also involved in the Effective Mathematics of the Uncountable conferences EMU 2008 and EMU 2009, held at the CUNY Graduate Center.

Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=CoskeyHamkins2013:ITTMandApplicationsToEquivRelations]

We describe the basic theory of infinite time Turing machines and some recent developments, including the infinite time degree theory, infinite time complexity theory, and infinite time computable model theory. We focus particularly on the application of infinite time Turing machines to the analysis of the hierarchy of equivalence relations on the reals, in analogy with the theory arising from Borel reducibility. We define a notion of infinite time reducibility, which lifts much of the Borel theory into the class $Δ_{2}^{1}$ in a satisfying way.

Infinite time decidable equivalence relation theory

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=CoskeyHamkins2011:InfiniteTimeComputableEquivalenceRelations]

We introduce an analog of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $Δ_{2}^{1}$ reductions, and hence to the infinite time computable reductions.

Post's problem for ordinal register machines: an explicit approach

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsMiller2009:PostsProblemForORMsExplicitApproach]

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

Infinite time computable model theory

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory]

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines, which provide infinitary notions of computability for structures built on the reals $R$ . Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time computable analogue of the Completeness Theorem, turn out to be independent of ZFC.

A survey of infinite time Turing machines

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=Hamkins2007:ASurveyOfInfiniteTimeTuringMachines]

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.

$P \neq N P \cap co- N P$ for infinite time Turing machines

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=DeolalikarHamkinsSchindler2005:NPcoNP]

Extending results of Schindler [math.LO/0106087] and also my paper with Philip Welch, we establish in the context of infinite time Turing machines that $P$ is properly contained in $N P$ intersect $c o N P$ . Furthermore, $N P \cap c o N P$ is exactly the class of hyperarithmetic sets. For the more general classes, we establish that $P^{+} = (N P^{+} \cap c o N P^{+}) = (N P \cap c o N P)$ , though $P^{+ +}$ is properly contained in $N P^{+ +} \cap c o N P^{+ +}$ . Within any contiguous block of infinite clockable ordinals, we show that $P_{α}$ is not equal to $N P_{α} \cap c o N P_{α}$ , but if $β$ begins a gap in the clockable ordinals, then $P_{β} = N P_{β} \cap c o N P_{β}$ . Finally, we establish that $P^{f}$ is not equal to $N P^{f} \cap c o N P^{f}$ for most functions $f$ from the reals to the ordinals, although we provide examples where $P^{f} = N P^{f} \cap c o N P^{f}$ and $P^{f}$ is not equal to $N P^{f}$ .

Infinitary computability with infinite time Turing machines

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=Hamkins2005:InfinitaryComputabilityWithITTM]

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a theoretical model of infinitary computability, while remaining close in spirit to many of the methods and concepts of classical computability. The model gives rise to a robust theory of infinitary computability on the reals, such as notions of computability for functions $f : R \to R$ and notions of decidability for sets $A \subset R$ , with a rich degree structure. In this brief article, I would like to announce and explain a few of the most recent developments in the theory of infinite time Turing machines. These developments include the rise of infinitary complexity theory, with a solution of the infinite time Turing machine analogue of the $P$ versus $N P$ question, and the development of infinitary computable model theory. Much of the work on infinite time Turing machines lies within the boundaries between set theory, descriptive set theory, computability theory and computable model theory.

Supertask computation

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=Hamkins2004:SupertaskComputation]

Infinite time Turing machines extend the classical Turing machine concept to transfinite ordinal time, thereby providing a natural model of infinitary computability that sheds light on the power and limitations of supertask algorithms.

$P^{f} \neq {N P}^{f}$ for almost all $f$

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsWelch2003:PfneqNPf]

Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines $P^{f} = N P^{f}$ can be true for any function $f$ from the reals into $ω_{1}$ . We show that “almost everywhere” the answer is negative.

Post's problem for supertasks has both positive and negative solutions

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsLewis2002:PostProblem]

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post’s problem, the question whether there are supertask degrees between $0$ and the supertask jump $0^{▽}$ , has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^{▽}$ , but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.

Infinite time Turing machines

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=Hamkins2002:Turing]

This is a survey of the theory of infinite time Turing machines.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

Joel David Hamkins

mathematics and philosophy of the infinite

Tag Archives: ITTMs

Student talks on infinitary computability

Ansten Mørch-Klev

A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020

Effective Mathemematics of the Uncountable

Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

Infinite time decidable equivalence relation theory

Post's problem for ordinal register machines: an explicit approach

Infinite time computable model theory

A survey of infinite time Turing machines

$P \neq N P \cap co- N P$ for infinite time Turing machines

Infinitary computability with infinite time Turing machines

Supertask computation

$P^{f} \neq {N P}^{f}$ for almost all $f$

Post's problem for supertasks has both positive and negative solutions

Infinite time Turing machines

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: