The Length of Infinite Time

Turing Machine Computations

P. D. Welch

Graduate School of Science & Technology,

Kobe University, Rokko-dai, Nada-ku Kobe 657, Japan.

welch@pascal.seg.kobe-u.ac.jp

7’th January 1999 §1 Machine theoretic definitions and results. §2 Getting Clockables = Writables. §3 The set-theoretic context. Reference: “Infinite Time Turing Machines” J. Hamkins & A. Lewis, J. of Symbolic Logic (to appear).

§1 The H-K machines Hardware: just as for ordinary Turing Machines, but for convenience, we consider the infinite tape as divided into three infinite tapes, for input, scratch computations and an output tape.

One tape position is designated in advance, as the “Limit Position”.

[figure: 0; 1; 0; 1; 0; 1; Input; Scratch; Output; R/W Head; Limit Position; 1; 0; 0; 1; 1]

Software: just as for ordinary Turing Machines, but with the addition of an extra “limit state” q_{L}.

Let ⟨P_{n} | n < ω⟩ enumerate all programs. Let the cells be enumerated as ⟨C_{i} | i < ω⟩ with contents at time ν in the computation of program n denoted by C_{i}^{n}(ν) ∈ {0, 1}.

Action: At times ν = β + 1: obey the usual T.M. rules of the program P_{n}.

At limit times ν: R/W Head returns to the Limit Position; Cell values C_{i}(ν) = Lim_{\overline{τ}→ν} sup_{τ≥\overline{τ}} C_{i}(τ).

• φ_{n}(x)(x ∈ 2^{ω}) be the result of running P_{n} on input string x.

• ∀n, x∃α < ω_{1} so that the behaviour of φ_{n}(x) has “settled” by stage α: either it has entered a permanent looping cycle or it has halted: φ_{n}(x)↓y for some y ∈ 2^{ω}.

• Decidable properties: Arithmetic; “x ∈ W O”; (thus) any Π_{1}^{1} predicate. Def ξ ∈ W ⟷ ∃p ∈ ωϕ_{p}(0) ↓x (W = “Writables”) Note: “φ_{p}(x)↓y (in α steps)”, “φ_{p}(x)↑ ” are both Δ_{2}^{1} properties (in a code for α). Def λ =_{df} sup {||x|| : x ∈ W O ∩ W}; γ =_{df} sup {Clock }.

Clock =_{df} {α | ∃p ∈ ω ϕ_{p}(0) in exactly α steps }. Fact (Hamkins-Lewis) λ ≤ γ. Q.1 Is λ = γ? Def H_{λ} = \{y ∈ HC | ∃\overline{y} ∈ W ∧ \overline{y} codes y\}. Q.2 Is H_{λ} = L_{λ}? Fact (Hamkins-Lewis) H_{λ} is a transitive admissible set, closed under hyperjump (and more).

Oracles: For y ∈ 2^{ω} φ_{p}^{y}(x) ≃ φ_{p′}(⟨x, y⟩) For A ⊆ 2^{ω} φ_{p}^{A}(x). Ask Yes/No questions “Is z ∈ A?”

There is an associated reducibility relation associated to reals or sets of reals: x ≤_{∞} y, A ≤_{∞} B:

x ≤_{∞} y ⟷ ∃nφ_{n}(x)↓y

A ≤_{∞} B ⟷ ∃n∀xφ_{n}^{B}(x)↓1 if x ∈ A, ↓0 if x ∉ A

Jumps: O^{▽} =_{df} {n | φ_{n}(0)↓} (“Weak Jump”).

O^{▼} =_{df} {(n, x) ∈ ω × 2^{ω} | φ_{n}(x)↓} (“Strong Jump”).

Def Γ =_{df} {A ⊆ 2^{ω} | A is semi-decidable from a real } =

= {A ⊆ 2^{ω} | ∃r ∈ 2^{ω}∃n∀x x ∈ A ⟷ φ_{n}^{r}(x)↓1 }.

Δ =Γ ∩¬Γ .

