Infinite time recognizability from generic oracles and the recognizable jump operator 1

Abstract

By a theorem of Sacks, if a real x is recursive relative to all elements of a set of positive Lebesgue measure, x is recursive. This statement, and the analogous statement for non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations in: Notre Dame Journal of Formal Logic, to appear, arXiv:1307.0160 [math.LO]. Here, we start exploring another analogue concerning recognizability rather than computability. For a notion of relativized recognizability (introduced in: Annals of Pure and Applied Logic 165(9) (2014), 1353–1532, for ITRMs and generalized here to various other machine types), we show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager Borel set Y, then x is recognizable. We also show that a relativized version of this statement holds for Infinite Time Register Machines (ITRMs). This extends our work in: Evolving Computability: 11th Conference on Computability in Europe, 2015, pp. 137–145, where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its set-theoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitive-recursively equivalent, even though these two models are otherwise of vastly different strength. Finally, we introduce degrees of recognizability by considering the transitive closure of relativized recognizability and connect it with the recognizable jump operator to obtain a solution to Post’s problem for degrees of recognizability.

Keywords

Infinite Time Turing Machine ordinal computability recognizability genericity jump operator

1. Introduction

It is well-known (see e.g. [1] or Proposition 2.3 of [26]) that, if x is a non-recursive real number, the Turing upper-cone of x is meager. Intuitively, randomly choosing an oracle is not likely to increase the chance of solving the problem of computing a certain real fixed in advance. In a similar spirit, by a theorem of Sacks (see e.g. [14]), if a real x is recursive relative to all elements of a set Y of positive Lebesgue measure, x is recursive. These statement continue to hold for many machine models of infinitary computations as demonstrated in [11] (for some it is currently still open, while for others it turns out to be independent of $ZFC$ ).

Besides computability, there is another way in which an infinitary machine can ‘determine’ a real x: x is recognizable if and only if there is a program that halts on all oracles and outputs 1 when run on the oracle x and otherwise outputs 0. Recognizability is known to be a strictly (and in fact much) weaker property than computability. In [7], a notion of relativized recognizability for ITRMs was considered, resembling computations with oracles. This motivates us to ask whether the ‘random oracles are not informative’-intuition is sufficiently stable to still hold in this context, i.e. whether recognizability relative to all oracles in some ‘large’ set of reals (i.e. a set of positive Lebesgue measure or a non-meager Borel set) implies recognizability. In an earlier paper [8], we treated the simplest non-trivial case of this question, namely Infinite Time Register Machines (ITRMs) and recognizability from all oracles in a Borel set that is not meager. A strengthening of this result is proved in Section 2. A quick inspection of the proof reveals that it makes crucial use of a quite special and convenient property of ITRMs, namely that one can bound the halting time of a program using n registers and running in the oracle x by $ω_{n + 1}^{CK, x}$ from above, an ordinal which in turn has a code computable in the oracle x by an ITRM-program using more registers. As there is, by the work of Hamkins and Lewis [16] a universal Infinite Time Turing Machine (ITTM), we cannot expect this to work for ITTMs. Hence, we proceed in Section 3 by treating the considerably more delicate case of Infinite Time Turing Machines (ITTMs).

We then strengthen the analogy between computability and recognizability by introducing a jump operator for recognizability and exhibiting some of its basic properties. Finally, we introduce degrees of recognizability and show that, for ITRMs and ITTMs, there are recognizability degrees strictly between 0 and its recognizable jump.

In particular, we prove the following results:

