# Student talks on infinitary computability

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 $\omega$-regular languages and generalizations to longer transfinite strings.

## 10 thoughts on “Student talks on infinitary computability”

1. I am interested in reading the Habic and Alves papers. Will they be published on this website? Also a question on ITTM’s, in particular on Ordinal Turing Machines. Is ordinal computability absolute over the set-theoretic multiverse, or not?

• I believe that Habic intends to submit his paper for publication after some further refinements. But I think my other students did not intend to make their term papers publicly available. Meanwhile, if you are interested in infinite time computable model theory, you might take a look at my paper http://jdh.hamkins.org/infinitetimecomputablemodeltheory/, which the Alves paper was extending. Regarding your last question, the operation of most of the ordinal Turing machines are absolute to other models of set theory with the same ordinals. But even finite-time computation is not absolute to all other set-theoretic universes: for example, consider the program that on finite input $x$, first searches for a proof of a contradiction in ZFC + “there is a supercompact cardinal”, and only when this is found does it return $x^2$. In some models of set theory, this program computes the empty function, but in others, it computes the function $x\mapsto x^2$.

2. That is, will an ordinal Turing machine generate the same computable sets in every model (universe) of the multiverse, or are sets computable (‘recursive’ or ‘r.e.’ ) relative to the model of ZFC (or ZF, if Choice is forced to be false in the model) under consideration?

• Most of the models of ordinal Turing machines have a level of complexity that makes their operation absolute to other universes with the same ordinals. But some, such as the model introduced by Habic, where the machine receives special information signalling that it has reached an infinite cardinal stage of computation, are not absolute to such models, simply because the notion of cardinal itself is not absolute. That is, the question of whether a given ordinal is a cardinal can be changed by forcing. Nevertheless, it follows from what Habic proves that the question of whether a given set is decidable or not by such a machine is actually absolute anyway, since being computable by a cardinal-recognizing infinite time Turing machine is equivalent to being computable by an infinite time Turing machine with $0^\blacktriangledown$ as an oracle.

• Professor Hamkins: Thanks for the replies–they were very enlightening. Another question: Given Koepke’s thoerem:

A set x of ordinals is ordinal computable from a finite set of ordinal parameters iff it is an element of the constructible universe L

is there a notion of hypercomputation that allows ordinal
computation from an infinite set of ordinal parameters? If so, then 0-sharp and other non-constructable sets of integers would seem to be computable under this notion of hypercomputation and therefore be deemed to ‘exist'[?] If so, then how far (so to speak) can one stretch the notion of ‘hypercomputation’ ?

3. While not directly related, I am enjoying the fact that I recognize some of the names from MSE and MO.

• Asaf: If one considers the model of ZFC constructed as follows:

ii) Add omega_2 nonconstructible subsets of omega so that CH is false it the extension

iii) Collapse omega_2 to omega_1 so that CH is true but there are now omega_1 many (mutually) nonconstructible subsets of omega in this extension
(this is the model you spoke of in your answer to Ewan Delanoy’s question on mathstack exchange: “How many nonconstructible reals are needed to make the Continuum Hypothesis false?”)

what would Koepke’s theory of computation with Ordinal Turing machines ‘look like’ in this particular model (and would it be the same as if one merely added omega_1 mutually nonconstructible subsets of omega to L)?

Also how does this relate to Moschovakis’ Abstract first-order computability? (i.e. can hypercomputation be an instantiation of abstract first-order computabiity?)

• Dear Thomas,

I have absolutely no idea how to answer this question of yours. Simply because I am completely unfamiliar with Koepke’s theory. I am also not familiar enough with Moschovakis’ theory. In the answer that you are referring to I only gave an example to how the number of non-constructible reals needed to negate the continuum hypothesis cannot be decided internally.