Fact (Hamkins-Lewis) Δ ⊆ Δ_{2}^{1} is a σ-algebra, closed under Suslin’s operation A. Γ forms a Spector pointclass with norm ψ : A ⟶ On on a semi-decidable set A = {x ∈ 2^{ω} | φ_{p}(x)↓}:

ψ(x) ≃ α(φ_{p}(x)↓ in α steps. )

Q.3 What are the decidable sets of integers? What are the semi-decidable sets of reals?

§2 Clockables are Writable

Theorem 1 λ = γ.

This is a corollary of the Main Proposition below about stabilization times of cells.

Def (H-L) (i)The eventually writable reals: EW =_{df} {x | ∃p∃μ∀ν ≥ μφ_{p}(0) has x on its output tape at time ν}. (ii) The accidentally writable reals: AW =_{df} {x | ∃p∃μφ_{p}(0) has x on its output tape at time μ}; (iii) ζ =_{df} sup {||x|| : x ∈ EW ∩ W O}; (iv) Σ =_{df} sup {||x|| : x ∈ AW ∩ W O}.

Then W ⊆ EW ⊆ AW and one can show that the inclusions are strict; indeed H-L show λ < ζ < Σ.

Fix an arbitrary p ∈ ω and consider the computation φ_{p}(0) and the cells C_{i} = C_{i}^{p} of that machine’s tape.

Def For any time ν let

δ_{i}(ν) = sup {ν′ < ν | ν′ = 0 ∨ C_{i}(ν′) ≠ C_{i}(ν′ + 1)} ≤ ν.

For Lim(ν) we say C_{i} has (locally) stabilized at stage ν, if δ_{i}(ν) < ν.

Main Proposition ∀i δ_{i}(Σ) < Σ ⟶ δ_{i}(Σ) < ζ.

Proof: Consider U the universal machine that simulates, by cutting up its scratch tape into infinitely many slices, all the computations ϕ_{q}(0) for each q simultaneously.

Def Let σ(ν) =_{df} Σ{||x|| : x ∈ W O ∧ x is on one of U’s tapes at stage ν}.

(1) As ν → ∞ and as σ(ν) ∈ AW, σ(ν) becomes unbounded in Σ.

(2) Once ν is sufficiently large, all the tapes of U that are destined to be eventually written to, will have received those eventual values; hence at some earliest moment \overline{ν} say, σ(\overline{ν}) ≥ ζ, and this will hold at all later stages of time after \overline{ν}.

We describe now a machine M = M(i, p), whose scratch tape is divided into three infinite parts S_{0}, S_{1}, S_{2}. M is simulating the universal program U on S_{0} (by further slicing up of S_{0}). Let T denote M’s output tape. M is to behave as follows at time ν.

(i) M computes a current value for “σ(ν)” by looking at the cells of its “U”; (ii) on its scratch tape S_{1}, it writes a code for the whole course-of-computation of the first σ(ν) steps of ϕ_{p}(0). Let δ = δ_{i}(σ(ν)) the current stabilization value for cell C_{i}. (iii) Then M inspects T: the contents of T is a sequence x ∈ 2^{ω}, it tests (using S_{2}) if x ∈ W O. If (a) x was not a code for a wellorder, or if (b) ||x|| < δ, then x on T is overwritten by (a code for) δ (which M has available); otherwise T is left untouched. (iv) M runs another step in each of U’s computations, and then returns to stage (i) now at time ν + 1.

Claim If δ_{i}(Σ) < Σ then (a) the content of T is eventually constant, and codes an ordinal τ < ζ; (b) δ_{i}(Σ) ≤ τ.

Proof: Let δ̃ =_{df} δ_{i}(Σ) and suppose δ̃ < Σ. At various stages ν, the current σ(ν) is calculated. When M inspects T at (iii) above, it always leaves a code z on T with ||z|| ≥ δ each time.

