Table of Contents

Post’s and other problems of supertasks of higher type . . . . . . . . . . 1 Philip D. Welch

II Benedikt Löwe, Wolfgang Malzkorn, Thoralf Räsch Foundations of the Formal Sciences II Applications of Mathematical Logic in Philosophy and Linguistics Bonn, November 10-13, 2000, pp. 1–15.

Post’s and other problems of supertasks of higher type

Philip D. Welch^{⋆}

Dept. of Mathematics, University of Bristol. Bristol BS8 1TW, England.

Institut für Formale Logik, Währingerstr. 25, A-1090 Wien Austria.

E-mail: welch@logic.univie.ac.at

Abstract. We consider the theory of supertasks as implemented on infinite time Turing machines. We consider in particular computations in the type of sets of reals. We give some commentary on this and a number of open problems are raised.

1 Introduction

The theory of infinite time computations on sets of integers is now, at least, reasonably understood. We discuss here some open questions in both this theory but more particularly in that of the theory concerning

Received: ...;

In revised version: ...;

Accepted by the editors: ....

2000 Mathematics Subject Classification. PRIMARY 03D75,SECONDARY 03D60, 03D65, 03E60, 04A15.

⋆ We should like to thank the Institut für Formale Logik in Vienna for a Gastprofessur where this paper was written..

computations in the next type up, that is using reals as inputs/outputs, and sets of reals as oracles. This higher type theory has not as yet received the same attention as the theory on integers. The aim of this article is to provide some commentary on what we feel this higher type theory should look like, and to ask a number of questions whose answers should help develop that theory, and place it in a context with other theories of reducibilities at this level.

In this section we give some of the basic definitions (from [HaLe00]), and mention an alternative machine architecture that yields the same class of computable functions on single tape machines. In the next section we state the corresponding definitions and facts for the higher type theory. We give no proofs of these latter results. Often they are simply the analogous ones for the theory on integers, and the reader can construct them for his or herself.

We refer the reader to [HaLe00] or to Joel Hamkins’ article in this volume, for the basic structure, definitions, and results concerning such machines. We let P_{n} denote the n’th program in some fixed enumeration. In Section 2 we shall assume some familiarity with the notions of determinacy of two person perfect information games - see. eg, [Ka94]. For a pointclass Γ “Det(Γ)” will denote the assertion that games with payoff sets A ∈ Γ have winning strategies for one of the players.

It was noted in [HaSe01] that the machine architecture could be replaced by a single tape machine using 0 and 1 as an alphabet, but only as long as one considered computable functions f : ℕ → ℕ. For functions F : ℝ → ℝ it turned out that a single tape is insufficient.

We first note here that a not unattractive one (or three) tape machine model is obtained which computes the same class of functions (on either integers or reals) as the original machine architecture, by allowing into the alphabet blank cells on the tape. (To be sure one now has a machine that in essence works on 3^{ω} instead of 2^{ω}, although for the theorem above we still consider x ∈ ℝ input as an infinite sequence from {0, 1} only. A function F : ℝ → ℝ is computable by such a machine, if for all real input strings, the output strings are also real strings, i.e., without blanks.) The purpose of a “blank” or empty cell is to signify ambiguity. We adopt a new limit rule for specifying the contents of cells at limit stages: if a cell’s value has varied cofinally often below λ, we set the value to the “ambiguous” value of a blank.

Ambiguity limit rule: If λ is a limit ordinal, then the contents of the i’th cell on the tape at time λ, C_{i}(λ), is given by: If ∃ν_{0} < λ such that ∀ν < λ(ν_{0} < ν → C_{i}(ν_{0}) = C_{i}(ν)) then set C_{i}(λ) = C_{i}(ν_{0}); otherwise set C_{i}(λ) to be a blank.

One then has:

Theorem 1 Let C be the class of functions F : ℝ → ℝ computable by the Hamkins-Lewis machines of [HaLe00], and C′ those of the one-tape machine just specified. Then C = C′.

