Bounding lemmata for non-deterministic halting times of transfinite Turing machines

P.D. Welch

School of Mathematics, University of Bristol, BS8 1TW, England

Abstract

We use the methods of descriptive set theory and generalized recursion theory to prove various Bounding Lemmata that contribute to a body of results on halting times of non-deterministic infinite time Turing machine computations. In particular we observe that there is a Uniform Bounding Lemma which states that if any total algorithm halts before the first ordinal admissible in the input x, then there is a recursive ordinal γ by which the algorithm halts on all inputs.

Key words: models of computation, complexity classes, descriptive set theory 1991 MSC: 68Q05, 68Q15, 03D60, 03D65, 03E15

We consider some queries arising from the paper [2]. These concerned various complexity pointclasses defined using halting times of computations on the Infinite Time Turing machines of Hamkins and Kidder [3], with or without existential ‘non-determinacy’ witnesses. The main theorems of this note are the Bounding and Uniform Bounding Lemmata below. In particular it is the latter that answers a query from [2] and which explains various phenomena of their paper. Briefly put the Uniform Bounding Lemma states that if any total algorithm halts before the first ordinal admissible in the input x, then there is a recursive ordinal γ by which the algorithm halts irrespective of x.

We shall first recall the main definitions here of the machine architecture. Later we shall use some results and notions from admissibility theory (for which the reader may consult [1]) and from generalised recursion theory (see [7]) and descriptive set theory(see [4]).

⋆ The author acknowledges support of an EPSRC Springboard Fellowship whilst preparing this paper, and would like to thank the referee for their careful scrutiny and suggestions.

Email address: p.welch@bris.ac.uk (P.D. Welch).

Preprint submitted to Elsevier 15 December 2006

An infinite time Turing machine is essentially a standard Turing machine that is allowed to run for transfinite lengths of time. It comes with a standard finite program with an additional limit state, q_{L}, which by fiat it enters at limit stages of time λ; a read/write head returns to the leftmost cell(s) of an infinite tape or tapes also at such times. If we enumerate the cells of the tape(s) as C_{i} for i ∈ ℕ, and if C_{i} has content C_{i}(γ) ∈ {0, 1} at time γ, then, again by fiat, for any limit time λ, for any i < ω C_{i}(λ) = lim sup_{γ⟶λ}⟨C_{i}(γ)|γ < λ⟩. We have written cell(s) or tape(s) because although the model of [3] had three infinite tapes, for input, scratch work, and output respectively, and an alphabet consisting of just 0’s and 1’s, other, single tape, models are possible see [10]. We shall maintain however throughout this paper the formalism of [3]. In that case the read/write head is considered as reading simultaneously one cell from each of the three tapes. The state of the machine and its program then determine its next action depending on which triple of 0’s and 1’s it is reading. At successor stages of time it acts simply like an ordinary Turing machine.

As programs are finite we can consider them as enumerated ⟨P_{e}|e ∈ ω⟩ with P_{e} regarded as computing the e’th ITTM function φ_{e} : ℝ ⟶ ℝ where we identify ℝ with 2^{ℕ} . P_{e} thus acts on input strings x ∈ 2^{ℕ} ; integer input is obtained by identifying n with the string consisting of n 1’s followed by all 0’s. Like any Turing machine either P_{e}(x) halts, or runs for ever - we write P_{e}(x) ↓ or P_{e}(x) ↑. We shall be concerned here mostly, but not entirely with halting times of such computations.

Definition 1 P_{e}(x) ↓^{α} will denote that program P_{e}(x) ↓ in exactly α steps. P_{e}(x)↓^{≤α}, P_{e}(x)↓^{<α}are defined analogously.

To clarify the above: P_{e}(x)↓^{α} means that at ordinal time α the read/write head is in particular state q_{s} and is reading a triple of cells (one from each of the three tapes) so that it’s program determines that it go into a halting state q_{h}. Thus a machine may halt exactly at some limit stage of time α where then q_{s} = q_{L}.

Suppose x is simple: perhaps it is an integer (i.e. it is a binary code for n ∈ ℕ followed by an infinite string of 0’s), perhaps it is 0 (in the above sense) itself. What possible halting times as e varies are there for P_{e}(x)? [3] calls an ordinal clockable if it is the halting time of a computation with input 0.