Eventually (by (1) above) σ(ν)) becomes sufficiently large below Σ that it is greater than the true δ̃. At this time an ordinal ≥ δ̃ ends up written on T. But note the content of T remains fixed hereafter: there will not be any reason to overwrite it, irrespective of the fact that the value of σ(ν) fluctuates. This is our τ. Hence τ ∈ EW as witnessed by the machine M. Thus δ̃ ≤ τ < ζ.

Q.E.D.Claim & Proposition

Cor Theorem 1 holds. Proof: We have just seen that for any i < ω if C_{i} is stabilized at Σ, then the point of stabilization is below ζ. Hence a), the “snapshot” of the state of the computation (meaning the distribution of 0’s and 1’s in the cells C_{i}^{p}, the state of the machine, etc.) is exactly the same at time ζ and Σ; and moreover b), for no i < ω for which C_{i}(ζ) = 0, is C_{i}(ξ) = 1 for any ζ < ξ < Σ. The conclusion to be drawn from b) is that either φ_{p}(0)↓, and has halted at time μ < ζ, (so μ is “clockable”, i.e. μ < γ), or the snapshots at ζ and Σ are from a permanently looping cycle.

Claim If φ_{p}(0)↓then μ < λ. Proof: As μ < ζ let q ∈ ω be a program number so that ϕ_{q}(0) eventually writes μ on its output tape. Informally we let P_{r} be the program that (i) runs φ_{q}(0); (ii) keeps checking to see if O.T. of φ_{q}(0) contains an ordinal δ long enough to support a halting computation of φ_{p}(0). When (ii) occurs P_{r} is to halt with output that ordinal δ. Hence μ ≤ δ ∈ W. So μ < λ. Q.E.D.Claim

Hence every “clockable” ordinal is “writable”. Q.E.D.Cor

By similar arguments:

Cor H_{λ} = L_{λ}; L_{ζ} = \{y | y is coded by some \overline{y} ∈ EW\}.

Cor The decidable sets of integers are those x ∈ 2^{ω} ∩L_{λ}.

§3 The Set-Theoretic Context

Theorem 2 (ζ, Σ) is the lexicographically least pair with ζ Σ_{2}-extendible to Σ; i.e. L_{ζ} ≺_{Σ_{2}} L_{Σ} .

Proof: Sketch of L_{ζ} ≺_{Σ_{2}} L_{Σ} : suppose L_{Σ} ⊧ ∃x∀yψ(x, y, u) with u ∈ L_{ζ}, ψ ∈ Σ_{0}. Let x_{0} be the L_{Σ} -least witness. Let ρ_{0} be its L-rank. As u ∈ L_{ζ}, u ∈ EW. Fix a computation φ_{q}(0) that eventually has (a code for) u on its output tape. Suppose that at time ν the contents of this tape is u(ν).

We describe a machine similar to the above: let M run the universal machine U and compute σ(ν) as above. We let x(ν) denote the contents of M’s O.T. at time ν. Given σ(ν), M computes a code for L_{σ(ν)} and checks if L_{σ(ν)} ⊧ ∀yψ(x(ν), y, u(ν)) (and is the L-least such); If so, or if x(ν) is not a code for any set in L_{σ(ν)} then M leaves the O.T. unchanged and sets x(ν + 1) = x(ν). Otherwise it writes a code for the current L_{σ(ν)}-least witnessing x to its own O.T. as x(ν + 1). As σ(ν) is unbounded in Σ, eventually both u = u(ν) and σ(ν) > ρ_{0}. At this point a code for x_{0} is written to the O.T. This will never be overwritten (even were σ(ν) to drop below ρ_{0}). Hence x_{0} ∈ EW, and so x_{0} ∈ L_{ζ} by the results above.

Leastness: check that if L\overline{ζ} ≺_{Σ_{2}} L\overline{Σ} then \overline{ζ} and \overline{Σ} have “permanently repeating snapshots” of any computation.

Q.E.D.

Theorem 3 (i) λ is the least λ′ with L_{λ′} ≺_{Σ_{1}} L_{ζ} ; (ii) O^{▽} ≡_{1} A_{λ}^{1} (the Σ_{1}-mastercode for L_{λ}).