It is not hard to see that if we now define a one-tape machine using this ambiguity limit rule, then its action can be simulated on a {0, 1}- valued three tape [HaLe00]-machine. It was noted in [HaSe01] that the single tape machines with {0, 1} values only computed a class of functions that was not closed under composition. This had the effect that the natural simulation of a 3 tape machine by a 1 tape machine could not realise that it had performed a final compression of the simulated output. (A compression is a map of the form ⟨x_{0}y_{0}z_{0}x_{1}y_{1}z_{1} …⟩ ⟶ ⟨z_{0}z_{1}z_{2} …⟩; although clearly 1-tape computable on its own, one cannot compose it in a 1-tape computable fashion with the other steps of the simulation. One needs a flag or some device such as further scratch pad (see [HaSe01] Theorem 2.3) that is not part of the final output to allow us to know when the final compression is complete, and the 1-tape computation may halt.)

We have here an extra symbol - namely the blank - in the alphabet, and this gives us enough room to set flags and enable us to close up under composition, and thus calculate the same functions as the 3 tape model. (For readers familiar with [HaSe01] this is really an exercise.) However, the theorem above notwithstanding, we shall stick to the definitions and conventions of [HaLe00] for this paper. The rest of the definitions of this subsection are all taken from that paper. It should be noted that we deliberately elide the distinction between subsets of ω and their characteristic functions as elements of 2^{ω} and write “n ∈ g” interchangeably for “g(n) = 1” etc.

Definition 1 φ_{n}(x), for x ∈ 2^{ω}, denotes the result of running P_{n} on input string x.

For any n, x it is easily seen that there is a countable ordinal α so that the behaviour of φ_{n}(x) has “settled” by stage α: either it has halted or it has entered a permanent looping cycle: notationally, either φ_{n}(x)↓y for some y ∈ 2^{ω}, or else φ_{p}(x)↑. For a machine with an oracle f ∈ 2^{ω} we allow the machine to receive 0/1 answers to queries of the form “Does f(n) = 1”? We write “φ_{p}^{f}(x)↑y” for “program p with input x and oracle f eventually has a settled y on its output tape”; in other words, there is a time ν, so that for all later times φ_{p}^{f}(x) has y sitting on its output tape - although without requiring that φ_{p}^{f}(x)↓. The relations “φ_{p}^{f}(x)↑y”, “φ_{p}^{f}(x)↑”, and “φ_{p}^{f}(x)↓y” are Δ_{2}^{1} relations of f, x, (y). We let W O denote the set of reals in 2^{ω} that code wellorderings of ω.

Definition 2 x ∈ W ⟷ ∃p ∈ ωφ_{p}(0)↓x (W is the class of “writable” reals).

Fact 1 ([HaLe00] 3.7, 8.3) The “writable” ordinals, (those ordinals α so that there is x ∈ W ∩ W O with ||x|| = α) form an initial segment of the countable ordinals.

Definition 3 (i) λ =_{df} sup{||x|| : x ∈ W O ∩ W}; (ii) γ =_{df} sup{α | ∃p ∈ ω φ_{p}(0)↓ and halts in exactly α steps }.

Definition 4 (i) EW =_{df} {x ∈ 2^{ω} | ∃pφ_{p}(0)↑x}. EW is the set of “eventually writable” reals. (ii) ζ =_{df} sup{||x|| : x ∈ W O ∩ EW}.

Definition 5 Let Σ =_{df} sup{||t|| : t ∈ AW ∩ W O}. AW is the set of “accidentally writable” reals where: AW =_{df} {x ∈ 2^{ω} | ∃p x appears on any tape at any time of the computation of φ_{p}(0) }.

The accidentally writable reals are thus likely to be transient. (An equivalent class of reals is obtained by restricting the appearance of such reals to the output tape alone.) Clearly AW ⊇ EW ⊇ W. We let HC denote the class of hereditarily countable sets.

Definition 6 We write H(λ) (H(ζ), H(Σ) respectively) for the class of sets y ∈ HC so that ∃ȳ ∈ W (EW, AW respectively) with ȳ coding y.

We use the notation W^{f}, λ^{f} …, H^{f}(λ^{f}), … for the notions relativised to a real f.

Definition 7 (The weak jump) For f ∈ 2^{ω}, f^{▽} =_{df} {n ∈ ω | ϕ_{n}^{f}(0)↓}.

It is easy to see that f → f^{▽} is a Δ_{2}^{1} function. The notions of g is a decidable (or semi-decidable) set of integers is the natural one: g must have a totally (or partially) computable characteristic function:

Definition 8 g ∈ 2^{ω} is semi-decidable in the real f if for some e we have

∀n ∈ ω n ∈ g ⟷ φ_{e}^{f}(n)↓1.

As usual g is decidable (in f) if both it and its complement are semidecidable (in f).

