betaFeedback

WorksComputer Science

Postselection on Halting and Reductions to the Halting Problem

Abstract

A probabilistic Turing machine is an ordinary Turing machine that may also toss fair coins, with no limit on its running time or memory. If it always halts, it decides only computable problems. Aaronson et al. studied machines that may run forever on some coin tosses, with the answer read only from the runs that halt. Suppose the correct answer must be more than twice as likely as the wrong one. They showed that these machines decide exactly the problems solvable with a fixed list of questions about the halting problem. They asked what happens when the correct answer need only be the more likely one. We show that the machines then decide exactly the problems solvable by asking such questions one after another, each chosen after the earlier answers. We also show that the factor two can be replaced by any fixed factor greater than one. A machine may promise two numbers: a lower bound on its probability of halting, and a lower bound on its probability of being right when it halts. From these two numbers we compute exactly how many questions fixed in advance the machine can replace. The main idea is that probability acts as a budget for how often a computable guess may change its mind. The results extend to oracle machines and to machines nested inside each other. Quantum machines decide the same problems.

Introduction

A probabilistic Turing machine that halts with probability one computes nothing beyond the computable: de Leeuw, Moore, Shannon and Shapiro showed that coin tosses alone add no power [1]. Probability can add power when the machine is allowed to run forever on some of its coin tosses and its output is read conditional on halting, that is, only from the runs that halt. We call this postselection on halting. The event conditioned on is the halting of a run, and whether a given run halts may never be settled at any finite time.

Aaronson et al. studied postselection on halting as the computability version of the postselection rule for closed timelike curves, paths in spacetime that return to their own past [2]. § 1.5 explains this connection. They showed that if the machine must halt with probability one, it decides only computable languages [2 Proposition 9.1]. They also studied machines whose correct output must be more than twice as likely as the wrong one, among the halting runs. Such machines decide exactly the languages truth-table reducible to the halting problem [2 Proposition 9.2]. The halting problem HALT is the set of program–input pairs whose run eventually stops. A truth-table reduction fixes a finite list of questions about HALT, and a rule for combining the answers, before it sees any answer: its questions are nonadaptive. The factor two plays no special role: any fixed factor greater than one gives the same class Corollary 4.10. Directly after Proposition 9.2 the authors ask what class results with unbounded error, that is, when the correct output need only be strictly more likely than the wrong one. They leave this open.

The strict-majority question

An algorithm may also ask its questions about HALT one at a time, choosing each question after seeing the earlier answers; such questions are adaptive. Write Δ20\Delta^{0}_{2} for the class of languages decidable by an algorithm that asks adaptive questions about HALT. It contains every language truth-table reducible to HALT, and more.

Theorem A (Unbounded error). With unbounded error, postselection on halting decides exactly Δ20\Delta^0_2. The class is the same if the machine must halt with probability at least ρ\rho, for any fixed rational ρ<1\rho< 1. This is Theorem 3.2, proved in Section 3.

The proof uses a classical idea, Shoenfield’s limit lemma [3]. Think of an algorithm that, on input xx, never stops working but keeps announcing an answer, 0 or 1, and sometimes changes it. We call the announced answer its guess, and each change of the guess a mind change. The limit lemma says that Δ20\Delta^0_2 is exactly the class of languages for which some such algorithm, after finitely many mind changes, settles on the correct answer on every input. The algorithm itself never knows whether it has settled.

A postselection machine can turn such a guess into probabilities. Suppose that on some input the guess starts at 0, later changes to 1, and later changes back to 0, for good. The machine tosses coins to choose a moment: the start, the first change, the second change, and so on. Each moment gets just enough probability to put its value ahead of the other value. The machine then waits for the chosen moment and outputs the guess at that moment. If the chosen moment never comes, here the third change or any later one, the machine waits forever, and this run is not counted. Among the runs that halt, the final value of the guess is therefore ahead. The argument also works the other way. Watch a machine for longer and longer times, and at each time take as the guess the output that is ahead so far among the halted runs. This guess settles on the correct answer. So probability works as a budget for mind changes, and Ershov’s hierarchy of Δ20\Delta^0_2 by the number of mind changes [4, 5, 6] organizes the rest of the paper.

The exact trade-off

A machine can also promise two things. It can promise how often it halts: a halting floor ρ\rho asks that the machine halt with probability at least ρ\rho on every input. And it can promise how sure its answer is: a confidence a=12+ηa = \frac{1}{2} + \eta, with margin η>0\eta> 0, asks that the correct output have probability at least aa among the halting runs. A higher floor or a higher confidence is a stricter promise, so fewer languages are decided. Given the two numbers ρ\rho and η\eta, we compute exactly how many nonadaptive questions about HALT such machines can replace. This number is

n(ρ,η)=max⁡{j≥0:ρRj≤1},where R=a1−a=1+2η1−2η.n(\rho,\eta)=\max\{j\ge0:\rho R^j\le1\}, \qquad\text{where } R=\frac{a}{1-a}=\frac{1+2\eta}{1-2\eta}.

For example, floor 14\frac{1}{4} and margin 16\frac{1}{6} give a=23a=\frac{2}{3} and R=2R=2, so ρR2=1<ρR3\rho R^2=1<\rho R^3, and exactly two questions are allowed.

Theorem B (The sharp halting-floor theorem). For rationals ρ∈(0,1)\rho\in(0,1) and η∈(0,1/2)\eta\in(0,1/2), the machines with halting floor ρ\rho and margin η\eta decide exactly the languages truth-table reducible to the halting problem with at most n(ρ,η)n(\rho,\eta) queries. In particular they decide only computable languages if and only if ρa>1−a\rho a>1-a, and at equality one query is allowed. This is Theorem 4.7 and Corollary 4.8, in § 4.

The reason is one inequality. A guess that switches from one output to the other must first hold at least the fraction aa of the halting probability, and later at most the fraction 1−a1-a. Probabilities of halting only grow with time, so every mind change multiplies the halting probability by at least RR, and it can never exceed one. Conversely, a machine built from fair coins can release probability in exactly these proportions.

The full classification

We classify every natural pair of a halting requirement and a confidence requirement; Table 1 lists them. Two requirements are the weakest of their kind. Requirement (H0)(H0) asks only that the machine halt with positive probability on every input, however small. Requirement (C0)(C0) asks only for a strict conditional majority: on every input, among the halting runs, the correct output is strictly more likely than the wrong one. A floor or a margin is fixed if it is one number for all inputs. It is computable if it may depend on the input xx, through an algorithm that computes it from xx. A halting probability can also be computable: an algorithm computes it from the input, to any precision wanted. Zero error asks that every halting run give the correct output.

How often it haltsHow sure it isLanguages decided: questions about HALTProved in
computable probability, e.g. one(C0)(C0)decidable: no questionsProp. 4.3
(H0)(H0)zero errordecidable: no questionsProp. 4.4
floor ρ\rho (given)margin η\eta (given)at most n(ρ,η)n(\rho,\eta) nonadaptive questionsThm. 4.7
some fixed floorsome fixed marginbtt(HALT): a bounded number of nonadaptive questionsCor. 4.8
(H0)(H0), or a computable floorany fixed margin, or a computable margintt(HALT): finitely many nonadaptive questionsProp. 4.9
any fixed floor ρ\rhoa computable margintt(HALT): finitely many nonadaptive questionsProp. 4.9
(H0)(H0), or any fixed floor ρ<1\rho< 1(C0)(C0)Δ20\Delta^0_2: adaptive questionsThm. 3.2

Table 1. The classification of Theorem 4.11, from the strongest requirements (top) to the weakest (bottom). (H0)(H0), (C0)(C0), fixed and computable floors and margins, and zero error are defined just before the table; n(ρ,η)n(\rho,\eta) is the number of Theorem B. “Any” means that every value gives the same class.

Each row of Table 1 gives a halting requirement, a confidence requirement, the languages that such machines decide, and where this is proved. The classes come from four kinds of algorithms that ask questions about HALT. The decidable languages need no questions. The bounded truth-table reductions, btt(HALT), ask at most nn nonadaptive questions, for a fixed nn. The truth-table reductions, tt(HALT), ask finitely many nonadaptive questions, their number computed from the input. The class Δ20\Delta^0_2 allows adaptive questions. Read from top to bottom, the requirements get weaker and the classes get larger. Each of the four classes strictly contains the one before (Proposition 4.12). Theorem A is the last row and Theorem B the third.

Oracles, nesting and quantum computation

The same questions can be asked one level higher. An oracle for a language AA is a black box that answers every question “is yy in AA?” correctly, in one step. Give our machines such an oracle. The role of the halting problem is then played by the jump A′A': the set of programs that halt when they may consult the same oracle AA. With this change every result above still holds (Theorem 5.4). One new point appears. The oracle can help to compute a floor, a margin, or the questions of a reduction. So each statement must say who computes them: an ordinary algorithm, or an algorithm that may consult AA. The answer can change the class.

Machines can also be stacked. In a nested machine the oracle is not a black box. Its answers come from another machine of the same kind, whose own oracle may come from a third machine, and so on. A stack of kk machines has depth kk, and each level adds one jump. So under unbounded error, depth kk decides exactly the languages decidable with an oracle for ∅(k)\emptyset^{(k)}, the halting problem iterated kk times (Theorem 5.7). From depth two on, it matters who writes the questions. A reduction whose questions an ordinary algorithm can write down decides strictly fewer languages than one whose questions need help from the level below (Proposition 5.8).

Finally, a quantum machine replaces coin tosses by measurements of quantum bits. For every quantum machine some ordinary coin-tossing machine has exactly the same output probabilities, and the converse also holds. So quantum machines decide the same classes, with the same constants (Theorem 6.5).

Relation to time-loop models

A closed timelike curve (CTC) is a path in spacetime that returns to its own past; general relativity allows such paths in some solutions of its equations. A computer near a CTC could send part of its memory back to an earlier time. The danger is a paradox: the computer could send back the opposite of what it received, as in the grandfather paradox. A model of computation with CTCs therefore needs a consistency rule that says which courses of events are allowed, and two rules have been studied.

Deutsch’s rule [7] asks that the state sent back be a fixed point: the state that arrives in the past must be the state that is later sent back. For probabilistic and quantum states such a fixed point always exists, so no paradox can occur. The postselection rule was proposed independently by Bennett and Schumacher and by Svetlichny, and Lloyd et al. developed it and tested it experimentally (see [2 Section 9] and [8]). It keeps only the courses of events in which the state sent back agrees with the state received, and reads the output conditional on that event. With polynomial time and polynomially many bits in the loop, Deutsch’s rule decides exactly PSPACE, the problems solvable in polynomial space [9]. The postselection rule with quantum machines and bounded error decides exactly PP, unbounded-error probabilistic polynomial time [10]; see also [2 Section 9].

Aaronson et al. then removed all resource bounds [2]. Under Deutsch’s rule, classical and quantum computers with a CTC decide exactly Δ20\Delta^{0}_{2} [2 Theorems 3.2 and 3.3]. For the postselection rule they proposed postselection on halting: the runs that never halt are discarded, and the output is read from the runs that halt. A run that never halts plays the role of a course of events that is never completed consistently. Our results complete this comparison. With unbounded error, postselection on halting decides the same class as Deutsch’s rule, Δ20\Delta^{0}_{2} (Theorem A). With bounded error the two rules differ: Deutsch’s rule still gives Δ20\Delta^{0}_{2}, while postselection gives only the truth-table reductions. With a prescribed floor and nn ranging, the allowed number of nonadaptive questions is exactly n(ρ,n)n(\rho,n) (Theorem B). Under nesting the same split appears at every depth (Section 5). Section 7 and Table 5 place all these results side by side.

Time boundLoop carriesErrorDeutsch’s rulePostselection rule
polynomialpolynomially many bits or qubitsanyPSPACE, classical and quantum [9]quantum, bounded error: PP [10]; [2 Section 9]
polynomialone bit, or logarithmically manydepends on the underlying classclassical: the postselected version of the underlying class [16, 17]; logarithmically many bits add nothing [18]; logarithmically many qubits, bounded error: PP [24]one qubit implements any postselected measurement [19]; we know of no classification for one classical bit
noneunboundedzeroΔ20\Delta^{0}_{2} [2 Theorems 3.2 and 3.3]decidable (Proposition 4.4)
noneunboundedboundedΔ20\Delta^{0}_{2} [2 Theorems 3.2 and 3.3]prescribed floor and margin: n(ρ,η)n(\rho,\eta) nonadaptive queries (Theorem 4.7); no floor: tt(HALT) [2 Proposition 9.2], Proposition 4.9; halting with probability one: decidable [2 Proposition 9.1]
noneunboundedunboundedΔ20\Delta^{0}_{2} [2 Theorems 3.2 and 3.3]Δ20\Delta^{0}_{2}, with or without a fixed floor ρ<1\rho< 1 (Theorem 3.2)
none, nested to depth k≥2k \ge2unbounded at each levelfixed margin or unboundedΔk+10\Delta^{0}_{k+1} with a fixed margin [15 Theorem 1]; full classification [2 Section 3]unbounded error: Δk+10\Delta^{0}_{k+1}; fixed margin, no floor: tt⁡∅(k−1)(∅(k))\operatorname{tt}^{\emptyset^{(k-1)}}(\emptyset^{(k)}); prescribed pair: MC⁡n(∅(k−1))\operatorname{MC}_{n}(\emptyset^{(k-1)}) (Theorem 5.7)
noneunbounded qubitsas abovethe Δ20\Delta^{0}_{2} entries hold for quantum machines [2 Theorem 3.3]no class and no constant changes (Theorem 6.5)

Table 5. The two consistency rules in the regimes that have been studied. The first three columns fix the setting: the time bound of the machine, how much information the loop carries, and the error model. Each remaining cell names the languages decided and its source; cells that cite a result of this paper are new. PSPACE is polynomial space and PP unbounded-error probabilistic polynomial time; the other classes are those of Sections 2–5.

Two differences from the physical setting should be kept in mind. The condition here is eventual halting rather than the outcome of one finite measurement. And our nesting is a mathematical idealization in which each level receives exact membership answers from the level below (Remark 5.6).

Related work

De Leeuw et al. began the computability theory of probabilistic machines [1], and Freivalds studied machines that toss coins and compute in the limit [11]. Ershov stratified Δ20\Delta^{0}_{2} by the number of mind changes [4, 5, 6]. Carstens [12] identified the level of computably bounded changes with the truth-table reductions to the halting problem. Aaronson et al. use this identification [2 Section 4.3], and Downey and Greenberg state the mind-change form [13]. Aaronson et al. proved that bounded-error postselection on halting gives the truth-table reductions to the halting problem [2 Proposition 9.2]. Our Proposition 4.9 reproves it for every prescribed margin, and Theorem B refines it by counting queries. Zvonkin and Levin showed that the output masses of probabilistic machines are exactly the limits of increasing computable sequences [14]. Lemma 4.6 is the exact two-output form that our lower bounds use.

Closest to our nesting result is Raat’s study of nested Deutschian loops [15 Theorem 1]. He shows that depth dd decides every language decidable with an oracle for the dd-fold iterated halting problem, with bounded error. His rule is causal consistency, and postselection is absent from his thesis. His upper bound adapts the quantum proof of Aaronson et al., whose corrected version records the full nested classification [2 Section 3]. We reach the same classes with unbounded error, by classical means. Unlike Deutsch’s rule, postselection with a fixed margin stops strictly short of Δk+10\Delta^{0}_{k+1} at every depth kk.