(Theorem 3.5) Assume that x is ITTM-recognizable. Then x is computable or $0_{ITTM}^{'}$ , the halting real for ITTMs, is ITTM-computable from x.

Roughly, this shows that real numbers that are ‘unique’ from the perspective of ITTMs are never incomparable with the halting real for ITTMs.

(Theorem 3.12) Let x be uniformly ITTM-recognizable from all elements y of a comeager set Y. Then x is ITTM-recognizable.

This is an analogue for ITTM-recognizability of a result by Kleene and Post, according to which the Turing cone above a non-recursive degree is always a meager set (see e.g. Proposition 2.3 of [26]). By Corollary 3.18, the analogue for ordinal Turing machines with parameters is independent of ZFC. (The corresponding statement for ITRMs is the main result of [8], but also follows from the slightly more general Theorem 2.10 below.)

(Theorem 4.9) The recognizable jump $0^{r}$ of 0 is not recognizable for ITTMs and OTMs without or with a fixed parameter.

(Theorem 4.20) For $M \in {ITRM, ITTM}$ , there is x such that ${[0]}_{M}^{r} ≺_{M} {[x]}_{M}^{r} ≺_{M} {[0_{M}^{r}]}_{M}^{r}$ .

This is an analogue of Post’s problem for recognizability.

(Theorem 4.21) Let $M \in {ITRM, ITTM, OTM}$ . Assume that $V = L$ . Then the M-recognizability degrees are linearly ordered by the ordering induced by the canonical well-ordering $<_{L}$ of L.

Together with Proposition 4.22, this implies that the degree structure for recognizability is highly dependent on the set-theoretical background. Not even the existence of incomparable degrees (which follows in classical computability theory from a theorem of Kleene and Post, see e.g. Theorem 1.2 in Chapter VI of [31]) is absolute between transitive class-models of ZFC.

Notation.
If X is a set, $P (X)$ denotes its power set. We fix some natural enumeration $(P_{i} ∣ i \in ω)$ of the ITRM-programs. For P an ITRM-program, $x \subseteq ω$ and $i, j \in ω$ , we write $P^{x} (i) ↓ = j$ for the statement that P, when run in the oracle x with i in its first register and 0 in all other registers, halts with j in its first register. $P^{x} ↓$ abbreviates the statement that the computation of P in the oracle x on the input 0 halts. The same notation will be used for the other models of computation considered here.

For notions and results on admissible set theory see [3] or [29], for descriptive set theory see [19], concerning forcing [25]. KP denotes Kripke–Platek set theory. $ω_{i}^{CK, x}$ denotes the ith x-admissible infinite ordinal, $ω_{ω}^{CK, x} : = sup {ω_{i}^{CK, x} : i \in ω}$ . δ is the Kronecker symbol, i.e. for $x, y \subseteq ω$ , let $δ (x, y) = 1$ if and only if $x = y$ and $δ (x, y) = 0$ otherwise. We say that $A \subseteq [0, 1]$ is non-meager if and only if A is Borel and not meager. When $(A, \in)$ is a transitive ∈-structure and $f : ω \to A$ is a bijection, then $c : = {p (i, j) : f (i) \in f (j)}$ is called a code for $(A, \in)$ , where p is Cantor’s pairing function.

For $M \in {ITRM, ITTM, OTM}$ , ${RECOG}_{M}$ denotes the set of M-recognizables (to be defined below).
2. Infinite Time Register Machines

Infinite Time Register Machines (ITRMs), introduced in [10] and further studied in [23], work similarly to the classical unlimited register machines (URMs) described in [13]. In particular, they use finitely many registers each of which can store a single natural number. The difference is that ITRMs use transfinite ordinal running time: The state of an ITRM at a successor ordinal is obtained as for URMs. At limit times, the program line is the inferior limit of the earlier program lines and there is a similar limit rule for the register contents. If the inferior limit of the earlier register contents is infinite, the register is reset to 0.

For details on ITRMs, we refer to [22,23] and [10]. Here, we briefly review some standard notions and facts concerning ITRMs that will be used below.

Definition 2.1.
$x \subseteq ω$ is ITRM-computable in the oracle $y \subseteq ω$ if and only if there exists an ITRM-program P such that, for $i \in ω$ , P with oracle y stops for every natural number j in its first register at the start of the computation and returns 1 if and only if $j \in x$ and otherwise returns 0. A real ITRM-computable in the empty oracle is simply called ITRM-computable.

It is not hard to see that any ITRM-computation either stops or eventually cycles. Moreover, it can be shown (see [23]) that an ITRM-computation eventually cycles if and only if some state of the computation, consisting of the active program line index l and the register contents $(r_{1}, \dots, r_{n})$ appears at two different times $α < β$ such that neither the active program line index nor any of the register contents drops below their corresponding value at time α. This halting criterion can be effectively tested by an ITRM, which leads to the following crucial property of ITRMs, due to Koepke and Miller:
Theorem 2.2.
Let $P_{n}$ denote the set of ITRM-programs using at most n registers, and let $(P_{i, n} ∣ i \in ω)$ enumerate $P_{n}$ in some natural way. Then the bounded halting problem $H_{n}^{x} : = {i \in ω ∣ P_{i, n}^{x} (0) ↓}$ is computable uniformly in the oracle x by an ITRM-program (using more than n registers, of course).

Moreover, if $P \in P_{n}$ , $i \in ω$ , $x \subseteq ω$ and $P^{x} (i) ↓$ , then the computation takes less than $ω_{n + 1}^{CK, x}$ many steps. Consequently, if P is an ITRM-program and $i \in ω$ , $x \subseteq ω$ are such that $P^{x} (i) ↓$ , then $P^{x} (i)$ stops in less than $ω_{ω}^{CK, x}$ many steps.
Proof.
The corresponding results from [23] easily relativize. □
Theorem 2.3.
Let $x, y \subseteq ω$ . Then x is ITRM-computable in the oracle y if and only if $x \in L_{ω_{ω}^{CK, y}} [y]$ . Moreover, there is a function $g : ω \to ω$ such that any $x \in L_{ω_{n}^{CK, y}} [y]$ is computable in the oracle y by some ITRM-program P using at most $g (n)$ registers.
Proof.
This is a relativization of the main results of Koepke’s [22]. □
Lemma 2.4.
There are ITRM-programs $(Q_{n} : n \in ω)$ and Q such that, for every $x \subseteq ω$ :
$Q_{n}^{x}$ computes a real number coding $L_{ω_{n + 1}^{CK, x} + 2} [x]$ .

Given a natural number n and a natural number m coding a finite set p of natural numbers, $Q^{x} (m)$ computes a real number $y \supseteq p$ that is Cohen-generic over $L_{ω_{n + 1}^{CK, x} + 1} [x]$ .

Proof.
(1) By standard fine-structural considerations, such a code is contained in $L_{ω_{n + 1}^{CK, x} + 3} [x]$ and hence computable by some ITRM-program $P_{x}$ by Theorem 2.3. Moreover, there is some $k \in ω$ such that for each x, $P_{x}$ uses at most k many registers. To compute a code for $L_{ω_{n + 1}^{CK, x} + 2} [x]$ uniformly in the oracle x, we search, starting with $i = 0$ , through ω in the following way: Given $i \in ω$ , first determine, using Theorem 2.2, whether $\forall j \in ω P_{i, k}^{x} (j) ↓ {0, 1}$ , i.e. whether $P_{i, k}^{x}$ computes a real. If so, determine, using the techniques for evaluating first-order predicates with ITRMs from the proof of the lost melody theorem for ITRMs in [10], whether the real computed by $P_{i, k}^{x}$ is a code for a well-founded ∈-structure of the form $L_{α} [x]$ such that α is of the form $β + 2$ , $L_{β} [x] ⊧ KP$ and $L_{β} [x]$ contains exactly n elements of the form $L_{γ} [x]$ such that $L_{γ} [x] ⊧ KP$ . If this holds, then a code as desired has been found; otherwise, proceed with $i + 1$ . As we observed, some program in $P_{k}$ computes a code as desired, so this procedure will terminate for some finite value of i.

(2) As $L_{ω_{n + 1}^{CK, x} + 1} [x]$ is isomorphic (via the Levy collapsing map) to its own $Σ_{1}$ -Skolem hull of ${x}$ , it follows that $L_{ω_{n + 1}^{CK, x} + 1} [x]$ is countable in $L_{ω_{n + 1}^{CK, x} + 2} [x]$ . Hence the proof of the Rasiowa–Sikorski-lemma shows that a real extending p and Cohen-generic over $L_{ω_{n + 1}^{CK, x} + 1} [x]$ is contained in $L_{ω_{n + 1}^{CK, x} + 2} [x]$ . Use the program $P_{n}$ from (1) to compute a real number c coding $L_{ω_{n + 1}^{CK, x} + 2} [x]$ . Then search through ω to determine, again using the techniques for evaluating first-order statements with ITRMs, some $i \in ω$ that codes a real with the desired properties in c. From i and c, the desired real is now easily computable. □

We now define relativized recognizability and then proceed with stating and proving our theorem.
Definition 2.5.
Let $x, y \subseteq ω$ . We say that x is ITRM-recognizable from y, written $x ⩽_{ITRM}^{r} y$ , if and only if there is an ITRM-program P such that $P^{z} ↓ \in {0, 1}$ for every $z \subseteq ω$ and, for all $z \subseteq ω$ , we have $P^{z \oplus y} ↓ = δ (x, z)$ . For a set $Y \subseteq P (ω)$ , we say that x is uniformly recognizable from Y if and only if there is an ITRM-program P such that, for every $y \in Y$ and every $z \subseteq ω$ , we have $P^{z \oplus y} ↓ = δ (z, x)$ . In this case, we say that x is recognized from Y via P. We say that x is recognizable if and only if $x ⩽_{ITRM}^{r} 0$ . We denote the set of reals recognizable relative to $y \subseteq ω$ by ${RECOG}_{y}$ and abbreviate ${RECOG}_{0}$ by RECOG.
Remark.
As we are only concerned with ITRMs in this section, we will usually drop the prefix ‘ITRM’ here.
Remark.
The condition that $P^{z}$ stops with output 0 or 1 for every input is introduced merely for the sake of the simplification of further arguments; if P is a program using n registers, we can always use the solvability of the bounded halting problem for ITRMs using at most n registers given by Theorem 2.2 to produce another program $P^{'}$ that, given $z \subseteq ω$ , first tests whether $P^{z} ↓$ with output 0 or 1 and returns the output of $P^{z}$ if that is the case and otherwise outputs 0. $P^{' x}$ and $P^{x}$ will hence produce the same output wherever the output of P is of the required form and $P^{'}$ will satisfy our extra condition.

A typical phenomenon for models of infinitary computations is the existence of reals that are recognizable, but not computable. As computability is easily seen to imply recognizability, it follows that recognizability is a strictly weaker notion than computability. This was first shown in [16] for Infinite Time Turing Machines. Detailed treatments of recognizability for ITRMs and for infinitary machines in general can be found in [5,7,9,10].

We note here that recognizability is computably stable for ITRMs, i.e. preserved under ITRM-computable equivalence:
Definition 2.6.
For $x, y \subseteq ω$ , we write $x \equiv_{ITRM} y$ and say that x and y are ITRM-computably equivalent if and only if there are ITRM-programs P and Q such that $P^{x}$ computes y and $Q^{y}$ computes x.
Proposition 2.7.
Let $x \equiv_{ITRM} y$ be real numbers. Then $x \in RECOG$ if and only if $y \in RECOG$ .
Proof.
Assume that $x \in RECOG$ . Let P and Q be ITRM-programs such that $P^{x} ↓ = y$ and $Q^{y} ↓ = x$ , and let R be a program for recognizing x, i.e. such that $\forall z \subseteq ω R^{z} ↓ = δ (x, z)$ . To recognize y, we proceed as follows: Assume that z is given in the oracle.

Step 1: Check, using a halting problem solver (see Theorem 2.2) for Q, whether $Q^{z} (i) ↓$ for all $i \in ω$ . If not, then $z \neq y$ , as Q computes x from y and hence $Q^{y} (i) ↓$ for every $i \in ω$ . So in that case, output 0 and stop. Then check whether $Q^{z} (i) ↓ \in {0, 1}$ for all $i \in ω$ by an exhaustive search. If not, then $z \neq y$ , again since $Q^{y} ↓ = x$ , so in that case, output 0 and stop. Otherwise, proceed with step 2.

Step 2: Let $Q^{z} ↓ = a$ . Check whether $R^{a} ↓ = 1$ . If not, then $a \neq x$ as R recognizes x, and hence $z \neq y$ as $Q^{y} ↓ = x$ . In that case, output 0 and stop. Otherwise, proceed with step 3.

Step 3: At this point, we know that $Q^{z} ↓ = a = x$ . Check whether $P^{a} ↓ = z$ (using a halting problem solver as in step 1). If not, then $z \neq y$ as $P^{x} ↓ = y$ . In this case, output 0 and stop. Otherwise, $z = y$ , so output 1 and stop.

Hence $x \in RECOG$ implies $y \in RECOG$ . The reverse direction follows analogously. □
Remark.
Note that, however, relativized recognizability is not transitive (see [7]).
Lemma 2.8.
Let P be an ITRM-program using n registers, let $x \subseteq ω$ and suppose that g is Cohen-generic over $L_{ω_{n + 1}^{CK, x} + 1} [x]$ . Then $ω_{i}^{CK, x \oplus g} = ω_{i}^{CK, x}$ for $i ⩽ n + 1$ . Consequently, $P^{x \oplus g}$ halts in less than $ω_{n + 1}^{CK, x}$ many steps or does not halt at all.
Proof.
By Theorem 10.11 of [27], if M is admissible, $P$ is a forcing in M and G is $P$ -generic over M such that G intersects every subclass of M that is a union of a $Σ_{1} (M)$ and a $Π_{1} (M)$ class, then $M [G]$ is also admissible. Clearly, as $L_{α + 1} [x]$ contains all subclasses of $L_{α} [x]$ definable over $L_{α} [x]$ , we have that, when M is of the form $L_{α} [x]$ with x-admissible α and $g \subseteq ω$ Cohen-generic over $L_{α + 1} [x]$ , then $L_{α} [x] [g]$ is admissible.

As admissible ordinals are indecomposable, it follows from Theorem 9.0 of [27] that the forcing extension $L_{ω_{i}^{CK, x}} [x] [g]$ agrees with the relativized L-level $L_{ω_{i}^{CK, x}} [x \oplus g]$ for all $i ⩽ n + 1$ . Consequently, if g is as in the assumption of the lemma, then $L_{ω_{i}^{CK, x}} [x] [g] = L_{ω_{i}^{CK, x}} [x \oplus g]$ is admissible for $i ⩽ n + 1$ : so $ω_{i}^{CK, x}$ is $x \oplus g$ -admissible for $i ⩽ n + 1$ . Certainly, every $x \oplus g$ -admissible ordinal is also x-admissible, so that first $(n + 1)$ many x-admissible ordinals agree with the first $(n + 1)$ many $x \oplus g$ -admissible ordinals. Hence $ω_{n + 1}^{CK, x} = ω_{n + 1}^{CK, x \oplus g}$ .

The second claim now follows from Theorem 2.2. □

In [8], we showed that every real x that is uniformly recognizable from all elements of a non-meager Borel set is recognizable. Here, we demonstrate a relativized version of this result (though the proof pretty much remains the same).
Definition 2.9.
A real number z is an r-extracting real if and only if there are a comeager set of reals Y and a real number x such that $x ≰_{ITRM}^{r} z$ , but x is uniformly recognizable from ${z} \oplus Y : = {z \oplus y : y \in Y}$ .

Intuitively, a real x is r-extracting when addition of a typical oracle to x allows to extract more information than one gets from x itself. We will now show that r-extracting reals do not exist; the statement that recognizability from all oracles in a comeager set implies recognizability is in this language the special case that 0 is not r-extracting. This special case was proved as Theorem 7 of [8].
Theorem 2.10.
There are no uniformly r-extracting reals. I.e.: If $z \subseteq ω$ , $Y \subseteq [0, 1]$ is comeager, and $x \subseteq ω$ is uniformly recognizable in ${z} \oplus Y$ , then x is recognizable from z.
Proof.
Suppose that Y is comeager, $z \subseteq ω$ and $x \subseteq ω$ is uniformly recognized from all elements of ${z} \oplus Y$ by the ITRM-program P. Assume that P uses n registers. Let C be the set of real numbers that are Cohen-generic over $L_{ω_{n + 1}^{CK, x \oplus z} + 1} [x \oplus z]$ . As C is comeager, so is $Y \cap C$ . We can hence assume without loss of generality that $Y \subseteq C$ . Pick $y \in Y$ . By assumption, we have $P^{x \oplus (z \oplus y)} ↓ = 1$ . By Lemma 2.8, we have $ω_{n + 1}^{CK, x \oplus (z \oplus y)} = ω_{n + 1}^{CK, (x \oplus z) \oplus y} = ω_{n + 1}^{CK, x \oplus z}$ , so $P^{x \oplus (z \oplus y)}$ runs for $< ω_{n + 1}^{CK, x \oplus z}$ many steps and hence halts inside $L_{ω_{n + 1}^{CK, x \oplus z}} [x \oplus (z \oplus y)]$ . By the forcing theorem for admissible sets (see Lemma 10.10 of [27]), there must be some forcing condition $p \subseteq y$ such that $p ⊩ P^{x \oplus (z \oplus y)} ↓ = 1$ over $L_{ω_{n + 1}^{CK, x \oplus z}} [x \oplus z]$ . Hence, we have $P^{x \oplus (z \oplus g)} ↓ = 1$ for every $g \supseteq p$ that is Cohen-generic over $L_{ω_{n + 1}^{CK, x \oplus z} + 1} [x \oplus z]$ .

We claim that the following procedure recognizes x relative to z: Given a real a in the oracle, compute (a code for) $L_{ω_{n + 1}^{CK, a \oplus z} + 1} [a \oplus z]$ , using (1) of Lemma 2.4. From that code, compute a real $g_{a} \supseteq p$ that is Cohen-generic over $L_{ω_{n + 1}^{CK, a \oplus z} + 1} [a \oplus z]$ , using (2) of Lemma 2.4. Then run $P^{a \oplus (z \oplus g_{a})}$ , which must, by assumption, halt with output 0 or 1, and return its output. Let Q be an ITRM-program that carries out this procedure when given the oracle $a \oplus z$ .

We need to see that $Q^{a \oplus z} ↓ = 1$ if and only if $a = x$ , and otherwise $Q^{a \oplus z} ↓ = 0$ . That $Q^{x \oplus z} ↓ = 1$ is clear since the generic g picked in the procedure extends p, which forces $Q^{x \oplus (z \oplus g)}$ to converge to 1 in $L_{ω_{n + 1}^{CK, x \oplus z}} [x \oplus (z \oplus g)]$ and the computation is absolute between $L_{ω_{n + 1}^{CK, x \oplus z}} [x \oplus (z \oplus g)]$ and the real world.

Now suppose that $a \neq x$ , but that $Q^{a \oplus z} ↓ = 1$ . This implies that, for some $g_{a}$ Cohen-generic over $L_{ω_{n + 1}^{CK, a \oplus z} + 1} [a \oplus z]$ , we have $P^{a \oplus (z \oplus g_{a})} ↓ = 1$ . By the forcing theorem for admissible sets again, there is some forcing condition $q \subseteq g_{a}$ such that $q ⊩ P^{a \oplus (z \oplus g_{a})} ↓ = 1$ . Consequently, $P^{a \oplus (z \oplus \bar{g})} ↓ = 1$ holds for every $\bar{g} \supseteq q$ that is Cohen-generic over $L_{ω_{n + 1}^{CK, a \oplus z} + 1} [a \oplus z]$ . But the set $\hat{C}$ of all such $\bar{g}$ is not meager and must hence intersect Y; so let $g \in Y \cap \hat{C}$ . Then $P^{a \oplus (z \oplus g)} ↓ = 1$ , but $a \neq x$ , which contradicts the assumption that P recognizes x from ${z} \oplus Y$ . □

We can relax the condition of Y being comeager to Y merely being Borel and not meager.
Corollary 2.11.
Let $Y \subseteq [0, 1]$ be non-meager, $z \subseteq ω$ , and let $x \subseteq ω$ be uniformly recognizable from ${z} \oplus Y$ . Then $x ⩽_{ITRM}^{r} z$ .
Proof.
As Y is non-meager, there is an interval $I = (a, b) \subseteq [0, 1]$ such that Y is comeager in I. By shortening I if necessary, we may assume without loss of generality that I is of the form ${t x ∣ x \in^{ω} 2}$ for $t \in^{< ω} 2$ (where $t x$ denotes the concatenation of t and x) and (passing to $Y \cap I$ if necessary) that $Y \subseteq I$ . Suppose that P recognizes x relative to all elements of ${z} \oplus Y$ . We define a program $P^{'}$ that recognizes x from all elements of ${z} \oplus Y^{'}$ where $Y^{'} : = {x : t x \in I}$ , which is obviously a comeager set. $P^{' a \oplus (z \oplus y)}$ works by simply running $P^{a \oplus (z \oplus t y)}$ . Clearly, $P^{'}$ has the desired properties: For $y \in Y^{'}$ , we have $P^{' a \oplus (z \oplus y)} ↓ = 1$ if and only if $P^{a \oplus (z \oplus t y)} ↓ = 1$ which, as $t y \in Y$ by definition of $Y^{'}$ , is equivalent with $a = x$ . So $P^{'}$ recognizes x from all elements of ${z \oplus Y}$ for a comeager set Y. By Theorem 2.10, x is then uniformly recognizable from z. □

We have so far worked with uniform recognizability, i.e. the program recognizing x from z and some $y \in Y$ has to be the same for all elements of Y. If one wants to drop this assumption and allow x to be recognized from y by different programs P for different $y \in Y$ , the problem arises that the corresponding subsets $Y_{P}^{z} : = {y \in Y : P recognizes x from z \oplus y}$ might not have the property of Baire and hence not be comeager in some interval so that Theorem 2.10 is not applicable. At least under some (standard) set-theoretical extra assumption, however, we can strengthen the claim to drop the uniformity condition: Corollary 2.12.
Assume that every ${\tilde{Σ}}_{2}^{1}$ -set of reals has the Baire property. Let Y be a non-meager set, $x, z \subseteq ω$ and assume that, for every $y \in Y$ , there is some ITRM-program $P_{y}$ such that for all $a \subseteq ω$ , $P_{y}^{a \oplus (z \oplus y)} ↓ = 1$ if and only if $a = x$ and otherwise $P_{y}^{a \oplus (z \oplus y)} ↓ = 0$ . Then x is ITRM-recognizable from z.
Proof.
$Y_{P}^{z}$ is $Π_{2}^{1}$ in x and z for every ITRM-program P: Namely, the set of these y is definable by a formula ϕ expressing ‘For all $a, b \subseteq ω$ : If b codes the computation of P in the oracle $a \oplus (z \oplus y)$ and this computation stops with output 1, then $a = x$ ’. (Recall that, by the choice of P, the computation of P any oracle always terminates and hence is a countable set codable by a real.) As ‘b codes the computation of P in the oracle c’ is $Π_{1}^{1}$ in c, the negation is $Σ_{1}^{1}$ , so the statement ‘For all $a, b \subseteq ω$ : $a = x$ or b does not code the computation of P in the oracle $a \oplus (z \oplus y)$ ’, which is equivalent to ϕ, is $Π_{2}^{1}$ in z and x.

Thus, for each ITRM-program P, $Y_{P}$ has the Baire property (as its complement is ${\tilde{Σ}}_{2}^{1}$ and hence Baire by assumption and as complements of Baire sets are again Baire). Now $Y = ⋃_{i \in ω} Y_{P_{i}}$ . As Y is not meager, it cannot be the union of countably many meager sets. So there is some $k \in ω$ such that $\bar{Y} : = Y_{P_{k}}$ is not meager. As $\bar{Y}$ also has the Baire property, there is an interval such that $\bar{Y}$ is comeager relative to that interval. As in the proof of Corollary 2.11, it follows that x is uniformly ITRM-recognizable from $z \oplus y$ for all elements y of a comeager set of oracles, and hence, by Theorem 2.10, x is ITRM-recognizable from z. □
Remark.
The assumption that every ${\tilde{Σ}}_{2}^{1}$ -set of reals has the Baire property follows for example from the existence of a measurable cardinal (see e.g. Corollary 14.3 [19]). By Proposition 13.7 of [19], every ${\tilde{Σ}}_{2}^{1}$ -set is a union of $ℵ_{1}$ many Borel sets. By Theorem 2.20 of Chapter II of [25], ${MA}_{ω_{1}}$ implies that a union of $ℵ_{1}$ many meager sets is meager (and hence that a union of $ℵ_{1}$ many sets with the Baire property has the Baire property). As Borel sets have the Baire property, it thus also follows from ${MA}_{ω_{1}}$ that all ${\tilde{Σ}}_{2}^{1}$ -sets have the Baire property.

Moreover, the statement that all ${\tilde{Σ}}_{2}^{1}$ -sets of reals have the Baire property is equivalent to the statement that the set of reals that are Cohen-generic over $L [x]$ is comeager for every $x \subseteq ω$ (see Theorem 14.2 of [19]).

It well known that L contains ${\tilde{Σ}}_{2}^{1}$ -sets of reals that fail to have the Baire property (see e.g. Corollary 13.10 of [19] or observe that in L, the set of reals Cohen-generic over L is empty). On the other hand, ${MA}_{ω_{1}}$ holds in a forcing extension of L (see Theorem 10.11 of [19]). Thus, the statement that every ${\tilde{Σ}}_{2}^{1}$ -set of reals has the Baire property is independent of $ZFC$ .
Question.
Is this non-uniform version of Corollary 2.11 provable in $ZFC$ alone?

3. Infinite Time Turing Machines

Since there is in the case of ITTMs no analogue for the stratification of halting times as given by Theorem 2.2 for ITRMs, which is a crucial ingredient of the proof of Theorem 2.10, the treatment of ITTMs will require a new idea. This new idea is that, for a certain x recognizable from many oracles, there is a large subset of the oracles for which the full strength of $λ^{x}$ (the supremum of the ITTM-halting times in the oracle x) is unnecessary for performing the recognition: We can limit the ‘relevant’ halting times to a certain ordinal $α < λ^{x}$ . This serves a similar purpose as the stratification of halting times for ITRMs.

Definition 3.1.
Let $x \subseteq ω$ . $λ^{x}$ denotes the supremum of ITTM-halting times in the oracle x. A real x is ITTM-computable (or ITTM-writable) in the oracle y if and only if there is an ITTM-program P such that $P^{y}$ halts with x on the output tape. A real x is eventually writable in the oracle y if and only if there is an ITTM-program P such that $P^{y}$ does not halt, but eventually leaves the content of the output tape invariant and equal to x. $ζ^{x}$ denotes the supremum of those ordinals α such that $L_{α + 1} [x] ∖ L_{α} [x]$ contains a real that is eventually writable in the oracle x. A real number x is accidentally writable in the oracle y if and only if there is an ITTM-program P such that the tape content of the computation of $P^{y}$ is equal to x at some point of time. $Σ^{x}$ denotes the supremum of those ordinals α such that $L_{α + 1} [x] ∖ L_{α} [x]$ contains a real that is accidentally writable in x.
Theorem 3.2 (Welch).

A real y is ITTM-computable in the oracle x if and only if $y \in L_{λ^{x}} [x]$ , eventually writable if and only if $y \in L_{ζ^{x}} [x]$ and accidentally writable if and only if $y \in L_{Σ^{x}} [x]$ . Furthermore, $(λ^{x}, ζ^{x}, Σ^{x})$ is the lexically minimal triple $(α, β, γ)$ of ordinals such that $L_{α} [x] ≺_{Σ_{1}} L_{β} [x] ≺_{Σ_{2}} L_{γ} [x]$ .

Proof.
See [33]. □
Theorem 3.3 (Hamkins–Lewis).

For each real x, $λ^{x}$ is x-admissible, a limit of x-admissible ordinals and a limit of x-admissible limits of x-admissible ordinals.

Proof.
This follows from the ‘Indescribability Theorem’ 8.3 of [16] (which in fact shows that we could iterate the ‘limit of’-operation as often as we wanted) whose proof easily relativizes. □
Lemma 3.4.
Let x be ITTM-recognizable by the program P. Then $x \in L_{λ^{x}}$ and x is the unique witness to some $Σ_{1}$ -formula ϕ in $L_{λ^{x}}$ .
Proof.
By definition of $λ^{x}$ , $P^{x}$ halts in less than $λ^{x}$ many steps, hence $L_{λ^{x}} [x] ⊧ P^{x} ↓ = 1$ . Furthermore, as P recognizes x, x is the unique element of $L_{λ^{x}} [x]$ with this property. As $P^{y} ↓ = 1$ is $Σ_{1}$ -expressible in the parameter y, so is $\exists y P^{y} ↓ = 1$ . Now, $λ^{x}$ is a limit of admissible ordinals by Theorem 3.3.

By a theorem of Jensen and Karp [18], set theoretical $Σ_{1}$ -formulas are absolute between $L_{α}$ and $V_{α}$ when α is a limit of admissible ordinals. As $x \in V_{λ^{x}}$ , we have $V_{λ^{x}} ⊧ \exists y P^{y} ↓ = 1$ . Hence $L_{λ^{x}} ⊧ \exists y P^{y} ↓ = 1$ . So there is $y \in L_{λ^{x}}$ such that $L_{λ^{x}} ⊧ P^{y} ↓ = 1$ . By absoluteness of computations, $P^{y} ↓ = 1$ holds in the real world. As P recognizes x, we must have $y = x$ . So $x \in L_{λ^{x}}$ , and x is the unique witness in $L_{λ^{x}}$ to the $Σ_{1}$ -formula $\exists y P^{y} ↓ = 1$ . □

An important question in classical recursion theory is whether there exist ‘natural’, ‘specific’ examples of reals incomparable with $0^{'}$ in the sense of Turing reducibility (see e.g. [30]). For infinitary machines, it seems sensible to understand ‘specific’ as ‘recognizable’. The following can hence be seen as a proof that such reals do not exist for ITTMs. A similar result for ITRMs was obtained in [6].
Theorem 3.5.
Assume that x is ITTM-recognizable. Then x is computable or $0_{ITTM}^{'}$ , the halting real for ITTMs, is ITTM-computable from x.
Proof.
Assume that x is a lost melody, i.e. recognizable, but not computable. So, by Lemma 3.4, we have $x \in L_{λ^{x}} - L_{λ}$ . So $λ^{x} > λ$ . If P is a halting ITTM-program, then P will also halt inside the $Σ_{1}$ -Skolem hull $H$ of ∅ in $L_{λ}$ , so $H$ must contain the computation of P for each halting P. Thus, $H$ is isomorphic to $L_{λ}$ , so that a surjection of ω onto $L_{λ}$ is definable over $L_{λ}$ . Hence λ is an index, i.e. $(L_{λ + 1} - L_{λ}) \cap R \neq \emptyset$ . By a theorem of Boolos and Putnam (see [4]), $L_{λ + 1}$ contains an arithmetical copy of $L_{λ}$ , i.e. $cc (L_{λ}) \in L_{λ + 1}$ . Hence $cc (L_{λ}) \in L_{λ^{x}} [x]$ , so $cc (L_{λ})$ is computable from x. However, from $cc (L_{λ})$ , it is easy to obtain $0_{ITTM}^{'}$ by using $cc (L_{λ})$ for evaluating statements of the form $P_{i} ↓$ in $L_{λ}$ . □
Lemma 3.6.
Let $x \subseteq ω$ , and let y be Cohen-generic over $L_{Σ^{x} + 1} [x]$ . Then $λ^{x \oplus y} = λ^{x}$ .
Proof.
This is the relativized version of a fact used in the proof of Theorem 3.1 of [32]. The proof given in Lemma 33 of [11] relativizes. □

We will need the following theorem due to A. Mathias, which implies that, under rather mild assumptions on the closedness of $L_{α} [x]$ , the forcing extensions some of some $L_{α} [x]$ by a generic real y is the same as $L_{α} [x \oplus y]$ . Here, $P_{θ}^{e}$ denotes the provident hierarchy relativized to e and ${(P_{θ}^{e})}^{P} [G]$ denotes the generic extension of $P_{θ}^{e}$ by G, where G is a $P$ -generic filter over $P_{θ}^{e}$ . For the definition of the provident hierarchy and of a provident set, see [27].
Theorem 3.7.
Let θ be an indecomposable ordinal strictly greater than the rank of a transitive set e which contains the notion of forcing $P$ . Let G be $(P_{θ}^{e}, P)$ -generic. Then ${(P_{θ}^{e})}^{P} [G] = P_{θ}^{e \cup {G}}$ .
Proof.
See [27], Theorem 9. □
Remark.
This theorem does not immediately apply in the case of real numbers as these are in general not transitive; we can e.g. circumvent this problem by replacing $e \subseteq ω$ by the transitive set $e^{'} : = ω \cup {{i + 1} : i \in e}$ . As we will only use this theorem in the context of Cohen-forcing which is contained in $L_{ω + 6}$ , the condition that e must contain the notion of forcing is not relevant for our purposes: The relevant information can always be encoded in a transitive set of rank $ω + i$ where $i \in ω$ .

Moreover, if x is a real number and α is x-admissible, then we have $P_{α} [x] = J_{α} [x] = L_{α} [x]$ . As these hierarchies are continuous by definition, the same holds when α is a limit of x-admissible ordinals.
Corollary 3.8.
Let $x, y \subseteq ω$ . Write $L_{α}^{x}$ for the αth level of the L-hierarchy relativized to x and, if y is generic over some M, write $M [y]$ for the generic extension. Suppose that α is x-admissible or a limit of x-admissible ordinals and that y is Cohen-generic over $L_{α} [x]$ . Then $L_{α}^{x \oplus y} = L_{α}^{x} [y]$ .

From now on, we therefore can and will use the square bracket notation in both cases.
Lemma 3.9.
Let $x \subseteq ω$ , ϕ a $Σ_{1}$ -formula in the parameter x, possibly with real parameters in $L_{α} [x]$ where α is a limit of x-admissible ordinals. Then ϕ is absolute between $V_{α}$ and $L_{α} [x]$ .
Proof.
This is a relativization of the Jensen–Karp theorem in Section 5 of [18]. The proof more or less relativizes, we elaborate on the necessary changes in the Appendix, see Theorem A.1. □
Lemma 3.10.
Assume that a real x is recognizable relative to a real y. Then $x \in L_{λ^{x \oplus y}} [y]$ .
Proof.
Here, we use Lemma 3.9: Since $λ^{x \oplus y}$ is a limit of $x \oplus y$ -admissible ordinals and each $x \oplus y$ -admissible ordinal is in particular y-admissible, $λ^{x \oplus y}$ is a limit of y-admissible ordinals. As $\exists z P^{z \oplus y} ↓ = 1$ is $Σ_{1}$ , it is hence absolute between $V_{λ^{x \oplus y}}$ and $L_{λ^{x \oplus y}} [y]$ , as the latter contains the necessary parameter y (as $λ^{x \oplus y}$ is a limit of $x \oplus y$ -admissibles by Theorem 3.3 and hence of y-admissibles). Consequently, it holds in $L_{λ^{x \oplus y}} [y]$ , so this structure contains x by absoluteness of computations. □
Lemma 3.11.
Assume that a real x is ITTM-recognizable relative to all $y \in M$ , where $M \subseteq P (ω)$ is Borel and non-meager. Then $x \in L_{λ^{x}}$ .
Proof.
The set will contain mutually generics $g_{1}$ , $g_{2}$ over $L_{Σ^{x} + 1} [x]$ by Lemma 30 of [11]. We have $λ^{x \oplus g_{1}} = λ^{x \oplus g_{2}} = λ^{x}$ by Lemma 3.6. So, by Lemma 3.10, Lemma 3.8 and Lemma 28 of [11], we will have $x \in L_{λ^{x \oplus g_{1}}} [x \oplus g_{1}] \cap L_{λ^{x \oplus g_{2}}} [x \oplus g_{2}] = L_{λ^{x}} [g_{1}] \cap L_{λ^{x}} [g_{2}] = L_{λ^{x}}$ , as desired. □
Theorem 3.12.
Let x be uniformly ITTM-recognizable from all elements y of a comeager set Y. Then x is ITTM-recognizable.
Proof.
Let P be an ITTM-program that recognizes x relative to every element $y \in Y$ . By Lemma 3.11, we have $x \in L_{λ^{x}}$ . The set $C_{β}^{z}$ of reals Cohen-generic over $L_{β} [z]$ is comeager for every countable ordinal β and every real z. We may hence assume without loss of generality that $Y \subseteq C_{Σ^{x} + 1}^{x}$ . By Lemma 3.6 then, $λ^{x \oplus y} = λ^{x}$ holds for all $y \in Y$ . Hence $P^{x \oplus y} ↓ = 1$ in less than $λ^{x}$ many steps for every $y \in Y$ . For $y \in Y$ , let $τ (y)$ be the halting time of $P^{x \oplus y}$ . Then τ (as a function from $R$ to $λ^{x}$ ) has comeager pre-image and countable domain, hence there is some $ζ < λ^{x}$ such that $τ^{- 1} [ζ]$ is not meager (since otherwise, $R$ was a countable union of meager sets, i.e. meager). Let $ζ < λ^{x}$ be minimal with this property, and let $\bar{Y} = τ^{- 1} [ζ]$ .

Let α be the smallest admissible limit of admissible ordinals greater than ζ. Then $α + 1 < λ^{x}$ by Theorem 3.3.

We claim that $x \in L_{α}$ . To see this, let $g_{1}$ , $g_{2}$ be mutually (Cohen-)generic over $L_{Σ^{x}}$ and elements of $\bar{Y}$ , which exist by Lemma 3.6: First, as $\bar{Y}$ is not meager and $Σ^{x}$ is countable, $\bar{Y}$ contains a real $g_{1}$ generic over $L_{Σ^{x}}$ . Again by Lemma 3.6, $\bar{Y}$ contains a real $g_{2}$ generic over $L_{Σ^{x}} [g_{1}]$ . By standard facts on Cohen-forcing (see e.g. Lemma 30 of [11]), $g_{1}$ and $g_{2}$ are mutually generic over $L_{Σ^{x}}$ .

So $P^{x \oplus g_{1}} ↓ = 1$ and $P^{x \oplus g_{2}} ↓ = 1$ . As therefore $V_{α} ⊧ \exists z P^{z \oplus g_{1}} ↓ = 1 \land P^{z \oplus g_{2}} ↓ = 1$ , we have $L_{α} [g_{1}] ⊧ \exists z P^{z \oplus g_{1}} ↓ = 1$ and $L_{α} [g_{2}] ⊧ \exists z P^{z \oplus g_{2}} ↓ = 1$ by Lemma 3.9.

As $g_{1}, g_{2} \in Y$ (so P recognizes x relative to $g_{1}$ and $g_{2}$ ) and by absoluteness of computations, the elements $z_{1} \in L_{α} [g_{1}]$ and $z_{2} \in L_{α} [g_{2}]$ witnessing $\exists z P^{z \oplus g_{1}} ↓ = 1$ and $L_{α} [g_{2}] ⊧ \exists z P^{z \oplus g_{2}} ↓ = 1$ must both be equal to x, so we have $x \in L_{α} [g_{1}]$ and $x \in L_{α} [g_{2}]$ , so that finally $x \in L_{α} [g_{1}] \cap L_{α} [g_{2}] = L_{α}$ by mutual genericity of $g_{1}$ , $g_{2}$ over $L_{λ^{x}}$ and hence over $L_{α} \subseteq L_{λ^{x}}$ .

$P^{z \oplus g_{1}}$ may not stop in less than α many steps for each $z \in L_{α}$ ; however, by absoluteness of computations and since P recognizes z from $g_{1}$ , it only does so with output 1 if $z = x$ . So we have that $L_{α} [g_{1}] ⊧ \forall z P^{z \oplus g_{1}} ↓ = 1 \leftrightarrow x = z$ . By the forcing theorem for admissible sets (see e.g. Lemma 32 of [11]), there is a finite $p \subseteq ω$ such that $p ⊩ \forall z P^{z \oplus g_{1}} ↓ = 1 \leftrightarrow x = z$ over $L_{α}$ . Consequently, the same holds for every real $g \supseteq p$ which is Cohen-generic over $L_{α + 1}$ .

We can now recognize x by the following procedure: Given a real z in the oracle, we let all ITTM-programs run simultaneously in the oracle z and check the output whenever a computation stops until we find a pair $(L_{ξ} [z], g)$ 2
²
This is a slight abuse of notation. The first element should of course actually be a real number coding $L_{ξ} [z]$ .

such that $g \supseteq p$ , g is generic over $L_{ξ + 1} [z]$ and ξ is a z-admissible limit of z-admissible ordinals greater than the halting time of $P^{z \oplus g}$ . (We shall see below that such a pair exists for every z and is an element of $L_{λ^{z}} [z]$ and thus computable by some ITTM in the oracle z so that the search always terminates.) Now check (1) whether $z \in L_{ξ}$ and (2) whether $L_{ξ} ⊧ \forall y \subseteq ω P^{y \oplus g} ↓ = 1 \leftrightarrow y = z$ , i.e. whether z is the unique element y of $L_{ξ}$ such that $P^{y \oplus g} ↓ = 1$ in less than ξ many steps. This can be done by evaluating a recursive truth predicate in $L_{ξ}$ . We claim that, if either fails, then $z \neq x$ , otherwise $z = x$ .

To see that this procedure works, we first observe that such a pair $(L_{ξ} [z], g)$ always exists and is ITTM-computable from z: Given the oracle z, pick some $\hat{g} \supseteq p$ Cohen-generic over $L_{Σ^{z} + 1} [z]$ . Then $P^{z \oplus \hat{g}} ↓$ in less than $λ^{z}$ many steps by Lemma 3.6. Let $\hat{ζ}$ be the halting time of $P^{z \oplus \hat{g}} ↓$ , and let $\hat{α}$ be the smallest z-admissible limit of z-admissible ordinals greater than $\hat{ζ}$ . By Theorem 3.3, we have $\hat{α} < λ^{z}$ . Then $L_{\hat{α}} [z] [\hat{g}] ⊧ P^{z \oplus \hat{g}} ↓$ .3
³
We may use the generic extension and the relativized constructibility equivalently by Theorem 3.8.

Again by the forcing theorem over admissible sets, there is $q \subseteq \hat{g}$ such that $q ⊩ P^{z \oplus \hat{g}} ↓$ over $L_{\hat{α}} [z]$ . As $\hat{g} \supseteq p$ , q and p are compatible; let $s = q \cup p$ . Now, if ${\hat{g}}^{'} \supseteq s$ is another generic over $L_{\hat{α} + 1} [z]$ , then we still have $L_{\hat{α}} [z] [\hat{g}] ⊧ P^{z \oplus {\hat{g}}^{'}} ↓$ ; so the halting time of $P^{z \oplus {\hat{g}}^{'}}$ is less than $\hat{α}$ . As the projectum in $L [z]$ will drop to ω between $\hat{α}$ and $λ^{z}$ (it drops at every halting time, of which $λ^{z}$ is the supremum), making $L_{\hat{α}} [z]$ countable in $L_{λ^{z}} [z]$ , so that the Rasiowa–Sikorski-construction can be carried out inside $L_{λ^{z}} [z]$ with the result that such a real $\hat{g}$ will (along with a real coding $L_{\hat{α}} [z]$ ) be contained in $L_{λ^{z}} [z]$ .

Now, if $z = x$ , then, as g is generic and extends p which forces $P^{x \oplus g}$ to converge to 1, the procedure will clearly halt with output 1. So assume towards a contradiction that our procedure stops with output 1 in the oracle $z \neq x$ . Let $(L_{ξ} [z], g)$ be the pair found in the execution of the procedure. In particular, this means that $z \in L_{ξ}$ . We distinguish two cases: Case 1.
$ξ ⩾ α$ . Then $g \supseteq p$ , being generic over $L_{ξ + 1}$ , is also generic over $L_{α + 1}$ . Hence $P^{x \oplus g} ↓ = 1$ in less than $α ⩽ ξ$ many steps by the choice of p and the fact that $x \in L_{α} \subseteq L_{ξ}$ . So z is not the only element y of $L_{ξ}$ with $P^{y \oplus g} ↓ = 1$ in less than ξ many steps, contradicting the assumption that our procedure stopped with output 1.
Case 2.
$ξ < α$ . As $z \in L_{ξ}$ and ξ is admissible, we have $L_{ξ} [z] = L_{ξ}$ By the forcing theorem over admissible sets once more, there is a finite $q \subseteq g$ such that $q ⊩ P^{z \oplus g} ↓ = 1$ over $L_{ξ}$ (thus in less than ξ many steps). As $g \supseteq p$ , q and p are compatible; let $s = q \cup p$ . Now pick $\bar{g} \supseteq s$ generic over $L_{α + 1}$ . Then, as $\bar{g} \supseteq p$ , x should be the only element y of $L_{α}$ with $P^{y \oplus g} ↓ = 1$ in less than α many steps; but as $\bar{g} \supseteq q$ , we also have that $P^{z \oplus \bar{g}} ↓ = 1$ in less than $ξ < α$ many steps, contradicting the assumption that $z \neq x$ .

Hence the procedure identifies x, as desired. □

As in the ITRM-part, we can deduce: Corollary 3.13.

Let $Y \subseteq [0, 1]$ be non-meager, and let $x \subseteq ω$ be uniformly ITTM-recognizable in Y. Then x is ITTM-recognizable.

Assume that every ${\tilde{Σ}}_{2}^{1}$ -set of reals has the Baire property. Let Y be a non-meager set, $x \subseteq ω$ and assume that, for every $y \in Y$ , there is some ITTM-program P such that $P^{z \oplus y} ↓ = 1$ if and only if $z = x$ . Then x is ITTM-recognizable.

3.1. Other machines

Other notable machine models of infinitary computability include α-Turing machines (see [24]), α-register machines (see [21] and [9]), and ordinal Turing machines (OTMs) (see [20]) with and without ordinal parameters.

Concerning OTMs without parameters, we have that, by [9], recognizability equals computability, and the proof relativizes: Roughly, there is a non-halting OTM-program Q that, given the oracle x, enumerates $L [x]$ . By Shoenfield absoluteness, if P is a program that parameter-freely recognizes y relative to x, then, as ‘There is a real z such that $P^{z \oplus x} ↓ = 1$ ’ is a $Σ_{1}$ -statement which, as it holds in V by assumption, must also hold in $L [x]$ . One can thus compute y in the oracle x by a parameter-free OTM by enumerating $L [x]$ , running $P^{z \oplus x}$ whenever a new real z is produced and halting and outputting z once $P^{z \oplus x} ↓ = 1$ . As the claim that parameter-free OTM-computability from all elements of a non-meager or a positive set of oracles implies OTM-computability is independent of ZFC by Section 2.1 of [11], the same holds for the recognizable analogue.

Recognizability for OTMs with ordinal parameters is a more delicate issue. It is shown in [9] that $0^{♯}$ is OTM-recognizable in the parameter $ω_{1}$ , and the same argument can be applied to show the recognizability of reals even more remote from L. One of the results of [12] is that, under the assumption that $M_{1}^{♯}$ exists, the closure of ∅ under relativized parameter-OTM recognizability (for real numbers) coincides with $R^{M_{1}}$ , where $M_{1}$ is the mouse for a Woodin cardinal. Trivially, as every constructible real is computable and hence recognizable by some parameter-OTM, the claim that for parameter-OTMs, recognizability from all elements of a non-meager set implies recognizability holds in L. On the other hand, we have:

Lemma 3.14.
Let $P$ be a weakly homogenous notion of forcing (i.e. for any two conditions p, q, there is an automorphism π of $P$ such that $π (p)$ and q are compatible), $M ⊧ ZFC$ a transitive model containing $P$ , G a $P$ -generic filter over M and $x \subseteq ω$ such that $x \in M [G] ∖ M$ . Then x is not recognizable.
Proof.
Assume otherwise, and fix a weakly homogenous forcing notion $P$ , a transitive $M ⊧ ZFC$ containing $P$ , a $P$ -generic filter G over M and a real $x \in M [G] ∖ M$ such that, for some OTM-program P and some ordinal α, P recognizes x in the parameter α. By absoluteness of computations, this means in particular that P recognizes x in the parameter α in $M [G]$ .

By the forcing theorem, there is then a condition $p \in G$ such that p forces that $\overset{ˇ}{P}$ recognizes $\dot{x}$ in the parameter $\overset{ˇ}{α}$ , where we denote by $\overset{ˇ}{z}$ the canonical name for z. If p would decide every bit of x, then we would have $x \in M$ , contradicting our assumption. Let $q_{0}$ , $q_{1}$ be two strengthenings of p that decide some bit differently, say $q_{0} ⊩ \dot{x} (i) = 0$ and $q_{1} ⊩ \dot{x} (i) = 1$ with $i \in ω$ , and let π be an automorphism of $P$ such that $π (q_{1})$ and $q_{0}$ are compatible. Let $G^{'}$ be a filter containing $q_{0}$ and $π (q_{1})$ . Then, as $q_{0}$ and $q_{1}$ strengthen p which forces that $\dot{x}$ is recognized by P in the parameter α, we have $q_{0} ⊩ {\overset{ˇ}{P}}^{\dot{x}} (\overset{ˇ}{α}) ↓ = 1$ , $π (q_{1}) ⊩ {\overset{ˇ}{P}}^{π (\dot{x})} (\overset{ˇ}{α}) ↓ = 1$ and $π (q_{1}) ⊩ π (\dot{x}) (π (i)) = π (1)$ , i.e. $π (q_{1}) ⊩ π (\dot{x}) (i) = 1$ . Hence in $M [G^{'}]$ , we have $x_{0} : = {\dot{x}}^{G^{'}} \neq π {(\dot{x})}^{G^{'}} = : x_{1}$ , but also both $P^{x_{0}} (α) ↓ = 1$ and $P^{x_{1}} (α) ↓ = 1$ . On the other hand, as $G^{'}$ contains p, P recognizes some real number in the parameter α, a contradiction. This shows that no real that is added by a weakly homogenous forcing is recognizable. □
Definition 3.15.
Let $L$ denote Laver forcing (see e.g. Definition 28.15 of [17]). Thus, $L$ consists of trees p of finite sequences of natural numbers with the properties that (i) there is a maximal element $t_{p} \in p$ , called the ‘stem’ of p, such that every $s \in p$ extends $t_{p}$ or is an initial segment thereof and (ii) every $t \in p$ that extends $t_{p}$ has infinitely many successors that are by exactly one element longer than t. The partial ordering on $L$ is just the subset relation.
Lemma 3.16.
Laver forcing is weakly homogenous.
Proof.
Suppose that p and q are conditions of Laver-forcing. We want to find Laver conditions $p^{'} ⩽ p$ , $q^{'} ⩽ q$ and an automorphism π of $P$ such that $π (p^{'}) = q^{'}$ . If the stems of p and q have different lengths, we can cut off branches from the condition with the shorter stem until the lengths are equal, which will strengthen this condition. We may thus assume without loss of generality that the stems of p and q are of equal length.

We now thin out p, q to $p^{'}, q^{'} \in L$ without changing the length of the stem such that for each $i \in ω$ , the ith levels of $p^{'}$ and $q^{'}$ have no common label and each label appears at most once. It is easy to see that, when $β : ω \to ω$ is bijective, then $π_{β}^{i} : L \to L$ that applies β to each label in the ith level of a tree, is an automorphism of $L$ . But now, by choosing appropriate $β_{i}$ for each $i \in ω$ and applying $π : = ⋃_{j \in ω} π_{β_{j}}^{j}$ , we have an automorphism of $L$ that maps $p^{'}$ to $q^{'}$ . Thus, we have $π (p) \supset π (p^{'}) = q^{'} \subseteq q$ , hence $q^{'}$ is a common strengthening of q and $π (p)$ , so that $π (p)$ and q are compatible. □
Theorem 3.17.
There is a generic extension $L [G]$ of L such that the generic reals form a comeager sets, yet none of them is parameter-OTM-recognizable.
Proof.
By [15], Laver forcing is minimal; hence, when x, y are generic, they are constructible in each other, i.e. $x \in L [y]$ and $y \in L [x]$ . As the parameter-OTM-computable reals in the oracle y are exactly the elements of $L [y]$ (see e.g. Lemma 17 of [11]), this means that all generics are parameter-OTM-computable, and hence in particular recognizable, from each other.

On the other hand, Laver forcing is weakly homogenous by Lemma 3.16.

Now let G be generic for Laver forcing over L and consider $L [G]$ . By Lemma 3.14, it follows that no real that is added through the forcing is recognizable. By Theorem 7.3.28 of [2], Laver forcing makes the set of ground model reals meager, so that the added elements form a comeager set. Any real in $L [G] ∖ L$ is hence recognizable relative to all other such reals, but not itself recognizable.

Therefore, the claim that parameter-OTM-recognizability from all elements of a comeager set of oracles implies parameter-OTM-recognizability fails in $L [G]$ . □

By Theorem 3.17 and the remark preceeding it, we get:
Corollary 3.18.
It is independent of ZFC whether parameter-OTM-recognizability from all elements of a comeager set of oracles implies parameter-OTM-recognizability.

Recognizability for α-register machines was considered briefly in [9], where it turned out that the existence of lost melodies depends on α. We do not know for which α the analogue of our statement holds.
4. The recognizable jump operator

A notion of computability is commonly accompanied by a corresponding jump operator; a jump operator can roughly be seen as the set of programs that compute something in the sense of the notion of computability in question. This motivates the introduction of a jump operator for recognizability. This jump operator will turn out to be strongly connected to $Σ_{1}$ -stability and is conceptually stable in the sense that the recognizable jumps for ITRMs and ITTMs, which are otherwise very different in strength, are primitive recursively equivalent.

In this section, we will, besides ITRMs and ITTMs, also consider Ordinal Turing Machines (OTMs), introduced in [20]. Unless stated otherwise, we will consider OTMs without ordinal parameters.

It is easy to see that the two variants of the jump operator given by (1) $x^{'} : = {i \in ω : \forall j \in ω P_{i}^{x} (j) ↓}$ and (2) $x^{'} : = {i \in ω : P^{x} (0) ↓}$ are equivalent for the models of computability discussed here (i.e. ITRMs, ITTMs, OTMs). Namely, to reduce (1) to (2), consider, given the index i, the program Q that, for any input in the first register, lets $P_{i}^{x} (j)$ run successively for all $j \in ω$ . Then $Q^{x} (0)$ halts if and only if $P_{i}^{x} (j)$ halts for every $j \in ω$ , and an index for Q is easily Turing-computable from i. To reduce (2) to (1), given index i, consider the program Q that, for any input in the first register, runs $P_{i}^{x} (0)$ . Then $P_{i}^{x} (0)$ halts if and only if $Q^{x} (j)$ halts for every $j \in ω$ . We can thus say that the jump operator for a model of infinitary computability sends a real x to the set of all indices $i \in ω$ such that $P_{i}^{x}$ computes a real number.

Analogously, we now define the ‘recognizable jump operator’, or r-jump, $x^{r}$ of a real to be the set of all indices $i \in ω$ such that $P_{i}^{x}$ recognizes a real:

Definition 4.1.
Let M be ITRM, ITTM or OTM, $x \subseteq ω$ . Fix a natural enumeration $(P_{i, M} : i \in ω)$ of the M-programs. Then $x_{M}^{r}$ , the r-jump of x (for M), is defined as ${i \in ω : \exists y \subseteq ω \forall z \subseteq ω P_{i, M}^{z \oplus x} ↓ = δ (z, y)}$ . We can iterate this operator by setting $r - x_{M}^{0} : = 0$ and $r - x_{M}^{i + 1} : = {(r - x_{M}^{i})}_{M}^{r}$ . Transfinite iterations are also possible as for the Turing jump, but will not be considered here. When M is clear from the context, we drop it.

Many of the following theorems hold for ITRMs, ITTMs and OTMs. To avoid repitions, we use an index M to denote, unless stated otherwise, ITRMs, ITTMs and OTMs for the rest of the section. Thus, $\equiv_{M}$ means computational equivalence in the sense of the model M.

We start by noting that the recognizable jump enjoys the appropriate amount of stability to be expected of a jump operator:
Proposition 4.2.
Let $x, y \subseteq ω$ such that $x \equiv_{M} y$ . Then $x_{M}^{r} \equiv_{M} y_{M}^{r}$ .
Proof.
We show that $x_{M}^{r} ⩽_{M} y_{M}^{r}$ , the other direction following by symmetry. So assume that $y_{M}^{r}$ is given in the oracle and we want to determine whether ${(P_{i}^{M})}^{x}$ recognizes a real number. Let Q be an M-program that computes $x_{M}^{r}$ from $y_{M}^{r}$ . From $P_{i}^{M}$ and Q, it is easy to obtain (primitive recursively, in fact) an M-program $Q_{i}^{'}$ that, given the oracle $z_{0} \oplus z_{1}$ , works by first applying Q to $z_{0}$ and then, after $Q^{z_{0}}$ halts (if it does) with output z, running ${(P_{i}^{M})}^{z \oplus z_{1}}$ . Now, $Q_{i}^{'}$ recognizes a real relative to y if and only if $P_{i}^{M}$ recognizes a real relative to x; but whether $Q_{i}^{'}$ recognizes a real number can simply be determined by using $y_{M}^{r}$ . □
Proposition 4.3.
$0_{M}^{r}$ is absolute between V and L for $M \in {ITRM, ITTM}$ .
Proof.
That a program P does not recognize a real number means that one of the following holds: (1) There is a real number x such that $P^{x} ↑$ . (2) There is a real number x such that $P^{x} ↓ \notin {0, 1}$ . (3) There is no real number x such that $P^{x} ↓ = 1$ . (4) There are different real numbers x, y such that $P^{x} ↓ = 1$ and $P^{y} ↓ = 1$ . So (2) and (4) are set-theoretical $Σ_{1}$ -statements and hence absolute between V and L. Concerning (3), if L contains a real number x such that $P^{x} ↓ = 1$ , then, by absoluteness of computations, so does V. On the other hand, if $V ⊧ \exists x P^{x} ↓ = 1$ , then, by Shoenfield absoluteness, $L ⊧ \exists x P^{x} ↓ = 1$ and by absoluteness of computations, L contains some y such that $P^{y} ↓ = 1$ . Finally, (1) is $Σ_{1}$ -expressible for ITRMs as ‘There is $y \subseteq ω$ such that $L_{ω_{ω}^{CK, y}} [y] ⊧ P^{y} ↑$ ’ and for ITTMs as ‘There is $y \subseteq ω$ such that $L_{λ^{y}} [y] ⊧ P^{y} ↑$ ’ together with Theorem 3.2. □

We observe that the computable jump of x reduces to the recognizable jump of x, so that the latter is not computable from x:
Proposition 4.4.
$x_{M}^{'} ⩽_{T} x_{M}^{r}$ (where $⩽_{T}$ denotes Turing reducibility).
Proof.
Let $i \in ω$ . To test, using $x_{M}^{r}$ , whether $P_{i}^{x} (0)$ halts, we compute from i a code for the program Q that does the following: First, Q runs $P^{x} (0)$ . Once $P^{x} (0)$ has stopped (if ever), Q checks whether $x = 0$ and returns 1 if $x = 0$ and otherwise 0. Clearly, Q recognizes a real (namely 0) if and only if $P^{x} (0)$ halts. And an index for Q is easily Turing-computable from i. □

A crucial property of the computable jump is that $x_{M}^{'}$ is not M-computable from x. The next goal is to show that the same holds for the r-jump.
Definition 4.5 (See [3]).

An ordinal α is 1-stable if and only if $L_{α} ≺_{Σ_{1}} L$ . α is $Σ_{1}$ -fixed if and only if there is some $Σ_{1}$ -statement ϕ such that α is minimal with the property that $L_{α} ⊧ ϕ$ . For $ι \in On$ , $σ_{ι}$ denotes the ιth 1-stable ordinal. The first 1-stable ordinal, $σ_{0}$ , is also denoted σ. This notation relativizes to real parameters in the obvious way.

Lemma 4.6.

σ is the supremum of the $Σ_{1}$ -fixed ordinals.

If α is 1-stable, then α is recursively inaccessible, i.e. an admissible limit of admissible ordinals.

$L_{σ}$ is the set of all x that are parameter-free $Σ_{1}$ -definable in L.

Proof.
See Corollary V.7.9 and Corollary V.7.6 of [3]. □
Lemma 4.7.
$σ = sup {α \in On : \exists x \in {RECOG}_{M} (x \notin L_{α} \land x \in L_{α + 1})}$ . In particular, we have ${RECOG}_{M} \subseteq L_{σ}$ .
Proof.
This is done in Theorem 27 of [7] for ITRMs, but the same argument works for ITTMs and parameter-free OTMs: If $x \subseteq ω$ is M-recognizable, then, by Shoenfield absoluteness, it is constructible. Now, if P recognizes x, then $\exists y P^{y} ↓ = 1$ is a $Σ_{1}$ -definition must become true for the first time in some $L_{α}$ with $α < σ$ , so that $x \in L_{σ}$ . On the other hand, if α is minimal such that $L_{α} ⊧ ϕ$ for some $Σ_{1}$ -statement ϕ, then $L_{α + 1}$ will contain a $<_{L}$ -minimal real coding $L_{α}$ which can be recognized as the $<_{L}$ -minimal code of an L-level in which ϕ holds. □

As one would expect, the recognizable jump of a real number x transcends recognizability relative to x:
Theorem 4.8.
Let $x \subseteq ω$ . Then $x_{M}^{r}$ is not M-recognizable relative to x.
Proof.
We prove this for $x = 0$ . The proof relativizes to arbitrary oracles.

By Lemma 4.7, it suffices to show that $0_{M}^{r} \notin L_{σ}$ . So assume otherwise for a contradiction. By Lemma 4.6 then, let ϕ be a $Σ_{1}$ -formula such that $0_{M}^{r}$ is unique with the property that $L ⊧ ϕ (0_{M}^{r})$ . Clearly, $0_{M}^{r}$ is an infinite set. Hence the function $f : ω \to ω$ sending i to the ith element of $0_{M}^{r}$ is total and definable in the parameter $0_{M}^{r}$ and hence also contained in $L_{σ}$ .

Now, let $g : ω \to σ$ be the function that sends $i \in ω$ to the smallest $α \in On$ such that $L_{α} ⊧ \exists x P_{f (i)}^{x} ↓ = 1$ . As $P_{f (i)}^{x} ↓ = 1$ is $Σ_{1}$ in the parameter $0_{M}^{r}$ , such an α is clearly $Σ_{1}$ -fixed and hence below σ by Lemma 4.6. Moreover, $L_{α}$ will contain the unique real x such that $P_{f (i)}^{x} ↓ = 1$ . Hence, the supremum of these α will be σ by Lemma 4.7. We show that g is $Σ_{1}$ -definable over $L_{σ}$ . This will be the desired contradiction, as g will then be a $Σ_{1}$ -definable total function mapping $ω < σ$ cofinally into σ, contradicting the fact that σ is admissible by Lemma 4.6. But $g (i) = α$ can be written as $\exists x, y, j [(ϕ (x) \land j \in x \land | x \cap j | = i) \land (y = L_{α} \land y ⊧ (\exists z P_{j}^{z} ↓ = 1) \land y ⊧ (\forall γ \in α (L_{γ} ⊭ (\exists z P_{j}^{z} ↓ = 1))))]$ (where the first conjunct says that j is the ith element of $0_{M}^{r}$ while the second expresses that α is minimal with the property that $L_{α}$ believes in the existence of some real z with $P_{f (i)}^{z} ↓ = 1$ ), which is $Σ_{1}$ . □

We can also show the unrecognizability of the recognizable jump more directly by a diagonalization argument that works rather generally for models of computation that allow universal programs (which includes ITTMs, OTMs, OTMs with a fixed parameter α, etc. but not ITRMs):
Theorem 4.9.
The recognizable jump $0^{r}$ is not recognizable.
Proof.
Assume otherwise, so that $0^{r} \in RECOG$ . Let $(P_{i} : i \in ω)$ enumerate the programs. Denote by $j_{i}$ the ith element of $0^{r}$ for $i \in ω$ (so $j_{i}$ is the index of the ith recognizing program) and by $x_{i}$ the real recognized by $P_{j_{i}}$ . We note that $x : = ⨁_{i \in ω} x_{i}$ is recognizable relative to $0^{r}$ by observing that the following procedure recognizes x relative to $0^{r}$ : Given $y = ⨁_{i \in ω} y_{i}$ in the oracle, we perform the following for every $i \in ω$ : First, we find $j_{i}$ using $0^{r}$ . Then, we run $P_{j_{i}}^{y_{i}}$ . As $j_{i} \in 0^{r}$ , $P_{j_{i}}^{y_{i}}$ must stop with output 0 or 1. If the output is 0, then $y \neq x$ and we stop with output 0; otherwise, we continue. When we have run through all $i \in ω$ in this way, then $x = y$ .

It follows that $z : = x \oplus 0^{r}$ is recognizable (the second component $0^{r}$ is recognizable by assumption, the first then relative to the second by the above). We will now construct a nonrecognizable real $\bar{z}$ from z by diagonalizing against $(x_{i} : i \in ω)$ ; as $\bar{z}$ will be seen to be recognizable if z is, this will be a contradiction.

Let $p : ω \times ω \to ω$ denote Cantor’s pairing function. The 0th bit of $x_{i}$ is represented by the $2 p (i, 0)$ th bit of z. We now define $\bar{z}$ by letting $\bar{z} (2 p (i, 0)) : = 1 - z (2 p (i, 0))$ if $x_{i} (0) = x_{i} (2 p (i, 0))$ and $\bar{z} (j) = z (j)$ otherwise. Note that the so constructed $\bar{z}$ will hence differ from $x_{i}$ in the $2 p (i, 0)$ th bit for all $i \in ω$ : If $x_{i} (0) \neq x_{i} (2 p (i, 0))$ , then $\bar{z} (2 p (i, 0)) = x_{i} (0) \neq x_{i} (2 p (i, 0)) = z_{i} (2 p (i, 0)) = \bar{z} (2 p (i, 0))$ , and if $x_{i} (0) = x_{i} (2 p (i, 0))$ , then $\bar{z} (2 p (i, 0)) = x_{i} (0) = x_{i} (2 p (i, 0)) = z_{i} (2 p (i, 0)) \neq 1 - z_{i} (2 p (i, 0)) = \bar{z} (2 p (i, 0))$ . As each recognizable real is among the $x_{i}$ and $\bar{z}$ is different from all the $x_{i}$ , $\bar{z}$ cannot be recognizable.

On the other hand, given that $0^{r}$ is recognizable, the following procedure recognizes $\bar{z}$ : Given $y = y_{1} \oplus y_{2}$ in the oracle, first check whether $y_{2} = 0^{r}$ . If not, then $y \neq \bar{z}$ . Otherwise, let $y_{1} = ⨁_{i \in ω} y_{1, i}$ and run the following procedure for each $i \in ω$ : First, check whether $y_{1, i} (0) = y_{1, i} (2 p (i, 0))$ . If yes, then $y \neq \bar{z}$ . Otherwise, let ${\tilde{y}}_{1, i} (0) = 1 - y_{1, i} (0)$ and ${\tilde{y}}_{1, i} (j) = y_{1, i} (j)$ for $j > 0$ and check whether $P_{j_{i}}^{y_{1, i}} ↓ = 1$ or $P_{j_{i}}^{{\tilde{y}}_{1, i}} ↓ = 1$ . If not, then $y \neq \bar{z}$ . If, on the other hand, we have run through all natural numbers in this manner, then $y = \bar{z}$ .

So it follows that $\bar{z}$ is both recognizable and unrecognizable, a contradiction. Thus $0^{r}$ is not recognizable. □

Iterating the argument for Theorem 4.8, we get:
Corollary 4.10.
For $i \in ω$ and $M \in {ITRM, ITTM}$ , we have $r - 0_{M}^{i} \in L_{σ_{i + 1}} ∖ L_{σ_{i}}$ . In particular, $r - 0_{M}^{i}$ is not M-recognizable from $r - 0_{M}^{i - 1}$ for $i > 0$ .
Proof.
We adapt the proof of Theorem 4.8. As there, we can see that $r - 0_{M}^{k} \notin L_{σ_{k}}$ , using that, by Corollary 7.9 of [3], $L_{σ_{j + 1}}$ consists of those elements of L that are definable by ordinal parameters $⩽ σ_{j}$ for all $j \in ω$ . If we had $r - 0_{M}^{k} \in L_{σ_{k}}$ , the function g sending each $i \in ω$ to the smallest ordinal $α_{i}$ such that $L_{α_{i}}$ contains some computation of $P_{f (i)}^{x \oplus r - 0_{M}^{k}}$ that converges to 1, where $x \subseteq ω$ and $f (i)$ denotes the ith element of $r - 0_{M}^{k}$ would be $Σ_{1}$ -definable over $L_{σ_{k}}$ and cofinal in $σ_{k}$ , so that $σ_{k}$ could not be admissible, contradicting Corollary 7.6 of [3].

To see that $r - 0_{M}^{i} \in L_{σ_{i + 1}}$ , we proceed inductively, using the assumption $r - 0_{M}^{i - 1} \in L_{σ_{i}}$ (for $i > 0$ ) to show that $r - 0_{M}^{i}$ is definable over $L_{σ_{i}}$ and hence contained in $L_{σ_{i + 1}}$ . Claim.
For every $j \in ω$ , the program $P_{j}$ recognizes a real number relative to $r - 0_{M}^{i - 1}$ if and only if $L_{σ_{i}}$ believes that it does.
Proof.
For ITRMs and ITTMs, the property that $P^{x} ↑$ is $Σ_{1}$ -expressable in the parameter x by stating that $P^{x}$ does not halt in $ω_{ω}^{CK, x}$ many steps or (by Theorem 3.2) that there is a minimal triple $(α, β, γ)$ with $L_{α} [x] ≺_{Σ_{1}} L_{β} [x] ≺_{Σ_{2}} L_{γ} [x]$ and $P^{x}$ does not halt in α many steps, respectively. Hence $\exists x P^{x \oplus r - 0_{M}^{i - 1}} ↑$ is $Σ_{1}$ in the parameter $r - 0_{M}^{i - 1}$ and thus absolute between $L_{σ_{i}}$ and the real world for every P. Thus, if there was some real number x for which $P^{x \oplus r - 0_{M}^{i - 1}}$ did not halt, such an x would be contained in $L_{σ}$ . Hence, the statement ‘For every real x, $P^{x \oplus r - 0_{M}^{i - 1}}$ halts’ is absolute for $L_{σ_{i}}$ . Similarly, we get the absoluteness of $ϕ_{0} (P) : = ‘For every x, P^{x \oplus r - 0_{M}^{i - 1}} halts with output 0 or 1 ’$ for $L_{σ_{i}}$ . The statement $ϕ_{1} (P) : = \exists x P^{x \oplus r - 0_{M}^{i - 1}} ↓ = 1$ is $Σ_{1}$ in $r - 0_{M}^{i - 1}$ and thus absolute between $L_{σ_{i}}$ and L by the stability of $σ_{i}$ , and by the recursive inaccessibility of $σ_{i}$ and Theorem 3.9 also between L and V. Finally, $ϕ_{2} (P) : = \exists x, y (x \neq y \land P^{x \oplus r - 0_{M}^{i - 1}} ↓ = 1 \land P^{y \oplus r - 0_{M}^{i - 1}} ↓ = 1)$ is also $Σ_{1}$ in $r - 0_{M}^{i - 1}$ and hence absolute for $L_{σ_{i}}$ for the same reason. Hence the statement ‘P recognizes some real number from $r - 0_{M}^{i - 1}$ ’ is equivalent with $ϕ_{0} (P) \land ϕ_{1} (P) \land \neg ϕ_{2} (P)$ and therefore absolute for $L_{σ_{i}}$ , as desired. Thus $k \in r - 0_{M}^{i}$ if and only if $L_{σ_{i}} ⊧ k \in r - 0_{M}^{i}$ for all $k \in ω$ . □

By the claim, $r - 0_{M}^{i}$ is definable over $L_{σ_{i}}$ as the set ${k \in ω : ϕ_{0} (P_{k}) \land ϕ_{1} (P_{k}) \land \neg ϕ_{2} (P_{k})}$ . Hence $r - 0_{M}^{i} \in L_{σ_{i + 1}}$ . □
Remark.
For parameter-free OTMs, we have no $Σ_{1}$ -definable bound on the halting times so that $P^{x} ↑$ might fail to be $Σ_{1}$ -expressible; hence the argument does not work in this case. Clearly, $0_{OTM}^{r}$ is constructible when $V = L$ , but we currently do not even know whether the constructibility of $0_{OTM}^{r}$ follows from ZFC alone.
Proposition 4.11.
$0_{ITRM}^{r} ⩽_{T} 0_{ITTM}^{r} ⩽_{T} 0_{OTM}^{r}$ .
Proof.
It is easy to see that ITRM-programs can be simulated by ITTM-programs and ITTM-programs can be simulated by OTM-programs and there are recursive maps f, g sending each ITRM-program P to an ITTM-program $P^{'}$ with the same behaviour for all oracles and each ITTM-program Q to an OTM-program $\hat{Q}$ with the same behaviour for all oracles, respectively. □

The following results concern the strength of the recognizable jump operator.

We have shown above how to retrieve the halting information from $0^{(r)}$ for ITRMs. This can in fact be iterated:
Theorem 4.12.
From $0_{ITRM}^{r}$ and $i \in ω$ , we can Turing-compute $0_{ITRM}^{(i)}$ (i.e. the ith iterated halting problem) for ITRMs.
Proof.
Recall that when x is ITRM-recognizable, then so is $x^{'}$ (see Corollary 35 of [6]) and hence so are all finite iterations of the jump of x. Suppose we want to compute $0_{ITRM}^{(i + 1)}$ from $0^{(r)}$ . Let P be an ITRM-program recognizing $0^{(i)}$ . Then, using P, it is easy to find (effectively) for every $j \in ω$ an ITRM-program $Q_{j}$ such that $Q_{j}^{x} ↓ = 1$ if and only if x is the $<_{L}$ -minimal code of a halting computation of $P_{j}^{0_{ITRM}^{(i)}}$ . In fact, an index $f (j)$ for $Q_{j}$ can be obtained primitive recursively from j. Now $Q_{j}$ will recognize a real number if and only if $P_{j}^{0^{(i)}}$ halts, i.e. $f (j) \in 0^{(r)}$ if and only if $j \in 0^{(i + 1)}$ . Hence $0_{ITRM}^{(i + 1)}$ can be obtained by a Turing-computation from $0_{ITRM}^{(r)}$ . □

We note here the somewhat curious fact that there are ITRM-unrecognizable real numbers x between 0 and $0_{ITRM}^{'}$ such that their ITRM-jump $x_{ITRM}^{'}$ is recognizable:
Lemma 4.13.
There is an ITRM-unrecognizable real x such that $x^{'}$ is recognizable. In fact, x can be taken to be strictly below $0_{ITRM}^{'}$ .
Proof.
Trivially, we have $0_{ITRM}^{'} ⩽_{ITRM} x_{ITRM}^{'}$ for any x.

Let x be Cohen-generic over $L_{ω_{ω}^{CK}}$ and ITRM-computable from $0_{ITRM}^{'}$ . It follows from Lemma 29 of [6] that such an x exists. From Theorem 16 of the same paper, it follows that $x <_{ITRM} 0_{ITRM}^{'}$ . Clearly, $x \notin L_{ω_{ω}^{CK}}$ , so x is not ITRM-computable.

We also have that $ω_{ω}^{CK, x} = ω_{ω}^{CK}$ . Now if $i \in ω$ and $P_{i}$ is the ith ITRM-program using n registers, then $P_{i}^{x}$ stops if and only if there is a forcing condition p such that $p ⊩ P_{i}^{\overset{ˇ}{x}} ↓$ over $L_{ω_{n + 1}^{CK}}$ . But from $0_{ITRM}^{'}$ , we can compute a code for $L_{ω_{n + 1}^{CK}}$ , which suffices both to evaluate the statement that a condition p forces a certain statement over $L_{ω_{n + 1}^{CK}}$ , and to exhaustively search for such a condition. If none is found, then $P_{i}^{x}$ will not halt, otherwise it will. This hence allows us to solve the halting problem relative to x in the oracle $0_{ITRM}^{'}$ , so that $x_{ITRM}^{'} ⩽_{ITRM} 0_{ITRM}^{'}$ . Hence $x_{ITRM}^{'} \equiv_{ITRM} 0_{ITRM}^{'}$ .

As $0_{ITRM}^{'}$ is ITRM-recognizable by Section 4 of [5], it follows from Proposition 2.7 that $x_{ITRM}^{'}$ is also ITRM-recognizable, so x is as desired. □

With a similar idea to that of the proof of Lemma 4.13, we also get the following, stronger statement that the jump of every real ITRM-computable from, but not ITRM-equivalent to $0_{ITRM}^{'}$ is ‘ITRM-low’, i.e. has its jump equivalent to $0_{ITRM}^{'}$ :
Corollary 4.14.
Let $x <_{ITRM} 0_{ITRM}^{'}$ . Then $x_{ITRM}^{'} \equiv_{ITRM} 0_{ITRM}^{'}$ .
Proof.
We claim that, for $x <_{ITRM} 0_{ITRM}^{'}$ , we have $ω_{ω}^{CK, x} = ω_{ω}^{CK}$ : Clearly, $ω_{ω}^{CK, x} ⩾ ω_{ω}^{CK}$ . Suppose the inequality was strict. As already $L_{ω_{ω}^{CK + 1}}$ contains a real c coding $L_{ω_{ω}^{CK}}$ by a standard fine-structural argument, such a code is then also contained in $L_{ω_{ω}^{CK, x}} [x]$ and thus ITRM-computable from x. But, as ITRM-programs in the empty oracle either halt inside $L_{ω_{ω}^{CK}}$ or do not halt at all, we can compute $0_{ITRM}^{'}$ by evaluating truth-predicates for first-order formulas in $L_{ω_{ω}^{CK}}$ , which can be done uniformly by an ITRM in the oracle c. Hence $0_{ITRM}^{'} ⩽_{ITRM} c ⩽ x$ , which contradicts the assumption that x lies strictly below $0_{ITRM}^{'}$ .

We can now argue as in the proof of Lemma 4.13 to see that $x_{ITRM}^{'} ⩽_{ITRM} 0_{ITRM}^{'}$ : To compute $x^{'}$ from $0_{ITRM}^{'}$ , first compute x from $0_{ITRM}^{'}$ , which is possible by assumption. Therefore, we have $x \in L_{ω_{ω}^{CK, 0_{ITRM}^{'}}} [0_{ITRM}^{'}]$ and as $ω_{ω}^{CK, 0_{ITRM}^{'}} > ω_{ω}^{CK}$ , it follows that $L_{ω_{ω}^{CK, 0_{ITRM}^{'}}} [0_{ITRM}^{'}]$ contains a code $\bar{c}$ for $L_{ω_{ω}^{CK}} [x] = L_{ω_{ω}^{CK, x}} [x]$ . Hence such a code is ITRM-computable from $0_{ITRM}^{'}$ . As above, $c^{'}$ can then be used to solve the halting problem relative to x, so $x_{ITRM}^{'} ⩽_{ITRM} \bar{c} ⩽_{ITRM} 0_{ITRM}^{'}$ , as desired. □
Remark.
Shoenfield’s jump inversion theorem implies that, for Turing machines, there is some $c <_{T} 0^{'}$ such that $c^{'} = 0^{″}$ . Corollary 4.14 shows that this is impossible for ITRMs.

We now characterize the computational strength of the recognizable jump.
Definition 4.15.
For $N ⊧ ZFC$ , let $T^{N}$ denote the set of parameter-free $Σ_{1}$ -statements that hold in N.

Note that $T$ is absolute between transitive models of ZFC by Shoenfield’s absoluteness theorem; as we are only interested in transitive models here, we can simply write $T$ . In particular, we have $T = T^{L}$ .
Theorem 4.16.
Let $0^{(r)}$ denote the recognizable jump for any of ITRMs, ITTMs and parameter-free OTMs. Then $T ⩽_{T} 0^{(r)}$ , i.e. the parameter-free $Σ_{1}$ -theory of L (and hence of V) $T$ is Turing-reducible to the recognizable jump.
Proof.
Let $(ϕ_{i} : i \in ω)$ enumerate the set-theoretical $Σ_{1}$ -statements without free variables in some natural way. Let $i \in ω$ be arbitrary and assume that $L ⊧ ϕ_{i}$ . Then there is a minimal $α \in On$ such that $L_{α} ⊧ ϕ_{i}$ . By an easy condensation argument, we have $α < ω_{1}^{L}$ . Hence, there is some $<_{L}$ -minimal real $r_{i}$ coding $L_{α}$ .

Now, given $i \in ω$ , it is easy to write a program $C_{i}$ that checks whether its oracle y is a $<_{L}$ -minimal code for an L-structure $L_{α}$ such that $L_{α} ⊧ ϕ_{i}$ : In fact, $C_{i}$ can be obtained from i primitive recursively. Let $c (i)$ denote the index of $C_{i}$ in the enumeration $(P_{i} : i \in ω)$ of programs.

But if $ϕ_{i}$ holds, then there is a unique oracle x such that $C_{i}^{x} ↓ = 1$ , namely $x = r_{i}$ . If, on the other hand $ϕ_{i}$ is false, then there is no such oracle. Hence $C_{i}$ recognizes a real number if and only if $ϕ_{i}$ holds, i.e. $ϕ_{i}$ holds if and only if $c (i) \in 0^{(r)}$ . As $c (i)$ is primitive recursive in i, we can Turing-compute $Σ_{1}$ -truth from $0^{(r)}$ . □

For ITTMs and ITRMs, we also get the converse. This can be seen as the recognizable counterpart of a theorem of Welch (see Corollary 1 of [34]) showing that the (computational) ITTM-jump of a real x corresponds to a Master code for $L_{λ^{x}} [x]$ , i.e. a $Σ_{1}$ -truth predicate for that structure:
Theorem 4.17.
Let $0^{(r)}$ denote the recognizable jump for ITRMs or ITTMs. Then $0^{(r)} ⩽_{T} T$ , i.e. the recognizable jump of 0 for ITRMs and ITTMs is Turing-reducible (and hence, by Theorem 4.16 , Turing-equivalent) to the parameter-free $Σ_{1}$ -theory of L.
Proof.
We start by noting that, for P an ITRM- or an ITTM-program, the following statements are $Σ_{1}$ :
There is some $x \subseteq ω$ such that $P^{x} ↓ = 1$ .

There is some $x \subseteq ω$ such that $P^{x} ↑$ or $P^{x} ↓ \notin {0, 1}$ .

There are $x, y \subseteq ω$ such that $x \neq y$ and $P^{x} ↓ = 1$ and $P^{y} ↓ = 1$ .
This is straightforward for (1), which can be expressed as ‘There is $x \subseteq ω$ and a P-computation in the oracle x that contains a halting state with 1 written in the first register/on the first tape cell’, and similarly for (3) and the claim that there is x such that $P^{x} ↓ \notin {0, 1}$ . The only complication arises with the statement that $P^{x}$ diverges for some x. We treat the ITRM- and the ITTM-case separately:

For ITRMs, $P^{x} ↑$ means, by Theorem 2.2, that $L_{ω_{ω}^{CK, x}} [x] ⊧ P^{x} ↑$ , which can be expressed as ‘There are a set y and an ordinal α such that $y = L_{α} [x]$ , y contains infinitely many x-admissible ordinals and $y ⊧ P^{x} ↑$ ’. As ‘ $y = L_{α} [x]$ ’ is $Σ_{1}$ in x and α, this is a $Σ_{1}$ -statement.

For ITTMs, $P^{x} ↑$ means, by definition of $λ^{x}$ , that $L_{λ^{x}} [x] ⊧ P^{x} ↑$ ; this can, by [33], be expressed as ‘There are sets a, b, c and ordinals α, β, γ such that $a = L_{α} [x]$ , $b = L_{β} [x]$ and $c = L_{γ} [x]$ , $a ≺_{Σ_{1}} b$ , $b ≺_{Σ_{2}} c$ and $a ⊧ P^{x} ↑$ ’, which again is $Σ_{1}$ .

Now, it is easy to see that the statements $ϕ_{1}^{P, ITRM}$ , $ϕ_{2}^{P, ITRM}$ , $ϕ_{3}^{P, ITRM}$ and $ϕ_{1}^{P, ITTM}$ , $ϕ_{2}^{P, ITTM}$ , $ϕ_{3}^{P, ITTM}$ expressing (1)–(3) for ITRMs and ITTMs in $Σ_{1}$ -form, respectively, can be obtained primitive recursively from P. Note that, as parameter-free $Σ_{1}$ -statements, all of these statements are absolute between V and L by Shoenfield absoluteness. Hence P is recognizing if and only if $ϕ_{1}^{P}$ holds and $ϕ_{2}^{P}$ , $ϕ_{3}^{P}$ are false (for the machine type in question), which, by absoluteness, holds if and only if the hold in L, which in turn can be checked by using the (oracle coding the) parameter-free $Σ_{1}$ -theory of L. □
Remark.
This does not work for OTMs since there is no bound on the halting time of an OTM in the oracle x that is $Σ_{1}$ -definable in the oracle x, so that $\exists x P^{x} ↑$ is not $Σ_{1}$ -expressible. It is in fact easy to see that it is not: For there is a parameter-free OTM that, given a parameter-free $Σ_{1}$ -statement ϕ, halts if and only if ϕ holds: P works simply by writing L on the tape and checking at each level whether ϕ holds in it. Also, the statement that an OTM-program Q halts is clearly $Σ_{1}$ -expressible. If the divergence of Q was $Σ_{1}$ -expressible as well, OTMs could solve their own halting problem, which they clearly cannot. At this moment, we do not know of a characterization of the recognizable OTM-jump in the spirit of Theorem 4.17.

The concept of relativized recognizability makes it tempting to define ‘degrees of recognizability’. This, however, is hindered by the observation made in [7] that relativized recognizability is not transitive. There are two ways around this: One can either give up on having degrees and merely study the reducibility relation on single real numbers, or one can replace relativized recognizability with its transitive closure to make it an equivalence relation. We shall take the second route here.
Definition 4.18.
We let $x ⪯_{M} y$ if and only if there is a finite sequence $x = z_{0}, z_{1}, \dots, z_{n} = y$ such that $z_{i} ⩽_{M}^{r} z_{i + 1}$ for $i \in {0, \dots, n - 1}$ . If $x ⪯_{M} y$ , we say that x is heriditarily M-recognizable from y.
Remark.
In fact, the reduction turns out to be much simpler: A two-step iteration suffices to give the whole transitive closure. Even more: It is not hard to show (see e.g. [12]) that $x ⪯_{M} y$ if and only if there is z such that $z ⩽_{M}^{r} y$ and x is primitive recursive in z (and less).
Definition 4.19.
x and y are called M-recognizably equivalent, written $x ≍_{M} y$ if and only if $x ⪯_{M} y$ and $y ⪯_{M} x$ . It is easy to see that M-recognizable equivalence is indeed an equivalence relation. ${[x]}_{M}^{r}$ will denote the $≍_{M}$ -equivalence class of x, called M-recognizability degree of x.

We can now formulate and solve a recognizable analogue for Post’s problem. For convenience, we write $α_{M}$ where $α_{ITRM}^{x} = ω_{ω}^{CK, x}$ , $α_{ITTM}^{x} = λ^{x}$ and $α_{OTM} = σ^{x}$ for $x \subseteq ω$ . We call $α_{M}^{x}$ the M-characteristic ordinal for x.
Theorem 4.20.
For $M \in {ITRM, ITTM}$ , there is x such that ${[0]}_{M}^{r} ≺_{M} {[x]}_{M}^{r} ≺_{M} {[0_{M}^{r}]}_{M}^{r}$ .
Proof.
Let x be the $<_{L}$ -minimal Cohen-generic real over $L_{σ + 1}$ . We claim that $x \notin {[0]}_{M}^{r}$ : For if it was, then x would, by our remark above, be recursive in a recognizable real, but all recognizable real numbers and all real numbers recursive in recognizable real numbers are contained in $L_{σ}$ , which x clearly is not.

Second, we need to see that $0_{M}^{r} \notin {[x]}_{M}^{r}$ . We claim that $α_{M}^{0_{M}^{r}} > σ = σ^{x} ⩾ α_{M}^{y}$ for every $y \in {[x]}_{M}^{r}$ , which suffices.

For the first inequality, note that a real number coding a well-ordering of order-type σ is M-computable from $0_{M}^{r}$ . To see this, first split ω into ω many disjoint infinite portions ${(A_{i})}_{i \in ω}$ in some effective way and declare any element of $A_{i}$ to be smaller than any element of $A_{j}$ for $i < j$ . The $A_{i}$ are then ordered as follows: Using $0_{M}^{r}$ , search for the ith M-program Q such that Q recognizes a code for a well-ordering. ‘There is some x that codes a well-ordering such that $Q^{x} ↓ = 1$ ’ is a $Σ_{1}$ -statement whose truth value can be evaluated using $0_{M}^{r}$ by Theorem 4.16. By the same argument, every bit of the real number $c_{Q}$ recognized by Q can be computed from $0_{M}^{r}$ . Now order $A_{i}$ in the way coded by $c_{Q}$ . The resulting real number will code a well-ordering whose order-type is the ordinal sum of all ordinals with a recognizable code, which is σ.

That $σ^{x} = σ$ follows from the genericity of x: Let P be an OTM-program such that $P^{x}$ halts in α many steps. By the forcing theorem for admissible sets (see e.g. Lemma 32 of [11]), there is a condition $p \subseteq x$ such that $p ⊩$ ‘ $P^{x}$ halts in α many steps’. Hence $L ⊧ \exists α (p ⊩ ‘ P^{x} halts in α many steps’)$ , which is a $Σ_{1}$ -statement and hence must become true already in $L_{σ}$ . Thus, we must have $α < σ$ and σ is the supremum of OTM-halting times in the oracle x, so $σ^{x} = σ$ .

For the second inequality, suppose z is such that $z ⩽_{M}^{r} x$ and y is primitive recursive in z. Clearly, we must have $α_{M}^{y} ⩽ α_{M}^{z}$ , so it suffices to see that $α_{M}^{z} ⩽ σ$ . Let P be a program that recognizes z relative to x. Then $\exists a P^{a \oplus x} ↓ = 1$ is a $Σ_{1}$ -statement in the parameter x which, for $x \in L$ , is absolute between V and L by Shoenfield absoluteness and moreover, by definition of $σ^{x}$ , either becomes true in some $L_{α} [x]$ with $α < σ^{x}$ or is false. As it is true by assumption, we must have $z \in L_{σ^{x}} [x] = L_{σ} [x]$ . Now let Q be an M-program such that $Q^{z}$ halts. Then $\exists a \exists α [P^{a \oplus x} ↓ = 1 \land {(P^{a} ↓)}^{L_{α} [a]}]$ is again a $Σ_{1}$ -statement in the parameter x, which is true by assumption and must hence hold in some $L_{β} [a]$ with $β < σ^{x}$ . Hence the halting times of M-programs in the oracle z are indeed majorized by $σ^{x} = σ$ , as desired.

Finally, we show that $x ⩽_{M}^{r} 0_{M}^{r}$ . This, together with the preceeding, shows that the strict inequality holds for such an x and hence that x is as desired. But as we saw above that $σ < α_{M}^{0_{M}^{r}}$ , we have $L_{σ + ω} \subseteq L_{α_{M}^{0_{M}^{r}}} [0_{M}^{r}]$ . Now, the $Σ_{1}$ -Skolem hull of ∅ in $L_{σ}$ will be an L-level reflecting every $Σ_{1}$ -statement that holds in $L_{σ}$ and hence, by definition of σ, be isomorphic to $L_{σ}$ . Thus, a surjection of ω onto $L_{σ}$ is definable over $L_{σ}$ and hence $L_{σ + 1}$ is countable in $L_{σ + 2}$ . Thus, a real number y that is Cohen-generic over $L_{σ + 1}$ is contained in $L_{σ + 3} \subseteq L_{α_{M}^{0_{M}^{r}}} [0_{M}^{r}]$ , so the $<_{L}$ -smallest such y is in particular M-computable from $0_{M}^{r}$ and hence M-recognizable from $0_{M}^{r}$ . □

We conclude by observing that the structure of M-recognizability degrees turns out to depend heavily on the set-theoretical background:
Theorem 4.21.
Let $M \in {ITRM, ITTM, OTM}$ . Assume that $V = L$ . Then the M-recognizability degrees are linearly ordered by the ordering induced by the canonical well-ordering $<_{L}$ of L.
Proof.
Relative to $x \subseteq$ , we can recognize the $<_{L}$ -minimal code of the minimal L-level $L_{α_{x}}$ containing x. From a code for $L_{α_{x}}$ , every real $z \in L_{α_{x}}$ is computable and hence recognizable. Hence every real in $L_{α_{x}}$ is heriditarily recognizable from x.

Now, for any $x, y \in L$ , we have either $α_{x} ⩽ α_{y}$ or $α_{x} > α_{y}$ , i.e. $x \in L_{α_{y}}$ or $y \in L_{α_{x}}$ . Hence one of them is heriditarily M-recognizable from the other. Moreover, if $x ⩽_{L} y$ , then $α_{x} ⩽ α_{y}$ , so x is heriditarily M-recognizable from y. □

On the other hand:
Proposition 4.22.
Let $M \in {ITRM, ITTM, OTM}$ . If x, y are mutually Cohen-generic over L, then neither $x ⪯_{M} y$ nor $y ⪯_{M} x$ .
Proof.
Assume for a contradiction that $x ⪯_{M} y$ . Let P be a program that recognizes a real z relative to y such that x is primitive recursive in x which exists by the remark following Theorem 4.18. Then x is $Σ_{1}$ -definable from y and hence, by Shoenfield absoluteness, we get $x \in L [y]$ , which contradicts the assumption that x is Cohen-generic over $L [y]$ . □

Consequently, the existence of $⪯_{M}$ -incomparable M-degrees of recognizability is independent of ZFC for $M \in {ITRM, ITTM, OTM}$ . The study of the structure of the degrees of recognizability will hence need to work under set-theoretical extra assumptions to obtain substantial results.
5. Conclusion and further work

It is natural to ask what happens when we replace the condition of non-meagerness by the condition of positive Lebesgue measure in results like Theorems 2.10 or 3.12. Hence, we ask:

Question.

Suppose that $Y \subseteq [0, 1]$ is a set of positive Lebesgue measure, and let $x \subseteq ω$ be such that x is ITRM-recognizable (uniformly or not) relative to every $y \in Y$ . Does it follow that x is ITRM-recognizable?

Question.

Same question for ITTM-recognizability instead of ITRM-recognizability.

This and other related topics can be dealt with using random forcing over models of $KP$ , which will be treated in future work with Philipp Schlicht.

Another possible topic to pursue is relativized recognizability for α-Turing machines and α-register machines, both of the resetting and the unresetting type. Introductions to and various results about computational strength, computability from random oracles as well as on recognizability for these machines can be found in [9,24,28] and [11]. In particular, we ask:

Question.

For which α is it true that the recognizability by an α-Turing machine or an α-register machine of a real number x relative to all elements of a set Y of real numbers that is ‘large’ (e.g. in the sense of being comeager or of Lebesgue measure 1)?

Question.

What is the strength of the recognizable jump of 0 for α-Turing machines and α-register machines? What does the recognizable degree structure for such machines look like?

Question.

Characterize the recognizable jump of 0 for Ordinal Turing Machines without parameters, possibly analogous to Theorem 4.17. In particular, is it provable in ZFC that $0_{OTM}^{r}$ is constructible?

Footnotes

Acknowledgements

We thank Philipp Schlicht for a discussion on Corollary 2.12 (and the remark following it) as well as various helpful comments on the presentation of the proof of Theorem 2.10 and discussions during which Lemma 3.14 and Theorem were suggested, along with parts of their proofs. We also thank the two anonymous referees for suggesting various improvements on our presentation.

The relativized Jensen–Karp-theorem

In this section, we prove a relativization and a slight strengthening of the Jensen–Karp theorem (see Section 5 of [18]). The theorem says that, when ϕ is a $Σ_{1}$ -statement with real parameters in $L_{α}$ and α is a limit of admissible ordinals, then $V_{α} ⊧ ϕ$ if and only if $L_{α} ⊧ ϕ$ . In the proof of our theorem concerning ITTMs above, we made use of the following relativization:

Moreover, we have the following strengthening:

Both theorems can be combined in the obvious way. The proofs work very much along the lines of Jensen’s and Karp’s proof of the second theorem in Section 5 of [18]; it is for the sake of completeness that we give the details of the proof of Theorem A.1 here.

The central tool in both proofs is the following variant of Jensen’s and Karp’s ‘Main Lemma’ (for the definition of ‘prim’, see [18]):

As admissible sets are closed under primitive recursive set functions in parameters contained in the set, we get that such a set $t^{'}$ is contained in $L_{α_{x}^{+ +}} [x]$ , where $β_{x}^{+}$ denotes the smallest x-admissible ordinal $> β$ . Now, if ϕ is $\exists v ψ (v, x)$ with $ψ \in Δ_{0}$ and $y \in t^{'}$ is such that $t^{'} ⊧ ψ (y, x)$ , then we have $y \in L_{α_{x}^{+ +}} [x]$ . By transitivity of $t^{'}$ , the $Δ_{0}$ -formula ψ is absolute between $t^{'}$ and $L_{α_{x}^{+ +}} [x]$ , so $L_{α_{x}^{+ +}} [x] ⊧ ψ (y, x)$ and hence $L_{α_{x}^{+ +}} [x] ⊧ ϕ (x)$ . Then, of course, we also have $L_{α_{x}^{+ ω}} [x] ⊧ ϕ (x)$ , where $β_{x}^{+ ω}$ denotes the first limit of x-admissibles $> β$ , so Theorems A.1 and A.2 easily follow.

We proceed with the proof of Lemma A.4. The general strategy is to effectively build a theory $T ∋ ϕ$ such that the canonical Henkin model of $T$ is a well-founded extensional ∈-structure M and then take $t^{'}$ to be the transitive collapse of M. The main technical difficulty is hence to construct the theory $T$ .

References

Barmpalias and

Lewis-Pye, The information content of typical reals, in: Turing’s Ideas – Their Significance and Impact,

Sommaruga and

Strahm, eds, Springer, Basel, 2014.

Bartoszynski and

Judah, Set Theory: On the Structure of the Real Line A, K. Peters Ltd, 1995.

Barwise, Admissible Sets and Structures, Springer, Heidelberg, 1975. doi:10.1007/978-3-662-11035-5.

Boolos and

Putnam, Degrees of unsolvability of constructible sets of integers, J. Symb. Logic 33 (1968), 497–513. doi:10.2307/2271357.

Carl, Optimal results on recognizability by infinite time register machines, Journal of Symbolic Logic 80(04) (2015), 1116–1130. doi:10.1017/jsl.2015.8.

Carl, Randomness and degree theory for infinite time register machines, Computability 5(2) (2016), 181–196, available at: http://arxiv.org/find/all/1/all:+AND+merlin+carl/0/1/0/all/0/1.

Carl, The distribution of ITRM-recognizable reals, in: Turing Centenary Conference: How the World Computes, S.B. Cooper et al., eds, Annals of Pure and Applied Logic 165(9) (2014), 1353–1532.

Carl, ITRM-recognizability from random oracles, in: Evolving Computability: 11th Conference on Computability in Europe,

Beckmann et al., eds, Lecture Notes in Computer Science, Vol. 9136, 2015, pp. 137–145.

Carl, The lost melody phenomenon, in: Infinity, Computability, and Metamathematics: Festschrift Celebrating the 60th Birthdays of Peter Koepke and Philip Welch,

Geschke et al., eds, pp. 49–70.

10.

Carl,

Fischbach,

Koepke,

Miller,

Nasfi and

Weckbecker, The basic theory of infinite time register machines, Archive for Mathematical Logic 49(2) (2010), 249–273. doi:10.1007/s00153-009-0167-x.

11.

Carl and

Schlicht, Infinite computations with random oracles, Notre Dame Journal of Formal Logic, to appear, Preprint available at: arXiv:1307.0160 [math.LO].

12.

Carl,

Schlicht and

Welch, Recognizable sets and Woodin cardinals: Computation beyond the constructible universe, Preprint, submitted, available at: http://arxiv.org/pdf/1512.06101.pdf.

13.

Cutland, Computability – An Introduction to Recursive Function Theory, Cambridge University Press, 1980.

14.

R.G.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer LLC, 2010.

15.

C.W.

Gray, Iterated forcing from the strategic point of view, PhD thesis, University of California, Berkeley, California, 1980.

16.

Hamkins and

Lewis, Infinite time Turing machines, Journal of Symbolic Logic 65(2) (2000), 567–604. doi:10.2307/2586556.

17.

Jech, Set Theory, 3rd Millenium edn, revised and expanded, Springer Monographs in Mathematics, Springer, 2002.

18.

Jensen and

Karp, Primitive recursive set functions, in: Axiomatic Set Theory, Proc. Sympos. Pure Math., Vol. XIII, Part I, Amer. Math. Soc., Providence, RI, 1971, pp. 143–176.

19.

Kanamori, The Higher Infinite, Springer, Berlin, 2005.

20.

Koepke, Turing computations on ordinals, The Bulletin of Symbolic Logic 11(3) (2005). doi:10.2178/bsl/1122038993.

21.

Koepke, Infinite time register machines, in: Logical Approaches to Computational Barriers,

Beckmann et al., eds, Lecture Notes in Computer Science, Vol. 3988, 2006, pp. 257–266. doi:10.1007/11780342_27.

22.

Koepke, Ordinal computability, in: Mathematical Theory and Computational Practice,

Ambos-Spies et al., eds, Lecture Notes in Computer Science, Vol. 5635, 2009, pp. 280–289. doi:10.1007/978-3-642-03073-4_29.

23.

Koepke and

Miller, An enhanced theory of infinite time register machines, in: Logic and Theory of Algorithms,

Beckmann et al., eds, Lecture Notes in Computer Science, Vol. 5028, 2008, pp. 306–315. doi:10.1007/978-3-540-69407-6_34.

24.

Koepke and

Seyfferth, Ordinal machines and admissible recursion theory, Annals of Pure and Applied Logic 160 (2009), 310–318. doi:10.1016/j.apal.2009.01.005.

25.

Kunen, Set Theory. An Introduction to Independence Proofs, Elsevier, 2006.

26.

Löwe, Turing cones and set theory of the reals, Archive for Mathematical Logic 40(8) (2001), 651–664. doi:10.1007/s001530100092.

27.

A.R.D.

Mathias, Provident sets and rudimentary set forcing, Preprint, available at: https://www.dpmms.cam.ac.uk/~ardm/fifofields3.pdf.

28.

Rin, The computational strengths of α-tape infinite time Turing machines, Annals of Pure and Applied Logic 165(9) (2014), 1501–1511. doi:10.1016/j.apal.2014.04.016.

29.

Sacks, Higher Recursion Theory, Springer, Heidelberg, 1990. doi:10.1007/978-3-662-12013-2.

30.

Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society 75(2) (2007), 287–297. doi:10.1112/jlms/jdl015.

31.

Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic, Springer, Heidelberg, 1987.

32.

Welch, Minimality arguments for infinite time Turing degrees, in: Sets and Proofs,

S.B.

Cooper and

J.K.

Truss, eds, London Mathematical Society Lecture Note Series, Vol. 258, 1999, pp. 425–436.

33.

Welch, Eventually infinite time Turing degrees: Infinite time decidable reals, The Journal of Symbolic Logic 65(3) (2000), 1193–1203. doi:10.2307/2586695.

34.

Welch, Discrete transfinite computation, in: Turing’s Ideas – Their Significance and Impact,

Sommaruga and

Strahm, eds, Springer, Basel, 2014.

Infinite time recognizability from generic oracles and the recognizable jump operator 1

Abstract

Keywords

1. Introduction

Proof. See [33]. □ Theorem 3.3 (Hamkins–Lewis).

Footnotes

Acknowledgements

The relativized Jensen–Karp-theorem

References

Proof.
See [33]. □
Theorem 3.3 (Hamkins–Lewis).