For the ordinary notion of Turing computability one has the equivalence between the semi-decidable, i.e. , the recursively enumerable, sets of integers as those that are the domain of some computable function, with, as alternative, those that are the range of such. One can establish this by observing that from the universality of Kleene’s T -predicate one may simply test integers to see if they code a whole course of computation of the relevant function, and seeing if they terminate in a desired number output. The point is that the course of computation can be coded as something within the domain of the Turing machine. But is that the case for infinite time Turing machines? Or do we have in the phraseology of Sacks [Sa80], a “violation of parity” (between the type of the object in the domain of the computation, and that of the computation itself)? In essence we are asking whether (a code for) a halting computation can also be the result of a halting output of another computation. For this it is enough to have a real code for the length of any halting computation to be a potential output of some halting computation. Once we have such a code to hand we can then write a program simulating the original course of computation along that ordinal, and so output a code for the course of that computation. In the terms we have defined, we are asking whether γ ≤ λ. This had been the principal open problem left from [HaLe00]. The answer is affirmative.

Theorem 2 ([We00a] Thm.1.1) λ = γ, and by relativisation for all f ∈ 2^{ω} λ^{f} = γ^{f}.

Once we have this result we can answer a number of questions, as to what the decidable sets of integers are, what is complexity of the weak jump operator, what are the sets H(λ) etc.

Theorem 3 ([We00a] Cors. 3.1,3.3,3.5) For θ ∈ {λ, ζ, Σ} H(θ) = L_{θ}, and for any f ∈ 2^{ω} H^{f}(θ^{f}) = L_{θ^{f}} [f].

Corollary 4 The decidable sets of integers are precisely those of P(ω) ∩ L_{λ}.

The relationship between the various H(θ) sets is given by:

Theorem 5 ([We00] The “(λ, ζ, Σ) Theorem”) (i) L_{λ} ≺_{Σ_{1}} L_{ζ} ≺_{Σ_{2}} L_{Σ}. (ii) (λ, ζ, Σ) is the lexicographically least triple of ordinals satisfying this relation.

This theorem implies that we may consider the definable sets of integers as those Σ_{1}-definable inside the least model of KP with a transitive Σ_{2}-end extension. It further implies that L_{λ}, L_{ζ} are admissible sets satisfying strong reflection properties. For example, there are unboundedly many α below any of the ordinals λ, ζ, Σ where L_{α} ⊧ Σ_{2}-KP (meaning Kripke-Platek set theory with Σ_{2}-Collection and Δ_{2}-Comprehension axioms).

By appealing to Theorem 2 as γ^{f} = λ^{f}, Theorem 3, and by considering the running of such machines inside L_{λ^{f}} [f] one sees:

Corollary 6 f^{▽} ∈ Σ_{1}(L_{λ^{f}} [f]).

As f^{▽} is not an f-decidable set of integers, it cannot lie inside L_{λ^{f}} [f]. It is thus perhaps unsurprisingly a Σ_{1}-mastercode for L_{λ}.

Corollary 7 ([We00] ) f^{▽} is (ordinary) Turing isomorphic to Σ_{1}-T h(L_{λ}), the complete Σ_{1} theory of L_{λ}.

There is the natural reducibility relation associated to reals:

Definition 9 For x, y ∈ 2^{ω}:

x ≤_{∞} y ⟷ ∃n∀k ∈ ω [φ_{n}^{y}(k)↓1 ↔ x(k) = 1 ∧ φ_{n}^{y}(k)↓0 ↔ x(k) = 0]

Corollary 6 enables one to see that the assignment f ↦ λ^{f} satisfies the usual Spector Criterion:

Lemma 8 (i) x ≤_{∞} y ⟷ x ∈ L_{λ^{y}}[y]; thus (ii) x ≤_{∞} y ⟶ λ^{x} ≤ λ^{y}; (iii) The assignment x ⟶ λ^{x} then satisfies a Spector criterion:

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