With resource bounds, both rules have been studied in detail; Table 5 in § 7 collects these results together with ours. Say and Yakaryılmaz showed that a single time-traveling bit decides exactly the postselected version of the underlying class [16, 17]. O’Donnell and Say showed that logarithmically many bits add nothing [18]. Brun and Wilde showed that a single qubit sent through a postselected loop already implements any postselected measurement [19]. Postselected quantum classes go back to Aaronson’s PostBQP, which he showed equals PP [10].

The paper is organized as follows. § 2 fixes the computability notions. Section 3 answers the strict-majority question, § 4 proves the exact trade-off and the classification, § 5 treats oracles and nesting, and § 6 quantum machines. Appendices A and B contain the proofs for § 5 and § 6. § 7 compares the two time-loop rules and collects open questions.

Background

This section fixes, in plain words, the computability notions used throughout. Everything is classical; the citations record where each notion is treated in detail.

Programs and the halting problem

An algorithm is a finite program for an ordinary deterministic Turing machine. Programs are finite strings, so they have a computable enumeration P0,P1,P2,…P_0, P_1, P_2, \ldots without repetitions, and simulating PeP_e on input ww for tt transitions is itself computable. A language LL is decidable if some algorithm halts on every input xx and outputs 1L(x)\mathbf{1}_{L}(x), which is 11 if x∈Lx \in L and 00 otherwise.

The halting problem is the language

HALT={⟨e,w⟩:Pe(w) halts}\mathrm{HALT} = \{\langle e,w\rangle: P_e(w)\ \text{halts}\}

of program–input pairs whose run eventually halts. It is not decidable: if a program HH decided it, the program that on input ee runs HH on ⟨e,e⟩\langle e,e\rangle and halts exactly when HH outputs 00 would halt on its own index exactly when it does not.

Oracles and reductions

An oracle is a language AA. An oracle machine is an algorithm that may also submit a query yy and receive the bit 1A(y)\mathbf{1}_{A}(y) in one step. A language LL is Turing reducible to AA, written L≤TAL \leq_T A, if some oracle machine with oracle AA halts on every input and decides LL. Later queries may depend on earlier answers; such reductions are called adaptive. We write Δ20\Delta^{0}_{2} for the languages Turing reducible to HALT.

A stricter kind of reduction prepares all questions in advance. A truth table for mm query positions is a map τ:{0,1}m→{0,1}\tau: \{0,1\}^{m} \to\{0,1\}. A language LL is truth-table reducible to AA, written L≤ttAL \leq_{\mathrm{tt}} A, if a total algorithm, given xx, outputs queries y1,…,ymy_1,\ldots,y_m and a truth table τx\tau_x, and

1L(x)=τx(1A(y1),…,1A(ym)).(1)\mathbf{1}_{L}(x) = \tau_x\bigl(\mathbf{1}_{A}(y_1),\ldots,\mathbf{1}_{A}(y_m)\bigr). \tag*{(1)}

Neither the queries nor the table depends on the oracle answers. The number mm of queries may depend on xx, but it is part of what the algorithm computes. A language is bounded truth-table reducible to AA, written L≤bttAL \leq_{\mathrm{btt}} A, if a fixed nn bounds the number of queries on every input; the least such nn is the norm of the reduction. We write btt(HALT) and tt(HALT) for the two classes of languages reducible to HALT in the respective sense, and R∥HALT\mathrm{R}_{\parallel}^{\mathrm{HALT}} as a synonym for tt(HALT).

Each model restricts the next one, so

decidable⊆btt(HALT)⊆tt(HALT)⊆Δ20.\text{decidable} \subseteq\mathrm{btt}(\mathrm{HALT}) \subseteq\mathrm{tt}(\mathrm{HALT}) \subseteq\Delta_{2}^{0}.

The total-table convention above gives the same class as the nonadaptive halting-oracle convention in [2 Proposition 9.2]. The only possible issue is a final computation that is required to halt only on the actual oracle-answer vector. For each of the finitely many candidate vectors, add a halting query asking whether that final computation outputs one. All these queries can be prepared in advance. A total Boolean table then selects the additional answer corresponding to the original answer vector. Thus even a partial final computation can be replaced by a total table here; no such equivalence for arbitrary oracles is being assumed.

Oracles also lead to the halting problem relative to an oracle, to its iterates, and to the higher levels of the arithmetic hierarchy; § 5 defines these where they are first used.

Approximations in the limit

A computable approximation of LL is a total computable function g:{0,1}∗×N0→{0,1}g : \{0,1\}^{*} \times\mathbb{N}_{0} \to\{0,1\} with lim⁡t→∞g(x,t)=1L(x)\lim_{t\to\infty} g(x,t) = 1_{L}(x) for every xx. A mind change of gg at xx is a stage t≥1t \geq1 with g(x,t)≠g(x,t−1)g(x,t) \ne g(x,t-1); the number of mind changes is

mchg(x)=∣{t≥1:g(x,t)≠g(x,t−1)}∣.m_{\mathrm{chg}}(x)=\left|\{t \geq1 : g(x,t) \ne g(x,t-1)\}\right|.

The limit lemma of Shoenfield [3] states that L≤THALTL \leq_{\mathrm{T}} \mathrm{HALT} if and only if LL has a computable approximation. A convergent Boolean sequence changes only finitely often, but the number of changes need not have a computable bound.

Approximations with bounded changes form a hierarchy, due to Ershov [4, 5, 6]. In Ershov’s convention, a language is kk-c.e., for k≥0k \geq0, if it has a computable approximation that starts at 0 and makes at most kk mind changes on every input. It is ω\omega-c.e. if it has a computable approximation whose mind changes are bounded by some computable function of xx.

In this paper an approximation may start at either value; we call this the free start. We use it because with a free start the number of mind changes equals the number of nonadaptive halting queries exactly (Lemma 4.5), which makes the counts of Section 4 exact. Passing to Ershov’s convention costs at most one change: if g(x,0)=1g(x,0)=1, put a stage with value 0 in front. So a language with at most kk changes from a free start is (k+1)(k+1)-c.e., and the union over all kk, like the ω\omega-c.e. class, is the same under both conventions. Single levels can differ. The complement of HALT has an approximation that starts at 1 and changes at most once. It is not 1-c.e.: such an approximation would turn to 1 exactly on the pairs that never halt, so running it alongside the simulation of Pe(w)P_e(w) would decide HALT. Carstens [12] showed that tt(HALT) is exactly the class of ω\omega-c.e. languages; see also [2 Section 4.3], and [13 Section 2] for the mind-change formulation.

Reals approximable from below

A real number α\alpha is left-computably enumerable if it is the limit of a computable nondecreasing sequence of rational numbers. Such a sequence approximates α\alpha from below at a possibly noncomputable rate. If a real of this kind also has a computable sequence converging to it from above, then it is computable. Given kk, search for a stage at which the two sequences differ by at most 2−k2^{-k}.

Unbounded error: the class Δ20\Delta^0_2

We now define the model discussed in [2 Section 9] in connection with postselected closed timelike curves [8]. A machine here may run forever on some of its coin tosses. Conditional on halting, its correct output must be more likely than its incorrect output. This is unbounded-error postselection.

The concrete question is stated directly after Proposition 9.2 of the corrected version [2 Section 9]. That proposition classifies the machines whose correct output is more than twice as likely as their incorrect output: they decide exactly the languages truth-table reducible to HALT. The authors then ask for the class that results with unbounded error, that is, when the correct output need only be strictly more likely than the incorrect one, and they leave this open. Theorem 3.2 answers the question. Corollary 3.3 then shows that a computable positive lower bound on the advantage of the correct output strictly shrinks the class, and § 4 finds every class in between.

The machine and its answer rule

Definition 3.1 (Partial postselection). A machine MM is an ordinary finite-program probabilistic Turing machine: each transition follows its deterministic instructions or uses a new independent fair coin to choose between two instructions. At most one new coin is used per transition. It receives no oracle answers. On input x∈{0,1}∗x \in\{0,1\}^* it either halts with output 0 or 1, or runs forever.

Write

pi(x)=P[M(x) eventually halts with output i],Phalt(x)=p0(x)+p1(x)≤1.p_i(x) = \mathbb{P}[M(x)\text{ eventually halts with output }i], \qquad P_{\mathrm{halt}}(x) = p_0(x) + p_1(x) \le1.

The class U\mathcal{U} consists of the languages LL for which one such machine satisfies, on every input,

x∈L⇒p1(x)>p0(x),x∉L⇒p0(x)>p1(x).(2)x \in L \Rightarrow p_1(x) > p_0(x), \qquad x \notin L \Rightarrow p_0(x) > p_1(x). \tag*{(2)}

The strict inequalities imply Phalt(x)>0P_{\mathrm{halt}}(x) > 0. Write q(x)=P[M(x)=1L(x)∣M(x) halts]q(x) = \mathbb{P}[M(x) = 1_L(x) \mid M(x)\text{ halts}] for conditional correctness; the requirement is q(x)>1/2q(x) > 1/2. Here 1L1_L is the characteristic function of LL. We impose no time or space bound, no computable lower bound on the conditional advantage q(x)−1/2q(x) - 1/2, and no bound on the number of coins used. Ties are excluded on both yes- and no-inputs.

For comparison, an unconditional correct-output probability above 1/21/2 would yield a decidable language: enumerate finite computation trees until one output accumulates mass above 1/21/2. This is an elementary instance of the classical probabilistic-computability setting of de Leeuw et al. [1]. Our requirement is instead p1L(x)(x)>Phalt(x)/2p_{1_L(x)}(x) > P_{\mathrm{halt}}(x)/2, where Phalt(x)P_{\mathrm{halt}}(x) can be less than one. Almost-surely halting postselection with an additional discarded output also gives only decidable languages [2 Proposition 9.1].

The characterization

By the limit lemma (§ 2), a language lies in Δ20\Delta^0_2 exactly when it has a computable approximation g(x,t)g(x,t) with values in {0,1}\{0,1\}. The number of its mind changes need not have a computable bound.

The proof builds on the guess-and-diverge device in [2 proof of Proposition 9.2]. The additional step is to assign summable weights to successive changes of a computable guess, so that every change reverses the accumulated majority. The limit lemma turns adaptive halting-oracle computation into a computable sequence of guesses. The endpoint with halting probability one is included for comparison and is already covered by [2 Proposition 9.1].

Theorem 3.2 (Unbounded-error postselection on halting). The class U\mathcal{U} equals Δ20\Delta^{0}_{2}. For every fixed rational ρ∈(0,1)\rho\in(0,1), the same class results if one also requires Phalt(x)≥ρP_{\mathrm{halt}}(x) \ge\rho on every input. At ρ=1\rho= 1 the class is the decidable languages, as already follows from [2 Proposition 9.1]. The transformations are effective: they construct the required program from the code of the supplied machine or approximation and the rational ρ<1\rho< 1, assuming the stated properties hold for that code.

Proof. Upper bound. Let pi,t(x)p_{i,t}(x) be the probability of halting with output ii within tt transitions. It is an exactly computable dyadic rational, meaning an integer divided by a power of two. To see this, enumerate the 2t2^{t} strings of coin bits, simulate at most tt transitions using each string as the available random tape, and divide the number that halt with output ii by 2t2^{t}. A run that halts early ignores the remaining bits of its string, so each string is counted once and no mass is double counted. Then pi,t(x)↑pi(x)p_{i,t}(x) \mathrel{\uparrow} p_i(x), since every halting run halts at a finite time. Hence

dt(x)=p1,t(x)−p0,t(x)⟶d(x)=p1(x)−p0(x)≠0.d_t(x) = p_{1,t}(x) - p_{0,t}(x) \longrightarrow d(x) = p_1(x) - p_0(x) \ne0.

The total computable approximation a(x,t)=1{dt(x)>0}a(x,t) = \mathbf{1}\{d_t(x) > 0\} stabilizes to 1L(x)\mathbf{1}_{L}(x). Temporary ties are assigned zero and do not affect the limit. The limit lemma yields L∈Δ20L \in\Delta^{0}_{2}; no convergence rate is used.

Lower bound. Fix a total computable convergent approximation gg. Draw one integer J≥0J \ge0 with probabilities

w0=P[J=0]=14,wk=P[J=k]=32k+2(k≥1).(3)w_0 = \mathbb{P}[J = 0] = \frac{1}{4}, \qquad w_k = \mathbb{P}[J = k] = \frac{3}{2^{k+2}} \quad(k \ge1). \tag*{(3)}

An exact fair-coin sampler tosses two coins and returns zero on the outcome 00. On the other three outcomes it tosses fresh coins until the first head and returns the number of coins tossed, k≥1k \ge1. Thus P[J=k]=(3/4)2−k\mathbb{P}[J = k] = (3/4)2^{-k} for k≥1k \ge1, and the weights sum to one. The exceptional all-tails continuation has probability zero and may run forever, as the model permits.

If J=0J = 0, output g(x,0)g(x,0). If J=k≥1J = k \ge1, compute g(x,0),g(x,1),…g(x,0), g(x,1), \ldots in order until the kkth change of value and output its new value. Totality of gg ensures that every finite stage is eventually computed. A branch waiting for a nonexistent change runs forever; it does not attempt to recognize nonoccurrence.

For the analysis only, put

mchg=mchg(x)=∣{t≥1:g(x,t)≠g(x,t−1)}∣<∞,σ0=2g(x,0)−1.m_{\mathrm{chg}} = m_{\mathrm{chg}}(x) = \left|\{t \ge1 : g(x,t) \ne g(x,t-1)\}\right| < \infty, \qquad\sigma_0 = 2g(x,0) - 1.

Exactly the branches J≤mchgJ \le m_{\mathrm{chg}} halt. Since each Boolean change flips the sign, direct summation gives

Phalt(x)=14+∑k=1mchg32k+2=1−12mchg+2≥14.(4)P_{\mathrm{halt}}(x) = \frac{1}{4} + \sum_{k=1}^{m_{\mathrm{chg}}} \frac{3}{2^{k+2}} = 1 - \frac{1}{2^{m_{\mathrm{chg}}+2}} \ge\frac{1}{4}. \tag*{(4)}
d(x)=σ04+∑k=1mchg3(−1)kσ02k+2=(−1)mchgσ02mchg+2=21L(x)−12mchg+2.(5)d(x) = \frac{\sigma_0}{4} + \sum_{k=1}^{m_{\mathrm{chg}}} \frac{3(-1)^k\sigma_0}{2^{k+2}} = \frac{(-1)^{m_{\mathrm{chg}}}\sigma_0}{2^{m_{\mathrm{chg}}+2}} = \frac{2\mathbf{1}_{L}(x)-1}{2^{m_{\mathrm{chg}}+2}}. \tag*{(5)}

For completeness, the signed-sum identity follows by induction: its value at mchg=0m_{\mathrm{chg}} = 0 is σ0/4\sigma_0/4; adding the next term to (−1)mchgσ0/2mchg+2(-1)^{m_{\mathrm{chg}}}\sigma_0/2^{m_{\mathrm{chg}}+2} gives (−1)mchg+1σ0/2mchg+3(-1)^{m_{\mathrm{chg}}+1}\sigma_0/2^{m_{\mathrm{chg}}+3}. Equation (4) proves both strict inequalities in (1), including the case mchg=0m_{\mathrm{chg}} = 0.

The machine contains a program for gg and the fixed sampler. It never uses mchg(x)m_{\mathrm{chg}}(x) or a stabilization stage. Thus the code of this machine can be computed from the code of gg. The upper-bound construction is likewise effective from the code of MM.

A prescribed halting bound. Given rational 0<ρ<10 < \rho< 1, choose an integer k≥0k \ge0 with 1−3⋅2−k/4≥ρ1 - 3 \cdot2^{-k}/4 \ge\rho, and put c=2−kc = 2^{-k}. With probability cc, run the machine just constructed; otherwise halt with an independent fair output bit. This choice uses only finitely many fair coins. If pi′(x)p_i'(x), Phalt′(x)P_{\mathrm{halt}}'(x) and d′(x)d'(x) are the new output masses, halting probability and signed gap, then

