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.
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$.
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’ ?
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:
i) Start with L for V=L
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.
Sorry I cannot help you further than that.
The reason I asked the question was because Koepke’s theorem seems to put one in the same predicament Cohen showed forth in his paper “The Discovery of Forcing” with regards to not-CH. In this paper, Cohen proved the following theorem:
“One cannot prove the existence of any uncountable standard model in which AC holds and CH is false…[Cohen, 2002 pg. 1090]” (Proof: “If M is an uncountable standard model in which AC holds, it is easy to see that M contains all countable ordinals. If the Axiom of Constructiblilty is assumed, this means that all the real numbers are in M and are constructible in M. Hence CH holds [Cohen, ibid, pp 1090-1].”
If one considers the model V=HOD of ZFC, (since HOD sets are defined from a finite set of ordinal parameters), can one prove the existence of an uncountable standard model M in which AC holds and there exists a set in HOD (relativised to M) which is not ordinal computable? The proof that one cannot seems to rest on an analogy with Cohen’s proof (should be able to be proved the same way. One can, of course, assume the existence of a measurable cardinal to get nonconstructible sets, but this is in stark contrast to ordinary recursion theory over the natural numbers where there are definable non-r.e. sets (eg. the productive sets). This is one of the reasons I asked the question.
Pingback: A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020 | Joel David Hamkins