The analogy of ≤_{∞} with ordinary Turing reducibility is explored in [HaLe00]. We take Lemma 8 as indicating that the proper analogy here is rather with something intermediate between hyperdegrees (with the assignment x ↦ ω_{1}^{x}^{1} and that of Δ_{2}^{1}-degrees (with assignment x ↦ Δ_{2}^{1}(x)).

The principle open question we can formulate at this point is the following.

Question 1 Let D be a countable set of infinite time degrees. Does D have a minimal upper bound?

This question remains unresolved for hyperdegrees. For Δ_{2}^{1}-degrees there are two differing but complete pictures, both with affirmative answers, depending on whether ℝ ⊆ L or not (see [Fr74]). There are some partial results on Question 1 in [We99], but they are very partial, and the problem looks difficult^{2}.

1.1 Eventually infinite time degrees

There is one sense in which one could argue that the ordinal ζ is perhaps more fundamental than λ. It is after all the point by which the behaviour of the machine on a computation of the form φ_{e}(k) is determined: either it has halted, or it has begun to loop permanently at some ordinal ζ̄ ≤ ζ. (Moreover there is e so that this upper bound is attained here. It would take us too far afield here, but it is essentially the pattern of the universal machine φ_{U}’s output tape at stage ζ that is recursively isomorphic to certain sets of interest occurring in the revision theory of truth based on Herzberger sequences.)

We could thus define a reducibility relation “x is eventually writable from y”.

Definition 10 x ≤_{e∞} y ⟷ x ∈ EW^{y}.

We define a jump:

Definition 11 x̃ is the set of indices {p ∈ ω | ∃y ∈ EW^{x} φ_{p}^{x}(0)↑y}.

1 We write ω_{1}^{x} for the least ordinal not recursive in x 2 [We99] uses some unexplained notation which we here clarify: F (e, f) = β abbreviates

”φ_{e}^{f} (0)↓ in exactly β steps”

We have parallel to the above:

Lemma 9 (i) x ≤_{e∞} y ⟷ x ∈ L_{ζ^{y}}[y]; thus (ii) x ≤_{e∞} y ⟶ ζ^{x} ≤ ζ^{y}; (iii) The assignment x ⟶ ζ^{x} then satisfies the Spector criterion:

x ≤_{e∞} y ⟶ (x̃ ≤_{e∞} y ⟷ ζ^{x} < ζ^{y}).

Lemma 10 x̃ is Turing isomorphic to the complete Σ_{2}(L_{ζ^{x}}[x]) set of integers.

Again the variant of Question 1 arises.

Question 2 Let D be a countable set of eventually infinite time degrees. Does D have a ≤_{e∞} minimal upper bound?

Definition 12 Let F = {x ∈ 2^{ω} | x ∈ L_{ζ^{x}}}.

We note that it makes no difference whether we write ζ^{x} or λ^{x} in this definition, since there is a program that given an x as input, searches for its L-rank. Once found we can ensure the program halts. Hence if x ∈ F then x ∈ L_{λ^{x}}. There is an analogy here with Q, (see [Ke75] or [Mo80, 4F.4] for the basic properties and structure of Q) the largest thin Π_{1}^{1} set of quickly constructible reals: Q =_{df} {x|x ∈ L_{ω_{1}^{x}}}.

We may define a natural hierarchy of eventually infinite degrees through F in the spirit of [Ke75] (where this is done for Q and hyperdegrees) by e_{0} = [0]˜ ; e_{α+1} = [ẽ_{α}]˜ ; e_{μ} ≃ lub{ e_{α} | α < μ} for Lim(μ) if defined. (Here “lub” abbreviates “least upper bound” in the degree ordering.)

Question 3 What is the natural length of this hierarchy? That is, what is the least ρ so that e_{ρ} is undefined?

(The version of this question for the infinite time degrees has a known answer: the natural hierarchy is undefined even at the ω’th stage.)

2 Higher Type Computation

We briefly review again the relevant definitions from [HaLe00].

For A ⊆ 2^{ω} φ_{p}^{A}(x) represents the function defined by the p’th program in a recursive listing of programs allowing queries of the set A, as to whether a real currently on the scratch tape is, or is not, in A (and receiving a simple 0/1 answer), using real input x.

Definition 13 ([HaLe00] The strong jump) 0^{▼} =_{df} {(n, x) ∈ ω × 2^{ω} | φ_{n}(x)↓} . For A ⊆ 2^{ω} define A^{▼} =_{df} {(n, x) ∈ ω × 2^{ω} | φ_{n}^{A}(x)↓}.

There is an associated reducibility relation associated to sets of reals:

Definition 14

A ≤_{∞} B ⟷ ∃n∀x ∈ 2^{ω} [φ_{n}^{B}(x)↓1 ⟷ x ∈ A ∧ φ_{n}^{B}(x)↓0 ⟷ x ∉ A]

We make specifically semi-decidability into a definition:

Definition 15 A set of reals A is semi-decidable in a set of reals B if and only if:

∃n∀x ∈ 2^{ω} [φ_{n}^{B}(x)↓1 ⟷ x ∈ A ]

(ii) A set of reals A is semi-decidable in a set of reals B and a real y ∈ 2^{ω} if and only if:

∃n∀x ∈ 2^{ω} [φ_{n}^{B,y}(x)↓1 ⟷ x ∈ A ]

We want a notion of “semi-decidability” that results in a pointclass of sets closed under continuous preimages. Thus (when sufficient determinacy) it shall have a Wadge rank, which in turn gives a measure of complexity to the notion of semi-decidability we have defined. (Wadge defined the following ordering on sets of reals: A ≤_{W} B if there is a continuous reduction of A to B: i.e. there is a continuous f : 2^{ω} → 2^{ω} so that x ∈ A ↔ f(x) ∈ B. Then ≤_{W} is easily seen to be reflexive and transitive. This will give us a notion of Wadge rank of the sets of reals in any given pointclass Γ provided we know that ≤_{W} restricted to Γ is wellfounded. Assuming sufficient determinacy Wadge’s Lemma (cf. [Mo80, 7D.3]) asserts that ≤_{W} so restricted is (virtually) a linear ordering, and a theorem of Martin (cf. [Mo80, 7D.14]) asserts - still assuming sufficient determinacy, that it is wellfounded. For Γ equal to the class of Borel sets no determinacy is required (indeed, unlike Borel Determinacy, these facts can be proven in second order arithmetic). Assuming the full axiom of determinacy, AD, then the Wadge hierarchy so obtained has rank Θ =_{df} sup{γ | ∃g : ℝ → γ, g onto }.)

The notion “A is decidable in B” (respectively “in a real and B”) is as usual: this relation holds if both A and ¬A are semi-decidable in B (respectively in a real and B).

Definition 16 A ≤_{r,∞} B denotes that A is decidable in B and a real.

For the rest of this section “semi-decidability” will abbreviate “semidecidability in a real” - the boldface notion.

Definition 17 (i) Γ_{0} =_{df} {A ⊆ 2^{ω} | A is semi-decidable from a real } (ii) Δ_{0} =_{df} Γ_{0} ∩¬Γ_{0} .

Theorem 11 (Hamkins-Lewis)[HaLe00] Δ ⊆ Δ_{2}^{1} is a σ-algebra, closed under Suslin’s operation A, properly containing the Selivanovski^{3} Csets.

It is easy to verify that the semi-decidable in z sets of reals are provably Δ_{2}^{1}(z) and thus, by a result of Solovay (a proof is given in [FeNo74]), are all absolutely measurable, and enjoy the property of Baire.

There are two questions related to hierarchies with a classical flavour (as opposed to the descriptive set-theoretic viewpoint based on the later effective theory of Moschovakis and others). The first is to ask how the semi-decidable sets sit with relation to the Kolmogorov R-sets.

Question 4 Classify the semi-decidable sets of reals within the hierarchy of the R-sets.

We conjecture that they sit very low down in this hierarchy. The reader may consult [Hi78] V.4 and V.5 for an account of classical hierarchies through Δ_{2}^{1}. There is another notion of generalised computation, due to Blackwell [Bl78], the “Borel programmable functions” - derived from the theory of dynamic programming in probability theory. For this, let X, Y be perfect polish spaces, and 2^{ω} be Cantor space. A program is a function p : 2^{ω} → 2^{ω} so that ∀n x(n) ≤ p(x)(n) (thus we are really thinking, via characteristic functions, of p as operating on a subset x of ω and returning a possibly larger set p(x)). We iterate p in an obvious way, and let p_{α} be the α’th iterate, with p_{λ}(x)(n) = sup_{α<λ} p_{α}(n) for all n at limits λ. Let p_{Ω} be the fixed point function attained at some Ω < ω_{1}. A Borel function e : X → 2^{ω} is called an encoder, a Borel d : 2^{ω} → Y is a decoder. Let c_{i} be the constant function on ω with value i.

3 The Selivanovski C-sets are the smallest σ-algebra of sets containing the Borel sets, and

closed under operation A.

Definition 18 A function f : X → Y between perfect polish spaces X, Y is Borel programmable if it is of the form d∘p_{Ω}∘e for some d, p, e of the above form. A set A ⊆ X is Borel programmable if its characteristic function ρ_{A} : X → 2^{ω} is (where ρ_{A}(x) = c_{1} if x ∈ A and ρ_{A}(x) = c_{0} if x ∉ A.)

Question 5 Are the infinite time Turing machine decidable sets all Borel programmable sets?

It is easy to see from the definition of Borel programmable functions, that their computation could be effected on an infinite time Turing machine (equipped with oracles for the requisite Borel codes of the functions concerned). The question concerns the reverse inclusion. The question prima facie is not unreasonable, since by a result of Burgess and Lockhart [BuLo83] the Borel programmable sets also properly include the C-sets. However we conjecture the answer is negative.^{4}

In [HaLe??] a positive solution to Post’s problem (whether there can be A with 0 <_{∞} A <_{∞} 0^{▼}) is proposed. In fact two countable semidecidable sets A, B ⊆ 2^{ω}, which could be construed as constructed definably over L_{λ}, are seen to be ≤_{∞} -incomparable via a Friedberg-Muchnik type construction. Since the sets constructed are countable, they are obviously both of degree 0 when considering the boldface reducibility of decidability in reals. One can “remedy” that as follows

Lemma 12 (V = L). The set F of fast reals satisfies: 0 <_{∞} F <_{∞} 0^{▼}. Moreover F is not decidable in a real, and 0^{▼} is not decidable in any real and F; that is 0 <_{r,∞} F <_{r,∞} 0^{▼}.

F is thus, in L, a (boldface) strictly intermediate set. That some kind of set theoretic hypothesis is necessary to build intermediate sets will be seen below.

We take the view here that one tends not to consider the relation of “A is Δ_{n}^{1} in B” between sets of reals (although of course this makes perfect sense for sets of integers). We should like to generalise the notion of boldface semi-decidability that is afforded by Kleene degrees (see [HrSi80] for a discussion of this notion). Briefly, for sets of reals A, B one writes A ≤_{K} B (“A is Kleene recursive in B”) iff there is a real y so that the characteristics function χ_{A} of A is recursive (in the sense of Kleene [Kl59]) in y, χ_{B} and the existential integer quantifier ^{2}E. The computational model here differs from the infinite time Turing machines, but one can view it as a machine equipped with ability to quiz an oracle for B and y, with a countably infinite memory, and an ability to search that memory in a finite amount of time.

4 We are grateful to John Burgess for bringing this example to our attention - albeit in a rather

different context.

The Kleene recursive sets are then the Borel sets, and the Kleene semi-recursive sets are the coanalytic sets. Solovay had shown ([So71]) that under AD, the axiom of determinacy, the Kleene degrees are wellordered. The complete semi-recursive set is W O, the Π_{1}^{1} set of reals coding wellorders. The nature of the reducibility ordering ≤_{K} depends on one’s universe of discourse: contrasting with Solovay’s AD result already mentioned, in L, or in set generic extensions thereof, there are 2^{ℵ_{0}} ≤_{K}- incomparable semi-recursive sets below the degree of W O ([HrSi80]). A sharper result than Solovay’s (no pun intended) is the fact that if Π_{1}^{1}- determinacy holds then all Kleene semi-recursive, non-recursive sets have the same Kleene degree. This is a result of Steel [St80]. The converse also holds by Harrington [Ha78, Theorem 4.4]. We should expect an entirely analogous picture to obtain for the degrees of the semi-decidable sets defined above.

In the following we use freely the natural generalisations of the definitions and notations from the first section. We thus, for example, write “λ^{B}” for the first ordinal that is not (coded by) the output of any halting computation with oracle B, on input 0.

It follows from a version of the “λ, ζ, Σ-Theorem” (Theorem 5 above) that the sets of reals semi-decidable in x ∈ 2^{ω} are those sets 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).