pi′(x)=1−c2+cpi(x),Phalt′(x)=1−c+cPhalt(x)≥1−3c4≥ρ,d′(x)=cd(x).p_i'(x) = \frac{1-c}{2} + cp_i(x), \qquad P_{\mathrm{halt}}'(x) = 1-c+cP_{\mathrm{halt}}(x) \ge1-\frac{3c}{4} \ge\rho, \qquad d'(x)=cd(x).

The sign is unchanged because c>0c>0. Thus any prescribed bound below one is possible. If Phalt(x)=1P_{\mathrm{halt}}(x)=1 instead, the correct output has unconditional probability greater than 1/21/2. The finite-tree search described above then decides the language; conversely, a deterministic decider is an admissible machine. All these transformations are effective when their supplied programs have the stated properties. They need no algorithm for checking those properties.

The basic construction, before adding the balanced outputs, has the exact conditional advantage

q(x)−12=P[M(x)=1L(x)∣M(x) halts]−12=12(2mchg(x)+2−3).(6)q(x)-\frac{1}{2}=\mathbb{P}[M(x)=1_L(x)\mid M(x)\text{ halts}]-\frac{1}{2}=\frac{1}{2(2^{m_{\mathrm{chg}}(x)+2}-3)}. \tag*{(6)}

Each additional change reverses the accumulated bias and halves its magnitude. So the conditional advantage q(x)−12q(x)-\frac{1}{2} may have no computable positive lower bound, even though the halting probability never falls below 1/41/4.

A worked example

Suppose the initial guess is zero. The branch assigned to that guess has probability 1/41/4. The first change to one adds output-one mass 3/83/8, so one becomes the more likely output. A second change adds output-zero mass 3/163/16, making zero more likely again. Table 2 continues this calculation. The total halting probability increases, while the conditional advantage over one half decreases.

Changes mchgm_{\mathrm{chg}}Final guessp0p_0p1p_1Phalt=p0+p1P_{\mathrm{halt}}=p_0+p_1qq
001/41/401/41/41
111/41/43/83/85/85/83/53/5
207/167/163/83/813/1613/167/137/13
317/167/1615/3215/3229/3229/3215/2915/29

Table 2. Output probabilities after the last of mchgm_{\mathrm{chg}} changes, for an approximation starting at zero. Branches assigned to later changes run forever. The final guess is the correct answer, and qq is its probability conditional on halting.

The halting problem itself uses just the first two rows. Given a program and its input, initially guess zero and switch to one if its halting is observed. If it never halts, only the initial-guess branch outputs, and conditional correctness is one. If it halts, the branch waiting for the first change also outputs, and conditional correctness is 3/53/5. The machine never detects nonhalting. The general construction uses the same rule for approximations that may change many times.

Bounded error

Aaronson et al. proved that machines as in Definition 3.1 whose correct output is more than twice as likely as the incorrect one decide exactly the languages truth-table reducible to HALT [2 Proposition 9.2]. In symbols, this asks that q(x)>2/3q(x)>2/3 on every input. Proposition 4.9 in § 4 proves this again in both directions, for every prescribed margin and for computable margins. Recall from § 2 that R∥\mathrm{R}_{\parallel} is the class of languages truth-table reducible to HALT.

Corollary 3.3 (The computable-margin boundary). R∥HALT⊊Δ20=U\mathrm{R}_{\parallel}^{\mathrm{HALT}} \subsetneq\Delta^{0}_{2} = \mathcal{U}. So bounded error decides strictly fewer languages than unbounded error.

Proof. The equality is Theorem 3.2. The strict inclusion has the following standard diagonal proof. Identify finite binary inputs with nonnegative integers by ordering words first by length and then alphabetically within each length. Enumerate all ordinary programs as PeP_e, where ee is the program’s index in that computable enumeration. A program in this list may diverge; if it halts, its output may describe a finite halting-query list and a Boolean truth table. With a halting oracle, define a set AA by setting A(e)=0A(e) = 0 if Pe(e)P_e(e) does not halt or produces an invalid description. Otherwise evaluate the returned table using its finitely many halting queries and let A(e)A(e) be the opposite bit. This defines a total HALT-computable set. If a total truth-table reduction with index ee computed AA, its value at ee would contradict the definition of A(e)A(e). Thus A∈Δ20∖R∥HALTA \in\Delta^{0}_{2} \setminus\mathrm{R}_{\parallel}^{\mathrm{HALT}}.

So some languages in U\mathcal{U} have no machine with a computable positive margin, although they have the Phalt≥1/4P_{\mathrm{halt}} \ge1/4 machine of Theorem 3.2.

The ingredients are classical. Differences of left-computably enumerable reals (§ 2) are studied in [20, 21], and finite changes of computable approximations in [13 Section 2]. Probabilistic recursion theory also treats missing output mass as divergence [22 Section 2]. Our contribution is the exact classification for the strict conditional decision rule, with a uniform fair-coin construction and preservation of the class under any fixed halting lower bound below one. The almost-sure-halting endpoint is already known. The fixed-confidence comparison is a prior result, used here with explicit attribution.

The exact floor–confidence trade-off

Section 3 fixed the class at the two ends. A strict conditional majority decides exactly Δ20\Delta^{0}_{2} whatever fixed floor below one is imposed on the halting probability. A computable margin gives the truth-table class. This section finds the exact class for every pair of guarantees in between. Its main result, Theorem 4.7, counts the nonadaptive halting questions that a prescribed floor and a prescribed confidence allow. The other rows of Table 1 follow from it.

Two scales of guarantees

Definition 4.1 (Halting guarantees). Let MM be a machine as in Definition 3.1, and let ρ\rho be a rational number in (0,1)(0,1).

(H0) Phalt(x)>0P_{\mathrm{halt}}(x) > 0 on every input.

(Hρ\rho) Phalt(x)≥ρP_{\mathrm{halt}}(x) \ge\rho on every input. The number ρ\rho is then a halting floor.

(Hc) PhaltP_{\mathrm{halt}} is a computable halting probability: a total algorithm, given xx and kk, outputs a rational within 2−k2^{-k} of Phalt(x)P_{\mathrm{halt}}(x).

(H1) Phalt(x)=1P_{\mathrm{halt}}(x) = 1 on every input.

A computable floor is a total computable rational function ρ(x)\rho(x) with values in (0,1)(0,1) and Phalt(x)≥ρ(x)P_{\mathrm{halt}}(x) \ge\rho(x) on every input.

Definition 4.2 (Confidence guarantees). Let qq be the conditional correctness of MM, and let η\eta be a rational number in (0,1/2](0,1/2].

(C0) q(x)>1/2q(x)>1/2 on every input: a strict majority.

(Cη) q(x)≥1/2+ηq(x)\ge1/2+\eta on every input. The number η\eta is then a confidence margin, and a=12+ηa=\frac{1}{2}+\eta is the confidence. The case η=1/2\eta=1/2, that is q(x)=1q(x)=1, is zero error.

(Ceff) q(x)≥1/2+η(x)q(x)\ge1/2+\eta(x) on every input for a total computable rational function η\eta with values in (0,1/2)(0,1/2), a computable margin.

Requirement (H1) implies (Hc), and (H1) and every floor imply (H0). Requirement (Cη) implies (Ceff) when η<1/2\eta<1/2, and every confidence requirement implies (C0). A deterministic decider, viewed as a machine, satisfies (H1) together with zero error.

Throughout this section, pi,t(x)p_{i,t}(x) is the probability of halting with output ii within tt transitions, an exactly computable dyadic rational (proof of Theorem 3.2), and Pt(x)=p0,t(x)+p1,t(x)P_t(x)=p_{0,t}(x)+p_{1,t}(x). Both increase with tt, to pi(x)p_i(x) and Phalt(x)P_{\mathrm{halt}}(x).

A computable halting probability, and zero error

Proposition 4.3. Under (C0) and (Hc), the decided languages are exactly the decidable languages. Given the code of MM and a genuine program witnessing (Hc), one computes a decider. The converse transformation is effective as well.

Proof. Fix the input xx. Let rtr_t be a computable rational with ∣rt−Phalt(x)∣≤2−t|r_t-P_{\mathrm{halt}}(x)|\le2^{-t}, supplied by the (Hc) witness. The two quantities

ℓt=p1,t(x),ut=rt−p0,t(x)+2−t\ell_t=p_{1,t}(x),\qquad u_t=r_t-p_{0,t}(x)+2^{-t}

squeeze p1(x)p_1(x). The lower bound is clear. For the upper bound, p0,t(x)≤p0(x)p_{0,t}(x)\le p_0(x) and the error of rtr_t is at least −2−t-2^{-t}. The gap tends to zero:

ut−ℓt=(rt−Phalt)+(p0−p0,t)+2−t+(p1−p1,t)⟶0,u_t-\ell_t=(r_t-P_{\mathrm{halt}})+(p_0-p_{0,t})+2^{-t}+(p_1-p_{1,t})\longrightarrow0,

each of the four terms tending to zero. Given kk, search for the first tt with ut−ℓt≤2−ku_t-\ell_t\le2^{-k} and output ℓt\ell_t. The search terminates, and ∣p1(x)−ℓt∣≤ut−ℓt≤2−k|p_1(x)-\ell_t|\le u_t-\ell_t\le2^{-k}. So p1(x)p_1(x) is a computable real, uniformly in xx. Interchanging the roles of the two outputs shows the same for p0(x)p_0(x). Hence d(x)=p1(x)−p0(x)d(x)=p_1(x)-p_0(x) is computable to any precision.

Requirement (C0) gives d(x)≠0d(x)\ne0, with the sign of 21L(x)−12\mathbf{1}_L(x)-1. For k=1,2,…k=1,2,\ldots compute d^k\hat d_k with ∣d^k−d(x)∣≤2−k|\hat d_k-d(x)|\le2^{-k}, and stop at the first kk with ∣d^k∣>2−k|\hat d_k|>2^{-k}. Such a kk exists because ∣d(x)∣>2−k+1|d(x)|>2^{-k+1} for all large kk. At that stage, ∣d^k−d(x)∣≤2−k<∣d^k∣|\hat d_k-d(x)|\le2^{-k}<|\hat d_k|, so d^k\hat d_k and d(x)d(x) share the sign, and 1{d^k>0}=1L(x)\mathbf{1}\{\hat d_k>0\}=\mathbf{1}_L(x).

For the converse, let a decider for LL run as a probabilistic machine that never consults its coins. Then Phalt(x)=1P_{\mathrm{halt}}(x)=1 and q(x)=1q(x)=1, so (H1), hence (Hc), and (C0) hold. □

The case (H1) of Proposition 4.3 is [2 Proposition 9.1]. The squeeze needs less: the halting probability must merely be computable, and no flood on it is used.

Proposition 4.4 (Zero error). Under (H0) and zero error, the decided languages are exactly the decidable languages.

Proof. Every halting run outputs 1L(x)\mathbf{1}_L(x), and some run halts. Search the stages t=1,2,…t=1,2,\ldots for the first with Pt(x)>0P_t(x)>0, find a coin string of length tt whose run halts within tt transitions, and output its answer. Conversely, a decider is a machine with Phalt=1P_{\mathrm{halt}}=1 and q=1q=1. □

Mind changes, queries and masses

The bridge between postselection and classical reducibility is the correspondence between nonadaptive halting queries and mind changes. With the free start of § 2, the number of mind changes is exactly the number of queries.

Lemma 4.5. Let LL be a language and n≥0n \ge0 an integer.

(1) L≤bttHALTL \le_{\mathrm{btt}} \mathrm{HALT} with norm at most nn if and only if LL has a computable approximation with at most nn mind changes on every input.

(2) L≤ttHALTL \le_{\mathrm{tt}} \mathrm{HALT} if and only if LL has a computable approximation whose number of mind changes is bounded by a computable function of xx.

Both directions are effective: a program for either side yields a program for the other.

Proof. Part (1), “only if”. A total algorithm computes from xx the queries y1,…,ymy_1,\ldots,y_m with m≤nm \le n and the truth table τx\tau_x. Let bj,t=1b_{j,t}=1 if the run of yjy_j halts within tt transitions, and 00 otherwise. Each sequence bj,tb_{j,t} is computable and nondecreasing and changes value at most once. Put g(x,t)=τx(b1,t,…,bm,t)g(x,t)=\tau_x(b_{1,t},\ldots,b_{m,t}). Then gg is a total computable approximation: the observed answers converge to the true oracle answers, so g(x,t)g(x,t) converges to 1L(x)1_L(x). Every change of gg coincides with a change of some bj,⋅b_{j,\cdot}, so gg changes at most m≤nm \le n times.

Part (1), “if”. Let gg be a computable approximation with at most nn mind changes. For j=1,…,nj=1,\ldots,n let Px,jP_{x,j} be the program that hardwires xx and jj, ignores its input, simulates g(x,0),g(x,1),…g(x,0),g(x,1),\ldots, and halts exactly when it observes the jj-th mind change. The query yjy_j is the pair (Px,j,ϵ)(P_{x,j},\epsilon). It is answered positively exactly when j≤mchg(x)j \le m_{\mathrm{chg}}(x), so the number of positively answered queries is mchg(x)m_{\mathrm{chg}}(x). Boolean changes flip the value, so 1L(x)=g(x,0)⊕(mchg(x) mod 2)1_L(x)=g(x,0)\mathbin{\oplus}(m_{\mathrm{chg}}(x)\bmod2). The truth table τx(a1,…,an)=g(x,0)⊕a1⊕⋯⊕an\tau_x(a_1,\ldots,a_n)=g(x,0)\mathbin{\oplus}a_1\mathbin{\oplus}\cdots\mathbin{\oplus}a_n returns 1L(x)1_L(x) on the true answer vector, and the map from xx to the queries and the table is total computable. For n=0n=0 the approximation never changes, so LL is decidable and zero queries suffice.

Part (2), “only if”. The reduction computes, along with its queries, their number m(x)m(x), and the gg above changes at most m(x)m(x) times, a computable bound. Part (2), “if”. Apply the construction of part (1) with n=f(x)n=f(x), where ff is the computable bound. The number of queries then depends computably on xx, which the truth-table convention allows.

The truth-table equivalence of part (2) is due to [12]; see also [2 Section 4.3] and, for the mind-change form, [13 Section 2]. In Ershov’s terms, the class in part (1) contains the nn-c.e. languages and is contained in the (n+1)(n+1)-c.e. languages (§ 2).

The second tool turns prescribed output masses into a machine. A mass program is a pair of total computable functions ℓ0(x,t)\ell_0(x,t) and ℓ1(x,t)\ell_1(x,t) with nonnegative rational values, nondecreasing in tt, with ℓ0(x,t)+ℓ1(x,t)≤1\ell_0(x,t)+\ell_1(x,t)\le1. Their limits pi(x)=lim⁡tℓi(x,t)p_i(x)=\lim_t \ell_i(x,t) are left-computably enumerable reals, uniformly in xx (§ 2).

Lemma 4.6 (Exact realization of output masses). From a mass program one computes a machine as in Definition 3.1 whose output masses are exactly p0(x)=lim⁡tℓ0(x,t)p_0(x)=\lim_t\ell_0(x,t) and p1(x)=lim⁡tℓ1(x,t)p_1(x)=\lim_t\ell_1(x,t) on every input. The same holds with an oracle AA: if ℓ0\ell_0 and ℓ1\ell_1 are computed from AA, the machine is an oracle machine with oracle AA (Definition 5.1).