Further, let us define:

Definition 2 “P_{e}(x) ↓ y” will denote that P_{e}(x) ↓ and that y ∈ 2^{ℕ} is the contents of the output tape on halting. (Again P_{e}(x) ↓^{α} y etc. are defined analogously).

Then we say that y is writable if it is the output of some program: P_{e}(0)↓ y. An ordinal β is writable if some y ∈ WO is writable, and y codes a wellordering of rank β. What possible ordinals are writable? It is easy to readjust a program that demonstrates that β is writable to one that shows that any β′ < β is writable. Thus the writable ordinals are an initial segment, λ, of all ordinals. Hamkins and Lewis [3] showed that there are gaps in the clockable ordinals and the following:

Theorem 1 Hamkins and Lewis [3] If β is admissible then it is not clockable.

Welch [9] shows that λ, the suprema of the writable ordinals, is also the supremum of the clockable ordinals.

One may generalise these questions to those involving arbitrary input x. The following is Definition 5.18 of Deolalikar, Hamkins & Schindler:

Definition 3 An ordinal α is nondeterministically clockable if there is an algorithm P_{e} which halts in time at most α for all input and in time exactly α for some input. More generally, α is nondeterministically clockable before β if there is an algorithm that halts before β on all input and in time exactly α for some input.

Symbolically: α is nondeterministically clockable iff

∃e ∈ ℕ[∀x ∈ 2^{ℕ} P_{e}(x)↓^{≤α} ∧∃x ∈ 2^{ℕ} P_{e}(x)↓^{α}].

This notion arises in the paper [2], which was concerned with various complexity pointclasses defined using halting times of computations on these machines, with or without existential ‘non-determinacy’ witnesses. The nomenclature comes from Schindler’s paper [8]. The attempt there was made to generalise the concepts of the deterministic polynomial time class P and the non-deterministic class NP from ordinary recursion theory to the infinite time context. As ‘non-determinism’ in the ordinary recursion theoretic setting can be construed as an algorithm acting on a ‘guess’ one can use the same idea and define classes via machines that use ‘accept/reject’ programs to ascertain whether a number or real x is in a class A; non-determinism then here allows some extra side information from a guess to be used.

Definition 4 (see [2]) (i) A ∈ P^{α} if there is β < α and there is an infinite time Turing machine deciding each x ∈ A in fewer than β many steps.

(ii) A ∈ NP^{α} if there is β < α and there is an infinite time Turing machine T such that x ∈ A if and only if there is y ∈ ℝ such that T accepts (x, y), and T halts on any input (w, z) in fewer than β steps.

Here “deciding x ∈ A in fewer than β many steps” can be taken to mean that the machine rejects or accepts in less than β many steps. If β is a limit ordinal, then we may equivalently ask that in less than β many steps it halts with a 1 or 0 on the output tape depending on whether x is, or is not, in A. P is defined as P^{ω^{ω}} and NP as NP^{ω^{ω}} with the notation to be suggestive of ‘polynomial’ (although we are of the opinion that this is at most suggestive, and we remain unconvinced that there is any analogy of substance with the classical P/NP notions). We then have:

Theorem 2 ([2] Thm 3.2) The classes NP^{α} for ω+2 ≤ α ≤ ω_{1 ck} are all identical to the class Σ_{1}^{1} of lightface analytic sets. In particular, NP = NP_{ω+2}, and so membership in any NP set can be verified in only ω many steps. Similarly, the corresponding classes co-NP^{α}are all identical to the Π_{1}^{1} sets. Consequently, NP∩co-NP is exactly the class Δ_{1}^{1} of hyperarithmetic sets.

Here ω_{1 ck} is the supremum of all recursive ordinals, and ω_{1 ck}^{x} will be used to denote the supremum of all ordinals recursive in x (in both cases this means recursive in the usual, ordinary sense). We see then in the last theorem how the implicit existential quantifier over reals as guesses in the definition of NP surfaces in its classification. Clearly P ⊆ NP ∩co NP, and so the last theorem (due to Schindler) then shows however that “P ≠ NP ”.