In the latter equivalence, we should have precisely the notion of A being Kleene semi-recursive to B, if one simply replaced λ^{⟨x,y,B⟩} by ω_{1}^{⟨x,y,B⟩}. However we are not simply mimicking a (version equivalent to) Kleene’s definition here. Suppose we are given any function f : D → On of ordinary Turing degrees to countable ordinals that is definable via a Σ_{1} formula ψ(v_{0}, v_{1}) so that for any (ordinary) Turing degree [y]_{T} we have f([y]_{T}) = α iff L[y] ⊧ ψ(y, α); then we may define a slice through Δ_{2}^{1} by defining a lightface pointclass Γ_{0} as follows: A ∈ Γ_{0} if and only if for some formula θ(v_{0}, v_{1}) we have x ∈ A ⟷ L_{f(x)}[x] ⊧ θ(x). (A boldface definition would add in a real parameter.) How high a rank f has in ^{D}ℵ_{1} modulo the Martin measure (cf [Ka94] p386), assuming say Det(Δ_{2}^{1}), determines the complexity of the class Γ_{0}. By some measures λ^{x} is a large ordinal, and we are dealing with a complex class.

We may then, to be specific, ask questions about the semi-decidable sets below 0^{▼} as follows:

1) Is there A ⊆ 2^{ω}, A ∈ Γ_{0} , A not decidable in a real, but satisfying that 0^{▼} is not decidable in a real and A?

