Question

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.

Answer 1

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.