Theorem 3 ([2] Thms 3.1, 5.4) P ≠ NP ∩ co NP. In fact P^{α} ≠ NP^{α} ∩ co NP^{α} for ω + 2 ≤ α < ω_{1 ck}. However P^{α} = NP^{α} ∩ co NP^{α} for α = ω_{1 ck}.

The difference in the two parts of the result above reflects the difference in α < ω_{1 ck} being clockable, and ω_{1 ck} not being so: indeed it starts a gap of clockable ordinals of length ω: no ordinal β ∈ [ω_{1 ck}, ω_{1 ck} + ω) is clockable; the next clockable is ω_{1 ck} + ω.

We may widen the definition to allow not just constant bounds on the lengths of computations. In the following, we say that f : ℝ ⟶ On is a Turing invariant function if x, y have the same (ordinary) Turing degree, then f(x) = f(y).

Definition 5 Let f : ℝ ⟶ On be a Turing invariant function. (i) A ∈ P^{f} if there is an infinite time Turing machine deciding each x ∈ A in fewer than f(x) many steps.

(ii) A ∈ NP^{f} when there is an infinite time Turing machine T such that x ∈ A if and only if there is y ∈ ℝ such that T accepts (x, y), and T halts on any input (x, y) in fewer than f(x) many steps.

Of particular interest is the function f_{0}(x) = ω_{1 ck}^{x} + 1. They show:

Theorem 4 P^{f_{0}} = P^{ω_{1 ck}}.

They remark at the beginning of this section that P^{f_{0}} appears at first more generous than the earlier classes, because computations on inputs are now allowed up to ω_{1ck}^{x} steps.

“The equality [P^{f_{0}}] = P^{ω_{1 ck}} should be surprising, because it means that although the computations deciding x ∈ A for A ∈ P^{f_{0}} are allowed to compute up to ω_{1 ck}^{x}, in fact there is an algorithm needing uniformly fewer than ω_{1 ck} many steps. An affirmative answer to the following question would explain this phenomenon completely.

“Question 4.3 Suppose an algorithm halts on each input x in fewer than ω_{1 ck}^{x} steps. Then does it halt uniformly before ω_{1 ck}? ”

They also note that P^{ω_{1 ck}+1} = P^{ω_{1 ck}}: this is prima facie also surprising since stating that A ∈ P^{ω_{1 ck}+1} requires only that an algorithm determining membership in A must halt before ω_{1 ck}, whereas for the latter class an algorithm with uniform bound β < ω_{1 ck} is required. The Uniform Bounding Lemma below answers Question 4.3 in the affirmative, and the Bounding Lemma (also below) explains the second phenomenon, as well as having as a direct corollary the following theorem:

Theorem 5 If β is admissible then it is not nondeterministically clockable.

Besides the mentioned questions, we can make some further comments and improvements on one or two of their other theorems.

We drop the subscript ck and write ω_{1}^{x} for the first ordinal not recursive in x etc. In the sequel we let WF (WO) denote the set of real numbers coding wellfounded (respectively wellordered) relations. For y_{0} ∈ WO we let ∥y_{0}∥ ∈ On denote its ordinal rank.

Theorem 6 (Uniform Bounding Lemma) Let F : ℝ ⟶ ℝ be ITTM - computable and total as witnessed by φ_{e}. If ∀xφ_{e}(x)↓^{<ω_{1}^{x}} then ∃γ < ω_{1ck}∀xφ_{e}(x)↓^{<γ}.

Proof Let y be a code of a computation sequence φ_{e}(x)↓ witnessing that it halts. We think of such a code y as coding a sequence of “snapshots” of the tapes’ contents etc, along an ordering coded into y; we let Field(y) be this ordering. Then such a y_{x} which is moreover wellfounded, exists in L[x]. So let y_{x} be the L[x]-least code for such a wellordered sequence. Let Φ(y, e, x) abbreviate:

“y is the L[x]-least code for a wellordered halting computation sequence witnessing φ_{e}(x)↓”

Claim Φ(y, e, x) ⟺ L_{ω_{1}^{x}}[x] ⊧ Φ(y, e, x).