Cor x ≤_{∞} y ⟷ x ∈ L_{λ^{y}}[y]; the assignment x → λ^{x} satisfies a Spector Criterion, thus:

x ≤_{∞} y ⟶ (x^{▽} ≤_{∞} y ⟷ λ^{x} < λ^{y}).

• This lets us develop a degree theory on reals that is somewhere intermediate between Δ_{1}^{1}-degrees (or hyperdegrees) and Δ_{2}^{1}-degrees.

• We may characterise the jump hierarchy in terms of ζstable ordinals; further we may characterise the reals in the iterates of the (weak) jump operator 0^{▽α} for α < ζ; and the reals 0^{▽α} themselves as certain mastercodes.

• In particular we may answer various questions concerning minimal ∞-degrees.

The strength of the machine architecture

Kidder and Hamkins have defined the operation Γ_{HL}:

Γ_{HL}(⟨⟨C_{i}(τ) | i < ω⟩ | τ ≤ ν⟩) = ⟨C_{i}(ν + 1) | i < ω⟩

as being determined by the underlying Turing machine program at successor stages, whilst ⟨C_{i}(ν) | i < ω⟩ =

Γ_{HL}(⟨⟨C_{i}(τ) | i < ω⟩ | τ < ν⟩) = ⟨lim_{τ→ν} sup_{τ<τ′<ν} C_{i}(τ′) | i < ω⟩

at limit stages ν. More generally, let us call any function Γ : ^{<On}(^{ω}2) ⇒ (^{ω}2) defined on sequences of reals “appropriate”, and let us call a “Γ-machine”, one that uses the operator Γ at all limit stages. Let W_{Γ}, EW_{Γ} … denote the classes of reals arising when we use such a machine.

Def A Γ-machine is Σ_{n}-complete, if for any appropriate \overline{Γ} , provably total in Σ_{n}-KP, then EW_{Γ} ⊇ EW\overline{Γ}.

Theorem 4 (i) Γ_{HL} is Σ_{2}-complete.

(ii) For appropriate Σ_{2}-KP definable Γ, W ⊇ W_{Γ}.

(iii) However there is a provably total Γ^{∗} in Σ_{2}-KP +Σ_{2}- Separation, so that W_{Γ^{∗}} ⊃ EW.

Higher-Type Reducibility

It follows from the above that the sets of reals semidecidable in x ∈ 2^{ω} are those A expressible as follows: let ψ_{0}(v_{0}, v_{1}) be a Σ_{1} formula, then let

y ∈ A ⟺ L_{λ^{⟨x,y⟩}}[x, y] ⊧ ψ_{0}(x, y).

A is semi-decidable in B (A, B ⊆ 2^{ω}) and x ∈ 2^{ω} can be seen to be given similarly as:

y ∈ A ⟺ L_{λ^{⟨x,y,B⟩}}[x, y, B] ⊧ ψ_{0}(x, y, B).

Let A ≤_{r,∞} B denote A is infinite time computable from a real and B.

Post’s problem: are there

1) A ⊆ 2^{ω}, A ∈Γ , A not decidable but 0^{▼} ≰_{r,∞} A?

2) A, B ∈Γ A ≰_{r,∞} B ∧ B ≰_{r,∞} A?

• In L, the constructible universe, there are A, B as in 2).

• Det(Boolean (Γ )) ⇒ any A ∈Γ \Γ ∩¬Γ satisfies 0^{▼} ≡_{r,∞} A.

Open Questions

Open Question 1 Does a negative answer to 1) imply Det(Π_{1}^{1})? Or Det(Γ )? Open Question 2 Does Wadge-Det(Γ ) ⇒ Det(Γ )? Open Question 3 What is the strength of Det(Γ )? We do know that

• Det(Γ ) ⇒ ∃# for an inner model of a strong cardinal.

• In fact, an example of a decidable predicate is: “⟨x, y⟩ ∈ 2^{ω} codes countable premice M, N <_{∗} O^{¶} and M ≤_{∗} N in the (pre)mouse ordering.”