Proof. The machine reads fair coins b1,b2,…b_1,b_2,\ldots one at a time, which defines a uniform random point U=∑jbj2−jU=\sum_j b_j2^{-j} of [0,1)[0,1). After reading tt coins it knows the dyadic interval Dt=[k2−t,(k+1)2−t)D_t=[k2^{-t},(k+1)2^{-t}) that contains UU. It computes ℓ0(x,t)\ell_0(x,t) and ℓ1(x,t)\ell_1(x,t), halts with output 0 if Dt⊆[0,ℓ0(x,t))D_t\subseteq[0,\ell_0(x,t)), halts with output 1 if Dt⊆[1−ℓ1(x,t),1)D_t\subseteq[1-\ell_1(x,t),1), and otherwise reads the next coin. The two intervals are disjoint because ℓ0+ℓ1≤1\ell_0+\ell_1\le1, and each transition uses at most one coin.

If U<p0(x)U<p_0(x), then ℓ0(x,t)>U+ϵ\ell_0(x,t)>U+\epsilon for some ϵ>0\epsilon>0 and all large tt, while DtD_t has length 2−t2^{-t}, so the run halts with output 0. It cannot halt earlier with output 1, because U<p0≤1−p1≤1−ℓ1(x,t)U<p_0\le1-p_1\le1-\ell_1(x,t) at every stage. Conversely, a halt with output 0 at stage tt gives U∈[0,ℓ0(x,t))⊆[0,p0)U \in[0,\ell_0(x,t)) \subseteq[0,p_0). So the run outputs 0 exactly when U<p0(x)U < p_0(x). In the same way it outputs 1 when U>1−p1(x)U > 1-p_1(x), and an output 1 forces U≥1−p1(x)U \ge1-p_1(x). The single point U=1−p1(x)U = 1-p_1(x) has probability zero. Hence the output masses are p0(x)p_0(x) and p1(x)p_1(x). With an oracle, the machine computes ℓ0\ell_0 and ℓ1\ell_1 with its oracle and nothing else changes.

This is the two-output case of a classical fact: the output distributions of probabilistic machines are exactly the families of left-computably enumerable masses with total at most one. This goes back to Zvonkin and Levin [14]; see also [23]. We prove the form we need, which is exact, uniform and relativizes. We use it for every lower bound below, and in § 6 to transfer the results to quantum machines.

The sharp halting-floor theorem

Fix rationals ρ∈(0,1)\rho\in(0,1) and η∈(0,1/2)\eta\in(0,1/2), and put

a=12+η,R=a1−a=1+2η1−2η>1,n(ρ,η)=max⁡{j≥0: ρRj≤1}.a = \frac{1}{2}+\eta,\qquad R = \frac{a}{1-a} = \frac{1+2\eta}{1-2\eta}>1,\qquad n(\rho,\eta)=\max\{j\ge0:\ \rho R^j\le1\}.

The maximum exists because ρR0=ρ≤1\rho R^0=\rho\le1 and R>1R>1, and n(ρ,η)n(\rho,\eta) is computed exactly by rational arithmetic. Equivalently, n(ρ,η)=⌊log⁡(1/ρ)/log⁡R⌋n(\rho,\eta)=\lfloor\log(1/\rho)/\log R\rfloor; the rational form decides the case of equality without logarithms. In words: a floor ρ\rho and a margin η\eta together permit exactly n(ρ,η)n(\rho,\eta) halting questions fixed in advance.

Theorem 4.7 (Sharp halting-floor theorem). Let ρ∈(0,1)\rho\in(0,1) and η∈(0,1/2)\eta\in(0,1/2) be rationals, and n=n(ρ,η)n=n(\rho,\eta). A language is decided by a machine under (Hρ)(H\rho) and (Cη)(C\eta) if and only if it is truth-table reducible to HALT with at most nn queries on every input. Both directions are effective, from the code of the machine together with ρ\rho and η\eta, and from the code of the reduction.

