8
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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." $\endgroup$ Feb 8, 2013 at 7:06
  • $\begingroup$ I think this is a bit too vague - how do you propose for a Turing machine to make use of a set of reals as an oracle? If you want to use higher type objects as oracles, and reach set-theoretically huge classes like $\Sigma^2_1$, I think your best bet is to look not at infinite time Turing machines, but at $E$-recursion, which can handle arbitrary sets as oracles. $\endgroup$ Feb 8, 2013 at 7:41
  • $\begingroup$ A good source on $E$-recursion is www.math.harvard.edu/~sacks/erecint.pdf. By the way, what $\Delta^1_2$ sets can Hamkins' infinite time Turing machines decide? I'm not very familiar with that setup. $\endgroup$ Feb 8, 2013 at 7:44
  • 2
    $\begingroup$ 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$? $\endgroup$ Feb 8, 2013 at 13:51
  • 5
    $\begingroup$ One the funkiest question titles of all time! $\endgroup$ Feb 8, 2013 at 19:34

1 Answer 1

17
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ Joel, super clear answer, case closed. Thanks!!! $\endgroup$ Feb 8, 2013 at 18:53
  • 2
    $\begingroup$ 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$. $\endgroup$ Feb 9, 2013 at 1:32
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 26, 2013 at 11:34
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 26, 2013 at 11:36
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 26, 2013 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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