Proof: Note that as φ_{e} is total, our assumption that φ_{e}(x)↓^{<ω_{1}^{x}} implies, by running the algorithm P_{e} inside L_{ω_{1}^{x}}[x], that the latter has the L[x]-least witness y_{x} to Φ(y, e, x). Also notice that we cannot have for some y′ <_{L[x]} y_{x} that L_{ω_{1}^{x}}[x] ⊧ Φ(y′, e, x). This could only possibly occur if y′ coded some illfounded computation that was merely wellfounded in L_{ω_{1}^{x}}[x], and whose wellfounded part was of ordinal length ω_{1}^{x}. However as y_{x} ∈ L_{ω_{1}^{x}}[x],and ∥y_{x}∥ < ω_{1}^{x} the computation coded by y′ would have to halt at stage ∥y_{x}∥ too. This is absurd.

QED Claim

Φ(y, e, x) can be expressed as a Σ_{1} statement over L_{ω_{1}^{x}}[x]. Moreover, again using the totality of φ_{e}:

¬Φ(y, e, x) ⟺ L_{ω_{1}^{x}}[x] ⊧ ∃z(Φ(z, e, x) ∧ z ≠ y).

Hence Φ(y, e, x) is Δ_{1}^{1}. Hence

B = {y_{0}|∃x∃y(Φ(y, e, x) ∧ y_{0} = Field(y))} ∈ Σ_{1}^{1} ∩ WO .

By (lightface)Σ_{1}^{1}-boundedness, (see, e.g., [5] 4A.6) {∥y_{0}∥ : y_{0} ∈ B} is bounded in ω_{1 ck}. QED

At the close of Section 4 of a previous version of their paper there was some speculation that one might have in general that NP^{f} = Γ̆^{f}, the dual class of Γ^{f}. (Note that this is indeed true for the case of f(x) = ω_{1ck}: here NP^{f} = Σ_{1}^{1} = Γ̆^{f}.) We gave a counterexample to this which is the Lemma that follows, wherein P^{f} equals Δ(Γ^{f}). The point here is to ask the question “where does the existential witness y to x being in some NP^{f} set live?”

Call f : ℝ → On suitable if x ≤_{T} y → ω + 1 ≤ f(x) ≤ f(y). Let f be suitable such that L_{f(x)}[x] ⊧ KPI (KPI is the theory asserting that the universe is an admissible set which is a union of such.) Let:

Γ^{f} = {A ⊆ ℝ : ∃Σ_{1}φ∀x[x ∈ A ⟷ L_{f(x)}[x] ⊧ φ[x] ]}.

Lemma 7 (i) NP^{f} ⊆ Γ^{f} (and hence P^{f} ⊆ NP^{f} ∩ co NP^{f} ⊆ Γ^{f} ∩ co Γ^{f}.) Hence in general for such f, NP^{f} ≠ Γ̆^{f}. (ii) If additionally f satisfies ∀x f(x) ≤ Σ^{x} then P^{f} = NP^{f} ∩ co NP^{f} = Γ^{f} ∩ co Γ^{f}.

Proof Assume that NP^{f} ⊆ Γ^{f} is proven. That P^{f} ⊆ NP^{f}∩ co-NP^{f} ⊆ Γ^{f} ∩co Γ^{f} is straightforward. If f is chosen so that Γ^{f} is not self-dual, the final sentence then trivially follows. (Examples of such f are easily found: let f(x) be the least μ so that M = L_{μ}[x] is an admissible limit of admissibles; then ρ_{M}^{1} = ω and thus M’s Σ_{1} truth set is not in M, and so provides an example of a set in Γ^{f}\Γ̆^{f}.)

For the proof that NP^{f} ⊆ Γ^{f}, let φ_{e} be such that ∀x, yφ_{e}(x, y)↓^{<f(x)} and A = {x : ∃y φ_{e}(x, y)↓ 1}. So where can we find such a witnessing y if x is in A?

Suppose x ∈ A and y witnesses this. Suppose φ_{e}(x, y)↓^{γ} 1 with γ < f(x). Let u_{γ} ∈ M_{x} =_{df} L_{f(x)}[x], u_{γ} ∈ WO, with ∥u_{γ}∥ = γ. Let

B = {y : ∃z(z codes a wellfounded computation sequence witnessing φ_{e}(x, y)↓^{∥u_{γ}∥} 1)}