Proof. Upper bound. Let MM satisfy (Hρ)(H\rho) and (Cη)(C\eta) and decide LL. By Lemma 4.5(1) it suffices to compute an approximation of LL with at most nn mind changes. Since ρRn+1>1\rho R^{n+1}>1 and ρ′(a′/(1−a′))n+1\rho'(a'/(1-a'))^{n+1} depends continuously on (ρ′,a′)(\rho',a'), there are rationals ρ0∈(0,ρ)\rho_0\in(0,\rho) and a0∈(1/2,a)a_0\in(1/2,a) with

ρ0R0n+1>1,R0=a01−a0.\rho_0R_0^{n+1}>1,\qquad R_0=\frac{a_0}{1-a_0}.

A search over ρ0=ρ(1−2−m)\rho_0=\rho(1-2^{-m}) and a0=a−2−mηa_0=a-2^{-m}\eta, m=1,2,…m=1,2,\ldots, finds them. Call a stage ss ii-good if Ps(x)≥ρ0P_s(x)\ge\rho_0 and pi,s(x)≥a0Ps(x)p_{i,s}(x)\ge a_0P_s(x). Since a0>1/2a_0>1/2, no stage is good for both outputs.

Some stage is good. Indeed Ps→Phalt≥ρ>ρ0P_s\to P_{\mathrm{halt}}\ge\rho>\rho_0, and pL,s−a0Ps→pL−a0Phalt≥(a−a0)Phalt>0p_{L,s}-a_0P_s\to p_L-a_0P_{\mathrm{halt}}\ge(a-a_0)P_{\mathrm{halt}}>0, where pLp_L is the mass of the correct output 1L(x)1_L(x). Let s0s_0 be the first stage that is good for some output, and define g(x,0)g(x,0) to be that output. For t≥1t\ge1, put g(x,t)=1−g(x,t−1)g(x,t)=1-g(x,t-1) if stage s0+ts_0+t is (1−g(x,t−1))(1-g(x,t-1))-good, and g(x,t)=g(x,t−1)g(x,t)=g(x,t-1) otherwise. All tests compare exactly computed dyadic rationals with fixed rationals, so gg is total computable.

The approximation converges to 1L(x)1_L(x). The mass p1−L,s−a0Psp_{1-L,s}-a_0P_s of the wrong output tends to p1−L−a0Phalt≤(1−a−a0)Phalt<0p_{1-L}-a_0P_{\mathrm{halt}}\le(1-a-a_0)P_{\mathrm{halt}}<0, since a+a0>1a+a_0>1. So from some stage on, every stage is good for the correct output and no stage is good for the wrong one, and gg settles on 1L(x)1_L(x).

Now count the changes. Suppose the value ii is set at stage uu, either u=s0u=s_0 or a change, and the next change, to 1−i1-i, happens at stage v>uv>u. Stage uu is ii-good, so pi,u≥a0Pup_{i,u}\ge a_0P_u. Stage vv is (1−i)(1-i)-good, so pi,v=Pv−p1−i,v≤(1−a0)Pvp_{i,v}=P_v-p_{1-i,v}\le(1-a_0)P_v. The masses only grow, so

a0Pu≤pi,u≤pi,v≤(1−a0)Pv,that isPv≥R0Pu.a_0P_u\le p_{i,u}\le p_{i,v}\le(1-a_0)P_v,\qquad\text{that is}\qquad P_v\ge R_0P_u.

Each change multiplies the total mass by at least R0R_0. After kk changes the total mass is at least ρ0R0k\rho_0R_0^k, and it is at most one, so k≤nk\le n by the choice of ρ0\rho_0 and $a_0.

Lower bound. Let LL have a truth-table reduction to HALT with at most nn queries. Lemma 4.5(1) gives a computable approximation gg with at most nn mind changes. Let k(x,t)≤nk(x,t)\le n

be the number of changes of g(x,⋅)g(x,\cdot) up to stage tt. Assign mass ℓg(x,t)(x,t)=aρRk(x,t)\ell_{g(x,t)}(x,t)=a\rho R^{k(x,t)} to the current guess and mass ℓ1−g(x,t)(x,t)=(1−a)ρRk(x,t)\ell_{1-g(x,t)}(x,t)=(1-a)\rho R^{k(x,t)} to the other output. The total is ρRk(x,t)≤ρRn≤1\rho R^{k(x,t)}\leq\rho R^n\leq1.

These masses never decrease. At a change the old guess becomes the new loser, and its mass stays the same, because aρRk−1=(1−a)ρRka\rho R^{k-1}=(1-a)\rho R^k. The new guess receives the released mass ρRk−ρRk−1\rho R^k-\rho R^{k-1} and moves from (1−a)ρRk−1(1-a)\rho R^{k-1} to aρRka\rho R^k. So (ℓ0,ℓ1)(\ell_0,\ell_1) is a mass program, and Lemma 4.6 turns it into a machine. If gg makes k≤nk\leq n changes on xx, the machine has Phalt(x)=ρRk≥ρP_{\mathrm{halt}}(x)=\rho R^k\geq\rho, and the correct output, which is the final guess, has conditional probability exactly aa. So (Hρ)(H_\rho) and (Cη)(C_\eta) hold. The case ρRn=1\rho R^n=1 is included: the total mass may then reach one.

Corollary 4.8 (Exact thresholds). Let ρ∈(0,1)\rho\in(0,1) and η∈(0,1/2)\eta\in(0,1/2) be rationals, and a=12+ηa=\frac{1}{2}+\eta.

  1. Under (Hρ)(H_\rho) and (Cη)(C_\eta) the decided languages are exactly the decidable languages if and only if ρa>1−a\rho a>1-a.

  1. If ρa=1−a\rho a=1-a, then n(ρ,η)=1n(\rho,\eta)=1, and the halting problem is decided under (Hρ)(H_\rho) and (Cη)(C_\eta).

  1. The class can only grow as ρ\rho or η\eta decreases, and every norm occurs: n(2−j,1/6)=jn(2^{-j},1/6)=j for every j≥0j\geq0. The union of the classes over all rational pairs (ρ,η)(\rho,\eta) is btt(HALT).

  1. Pairs with different values of n(ρ,η)n(\rho,\eta) decide different classes: for every n≥0n\geq0 some language has a truth-table reduction to HALT with n+1n+1 queries but none with nn queries.

Proof. (1) n(ρ,η)=0n(\rho,\eta)=0 exactly when ρR>1\rho R>1, that is ρa>1−a\rho a>1-a, and a reduction with zero queries is a decider. If ρa≤1−a\rho a\leq1-a, then n≥1n\geq1 and the class contains HALT, which is undecidable. (2) If ρa=1−a\rho a=1-a, then ρR=1\rho R=1 and ρR2=R>1\rho R^2=R>1. (3) The function nn does not increase in ρ\rho, and RR increases with η\eta. For η=1/6\eta=1/6 we have a=2/3a=2/3 and R=2R=2, so 2−jRj=12^{-j}R^j=1 and 2−jRj+1=22^{-j}R^{j+1}=2. Every language in btt(HALT) has some norm jj, and Theorem 4.7 decides it with the pair (2−j,1/6)(2^{-j},1/6); conversely each pair gives a bounded norm.

(4) By Lemma 4.5(1) it suffices to build a computable approximation GG with at most n+1n+1 mind changes whose limit has no computable approximation with at most nn changes. Enumerate the partial computable functions φe\varphi_e of two arguments, and identify inputs with natural numbers as in the proof of Corollary 3.3. At input ee and stage tt, let ss be the largest number such that φe(e,0),…,φe(e,s)\varphi_e(e,0),\ldots,\varphi_e(e,s) all halt within tt steps with values in {0,1}\{0,1\}. If there is no such ss, put G(e,t)=0G(e,t)=0. Otherwise, if these values contain at most nn changes, put G(e,t)=1−φe(e,s)G(e,t)=1-\varphi_e(e,s), and if they contain more, keep G(e,t)=G(e,t−1)G(e,t)=G(e,t-1). The first value seen moves GG at most once, and each of the at most nn followed changes of φe\varphi_e moves it once; nothing moves it afterwards. So GG changes at most n+1n+1 times and converges. If a total φe\varphi_e approximated the limit with at most nn changes, then at input ee the value G(e,t)G(e,t) would equal 1−φe(e,s)1-\varphi_e(e,s) for all large tt, and the two limits would differ.

The excluded endpoints fit the same formula. As η\eta tends to 1/21/2 the ratio RR grows without bound, and at ρ=1\rho=1 no power RjR^j with j≥1j\geq1 fits under one; in both cases n=0n=0, which matches Propositions 4.3 and 4.4.

An example. Take floor ρ=1/4\rho=1/4 and margin η=1/6\eta=1/6, so a=2/3a=2/3 and R=2R=2. Then ρR2=1\rho R^2=1 and ρR3=2\rho R^3=2, so exactly two queries are needed. The lower-bound machine for an approximation that starts at 0 gives mass 1/61/6 to output 0 and 1/121/12 to output 1. A first change raises the mass of output 1 to 1/31/3, and a second change raises the mass of output 0 to 2/32/3. At each moment the current guess holds exactly two thirds of the halting mass. The halting problem itself needs one query, and it is decided with floor 1/21/2 and margin 1/61/6. Guess 0 with mass 1/31/3 against 1/61/6; when the queried run is seen to halt, raise the mass of output 1 to 2/32/3. By Corollary 4.8(1), no pair with ρ(12+η)>12−η\rho(\frac{1}{2}+\eta)>\frac{1}{2}-\eta decides it.

Computable guarantees

Without a floor, a positive halting probability still supplies one input by input. This turns Theorem 4.7 into a statement about truth-table reductions.

Proposition 4.9 (Computable guarantees). For a language LL, the following are equivalent.

  1. L≤ttHALTL \le_{\mathrm{tt}} \mathrm{HALT}.

  2. LL is decided under (H0)(H_0) and (Ceff)(C_{\mathrm{eff}}).

  3. LL is decided under (Cη)(C_\eta) together with (H0)(H_0) or a computable floor, for some, equivalently every, rational η∈(0,1/2)\eta\in(0,1/2).

  4. LL is decided under a computable floor and (Ceff)(C_{\mathrm{eff}}).

  5. LL is decided under (Hρ)(H_\rho) and (Ceff)(C_{\mathrm{eff}}), for some, equivalently every, rational ρ∈(0,1)\rho\in(0,1).

All transformations are effective.

Proof. From (2) to (1). Let MM satisfy (H0)(H_0) and (Ceff)(C_{\mathrm{eff}}) with margin η(x)\eta(x). Search for the first stage t1(x)t_1(x) with Pt1(x)>0P_{t_1}(x)>0; it exists by (H0)(H_0), and an algorithm finds it. Then ρ(x)=Pt1(x)/2\rho(x)=P_{t_1}(x)/2 is a computable floor with values in (0,1/2](0,1/2]. Run the upper-bound construction of Theorem 4.7 on input xx with ρ(x)\rho(x) and η(x)\eta(x) in place of the constants. Every quantity in it is a total computable function of xx, so the result is a computable approximation with at most n(ρ(x),η(x))n(\rho(x),\eta(x)) changes, a computable bound, and Lemma 4.5(2) gives the reduction.

The conditions (3), (4) and (5) each imply (2): a fixed margin below one half is a computable margin, and a floor of either kind implies (H0)(H_0).

From (1) to (3), for any prescribed η\eta. Lemma 4.5(2) gives an approximation with at most h(x)h(x) changes, hh computable. Put ρ(x)=R−h(x)−1\rho(x)=R^{-h(x)-1}, a computable floor with n(ρ(x),η)≥h(x)n(\rho(x),\eta)\ge h(x). The lower-bound construction of Theorem 4.7, run input by input, gives a machine with Phalt(x)≥ρ(x)>0P_{\mathrm{halt}}(x)\ge\rho(x)>0 and conditional correctness exactly 12+η\frac{1}{2}+\eta.

From (1) to (5), for any prescribed ρ\rho. With hh as before, search for the least m≥2m\ge2 such that η(x)=2−m\eta(x)=2^{-m} satisfies ρR(x)h(x)≤1\rho R(x)^{h(x)}\le1, where R(x)=(1+2η(x))/(1−2η(x))R(x)=(1+2\eta(x))/(1-2\eta(x)); it exists because R(x)→1R(x)\to1 as mm grows. Then n(ρ,η(x))≥h(x)n(\rho,\eta(x))\ge h(x), and the lower-bound construction gives a machine under (Hρ)(H_\rho) with computable margin η(x)\eta(x). A constant floor is a computable floor, so (4) follows as well.

Aaronson et al. proved the case of a factor two: machines whose correct output is more than twice as likely as the wrong one, that is, with q(x)>2/3q(x)>2/3, decide exactly tt⁡(HALT)\operatorname{tt}(\mathrm{HALT}) [2 Proposition 9.2]. The factor two plays no special role.

Corollary 4.10 (Any fixed factor). Let c>1c>1 be a real number. The languages decided by machines whose correct output is, on every input, more than cc times as likely as the wrong one are exactly the languages in tt⁡(HALT)\operatorname{tt}(\mathrm{HALT}).

Proof. Such a machine halts with positive probability, since otherwise both outputs have probability zero, and its conditional correctness satisfies q(x)>c/(1+c)q(x)>c/(1+c). Choose a rational η\eta with 0<η≤c/(1+c)−1/20<\eta\le c/(1+c)-1/2. Then (H0)(H_0) and (Cη)(C_\eta) hold, and Proposition 4.9 gives L≤ttHALTL\le_{\mathrm{tt}}\mathrm{HALT}. Conversely, choose a rational η<1/2\eta<1/2 with 1/2+η>c/(1+c)1/2+\eta>c/(1+c). By Proposition 4.9(3), every L≤ttHALTL\le_{\mathrm{tt}}\mathrm{HALT} is decided by a machine with (H0)(H_0) and conditional correctness exactly 1/2+η1/2+\eta, so its correct output is more than cc times as likely as the wrong one.

For c=2c=2 this is [2 Proposition 9.2]. The proof above reaches every factor directly, without repeating the machine.

The ladder

Theorem 4.11 (The reducibility ladder). Consider machines as in Definition 3.1, under the pairs of guarantees of Table 1.

  1. Under (C0) and (Hc), in particular under (H1), and under (H0) with zero error, the decided languages are exactly the decidable languages (Propositions 4.3 and 4.4).

  1. For each prescribed pair of rationals ρ∈(0,1)\rho\in(0,1) and η∈(0,1/2)\eta\in(0,1/2), the decided languages are exactly those with a truth-table reduction to HALT\mathrm{HALT} of at most n(ρ,η)n(\rho,\eta) queries (Theorem 4.7). The union over all pairs is btt⁡(HALT)\operatorname{btt}(\mathrm{HALT}) (Corollary 4.8).

  1. Under a prescribed or computable margin with (H0) or a computable floor, and under a computable margin with a fixed floor, the decided languages are exactly tt⁡(HALT)\operatorname{tt}(\mathrm{HALT}) (Proposition 4.9).

  1. Under (C0) together with (H0) or any fixed floor ρ<1\rho< 1, the decided languages are exactly Δ20\Delta^{0}_{2} (Theorem 3.2).

All transformations are effective, and each containment in

decidable⁡⊊btt⁡(HALT)⊊tt⁡(HALT)⊊Δ20\operatorname{decidable} \subsetneq\operatorname{btt}(\mathrm{HALT}) \subsetneq\operatorname{tt}(\mathrm{HALT}) \subsetneq\Delta^{0}_{2}

is strict by Proposition 4.12.

Proposition 4.12. The chain decidable⁡⊊btt⁡(HALT)⊊tt⁡(HALT)⊊Δ20\operatorname{decidable} \subsetneq\operatorname{btt}(\mathrm{HALT}) \subsetneq\operatorname{tt}(\mathrm{HALT}) \subsetneq\Delta^{0}_{2} is strict at each step.

Proof. First, HALT≤bttHALT\mathrm{HALT} \le_{\mathrm{btt}} \mathrm{HALT} with one query: the reduction asks whether the input pair itself halts and returns the answer. The halting problem is undecidable (§ 2), which separates the first step.

Second, we diagonalize against all bounded norms. Identify inputs with pairs ⟨e,k⟩\langle e,k\rangle of natural numbers, composing the input numbering from the proof of Corollary 3.3 with a computable pairing. Let v(⟨e,k⟩,t)v(\langle e,k\rangle,t) be the following computable value. Simulate program ee on input ⟨e,k⟩\langle e,k\rangle for tt transitions. If the program has halted with a valid description of at most kk halting queries y1,…,yqy_{1},\ldots,y_{q} and a truth table τ\tau, set v=τ(b1,t,…,bq,t)v = \tau(b_{1,t},\ldots,b_{q,t}). Here bj,t=1b_{j,t}=1 iff the run of yjy_{j} halts within tt transitions; otherwise set v=0v=0. Put g=1−vg=1-v. Each sequence bj,⋅b_{j,\cdot} changes at most once, and the description appears at most once, so gg changes at most k+1k+1 times at ⟨e,k⟩\langle e,k\rangle, a computable bound. The value converges: if program ee never returns a valid bounded description, vv is eventually 00. Let A=lim⁡tgA=\lim_{t}g. Then A≤ttHALTA\le_{\mathrm{tt}}\mathrm{HALT} by Lemma 4.5(2). Suppose a bounded truth-table reduction R′R' of norm nn, computed by program ee, decided AA. At x∗=⟨e,n⟩x^{*}=\langle e,n\rangle the program halts with a valid description of at most nn queries, the observed answers stabilize at the true ones, and vv converges to R′(x∗)R'(x^{*}). Then A(x∗)=1−R′(x∗)A(x^{*})=1-R'(x^{*}), contradicting A(x∗)=R′(x∗)A(x^{*})=R'(x^{*}).

Third, Corollary 3.3 constructs a language in Δ20\Delta^{0}_{2} outside R∥HALT=tt⁡(HALT)R_{\parallel}^{\mathrm{HALT}}=\operatorname{tt}(\mathrm{HALT}), which separates the last step.

Row (2) of the ladder runs through the finite levels of the Ershov hierarchy (§ 2), one norm at a time; row (3) is its ω\omega-level and row (4) the full limit-lemma level. The floor and the margin are two ways to bound the number of mind changes. Theorem 4.7 says how they combine: each change multiplies the halting mass by at least R=a/(1−a)R=a/(1-a), and the mass never exceeds one.

Oracles, nesting and the arithmetic hierarchy

Every class of Section 4 sits between the decidable languages and Δ20\Delta^{0}_{2}. This section asks what an oracle changes. With an oracle AA, a function can be computed by an ordinary algorithm or by one that also consults AA. The second can do more, so each guarantee and each reduction must say which computes it. With this settled, Theorem 5.4 gives the exact relativized classification, Theorem 5.7 the classes of nested machines, and Proposition 5.8 separates them. Oracle answers are exact throughout.

Machines with an oracle

Definition 5.1 (Probabilistic machine with an oracle). A probabilistic oracle machine with oracle AA is a finite-program machine as in Definition 3.1 whose transitions may also submit a query yy and then receive the exact bit 1A(y)1_A(y) in one step. At most one new coin is used per transition. On input xx, the numbers pi(x)p_i(x), phalt(x)p_{\mathrm{halt}}(x) and q(x)q(x) are defined as before.

The guarantees of Definitions 4.1 and 4.2 apply to these numbers, and we fix who computes each of them. Prescribed floors and margins are rational constants. A computable floor or margin is computed by an ordinary algorithm, without access to AA. A floor or margin computable from AA is computed by an algorithm with oracle AA; this is a weaker requirement, and row (4) of Theorem 5.4 shows that it gives a larger class. In (Hc), the halting probability must be computable from AA.

Simulating tt transitions and answering every query with the oracle computes pi,t(x)p_{i,t}(x) as a dyadic rational, and pi,t↑pip_{i,t} \mathrel{\uparrow} p_i as before. Every construction of Sections 3 and § 4 either reads a machine only through these simulations, or builds a machine that computes a given approximation or mass program (Lemma 4.6). Each therefore relativizes: give the program the oracle AA and change nothing else.

Definition 5.2 (Iterates). The jump of a language AA is

A′={⟨e,w⟩:PeA(w) halts},A' = \{\langle e,w\rangle: P_e^A(w)\text{ halts}\},

the halting problem of oracle machines with oracle AA. Put ∅(0)=∅\varnothing^{(0)}=\varnothing and ∅(k+1)=(∅(k))′\varnothing^{(k+1)}=(\varnothing^{(k)})', and let Δk+10\Delta^0_{k+1} be the class of languages Turing reducible to ∅(k)\varnothing^{(k)}. A language LL is many-one reducible to BB, written L≤mBL \le_m B, if a total computable ff satisfies 1L(x)=1B(f(x))1_L(x)=1_B(f(x)) on every input; this is a truth-table reduction with one query.

The paper uses one enumeration of programs, and an ordinary program is one without query instructions, so its run ignores the oracle. An oracle program run with oracle ∅\varnothing behaves exactly like the ordinary program obtained by answering every query with 00, and this replacement is computable. Hence HALT and ∅(1)\varnothing^{(1)} are many-one reducible to each other, and the reducibility classes above one coincide with those above the other, with unchanged numbers of queries. In particular Δ20\Delta^0_2, as defined in § 2, is Turing reducibility to ∅(1)\varnothing^{(1)}.

Who computes the reduction. For languages AA and BB we use three kinds of truth-table reductions to BB. In tt⁡(B)\operatorname{tt}(B) and btt⁡(B)\operatorname{btt}(B) an ordinary algorithm computes the queries, their number and table, as in § 2; btt⁡n(B)\operatorname{btt}_n(B) is the part of btt⁡(B)\operatorname{btt}(B) with at most nn queries on every input. In tt⁡A(B)\operatorname{tt}^A(B) an algorithm with oracle AA computes them. The superscript records who computes the questions, not which oracle is queried. It matters: with the help of AA one can write down questions that no ordinary algorithm can. Finally, MC⁡n(A)\operatorname{MC}_n(A) is the class of languages with an approximation computable from AA that makes at most nn mind changes on every input, from a free start. By Lemma 4.5, MC⁡n(∅)=btt⁡n(HALT)\operatorname{MC}_n(\varnothing)=\operatorname{btt}_n(\mathrm{HALT}). This is the class that a prescribed pair of constants decides in Theorem 5.4(2): the approximation read off an oracle machine is computed from AA, not by an ordinary algorithm.

Lemma 5.3 (Bridge lemma with an oracle). Let AA and LL be languages and n≥0n \ge0.

(1) L∈MCn(A)L \in\mathrm{MC}_n(A) if and only if LL has a truth-table reduction to A′A' with at most nn queries, in which an ordinary algorithm computes the queries and an algorithm with oracle AA computes the table.

(2) bttn(A′)⊆MCn(A)⊆bttn+1(A′)\mathrm{btt}_n(A') \subseteq\mathrm{MC}_n(A) \subseteq\mathrm{btt}_{n+1}(A').

(3) LL has an approximation computable from AA whose mind changes are bounded by a function computed by an ordinary algorithm if and only if L∈tt(A′)L \in\mathrm{tt}(A'). It has one with a bound computable from AA if and only if L∈ttA(A′)L \in\mathrm{tt}^{A}(A').

All directions are effective.

The extra query in part (2) is needed for the starting value. An approximation computable from AA may start at a value that only AA can compute, so an ordinary reduction must ask A′A' for it. For n=0n = 0 the two ends differ for every undecidable AA: MC0(A)\mathrm{MC}_0(A) is the class of languages computable from AA, while btt0(A′)\mathrm{btt}_0(A') is the class of decidable languages. Appendix § 8 proves the lemma, together with the limit lemma relative to an oracle (Lemma A.2): LL is Turing reducible to A′A' if and only if LL has an approximation computable from AA.

The relativized classification

Theorem 5.4 (Relativized ladder). Fix a language AA and consider probabilistic oracle machines with oracle AA.

(1) Under (C0) with a halting probability computable from AA, and under (H0) with zero error, the decided languages are exactly those computable from AA.

