Infinite-time Turing machine

An infinite-time Turing machine operates like a classical Turing machine but with a special rule for limit ordinal times. At successor stages, the machine follows the standard transition function. At limit stages, the machine's state and head position are defined as the lim inf of their previous values, and each cell of the tape is updated to the lim sup of its previous values, effectively capturing the eventual behavior of the computation.

This definition allows the machine to compute through all finite ordinals and then continue into the transfinite, with the computation potentially halting at any ordinal time. The machine has three tapes: input, scratch, and output, each with a single head. The input tape is read-only, and the output tape is write-only, while the scratch tape is read-write.

The sets decidable by infinite-time Turing machines form a strict superset of the arithmetical hierarchy, coinciding with the class Δ¹₂ of the analytical hierarchy. This means ITTMs can decide sets that are not decidable by any classical Turing machine, such as the truth of certain second-order arithmetic statements.

The halting problem for ITTMs is itself ITTM-decidable, but the set of ITTM-halting inputs is not ITTM-computable in the sense of being decidable by a machine that always halts. This leads to a transfinite version of the halting problem, with a hierarchy of halting problems indexed by ordinals, each more complex than the previous.

One lesser-known aspect is the existence of lost melodies: real numbers that are recognizable by an ITTM (i.e., there is a machine that halts exactly on that real) but not computable by any ITTM (i.e., no machine writes that real to the output tape). This phenomenon, analogous to a tune one can hum but not write down, highlights the subtlety of ITTM computability.

Another notable detail is the role of the lim inf and lim sup rules in defining the state and tape contents at limit ordinals. These rules ensure that the machine's behavior is well-defined and that the computation is continuous in a topological sense. Additionally, ITTMs can be used to characterize the complexity of sets in the projective hierarchy, and they have connections to descriptive set theory and the theory of admissible ordinals.

Several variants of infinite-time Turing machines have been studied. One notable variant allows the machine to have multiple tapes or to use a different limit rule, such as the eventual rule where the state is the eventual value if it stabilizes, otherwise a special undefined state. Another extension considers machines that can perform a finite number of operations at each limit stage, or that have access to an oracle for the halting problem of ordinary ITTMs.

These variants lead to different notions of computability and different hierarchies of decidable sets. For instance, the ITTM with ordinal parameters can decide sets that are not decidable by the basic model, and the ITTM with a tape of length ω₁ can compute functions on ordinals. The study of these variants is an active area of research in computability theory.

Transfinite ordinal

An ordinal number that is greater than all finite ordinals, such as ω, ω+1, and ω₁.

Lim inf

The limit inferior of a sequence, the infimum of the eventual values of the sequence.

Lim sup

The limit superior of a sequence, the supremum of the eventual values of the sequence.

Δ¹₂

A class in the analytical hierarchy consisting of sets that are both Σ¹₂ and Π¹₂.