B ≠ ∅, and B ∈ Σ_{1}^{1}(x, u_{γ}). The Kleene Basis Theorem (relativised to x, u_{γ}) then states that ∃y_{0} ∈ B y_{0} ≤_{T} O^{x,u_{γ}} (see, e.g., [7] Theorem III.1.3, O here is Kleene’s O notation.) However then there is such a y_{0} ∈ M_{x}, as O^{x,u_{γ}} ∈ M_{x} by our KPI assumption (recall that O^{x,u_{γ}} is Σ_{1}-definable over the least admissible set containing x, u_{γ}). So now

∀x[x ∈ A ⟺ M_{x} ⊧ “ ∃y_{0}φ_{e}(x, y_{0})↓ 1”]

and this yields a defining Σ_{1} formula for A, putting A into Γ^{f}. This concludes the proof of (i). Now assume f is as in (ii). Suppose A ∈ Γ^{f} ∩ co Γ^{f}. We show that A ∈ P^{f}. As A ∈ Γ^{f} there is a Σ_{1} φ so that ∀x[x ∈ A ⟷ L_{f(x)}[x] ⊧ φ[x] ].

Let P_{e} be the program that searches for a code of some L_{α}[x] that witnesses that φ[x] holds, and halts with output 1, if it finds such. Since f(x) ≤ Σ^{x} it can look for codes of such L_{α}[x] for any α < Σ^{x}. Then ∀x[x ∈ A ⟷ P_{e}(x) ↓ 1]. However we also have that A ∈ co-Γ^{f}. So there is another program P_{e′} that similarly searches for witnesses that to the fact that x ∉ A: thus we have ∀x[x ∉ A ⟷ P_{e′}(x) ↓ 1]. So let e′′ be the index of a program simulating these two programs together, looking for the first to halt, etc. This will halt before f(x). Hence A ∈ P^{f}.

QED

We can get another Bounding Lemma:

Theorem 8 (Bounding Lemma) Suppose β be admissible. Let F be ITTMcomputable, and total so that ∀xφ_{e}(x)↓^{≤β} where φ_{e} computes F. Then ∃γ < β ∀xφ_{e}(x)↓^{<γ} .

Proof Suppose the theorem false as witnessed by the total function φ = φ_{e}.

Then β is obviously countable. By a theorem of H. Friedman and Jensen any countable admissible β is ω_{1}^{r} for some r ⊆ ω (cf.[6]). Let T be the following theory consisting of the following sets of sentences in the language L_{∈,ṙ} augmented by a new constant c:

(i) KP +ṙ ⊆ ω; (ii) the ∈-diagram of ⟨L_{β}[r], ∈⟩ ;

(iii) “∀x[x ∈ ẏ ⟶ ⋁ ⋁_{z∈y} x = ż]” for all y ∈ L_{β}[r].

(iv) “γ ∈ c∧c is an ordinal” for all γ < β.

(v) “∀a ≤ cL_{a}[ṙ] |̸= KP”