(2) For each prescribed pair of rationals ρ∈(0,1)\rho\in(0, 1) and η∈(0,1/2)\eta\in(0, 1/2), with n=n(ρ,η)n = n(\rho, \eta), the decided languages are exactly MCn(A)\mathrm{MC}_n(A). So they include bttn(A′)\mathrm{btt}_n(A') and are included in bttn+1(A′)\mathrm{btt}_{n+1}(A'), and their union over all pairs is btt(A′)\mathrm{btt}(A').

(3) Under a computable margin with a fixed or computable floor, and under a computable floor with a fixed margin, the decided languages are exactly tt(A′)\mathrm{tt}(A').

(4) Under (H0) with a fixed or computable margin, the decided languages are exactly ttA(A′)\mathrm{tt}^{A}(A'). The same holds in row (3) when the floor or the margin is only computable from AA.

(5) Under (C0) with (H0) or a fixed floor ρ<1\rho< 1, the decided languages are exactly those Turing reducible to A′A'.

All transformations are effective. For A=∅A = \varnothing each row is the corresponding row of Theorem 4.11, and rows (3) and (4) give the same class.

Appendix § 8 gives the proof; Table 3 lists the rows. The construction of Theorem 4.7 relativizes: run with oracle AA, it gives an approximation computable from AA with at most n(ρ,η)n(\rho, \eta) changes. Its first value is read at the first stage that meets both thresholds, and finding that stage needs the oracle; hence row (2) gives MCn(A)\mathrm{MC}_n(A), not bttn(A′)\mathrm{btt}_n(A'). In row (3) an ordinary algorithm computes the change bound n(ρ(x),η(x))n(\rho(x), \eta(x)); in row (4) the floor comes from the first stage with positive halting mass, which needs the oracle.

Halting requirementConfidence requirementLanguages decided
PhaltP_{\mathrm{halt}} computable from AA(C0)computable from AA
(H0)zero errorcomputable from AA
the prescribed floor ρ\rhothe prescribed margin η\etaMCn(ρ,η)(A)\mathrm{MC}_{n(\rho,\eta)}(A), between bttn(A′)\mathrm{btt}_{n}(A') and bttn+1(A′)\mathrm{btt}_{n+1}(A')
some fixed floorsome fixed marginbtt(A′)\mathrm{btt}(A')
fixed or computable floorcomputable margin, or fixed margin with a computable floortt(A′)\mathrm{tt}(A')
(H0), or a floor computable from AAfixed or computable margin, or one computable from AAttA(A′)\mathrm{tt}^{A}(A')
(H0) or a fixed floor ρ<1\rho< 1(C0)Turing reducible to A′A'

Table 3. The relativized classification of Theorem 5.4. The machine has oracle AA; every reduction queries A′A'. “Computable” means computed by an ordinary algorithm. (C0) asks for a strict conditional majority, (H0) asks only that the machine halt with positive probability, and MCn(A)\mathrm{MC}_{n}(A) is defined before Lemma 5.3.

Nesting

Here nested postselection means that the oracle of a machine is itself decided by a machine of the same kind, under the same guarantees. Every level reads the level below through exact oracle answers and postselects its own run on halting.

Definition 5.5 (Depth-kk machines). A depth-one machine is a machine as in Definition 3.1. For k≥1k \ge1, a depth-(k+1)(k+1) machine is a pair (M,N)(M,N): NN is a depth-kk machine, which decides a language BB, and MM is a probabilistic oracle machine with oracle BB. The pair decides the language that MM decides. A row of guarantees holds at depth k+1k+1 if MM satisfies the row relative to BB, as fixed after Definition 5.1, and the same row holds for NN at depth kk. Prescribed constants are the same at all depths. Computable functions in a row, such as a margin or a floor, may differ from one depth to the next.

Remark 5.6 (Nesting by running the inner machine). Definition 5.5 gives each level exact membership answers. Suppose instead that the outer machine runs the inner machine as a subroutine on each query, uses its output, and runs forever when the inner run does. The whole computation is then one machine as in Definition 3.1, so under a strict conditional majority it decides a language in Δ20\Delta^{0}_{2} by Theorem 3.2, at any depth. Exact oracle answers are what let nesting climb the hierarchy.

Theorem 5.7 (Nesting). Consider depth-kk machines, with the rows of Theorem 5.4 read as in Definition 5.5. For every k≥1k \ge1:

  1. under (C0) with a computable halting probability, and under (H0) with zero error, the decided languages are the decidable ones;

  1. for a prescribed pair (ρ,η)(\rho,\eta) with n=n(ρ,η)n=n(\rho,\eta), the decided languages are the decidable ones if n=0n=0, and exactly MCn(∅(k−1))\mathrm{MC}_{n}(\varnothing^{(k-1)}) if n≥1n \ge1. The latter class lies between bttn(∅(k))\mathrm{btt}_{n}(\varnothing^{(k)}) and bttn+1(∅(k))\mathrm{btt}_{n+1}(\varnothing^{(k)}), and it equals bttn(HALT)\mathrm{btt}_{n}(\mathrm{HALT}) at k=1k=1. The union over all pairs is btt(∅(k))\mathrm{btt}(\varnothing^{(k)});

  1. under the computable guarantees of row (3), they are exactly tt(∅(k))\mathrm{tt}(\varnothing^{(k)});

  1. under (H0) with a fixed or computable margin, they are exactly tt∅(k−1)(∅(k))\mathrm{tt}^{\varnothing^{(k-1)}}(\varnothing^{(k)}), which is tt(HALT)\mathrm{tt}(\mathrm{HALT}) at k=1k=1;

  1. under (C0) with (H0) or a fixed floor ρ<1\rho<1, they are exactly Δk+10\Delta^{0}_{k+1}.

Rows (3) to (5), and row (2) when n≥1n \ge1, contain Δk0\Delta^{0}_{k}. All transformations are effective.

The proof, in Appendix A, is an induction on kk. For the upper bounds, the oracle BB of a depth-(k+1)(k+1) machine lies in a depth-kk class, hence is Turing reducible to ∅(k)\varnothing^{(k)}, so an approximation computable from BB is computable from ∅(k)\varnothing^{(k)}. For the lower bounds, take B=∅(k)B=\varnothing^{(k)}, which is decided at depth kk under every row except row (1) and row (2) with n=0n=0. This is where n≥1n \ge1 is needed: ∅(k)\varnothing^{(k)} has an approximation computable from ∅(k−1)\varnothing^{(k-1)} with one mind change, and none with zero.

Strictness, and what the oracle changes

Proposition 5.8. For every k≥2k \ge2,

decidable⊊btt(∅(k))⊊tt(∅(k))⊊tt∅(k−1)(∅(k))⊊Δk+10.\mathrm{decidable} \subsetneq\mathrm{btt}(\varnothing^{(k)}) \subsetneq\mathrm{tt}(\varnothing^{(k)}) \subsetneq\mathrm{tt}^{\varnothing^{(k-1)}}(\varnothing^{(k)}) \subsetneq\Delta^{0}_{k+1}.

At depth one the third and fourth classes coincide.

The first separation is witnessed by ∅(k)\varnothing^{(k)} itself, the second repeats the diagonal of Proposition 4.12 relative to ∅(k−1)\varnothing^{(k-1)}, and the last repeats the diagonal of Corollary 3.3 with oracle ∅(k)\varnothing^{(k)}; the details are in Appendix A. The third separation is the new one, and it follows from the next lemma with A=∅(k−1)A = \varnothing^{(k-1)}, which computes HALT when k≥2k \ge2.

Lemma 5.9. If HALT≤TA\mathrm{HALT} \leq_T A, then tt(A′)⊊ttA(A′)\mathrm{tt}(A') \subsetneq\mathrm{tt}^{A}(A').

Proof. The inclusion is clear, since an ordinary algorithm ignores its oracle. Identify inputs with natural numbers as in the proof of Corollary 3.3, and let PeP_e be the ee-th ordinary program. Define LL by an algorithm with oracle AA. On input ee, use AA to decide whether Pe(e)P_e(e) halts with a valid description of a list of queries y1,…,ymy_1,\ldots,y_m to A′A' and a table τ\tau. If it does, output the same queries with the table 1−τ1-\tau; otherwise output no queries and the constant table 0. This is a truth-table reduction to A′A' computed with oracle AA, so L∈ttA(A′)L \in\mathrm{tt}^{A}(A'). If PeP_e computed an ordinary truth-table reduction of LL to A′A', then Pe(e)P_e(e) would halt with a valid description, and 1L(e)=1−τ(1A′(y1),…,1A′(ym))≠1L(e)1_L(e) = 1 - \tau(1_{A'}(y_1),\ldots,1_{A'}(y_m)) \neq1_L(e).

At depth one, rows (3) and (4) give the same class: with or without a computable floor, a computable margin decides tt(HALT)\mathrm{tt}(\mathrm{HALT}). From depth two on, dropping the floor enlarges the class. With the floor, row (3) of Table 4 still yields reductions that an ordinary algorithm computes. Without it, row (4) yields reductions that need the oracle ∅(k−1)\varnothing^{(k-1)} to write down their questions, and the class is strictly larger. So from depth two on, it matters who can compute the halting floor, a distinction that no one-level analysis can see.

Nested postselection of Theorem 5.7: the languages decided at depth kk under each row of guarantees, required at every depth. (C0) asks for a strict conditional majority, (H0) asks only that the machine halt with positive probability, zero error asks that every halting run be correct, and MCn_n is as in Table 3. At k=1k = 1 rows four and five coincide.

Guarantees at every depthLanguages decided at depth kk
(C0) and computable PhaltP_{\mathrm{halt}}; or (H0) and zero errordecidable
the prescribed pair (ρ,η)(\rho,\eta), n=n(ρ,η)n = n(\rho,\eta)decidable if n=0n = 0; MCn(∅(k−1))\mathrm{MC}_n(\varnothing^{(k-1)}) if n≥1n \ge1
some fixed pairbtt(∅(k))\mathrm{btt}(\varnothing^{(k)})
computable guarantees of row (3)tt(∅(k))\mathrm{tt}(\varnothing^{(k)})
(H0) and a fixed or computable margintt∅(k−1)(∅(k))\mathrm{tt}^{\varnothing^{(k-1)}}(\varnothing^{(k)})
(C0), and (H0) or a fixed floor ρ<1\rho< 1Δk+10\Delta^{0}_{k+1}

Table 4. Nested postselection of Theorem 5.7: the languages decided at depth kk under each row of guarantees, required at every depth. (C0) asks for a strict conditional majority, (H0) asks only that the machine halt with positive probability, zero error asks that every halting run be correct, and MCn_n is as in Table 3. At k=1k = 1 rows four and five coincide.

The comparison with Deutschian computation has the same shape as our row (5). Raat shows that a Turing machine with nested Deutschian closed timelike curves of depth dd decides every language Turing reducible to ∅(d)\varnothing^{(d)}, with a fixed error margin [15 Theorem 1]. The matching upper bound adapts the quantum proof of Aaronson et al., and the corrected version of their paper records the full classification [2 Section 3]. His rule is causal consistency, not postselection, and his thesis treats no postselection. Our row (5) reaches the same classes, Δk+10\Delta^{0}_{k+1} at depth kk, for postselection on halting with unbounded error, with a proof inside the classical machinery of Sections 3 and 4. The bounded-error rows show a difference that his model does not have. Under Deutschian nesting, a fixed margin still reaches all of Δd+10\Delta^{0}_{d+1}. Under postselection on halting, a fixed margin at depth kk reaches only the class of row (4), strictly inside Δk+10\Delta^{0}_{k+1}, and a prescribed floor shrinks it further to the class of row (2).

Quantum machines

Aaronson et al. proved the classification for Deutsch’s rule for quantum as well as classical machines, with the same class Δ20\Delta^0_2 in both cases [2 Theorems 3.2 and 3.3]. This section fixes one model of a quantum machine with classical control and shows that quantum and classical machines produce exactly the same output masses. Every result of the paper then holds for quantum machines with the same classes and the same constants.

The model and its masses

Definition 6.1 (Quantum machine). A quantum machine is a deterministic Turing-machine control with a read-only input tape and a work tape. The control acts on a quantum register of qubits, that is, a finite block of quantum bits, and computes the positions of the qubits on its work tape. Each step executes one instruction. An ordinary transition changes the control configuration only. A gate instruction applies one gate of a fixed finite gate set GG of unitary matrices to named qubits; a qubit named for the first time starts in state ∣0⟩\lvert0\rangle. A measurement instruction checks whether one named qubit is 0 or 1, and the control branches on the outcome. The halting test measures a named flag qubit; on outcome 1 it measures a named output qubit and halts with that outcome, and on outcome 0 the run continues. The gate set contains the Hadamard gate HH and the bit flip XX. Every gate entry is a computable complex number, uniformly: an algorithm, given a gate, an entry position and kk, outputs rationals within 2−k2^{-k} of the real and imaginary parts. One constant cGc_G bounds the number of qubits any instruction names. With an oracle AA, the control may also submit queries, as in Definition 5.1.

A history is a finite binary string hh driving a run. The control consumes one bit of hh at each measurement and at each halting test. A halting test that returns flag 1 consumes one further bit, the output, and halts. Define unnormalized vectors u~h\widetilde{u}_h along the driven run, starting from the all-zero register state, which has norm one. A gate instruction multiplies by the gate extended with identities, fresh qubits included. A measurement with outcome bb multiplies by the projector ∣b⟩⟨b∣\lvert b\rangle\langle b\rvert. The weight of hh is W(h)=∥u~h∥2W(h)=\lVert\widetilde{u}_h\rVert^2, and hh is a complete history when the driven run halts right after consuming its last bit. Define

pi,t(x)=∑h complete, halting with output iwithin t stepsW(h),pi(x)=lim⁡tpi,t(x),Phalt=p0+p1,p_{i,t}(x)=\sum_{\substack{h\ \mathrm{complete,\ halting\ with\ output}\ i\\ \mathrm{within}\ t\ \mathrm{steps}}}W(h),\qquad p_i(x)=\lim_{t}p_{i,t}(x),\qquad P_{\mathrm{halt}}=p_0+p_1,

and q(x)=p1L(x)(x)/Phalt(x)q(x)=p_{1L(x)}(x)/P_{\mathrm{halt}}(x). The answer rule and the guarantees of Definitions 4.1 and 4.2 apply verbatim to these numbers.

Lemma 6.2 (Masses). For every quantum machine, the finite-time mass pi,t(x)p_{i,t}(x) is nondecreasing in tt, with p0,t+p1,t≤1p_{0,t}+p_{1,t}\leq1, and it is a computable real, uniformly in xx, tt and ii. With an oracle AA, it is computable from AA. Consequently the eventual masses p0(x)p_0(x) and p1(x)p_1(x) are left-computably enumerable reals, uniformly in xx (relative to AA when there is an oracle).

The eventual masses need not be computable, for quantum and classical machines alike: by Proposition 4.3, the machine that Theorem 3.2 builds for an undecidable language does not have a computable halting probability. Appendix § 9 proves Lemma 6.2 and the next lemma.

Lemma 6.3 (Hadamard simulation). From the code of a classical machine (Definition 3.1) or of an oracle machine (Definition 5.1), one computes a quantum machine, with the same oracle, that has the same masses p0p_0 and p1p_1 on every input.

Classical simulation, and the transfer

Lemma 6.4 (Classical simulation). From the code of a quantum machine one computes a classical machine (Definition 3.1) that has the same masses p0p_0 and p1p_1 on every input. With an oracle AA, the classical machine is an oracle machine with oracle AA.

Proof. By Lemma 6.2, compute rationals ri,sr_{i,s} with ∣ri,s−pi,s(x)∣≤2−s−2\lvert r_{i,s}-p_{i,s}(x)\rvert\le2^{-s-2}, and put ci,s=ri,s−2−s−1c_{i,s}=r_{i,s}-2^{-s-1}, so that pi,s−3⋅2−s−2≤ci,s<pi,sp_{i,s}-3\cdot2^{-s-2}\le c_{i,s}<p_{i,s}. Let

ℓi(x,t)=max⁡{0,ci,0,ci,1,…,ci,t}.\ell_i(x,t)=\max\{0,c_{i,0},c_{i,1},\ldots,c_{i,t}\}.

These rationals are computable and nondecreasing in tt. Since pi,sp_{i,s} is nondecreasing, ℓi(x,t)≤pi,t(x)\ell_i(x,t)\le p_{i,t}(x), so ℓ0+ℓ1≤p0,t+p1,t≤1\ell_0+\ell_1\le p_{0,t}+p_{1,t}\le1, and (ℓ0,ℓ1)(\ell_0,\ell_1) is a mass program. Its limits are the eventual masses: ℓi(x,t)≤pi(x)\ell_i(x,t)\le p_i(x), and ℓi(x,t)≥ci,t≥pi,t(x)−3⋅2−t−2→pi(x)\ell_i(x,t)\ge c_{i,t}\ge p_{i,t}(x)-3\cdot2^{-t-2}\to p_i(x). Lemma 4.6 turns the mass program into a classical machine with masses exactly p0p_0 and p1p_1. With an oracle, every step is computed from AA.

Theorem 6.5 (The classes are unchanged). Every result of Sections 3 to 5 holds verbatim for quantum machines, with or without an oracle and at every depth of nesting, with the same classes and the same constants. In particular, Theorem 4.7 holds for quantum machines with the same number n(ρ,η)n(\rho,\eta) of queries.

Proof. The answer rule and every guarantee are statements about the two mass functions p0p_0 and p1p_1 of a machine, and, in (Hc)(\mathrm{H_c}), about an algorithm that approximates their sum. By Lemmas 6.3 and 6.4, classical and quantum machines with oracle AA realize exactly the same pairs of mass functions, and one computes each machine from the other. So a language is decided under a given row of guarantees by a quantum machine if and only if it is decided under the same row by a classical machine, and every transformation stays effective. For nested machines, convert each level separately: the conversion keeps the masses relative to the oracle of that level, and so keeps the row at every depth.

For the upper bounds, the classical simulation saves us from redoing the constructions that read masses. For general gate sets the finite-time masses are computable reals rather than dyadic rationals, and a comparison between them need not be decidable. For the lower bounds, one measured Hadamard gate already produces a fair coin.

Comparison with Deutsch’s rule, and open questions

Combining Theorem 3.2 with [2 Theorem 3.2] gives an equality of language classes: unrestricted classical computation under Deutsch’s rule and unbounded-error postselection on halting both give Δ20\Delta^0_2. With bounded error the two rules part. Deutsch’s rule still gives Δ20\Delta^0_2, while postselection on halting gives the truth-table reductions to HALT, and with a prescribed floor and margin only n(ρ,η)n(\rho,\eta) nonadaptive queries (Theorem 4.7). Table 5 collects these results for both rules. Its first three columns separate the three things that a setting fixes: the time bound of the machine, the information that the loop carries, and the error model.

The table shows where the two rules diverge. With polynomial time and polynomial loops, and with no bounds at all, Deutsch’s rule gives one class whatever the error model. For one time-traveling bit the class depends on the error model of the underlying machine [16]. Postselection on halting splits by confidence and by the halting floor, and Theorem 4.7 gives the exact class for each choice of the two. From depth two on, it also matters who can compute the floor. Under nesting the rules differ most. With a fixed margin and no floor, postselection at depth kk decides a class strictly inside Δk+10\Delta^0_{k+1} (Proposition 5.8). Deutschian nesting with a fixed margin still decides every language Turing reducible to ∅(k)\varnothing^{(k)} {[15 Theorem 1]}.

The polynomial-time setting provides a useful contrast. Let NP\mathbf{NP} denote nondeterministic polynomial time, PP\mathbf{PP} unbounded-error probabilistic polynomial time, and PNP\mathbf{P}^{\mathbf{NP}} polynomial time with adaptive queries to an NP\mathbf{NP} oracle. Beigel [25] constructs an oracle relative to which PNP⊈PP\mathbf{P}^{\mathbf{NP}}\not\subseteq\mathbf{PP}. Polynomial-time postselection with a strict conditional majority decides exactly PP\mathbf{PP}: replacing every discarded outcome by a fair coin keeps the sign of the difference between the two output probabilities. Relative to Beigel’s oracle, this postselection therefore omits some languages decidable with adaptive NP queries. By Theorem 3.2, postselection on halting decides every language decidable with adaptive halting queries.

One idea runs through all classifications of this paper: probability mass is a budget for mind changes. Under a prescribed floor and margin, each change multiplies the halting mass by at least R=a/(1−a)R = a/(1-a), and the mass never exceeds one, so at most n(ρ,η)n(\rho,\eta) changes fit (Theorem 4.7). Without a floor, the first stage with positive mass supplies a floor input by input (Proposition 4.9). Under a strict majority, weights that shrink geometrically pay for any finite number of changes (Theorem 3.2). Lemma 4.5 then names the reducibility for each budget: a fixed number of changes is a bounded truth-table reduction with exactly that many queries, a computably bounded number a truth-table reduction, and an unbounded number the full Turing reducibility.

Remark 7.1 (Few coins). Suppose every run on inputs of length ℓ\ell tosses at most p(ℓ)p(\ell) coins, for a polynomial pp. Then at most 2p(ℓ)2^{p(\ell)} coin strings exist, the output masses change only when one of them halts, and the sign of p1,t−p0,tp_{1,t}-p_{0,t} changes at most 2p(ℓ)2^{p(\ell)} times. By Lemma 4.5, such machines decide only languages in tt(HALT), even with unbounded error. They do not decide all of it. Enumerate pairs of a machine and a polynomial, and force the ee-th machine to run forever once it exceeds its coin bound. On input ee, follow the sign of the ee-th capped machine’s output difference and output the opposite value. This approximation changes at most 2pe(∣e∣)+12^{p_e(|e|)}+1 times, so its limit is in tt(HALT), and it disagrees at input ee with the ee-th capped machine whenever that machine decides a language under a strict conditional majority. In the other direction, if a computable approximation makes at most p(∣x∣)p(|x|) changes, the machine of Theorem 3.2 needs only the branches J≤p(∣x∣)J \le p(|x|); letting the sampler run forever after p(∣x∣)+1p(|x|)+1 tails in its second phase keeps every weight it uses and tosses at most p(∣x∣)+3p(|x|) + 3 coins.

Open questions

  1. Sampled oracles. Replace exact oracle answers by samples. In a sampled depth-two machine (M,N)(M, N), each query yy of MM is answered by a bit bb drawn with probability pb(y)/Phalt(y)p_b(y)/P_{\mathrm{halt}}(y), where pbp_b and PhaltP_{\mathrm{halt}} are the masses of NN on yy. Every answer is a fresh sample, independent of the coins of MM and of all earlier answers, and every query returns. The masses of MM are taken over its coins and these samples. Which languages do sampled depth-two machines decide under a strict conditional majority at both levels? The same question can be asked at every depth and under each row of guarantees.

  1. Few coins. By Remark 7.1, machines that toss at most polynomially many coins decide, under a strict conditional majority, every language with a computable approximation making polynomially many changes in the input length. They decide only languages with an approximation making at most exponentially many changes. Which class do they decide exactly?

Proofs for Section 5

This appendix proves the results of Section 5. We use the definitions and notation of that section.

Facts about the jump

Lemma A.1 (Jump facts). (1) A≤mA′A \le_m A' for every language AA, by a computable map. Hence ∅(j)≤m∅(k)\emptyset^{(j)} \le_m \emptyset^{(k)} whenever j≤kj \le k, and ∅(k)\emptyset^{(k)} is undecidable for k≥1k \ge1.

(2) If k≥1k \ge1 and L≤T∅(k−1)L \le_T \emptyset^{(k-1)}, then L≤m∅(k)L \le_m \emptyset^{(k)}. So Δk0⊆btt⁡(∅(k))\Delta^0_k \subseteq\operatorname{btt}(\emptyset^{(k)}).

Proof. (1) Let eye_y be the AA-oracle program that, on any input, queries yy and halts exactly if the answer is 1. Then y∈Ay \in A if and only if ⟨ey,0⟩∈A′\langle e_y,0\rangle\in A', and y↦⟨ey,0⟩y \mapsto\langle e_y,0\rangle is computable. Composing along the chain gives ∅(j)≤m∅(k)\emptyset^{(j)} \le_m \emptyset^{(k)}. If ∅(k)\emptyset^{(k)} were decidable, then HALT would be decidable too, being many-one reducible to it, against Section 2.

(2) Let the ∅(k−1)\emptyset^{(k-1)}-oracle program DD decide LL. Let ex′e'_x be the ∅(k−1)\emptyset^{(k-1)}-oracle program that computes D(x)D(x) and halts exactly if the value is 1. Then x∈Lx \in L if and only if ⟨ex′,0⟩∈∅(k)\langle e'_x,0\rangle\in\emptyset^{(k)}, computably in xx. □\square

Lemma A.2 (Limit lemma with an oracle). A language LL is Turing reducible to A′A' if and only if LL has an approximation computable from AA. Both directions are effective.

Proof. Given a reduction, define g(x,t)g(x,t) by simulating it on xx for tt transitions. Answer each submitted query ⟨e,w⟩\langle e,w\rangle by running PeA(w)P^A_e(w) for tt transitions, reporting a halt within them and no otherwise. Output 0 if the simulated run does not halt within its budget. All inner simulations are bounded, so gg is computable from AA. If the run on xx halts within ss transitions, then for all large enough tt every simulated answer is the true one, so g(x,t)g(x,t) stabilizes at 1L(x)1_L(x).

Conversely, let gg be an approximation computable from AA. Let Qx,tQ_{x,t} be the AA-oracle program that hardwires xx and tt, simulates g(x,t),g(x,t+1),…g(x,t), g(x,t+1), \ldots and halts when it finds a stage s>ts > t with g(x,s)≠g(x,t)g(x,s) \ne g(x,t). So Qx,tQ_{x,t} halts exactly if gg changes after tt. A machine with oracle A′A' asks about ⟨Qx,t,ϵ⟩\langle Q_{x,t},\epsilon\rangle for t=0,1,2,…t = 0,1,2,\ldots until the first answer no, say at t0t_0; the search stops because gg converges. It then computes g(x,t0)g(x,t_0) with oracle AA, answering each AA-query yy by one further A′A'-query, of the kind in Lemma A.1(1). No change occurs after t0t_0, so the output is 1L(x)1_L(x). □

This is the limit lemma of Shoenfield [3], stated in § 2, with an oracle; the proof above is direct and uses nothing from outside.

Proof of Lemma 5.3. Let gg be an approximation computable from AA. For each xx and j≥1j \ge1 let Px,jP_{x,j} be the AA-oracle program that hardwires xx and jj, ignores its input, simulates g(x,0),g(x,1),…g(x,0),g(x,1),\ldots with oracle AA, and halts exactly when it observes the jj-th mind change. Let SxS_x be the AA-oracle program that computes g(x,0)g(x,0) and halts exactly if the value is 11. An ordinary algorithm computes the indices of Px,jP_{x,j} and SxS_x from xx and jj. Boolean changes flip the value, so

1L(x)=g(x,0)⊕(mchg(x) mod 2),1_L(x) = g(x,0) \mathbin{\oplus} (m_{\mathrm{chg}}(x) \bmod2),

where ⟨Px,j,ϵ⟩∈A′\langle P_{x,j},\epsilon\rangle\in A' exactly when j≤mchg(x)j \le m_{\mathrm{chg}}(x), and ⟨Sx,ϵ⟩∈A′\langle S_x,\epsilon\rangle\in A' exactly when g(x,0)=1g(x,0) = 1.

(1) If gg makes at most nn changes, query ⟨Px,j,ϵ⟩\langle P_{x,j},\epsilon\rangle for j=1,…,nj = 1,\ldots,n and use the table τx(a1,…,an)=g(x,0)⊕a1⊕⋯⊕an\tau_x(a_1,\ldots,a_n) = g(x,0) \mathbin{\oplus} a_1 \mathbin{\oplus} \cdots\mathbin{\oplus} a_n. The queries are computed ordinarily and the table with oracle AA. Conversely, let a reduction with m(x)≤nm(x) \le n queries y1,…,ymy_1,\ldots,y_m and table τx\tau_x be computed with oracle AA. Each query asks whether an AA-oracle run halts. Let bj,t=1b_{j,t} = 1 if the run of yjy_j halts within tt transitions, and 00 otherwise. Each sequence bj,⋅b_{j,\cdot} is computable from AA, nondecreasing, and changes at most once. So g(x,t)=τx(b1,t,…,bm,t)g(x,t) = \tau_x(b_{1,t},\ldots,b_{m,t}) is computable from AA, changes at most m(x)≤nm(x) \le n times, and converges to 1L(x)1_L(x).

(2) An ordinary reduction is a special case of part (1), which gives the first inclusion. For the second, add the query ⟨Sx,ϵ⟩\langle S_x,\epsilon\rangle to those of part (1) and use the table a0⊕a1⊕⋯⊕ana_0 \mathbin{\oplus} a_1 \mathbin{\oplus} \cdots\mathbin{\oplus} a_n, where a0a_0 is the answer to the new query. Now an ordinary algorithm computes the queries and the table, and there are n+1n+1 queries.

(3) If hh bounds the changes of gg, query ⟨Sx,ϵ⟩\langle S_x,\epsilon\rangle and ⟨Px,j,ϵ⟩\langle P_{x,j},\epsilon\rangle for j=1,…,h(x)j = 1,\ldots,h(x), and combine all answers by exclusive or. Only the length h(x)h(x) of the list may need the oracle; so the reduction lies in tt⁡(A′)\operatorname{tt}(A') when hh is computed ordinarily, and in tt⁡A(A′)\operatorname{tt}^{A}(A') when hh is computed from AA. Conversely, a reduction with m(x)m(x) queries gives, as in part (1), an approximation computable from AA with at most m(x)m(x) changes, and mm is computed by the same kind of algorithm as the reduction. □

Proof of Theorem 5.4

Proof of Theorem 5.4. Throughout, the values pi,t(x)p_{i,t}(x) and Pt(x)P_t(x) are dyadic rationals computed from AA by simulation, and Lemma 4.6 holds with oracle AA.

Row (1). The proof of Proposition 4.3 relativizes word for word. The witness for the halting probability is now an algorithm with oracle AA, the squeeze search terminates as before, and the sign of dd gives a decider computed from AA. The search in the proof of Proposition 4.4 also runs with oracle AA. Conversely, a decider with oracle AA, viewed as a machine that never tosses coins, has Phalt=1P_{\mathrm{halt}} = 1 and q=1q = 1.

Row (2). Let MM satisfy (Hρ)(\mathrm{H}\rho) and (Cη)(\mathrm{C}\eta). The upper-bound construction of Theorem 4.7 compares the values pi,s(x)p_{i,s}(x) and Ps(x)P_s(x) with fixed rationals, so with oracle AA it gives an approximation computable from AA with at most nn changes. Its counting argument uses only the monotonicity of the masses and P≤1P \le1. So L∈MCn(A)L \in\mathrm{MC}_n(A). Conversely, let gg be an approximation of LL computable from AA with at most nn changes. The masses of the lower-bound construction of Theorem 4.7 are then computed from AA, and Lemma 4.6 with oracle AA gives a machine with floor ρ\rho and conditional correctness exactly 12+η\frac{1}{2}+\eta. The inclusions are Lemma 5.3(2). Every nn is n(ρ,η)n(\rho,\eta) for some pair (Corollary 4.8(3)), so the union over all pairs lies between ⋃nbttn(A′)\bigcup_n \mathrm{btt}_n(A') and ⋃nbttn+1(A′)\bigcup_n \mathrm{btt}_{n+1}(A'), both of which are btt(A′)\mathrm{btt}(A').

Row (3). Let ρ(x)\rho(x) and η(x)\eta(x) be the floor and the margin, each a fixed rational or computed by an ordinary algorithm. Run the upper-bound construction of Theorem 4.7 on input xx with these values. The relaxed thresholds and the bound n(ρ(x),η(x))n(\rho(x),\eta(x)) depend only on ρ(x)\rho(x) and η(x)\eta(x), so an ordinary algorithm computes them, while the approximation is computed from AA. Lemma 5.3(3) gives L∈tt(A′)L \in\mathrm{tt}(A'). Conversely, Lemma 5.3(3) gives an approximation computable from AA with changes bounded by an ordinarily computed hh. For a fixed margin η\eta, the floor ρ(x)=R−h(x)−1\rho(x)=R^{-h(x)-1} is computable and n(ρ(x),η)≥h(x)n(\rho(x),\eta)\ge h(x). For a fixed floor ρ\rho, the margin η(x)=2−m\eta(x)=2^{-m}, with m≥2m\ge2 least such that ρR(x)h(x)≤1\rho R(x)^{h(x)}\le1, is computable, as in the proof of Proposition 4.9. In both cases the lower-bound construction of Theorem 4.7, run input by input with oracle AA, and Lemma 4.6 give the machine.

Row (4). Under (H0), search with oracle AA for the first stage t1(x)t_1(x) with Pt1(x)>0P_{t_1}(x)>0; it exists by (H0). The floor ρ(x)=Pt1(x)/2\rho(x)=P_{t_1}(x)/2 is computed from AA. Run the upper-bound construction with ρ(x)\rho(x) and the margin. The approximation and the bound n(ρ(x),η(x))n(\rho(x),\eta(x)) are now computed from AA, and Lemma 5.3(3) gives L∈ttA(A′)L\in\mathrm{tt}^{A}(A'). The same argument applies when the floor or the margin is given but computed only from AA. Conversely, Lemma 5.3(3) gives an approximation computable from AA with a bound hh computed from AA. For a prescribed margin η\eta, the floor R−h(x)−1R^{-h(x)-1} is computed from AA, and the lower-bound construction with Lemma 4.6 gives a machine under (H0) with margin exactly η\eta; its floor is computable from AA. For a fixed floor, choose the margin as in row (3), now with oracle AA.

Row (5). The approximation a(x,t)=1{dt(x)>0}a(x,t)=\mathbf{1}\{d_t(x)>0\} of the proof of Theorem 3.2 is computed from AA and converges to 1L(x)\mathbf{1}_{L}(x), so Lemma A.2 gives a Turing reduction to A′A'. Conversely, such a reduction gives an approximation computable from AA, and the machine of Theorem 3.2, with its padding and with oracle AA, decides LL under (C0) with any fixed floor ρ<1\rho<1.

For A=∅A=\varnothing, MCn(∅)=bttn(HALT)\mathrm{MC}_n(\varnothing)=\mathrm{btt}_n(\mathrm{HALT}) by Lemma 4.5, and tt∅(∅)=tt(HALT)\mathrm{tt}^{\varnothing}(\varnothing)=\mathrm{tt}(\mathrm{HALT}), since an algorithm with oracle ∅\varnothing is effectively an ordinary one. □

Proof of Theorem 5.7

Proof of Theorem 5.7. Each row is proved by induction on kk, both bounds together. At k=1k=1 each row is the corresponding row of Theorem 5.4 with A=∅A=\varnothing. Assume the row at depth kk, and let (M,N)(M,N) be a depth-(k+1)(k+1) machine, with NN deciding BB at depth kk and MM deciding LL.

Row (1). By induction BB is decidable, so computability from BB is ordinary computability, and row (1) of Theorem 5.4 with A=BA=B shows that LL is decidable. Conversely, a decider ignores coins and oracle, and any depth-kk machine under the row, such as one deciding the empty language, supplies NN.

Row (2) with n=0n=0 is the same argument: by induction BB is decidable, and MC0(B)\mathrm{MC}_0(B) is the class of languages computable from BB.

For rows (2) with n≥1n\ge1, (3), (4) and (5), the depth-kk class is contained in Δk+10\Delta^0_{k+1}, by Lemma A.2 relative to ∅(k−1)\varnothing^{(k-1)} and, in rows (3) and (4), because truth-table reductions are Turing reductions. So B≤T∅(k)B\le_T\varnothing^{(k)}, and every function computable from BB is computable from ∅(k)\varnothing^{(k)}.

Upper bounds. Apply the corresponding row of Theorem 5.4 to MM, relative to A=BA=B, and look at its proof. It gives an approximation of LL computable from BB, hence from ∅(k)\varnothing^{(k)}. In row (2) it makes at most nn changes. In row (3) its changes have a bound computed ordinarily, and in row (4) a bound computed from BB, hence from ∅(k)\varnothing^{(k)}. In row (5) there is no bound. Lemma 5.3, or Lemma A.2 in row (5), both relative to ∅(k)\varnothing^{(k)}, places LL in MCn(∅(k))\mathrm{MC}_n(\varnothing^{(k)}), tt(∅(k+1))\mathrm{tt}(\varnothing^{(k+1)}), tt∅(k)(∅(k+1))\mathrm{tt}^{\varnothing^{(k)}}(\varnothing^{(k+1)}) or Δk+20\Delta^0_{k+2}, respectively.

Lower bounds. Take B=∅(k)B=\varnothing^{(k)}. It has an approximation computable from ∅(k−1)\varnothing^{(k-1)} that starts at 0 and changes at most once: simulate the run with the oracle and switch to 1 when it halts. So B∈MC1(∅(k−1))⊆MCn(∅(k−1))B \in\mathrm{MC}_{1}(\varnothing^{(k-1)}) \subseteq\mathrm{MC}_{n}(\varnothing^{(k-1)}) for n≥1n \ge1, and BB lies in the depth-kk class of rows (3), (4) and (5) as well, by the one-query identity reduction. By induction a depth-kk machine NN decides BB under the row, with the same prescribed constants. The lower-bound direction of the corresponding row of Theorem 5.4, relative to A=BA = B, supplies MM for every LL in the depth-(k+1)(k+1) class, since B′=∅(k+1)B' = \varnothing^{(k+1)}.

The inclusions in row (2) are Lemma 5.3(2) with A=∅(k−1)A = \varnothing^{(k-1)}, and the union over all pairs is handled as in Theorem 5.4. For the last sentence of the theorem, Δk0=MC0(∅(k−1))⊆MCn(∅(k−1))\Delta^{0}_{k} = \mathrm{MC}_{0}(\varnothing^{(k-1)}) \subseteq\mathrm{MC}_{n}(\varnothing^{(k-1)}), and Δk0⊆btt(∅(k))\Delta^{0}_{k} \subseteq\mathrm{btt}(\varnothing^{(k)}) by Lemma A.1(2).

Proof of Proposition 5.8

Proof of Proposition 5.8. The inclusions hold: zero queries are allowed, a constant query bound is computable, an ordinary algorithm ignores its oracle, and a truth-table reduction is a Turing reduction. For the first separation, ∅(k)\varnothing^{(k)} itself has the one-query identity reduction, and it is undecidable by Lemma A.1(1).

Second step. Write C=∅(k−1)C = \varnothing^{(k-1)}, so the oracle queried is C′=∅(k)C' = \varnothing^{(k)}, and repeat the diagonal of Proposition 4.12 with the simulations read relative to CC. At the input ⟨e,c⟩\langle e, c\rangle, simulate the ordinary program ee on ⟨e,c⟩\langle e, c\rangle for tt transitions. If it outputs a valid description of at most cc queries and a table τ\tau, evaluate τ\tau on the answers observed by stage tt. These are bj,t=1b_{j,t} = 1 iff the CC-oracle run coded by query yjy_j halts within tt transitions. Each is computable from CC, nondecreasing, and changes at most once. If the description is absent or invalid, the value is 0. Complement the value. The approximation so defined is computable from CC, changes at most c+1c + 1 times, and converges, so its limit lies in tt(C′)\mathrm{tt}(C') by Lemma 5.3(3) with the ordinary bound c+1c + 1. An ordinary bounded reduction of norm nn computed by program ee is contradicted at ⟨e,n⟩\langle e, n\rangle, exactly as in Proposition 4.12.

Third step. Lemma 5.9 with A=∅(k−1)A = \varnothing^{(k-1)} applies, because k≥2k \ge2 and HALT≤m∅(1)≤m∅(k−1)\mathrm{HALT} \leq_m \varnothing^{(1)} \leq_m \varnothing^{(k-1)} by Lemma A.1(1).

Fourth step. Let B=∅(k−1)B = \varnothing^{(k-1)} and repeat the diagonal of Corollary 3.3 with oracle B′B'. On input ee, ask B′B' whether the BB-oracle program ee halts on input ee. If it does, run it, answering its BB-queries through B′B' by Lemma A.1(1). If it outputs a valid description, answer its queries with the oracle B′B', each query asking whether a BB-oracle run halts, and output the opposite of the table value. Otherwise output 0. This is a total computation with oracle B′B'; call its language FF, so FF is Turing reducible to ∅(k)\varnothing^{(k)}. A truth-table reduction computed with oracle BB by program ee is contradicted at input ee.

At depth one, tt0(∅)=tt(HALT)\mathrm{tt}^{0}(\varnothing) = \mathrm{tt}(\mathrm{HALT}), so the third and fourth classes coincide.

Proofs for Section 6

This appendix uses the model and the notation of Section 6.

Proof of Lemma 6.2. Each measurement or halting test splits the weight of a history among its outcome extensions, whose projectors are orthogonal and sum to the identity. Ordinary steps and unitary gates change no weight. An induction on tt therefore gives total weight one to the histories that are complete within tt plus those that have consumed all their bits without halting. So the index sets of the sums increase with tt, and each pi,tp_{i,t} is nondecreasing with total at most one.

For computability, fix xx, tt, ii, kk. A complete history within tt steps has length at most 2t2t, and simulation decides membership, so the sum ranges over at most 22t+12^{2t+1} effectively enumerable terms. Each weight is the squared norm of a product of at most tt matrices of dimension at most 2cgt2^{c_gt}, each with at most 2cg2^{c_g} nonzero entries of modulus at most one per row. Approximate every gate entry within δ=2−(k+(2cg+2)t+5)\delta= 2^{-(k+(2c_g+2)t+5)} and write c=cg≥1c = c_g \ge1. Each row of a step matrix has at most 2c2^{c} nonzero entries, all of modulus at most one, and every entry of an exact vector has modulus at most one. So the largest entry error eje_j after jj steps satisfies ej+1≤2c(1+δ)ej+2cδe_{j+1} \le2^c(1+\delta)e_j + 2^c\delta, with e0=0e_0 = 0. Since (1+δ)t≤2(1+\delta)^t \le2, this gives et≤2ct+2δ=2−(k+(c+2)t+3)e_t \le2^{ct+2}\delta= 2^{-(k+(c+2)t+3)}. A weight is a sum of at most 2ct2^{ct} squared moduli, each changed by at most 3et3e_t, so each weight changes by at most 2ct+2et=2−(k+2t+1)2^{ct+2}e_t = 2^{-(k+2t+1)}. The sum over at most 22t+12^{2t+1} histories therefore changes by at most 2−k2^{-k}. With an oracle AA, the simulations answer their queries with AA.

Finally, pi(x)p_i(x) is the limit of the nondecreasing sequence pi,t(x)p_{i,t}(x). The rationals ℓi(x,t)\ell_i(x,t) built from it in the proof of Lemma 6.4 form a computable nondecreasing sequence with the same limit, so pi(x)p_i(x) is left-computably enumerable, uniformly in xx.

Proof of Lemma 6.3. Keep the control, including any oracle queries. Replace each coin transition by three instructions: name a fresh qubit, apply HH, measure it, and branch on the outcome. The outcome bb has probability ∥∣b⟩⟨b∣H∣0⟩∥2=1/2\lVert|b\rangle\langle b|H|0\rangle\rVert^2 = 1/2, and after the measurement the fresh qubit is in the basis state ∣b⟩|b\rangle. Replace the halting transition that outputs ii by: apply XX to a fresh output qubit if i=1i = 1, apply XX to a fresh flag qubit, and execute the halting test. The flag then returns 11 and the output qubit returns ii, each with probability one. Along any driven run, the register is in a basis state at the end of every simulated classical transition. So the complete histories correspond one to one to the halting coin strings of the given machine, and a history with ℓ\ell coin bits has weight 2−ℓ2^{-\ell}. The sums defining p0p_0 and p1p_1 agree.

References

  1. [1]K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro. Computability by probabilistic machines. In Claude E. Shannon and John McCarthy, editors, Automata Studies, volume 34 of Annals of Mathematics Studies, pages 183–212. Princeton University Press, 1956. doi: 10.1515/9781400882681-8-010. URL https://www.jstor.org/stable/j.ctt1bgzb3s.12.DOI
  2. [2]Scott Aaronson, Mohammad Bavarian, Toby Cubitt, Sabee Grewal, Giulio Gueltrini, Ryan O’Donnell, and Marien Raat. Computability theory of closed timelike curves. arXiv:1609.05507v2, 2024. URL https://arxiv.org/abs/1609.05507v2. Corrected version.
  3. [3]Joseph R. Shoenfield. On degrees of unsolvability. Annals of Mathematics, 69(3):644–653, 1959. doi: 10.2307/1970028.
  4. [4]Yu. L. Ershov. A hierarchy of sets. I. Algebra and Logic, 7(1):25–43, 1968. doi: 10.1007/BF02218750. English translation of Algebra i Logika.DOI
  5. [5]Yu. L. Ershov. On a hierarchy of sets. II. Algebra and Logic, 7(4):212–232, 1968. doi: 10.1007/BF02218664. English translation of Algebra i Logika.DOI
  6. [6]Yu. L. Ershov. On a hierarchy of sets. III. Algebra and Logic, 9(1):20–31, 1970. doi: 10.1007/BF02219847. English translation of Algebra i Logika.DOI
  7. [7]David Deutsch. Quantum mechanics near closed timelike lines. Physical Review D, 44(10):3197–3217, 1991. doi: 10.1103/PhysRevD.44.3197.DOI
  8. [8]Seth Lloyd, Lorenzo Maccone, Raul Garcia-Patron, Vittorio Giovannetti, Yutaka Shikano, Stefano Pirandola, Lee A. Rozema, Ardavan Darabi, Yasaman Soudagar, Lynden K. Shalm, and Aephraim M. Steinberg. Closed timelike curves via postselection: Theory and experimental test of consistency. Physical Review Letters, 106(4):040403, 2011. doi: 10.1103/PhysRevLett.106.040403.DOI
  9. [9]Scott Aaronson and John Watrous. Closed timelike curves make quantum and classical computing equivalent. Proceedings of the Royal Society A, 465(2102):631–647, 2009. doi: 10.1098/rspa.2008.0350.DOI
  10. [10]Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461(2063):3473–3482, 2005. doi: 10.1098/rspa.2005.1546.DOI
  11. [11]R. V. Freivald. Functions computable in the limit by probabilistic machines. In Mathematical Foundations of Computer Science, volume 28 of Lecture Notes in Computer Science, pages 77–87. Springer, 1975. doi: 10.1007/3-540-07162-8_671.DOI
  12. [12]H. G. Carstens. δ⁰-Mengen. Archiv für mathematische Logik und Grundlagenforschung, 18(1):55–65, 1977. doi: 10.1007/BF02007257.
  13. [13]Rod Downey and Noam Greenberg. A hierarchy of computably enumerable degrees. Bulletin of Symbolic Logic, 24(1):53–89, 2018. doi: 10.1017/bsl.2017.41.DOI
  14. [14]A. K. Zvonkin and L. A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25(6):83–124, 1970. doi: 10.1070/RM1970v025n06ABEH001269.DOI
  15. [15]Marien Raat. Computation in nested closed timelike curves. Master’s thesis, Utrecht University, 2023. URL https://studenttheses.uu.nl/handle/20.500.12932/45273.
  16. [16]A. C. Cem Say and Abuzer Yakaryılmaz. Computation with narrow CTCs. In Unconventional Computation (UC 2011), volume 6714 of Lecture Notes in Computer Science, pages 201–211. Springer, 2011. doi: 10.1007/978-3-642-21341-0_23.DOI
  17. [17]A. C. Cem Say and Abuzer Yakaryılmaz. Computation with multiple CTCs of fixed length and width. Natural Computing, 11(4):579–594, 2012. doi: 10.1007/s11047-012-9337-6.
  18. [18]Ryan O’Donnell and A. C. Cem Say. One time-traveling bit is as good as logarithmically many. In 34th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of Leibniz International Proceedings in Informatics, pages 469–480. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2014. doi: 10.4230/LIPIcs.FSTTCS.2014.469.
  19. [19]Todd A. Brun and Mark M. Wilde. Perfect state distinguishability and computational speedups with postselected closed timelike curves. Foundations of Physics, 42(3):341–361, 2012. doi: 10.1007/s107 01-011-9601-0.
  20. [20]Klaus Ambos-Spies, Klaus Weihrauch, and Xizhong Zheng. Weakly computable real numbers. Journal of Complexity, 16(4):676–690, 2000. doi: 10.1006/jcom.2000.0561.
  21. [21]Xizhong Zheng. Closure properties of real number classes under limits and computable operators. In Computing and Combinatorics (COCOON 2000), volume 1858 of Lecture Notes in Computer Science, pages 170–179. Springer, 2000. doi: 10.1007/3-540-44968-X_17. URL https://www.cs.auckland.ac.nz/~cristian/toprint/comput_reals.pdf.
  22. [22]Ugo Dal Lago, Sara Zuppiroli, and Maurizio Gabbrielli. Probabilistic recursion theory and implicit computational complexity. Scientific Annals of Computer Science, 24(2):177–216, 2014. doi: 10.756 1/SACS.2014.2.177.
  23. [23]Alexander Shen. Around Kolmogorov complexity: basic notions and results. arXiv:1504.04955, 2015. URL https://arxiv.org/abs/1504.04955.
  24. [24]Ryan O’Donnell and A. C. Cem Say. The weakness of CTC qubits and the power of approximate counting. ACM Transactions on Computation Theory, 10(2):5:1–5:22, 2018. doi: 10.1145/3196832.
  25. [25]Richard Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4(4):339–349, 1994. doi: 10.1007/BF01263422.DOI

Paper details

vlnc:W_xfcf6yge
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents