What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set?
More generally, what is the complexity of ITTMs with $n$ higher types?
Definitions and background
An ITTM with $n$ higher types has a finite internal state and a finite number of tapes of types $1$ through $n+1$. A type 1 tape can be viewed as a subset of $ω$, type 2 - $P(ω)$, type 3 - $P(P(ω))$, and so on. A bit $S$ of a type $i>1$ tape $T$ (indicating whether $S∈T$; 0 indicates absence) can be accessed or modified by first storing $S$ in any type $i-1$ tape. A type 1 tape is the usual infinite tape (and a natural number is a type 0 input). All tapes are initially empty except for the type 1 input tape.
Just like an ITTM, the machine runs for an unlimited transfinite ordinal number of steps, with $\liminf$ behavior at limit stages ($\limsup$ gives essentially the same expressiveness). Thus, the contents of a tape $T$ at a limit time $α$ are $T_α = \liminf_{β→α} T_β = ∪_{λ<α} ∩_{λ<β<α} T_β$. Also, at limit stages, the internal state also uses $\liminf$ and the head locations for type 1 tapes are reset (though any reasonable variation gives the same expressiveness).
If there are no type >2 tapes, then the number of type 2 tapes is immaterial (if nonzero), but beyond that, the status is unclear, and it is possible (but not likely) that the above computational model is too restrictive.
Despite the use of infinite sets of higher types, the complexity is $Δ^1_2$, but apparently very high up in the $Δ^1_2$ hierarchy.
Upper bound:
Analogously to ITTMs (for which the below bounds are optimal (using $ω=ω_0$)), we have an upper bound on the complexity of ITTMs with $n$ higher types and input $r$. Let ordinals $β,γ$ be minimal with $L_β(r) ≺_{Σ_2} L_γ(r)$ and $ω_n^{L_β(r)} = ω_n^{L_γ(r)} < β < γ$. We have:
• If the machine halts, then its computational history and output (and the singleton set containing these) are $Δ_1^{L_β(r)}(r)$.
• If sets are never erased from a given tape, its eventual contents are (as a predicate) $Σ_1^{L_β(r)}(r)$.
• If a tape is eventually constant, its eventual contents are $Δ_2^{L_β(r)}(r)$ (for type $n+1$ tape, this is equivalent to being in $L_β(r)$).
• The contents of a tape at time $ω_1$ are $Σ_2^{L_β(r)}(r)$ (since we are using $\liminf$).
• At every point, the state is in $L_γ(r)$.
But are these bounds optimal?
Extensions with transfinite types: We can add fixed transfinite types using infinitely many tapes to access a bit of a tape of a transfinite type. Or we can even use a special tape to allow adding new tapes and types dynamically (with cofinal changes of a type resetting it to 0). However, if we could grow types without limits, then even for the simple model of ordinal register machines, recognizability would equal $Σ^1_2$ (or $Σ^1_2(r)$).