(vi) “∃x∃f[f maps c order preserving into Field(y) where y codes a halted course of computation of the form φ(x)↓.”

Claim If T_{0} ⊆ T, T_{0} ∈ L_{β}[r], then T_{0} has a model.

Proof Let δ < β be the least ordinal not “mentioned” in T_{0}. Find a (wellfounded) KP model N , with r ∈ N, and with an x ∈ N , with On^{N} > δ, and so that N ⊧ ¬φ(x)↓^{≤δ} . Then ∃f ∈ N with f : δ ⟶ Field(y) where y ∈ N codes the course of computation. Let δ interpret c. QED

By the Barwise Compactness Theorem T has a model M. By (i)-(iii) this is a KP model whose L[r]-part end-extends L_{β}[r], and moreover WFP(M)∩On = β (by virtue of (v).) Let x_{0} ∈ M witness (vi). Then we shall have that for every δ < β, M ⊧“ ¬φ(x_{0})↓^{<δ} ”. However in V we have then that φ(x_{0})↓^{β} . Moreover note that β is x_{0}-admissible (otherwise we could Σ_{1}-define inside M, β from x_{0} and ordinal parameters less than β). However we have just argued that β is x_{0}-clockable! This contradicts Theorem 1 above. QED

Hence in the terminology of [2] “P_{β} = P_{β+1}” and “NP_{β} = NP_{β+1}” so this shows that the requirement on β not being a limit of non-clockables, can be lifted from their [2] Theorem 5.10.

In section 6 of [2] they consider the P^{f}/NP^{f} classes restricted to sets of integers. The above arguments show that for many of them P^{f} = NP^{f}!. We shall use our following unpublished result which is cited in their paper as Lemma 5.8.

Lemma 9 ([11] Lemma 2.5) If α is a clockable ordinal, then every ordinal less than the next admissible ordinal beyond α is writable in time α + ω.

Lemma 10 Let β ≤ λ be such that β is an admissible limit of admissibles but is not interior to any gap in the clockables (i.e., it is a limit of clockables).

Then

P^{β} ∩ P(ℕ) = NP^{β} ∩ P(ℕ).

Proof: Let A ∈ NP^{β} ∩ P(ℕ). Let φ_{e} witness this: ∀n, y φ_{e}(n, y) ↓^{<β} and ∀n[n ∈ A ⟺ ∃yφ_{e}(n, y)↓ 1]. The Bounding Lemma shows that there is a smaller bound γ_{0} < β for the lengths of all these computations. Hence if n ∈ A then there is a y witnessing this, with φ_{e}(n, y)↓ 1 and converging in ≤ γ_{0}. steps. Let u ∈ L_{β} ∩ WO have rank γ_{0}. Set:

B_{n} = {z : ∃y(z codes a wellfounded computation witnessing φ_{e}(n, y)↓^{∥u∥} 1)}

Again ∅ ≠ B_{n} ∈ Σ_{1}^{1}(u). As above, appealing to the Kleene Basis theorem again, there are witnessing z, y_{0} ∈ L_{γ_{0}^{+}+1} if n ∈ A (where γ_{0}^{+} is next admissible above γ_{0}.) In other words to test for membership in A all we have to do is search through potential NP -witnesses y in L_{γ_{0}^{+}+1} ∈ L_{β}. But this puts

A ∈ Δ_{1}^{L_{β}}({γ_{0}}). By our assumption on β, by Lemma 10, γ_{0} is itself writable by some program φ_{f} in time < γ_{0}^{+}. Putting this together A ∈ Δ_{1}^{L_{β}}, so A ∈ P_{β}. QED

It would be interesting to have similar results for P(ℝ) rather than just for P(ℕ) here.

References

[1] K.J. Barwise. Admissible Sets and Structures. Perspectives in Mathematical Logic. Springer Verlag, 1975.

[2] V. Deolalikar, J.D. Hamkins, and R-D. Schindler. P ≠ NP ∩ co − NP for the infinite time Turing machines. Journal of Logic and Computation, 15:577–592, October 2005.

[3] J. D. Hamkins and A. Lewis. Infinite time Turing machines. Journal of Symbolic Logic, 65(2):567–604, 2000.

[4] Y. Moschovakis. Elementary Induction on Abstract structures, volume 77 of Studies in Logic series. North-Holland, Amsterdam, 1974.

[5] Y. Moschovakis. Descriptive Set theory. Studies in Logic series. North-Holland, Amsterdam, 1980.

[6] G. E. Sacks. Countable admissible ordinals and hyperdegrees. Advances in Mathematics, 19:213–262, 1976.

[7] G.E. Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic. Springer Verlag, 1990.

[8] R-D. Schindler. P ≠ NP for infinite time Turing machines. Monatsheft für Mathematik, 139(4):335–340, 2003.

[9] P. D. Welch. The length of infinite time Turing machine computations. Bulletin of the London Mathematical Society, 32:129–136, 2000.

[10] P. D. Welch. Post’s and other problems in higher type supertasks. In B. Löwe B. Piwinger T. Räsch, editor, Classical and New Paradigms of Computation and their Complexity hierarchies, Papers of the Conference Foundations of the Formal Sciences III, volume 23 of Trends in logic, pages 223–237. Kluwer, Oct 2004.

[11] P.D. Welch. Arithmetical quasi-inductive definitions and the transfinite action of one tape Turing machines. typescript, 2004.