2) Are there A, B ∈ Γ_{0} neither of which is decidable in a real from the other?

The outcome, just as for Kleene degrees, depends on the set theoretical universe one inhabits.

Theorem 13 In L, the constructible universe, (or in set generic extensions thereof) there are A, B as in 2).

We have not checked, but fully expect that, there are 2^{ℵ_{0}} many such incomparable sets A. We list a number of problems, which are supposed to elucidate the boldface reducibility ordering in the constructible universe. We expect their answer (and solution) to be similar to that for Kleene degrees.

Question 6 Assume V = L.

(i) Can there be a semi-decidable set A of minimal ≤_{r,∞}-degree? (ii) Can there be infinite descending sequences of ≤_{r,∞}-degrees? (iii) Are the ≤_{r,∞}-degrees of semi-decidable sets dense between 0 and 0^{▼}?

(We conjecture the answer to (iii) to be affirmative, thus solving the other two parts.) In the following we let for Γ (any pointclass) Boolean(Γ) denote the pointclass obtained from the sets of Γ and closing up under complementation and finite unions.

Theorem 14 Det(Boolean(Γ_{0})) ⟹ any A ∈ Γ_{0}\ Δ_{0} satisfies: 0^{▼} and A are mutually decidable in a real.

Thus sufficient determinacy ensures the answers to both questions is negative. In essence all one has to do for this latter theorem is to quote a result of Steel ([St80]) that for any boldface pointclass Γ the determinacy of sets in Boolean(Γ) ensures that any set not Γ-self-dual is continuously reducible to another such set.

