MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, if no modifications on sight, if the power of his machine plus infinitely iterated super jumps from super oracles (those consisting of uncountable sets of real numbers) could reach that level.

share|cite|improve this question
Do you mean "uncountable sequence of natural numbers?" – Noah Schweber Feb 8 '13 at 6:33
no, I mean of real numbers, because the input of his machines is a real number, that is, an infinite sequence of 1's and 0's (the tape has infinite length). this is an extract from his article: Thus,we want somehow to allow a set of real numbers,such as the halting problem H,to become an oracle for the machines.And since such a set could be uncountable,and these in particular is definitely uncountable,we can’t expect to be able to write out the entire contents of the oracle on an extra tape,as in the classical theory." – Julian Fernandez Feb 8 '13 at 7:06
actually I used "natural" instead of "real", I already corrected it. Thanks! – Julian Fernandez Feb 8 '13 at 7:09
Julian, can you confirm that you want $\Sigma^2_1$, which is a very significant step up in complexity, as opposed to $\Sigma^1_2$, which is a comparatively smaller step up from $\Delta^1_2$? – Joel David Hamkins Feb 8 '13 at 13:51
One the funkiest question titles of all time! – Mariano Suárez-Alvarez Feb 8 '13 at 19:34
up vote 15 down vote accepted

One should think of the class $\Delta^1_2$ as truly enormous, closed under powerful set-theoretical constructions. It may help to keep in mind that the minimal transitive model of ZFC, if it exists, is contained inside $\Delta^1_2$, and so one cannot jump out of $\Delta^1_2$ with a computational operation that is absolute to transitive models of set theory. Andy Lewis and I pointed out in our paper Infinite time Turing machines that $\Delta^1_2$ is closed under the boldface jump: if $A$ is $\Delta^1_2$, then so is $A^\blacktriangledown$.

In particular, let us imagine that we equip an infinite time Turing machine with a jump-operator black box, which whenever a real $x$ is written on a special tape, then the jump $x^\triangledown$ appears on another special tape. Such a machine could iteratively compute the jump transfinitely often, as suggested in your question. Nevertheless, these machines are still stuck inside $\Delta^1_2$; every function they compute and every set they decide will have complexity at most $\Delta^1_2$. (In fact, this model is simply equivalent to having the set $0^\blacktriangledown$ as a set oracle. And we can iterate this process an enormous number of times, so that oracle $0^{\blacktriangledown^{(\alpha)}}$ will still be in $\Delta^1_2$.)

Meanwhile, aiming to get beyond the $\Delta^1_2$ barrier, Philip Welch observed that the connection between infinite time Turing machines and $\Delta^1_2$ is related to the fact that the limit stage operation of the machine is defined by the limsup, a definition of complexity $\Sigma_2$ (the value is $0$ at the limit if there is an earlier stage, such that for all later stages, the value is $0$). With the goal of finding a corresponding machine-computation model giving rise to $\Delta^1_3$ and higher levels of the projective hierarchy, Philip Welch and Sy Friedman introduced new machine models with more complicated limit behavior in their article "Hypermachines", Journal of Symbolic Logic, 76, No.2, June 2011, 620-636. As far as achieving $\Sigma^1_n$ might be concerned, this seems to be the most promising answer to your question.

As for $\Sigma^2_1$, I don't know of anything resembling infinite time Turing machines that approaches it. At this level of complexity (and even at levels of complexity within the projective hierarchy), the behavior of a computational device able to decide such properties would have to be sensitive to the background set theory in which the device is operated, whereas our more ordinary conceptions of "computation" tend to be that they are absolute, for example, to forcing extensions.

share|cite|improve this answer
Joel, super clear answer, case closed. Thanks!!! – Julian Fernandez Feb 8 '13 at 18:53
Julian, thanks for your vote of confidence! But I think we should leave it open whether a clever person might come up with a concrete computational model approaching $\Sigma^2_1$. – Joel David Hamkins Feb 9 '13 at 1:32
Yes, the ITTM model has only ordinary tapes with $\omega$ many cells. I believe our oracle concept for sets of reals is the right one to consider, but I suppose I can imagine stronger ones. If you want to use uncountably many cells, then if the cells are to be well-ordered (in order to mak sense of traversing them), then you will not just be putting the set on the oracle tape, but the set in some order, which would carry more information. – Joel David Hamkins Mar 26 '13 at 11:34
Meanwhile, one can think of our oracle concept as having the yes-no answers for every real written out somewhere, with a call-by-address scheme, so to get to the information about a particular real, you just write it into the register, and then receive the yes/no answer. This way of thinking about it seems closer to what you describe, but is functionally equivalent to our oracle operation. – Joel David Hamkins Mar 26 '13 at 11:36
The ordinal-tape machines have by now been introduced and studied by Peter Koepke and others in his group, and there are infinite time register machines, and ordinal register machines, etc., exploring the full range of possibilities. – Joel David Hamkins Mar 26 '13 at 16:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.