There remains the question of how to measure the complexity of Γ_{0} . One method is to ascertain how much determinacy Det(Boolean(Γ_{0} )) actually is. Can one find an equivalence in terms of inner models of large cardinal axioms? We formulate this as follows:

Question 7 Determine the strength of Det(Boolean(Γ_{0} )). Can the sharp of an inner model of some large cardinal axiom be found which is equivalent to this?

In general the direction from a sharp to the determinacy is difficult. For the theory of Kleene degrees we have already remarked that there is a precise answer: Det(Boolean(Π_{1}^{1})) yields, by the above comments, that all non-Borel co-analytic sets are Kleene mutually reducible to the complete Π_{1}^{1} set. This conclusion had been obtained by Steel assuming just Det(Π_{1}^{1}). (Of course Harrington showed that Det(Π_{1}^{1}) implied the existence of x^{#} for any real x, and this was known by work of Martin to imply Det(Boolean(Π_{1}^{1}))).

We can appeal to methods of Steel [St82], using Friedman-style games to show that Det(Γ_{0} ) implies reasonable large cardinal strength. We first have:

Theorem 15 The following is a (lightface) decidable relation

“⟨x, y⟩ ∈ 2^{ω} codes countable premice M, N <_{∗} 0^{¶} and M ≤_{∗} N in the (pre)mouse ordering.”

In the above the (pre)mouse orderings <_{∗} and ≤_{∗} are the canonical ones. For premice M ≤_{∗} N is to be interpreted as “In the comparison coiteration of M with N to models M_{θ}, N_{θ} then either (i) θ is least so that one of the models is illfounded, and that model is M_{θ} or (ii) M_{θ} is an initial segment of N_{θ}.” The notation 0^{¶} denotes the sharp for an inner model of a strong cardinal (if it exists). Using the fact that Det(Γ_{0})) implies Det(Π_{1}^{1}) we may use the Σ_{3}^{1}-correctness of the core model built assuming there is no inner model with a strong cardinal ([StWe94]) and obtain:

Theorem 16 Det(Γ_{0}) implies 0^{¶} exists.

This latter embedding property is known as 0^{¶} (read as “0-pistol”) and in fact one has x^{¶} for any real x. But this seems far from an optimal result. Indeed to ask a question as to lower bounds:

Question 8 Does the mutual decidability in reals of all A, B ∈ Γ_{0} \ Δ_{0} imply x^{¶} exists for all x ∈ ℝ? Does it imply x^{#} exists?

We expect the answers should be affirmative.

16  Philip D. Welch

References

[Bl78] David Blackwell, Borel-programmable functions, in Annals of Probability, 1978, 6, 321-324.

[BuLo83] John P. Burgess and Richard A. Lockhart Classical hierarchies from a modern standpoint III, in Fundamenta mathematicae, 1983, 115, 107-118.

[FeNo74] Jens Eric Fenstad and Dag Normann, On absolutely measurable sets, in Fundamenta Mathematicae, 81, 1974, 91-98.

[Fr74] Harvey Friedman, Minimality in the Δ_{2}^{1}-degrees, in Fundamenta Mathematicae, 1974, 81, 183–192.

[HaLe00] Joel Hamkins & Andy Lewis, Infinite Time Turing Machines, Journal of Symbolic Logic, 65(2):567-604, 2000.

[HaLe??] Joel Hamkins & Andy Lewis, Post’s problem for supertasks has both positive and negative solutions, to appear in Archive for Mathematical Logic.

[HaSe01] Joel Hamkins & Daniel E. Seabold, Mathematical Logic Quarterly, 47(2):271–287, 2001.

[Ha78] Leo Harrington, Analytic determinacy and 0^{#}, Journal for Symbolic Logic, 1978, 43 No.4, 684-693.

[Hi78] Peter G. Hinman, “Recursion Theoretic Hierarchies”, Perspectives in Mathematical Logic Series, Springer Verlag, 1978.

[HrSi80] Karel Hrbacek & Stephen Simpson, On Kleene degrees of Analytic Sets, in Proceedings of the Kleene Symposium, Eds. J.Barwise, H.J.Keisler, & K.Kunen, North Holland Studies in Logic Series, 1980, 347-352

[Ka94] Akihiro Kanamori, The Higher Infinite, Springer Berlin 1994 [Perspectives in Mathematical Logic]

[Ke75] Alexander S.Kechris, The Theory of Countable Analytic Sets, in Transactions of the American Mathematical Society, 1975, 202, 259-297.

[Kl59] Stephen C. Kleene Recursive functionals and quantifiers of finite types, I; in Transactions of the American Mathematical Society, 61, 1959, 193-213.

[Mo80] Yiannis Moschovakis, Descriptive Set Theory, North-Holland Studies in Logic Series, 1980.

[Sa80] Gerald E. Sacks Post’s problem, Absoluteness and Recursion in Finite types. in Proceedings of the Kleene Symposium, Eds. J.Barwise, H.J.Keisler, & K.Kunen, North Holland Studies in Logic Series, 1980, 201-222.

[So71] Robert Solovay, Determinacy and type-2 recursion (abstract), in Journal for Symbolic Logic, 36, 1971, 374.

[StWe94] John R. Steel and Philip Welch, Σ_{3}^{1}-absoluteness and the second uniform indiscernible, in Israel Journal of Mathematics, 1998, 14, 157-190.

[St80] John R. Steel, Analytic Sets and Borel Isomorphisms, in Fundamenta Mathematicae, 1980, 108, 83-88.

[St82] John R. Steel, Determinacy in the Mitchell models, Annals of Mathematical Logic, 1982, 109-125.

[We99] Philip Welch, Minimality Arguments in the Infinite Time Turing Degrees, in ”Sets and Proofs” - Proc. Leeds Logic Colloquium, Ed. S.B.Cooper & J.K.Truss, London. Mathematical Society Lecture Notes in Mathematics Series, 259, April 1999, C.U.P., pp 425-436.

[We00] Philip Welch, Eventually Infinite Time Turing machine degrees: infinite time decidable reals, Journal of Symbolic Logic 65, No.3 (2000), p. 1193-1203.

[We00a] Philip Welch, The Length of Infinite Time Turing Machine Computations. Bulletin of the London Mathematical Society 32, No.2 (2000), p. 129-