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 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 . The class is the same if the machine must halt with probability at least , for any fixed rational . 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 , 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 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 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 asks that the machine halt with probability at least on every input. And it can promise how sure its answer is: a confidence , with margin , asks that the correct output have probability at least among the halting runs. A higher floor or a higher confidence is a stricter promise, so fewer languages are decided. Given the two numbers and , we compute exactly how many nonadaptive questions about HALT such machines can replace. This number is
For example, floor and margin give and , so , and exactly two questions are allowed.
Theorem B (The sharp halting-floor theorem). For rationals and , the machines with halting floor and margin decide exactly the languages truth-table reducible to the halting problem with at most queries. In particular they decide only computable languages if and only if , 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 of the halting probability, and later at most the fraction . Probabilities of halting only grow with time, so every mind change multiplies the halting probability by at least , 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 asks only that the machine halt with positive probability on every input, however small. Requirement 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 , through an algorithm that computes it from . 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 halts | How sure it is | Languages decided: questions about HALT | Proved in |
| computable probability, e.g. one | decidable: no questions | Prop. 4.3 | |
| zero error | decidable: no questions | Prop. 4.4 | |
| floor (given) | margin (given) | at most nonadaptive questions | Thm. 4.7 |
| some fixed floor | some fixed margin | btt(HALT): a bounded number of nonadaptive questions | Cor. 4.8 |
| , or a computable floor | any fixed margin, or a computable margin | tt(HALT): finitely many nonadaptive questions | Prop. 4.9 |
| any fixed floor | a computable margin | tt(HALT): finitely many nonadaptive questions | Prop. 4.9 |
| , or any fixed floor | : adaptive questions | Thm. 3.2 |
Table 1. The classification of Theorem 4.11, from the strongest requirements (top) to the weakest (bottom). , , fixed and computable floors and margins, and zero error are defined just before the table; 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 nonadaptive questions, for a fixed . The truth-table reductions, tt(HALT), ask finitely many nonadaptive questions, their number computed from the input. The class 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 is a black box that answers every question “is in ?” correctly, in one step. Give our machines such an oracle. The role of the halting problem is then played by the jump : the set of programs that halt when they may consult the same oracle . 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 . 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 machines has depth , and each level adds one jump. So under unbounded error, depth decides exactly the languages decidable with an oracle for , the halting problem iterated 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 [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, (Theorem A). With bounded error the two rules differ: Deutsch’s rule still gives , while postselection gives only the truth-table reductions. With a prescribed floor and ranging, the allowed number of nonadaptive questions is exactly (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 bound | Loop carries | Error | Deutsch’s rule | Postselection rule |
| polynomial | polynomially many bits or qubits | any | PSPACE, classical and quantum [9] | quantum, bounded error: PP [10]; [2 Section 9] |
| polynomial | one bit, or logarithmically many | depends on the underlying class | classical: 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 |
| none | unbounded | zero | [2 Theorems 3.2 and 3.3] | decidable (Proposition 4.4) |
| none | unbounded | bounded | [2 Theorems 3.2 and 3.3] | prescribed floor and margin: 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] |
| none | unbounded | unbounded | [2 Theorems 3.2 and 3.3] | , with or without a fixed floor (Theorem 3.2) |
| none, nested to depth | unbounded at each level | fixed margin or unbounded | with a fixed margin [15 Theorem 1]; full classification [2 Section 3] | unbounded error: ; fixed margin, no floor: ; prescribed pair: (Theorem 5.7) |
| none | unbounded qubits | as above | the 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 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 decides every language decidable with an oracle for the -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 at every depth .
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 without repetitions, and simulating on input for transitions is itself computable. A language is decidable if some algorithm halts on every input and outputs , which is if and otherwise.
The halting problem is the language
of program–input pairs whose run eventually halts. It is not decidable: if a program decided it, the program that on input runs on and halts exactly when outputs would halt on its own index exactly when it does not.
Oracles and reductions
An oracle is a language . An oracle machine is an algorithm that may also submit a query and receive the bit in one step. A language is Turing reducible to , written , if some oracle machine with oracle halts on every input and decides . Later queries may depend on earlier answers; such reductions are called adaptive. We write for the languages Turing reducible to HALT.
A stricter kind of reduction prepares all questions in advance. A truth table for query positions is a map . A language is truth-table reducible to , written , if a total algorithm, given , outputs queries and a truth table , and
Neither the queries nor the table depends on the oracle answers. The number of queries may depend on , but it is part of what the algorithm computes. A language is bounded truth-table reducible to , written , if a fixed bounds the number of queries on every input; the least such 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 as a synonym for tt(HALT).
Each model restricts the next one, so
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 is a total computable function with for every . A mind change of at is a stage with ; the number of mind changes is
The limit lemma of Shoenfield [3] states that if and only if 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 -c.e., for , if it has a computable approximation that starts at 0 and makes at most mind changes on every input. It is -c.e. if it has a computable approximation whose mind changes are bounded by some computable function of .
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 , put a stage with value 0 in front. So a language with at most changes from a free start is -c.e., and the union over all , like the -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 would decide HALT. Carstens [12] showed that tt(HALT) is exactly the class of -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 is left-computably enumerable if it is the limit of a computable nondecreasing sequence of rational numbers. Such a sequence approximates 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 , search for a stage at which the two sequences differ by at most .
Unbounded error: the class
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 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 it either halts with output 0 or 1, or runs forever.
Write
The class consists of the languages for which one such machine satisfies, on every input,
The strict inequalities imply . Write for conditional correctness; the requirement is . Here is the characteristic function of . We impose no time or space bound, no computable lower bound on the conditional advantage , 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 would yield a decidable language: enumerate finite computation trees until one output accumulates mass above . This is an elementary instance of the classical probabilistic-computability setting of de Leeuw et al. [1]. Our requirement is instead , where 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 exactly when it has a computable approximation with values in . 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 equals . For every fixed rational , the same class results if one also requires on every input. At 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 , assuming the stated properties hold for that code.
Proof. Upper bound. Let be the probability of halting with output within transitions. It is an exactly computable dyadic rational, meaning an integer divided by a power of two. To see this, enumerate the strings of coin bits, simulate at most transitions using each string as the available random tape, and divide the number that halt with output by . 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 , since every halting run halts at a finite time. Hence
The total computable approximation stabilizes to . Temporary ties are assigned zero and do not affect the limit. The limit lemma yields ; no convergence rate is used.
Lower bound. Fix a total computable convergent approximation . Draw one integer with probabilities
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, . Thus for , and the weights sum to one. The exceptional all-tails continuation has probability zero and may run forever, as the model permits.
If , output . If , compute in order until the th change of value and output its new value. Totality of 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
Exactly the branches halt. Since each Boolean change flips the sign, direct summation gives
For completeness, the signed-sum identity follows by induction: its value at is ; adding the next term to gives . Equation (4) proves both strict inequalities in (1), including the case .
The machine contains a program for and the fixed sampler. It never uses or a stabilization stage. Thus the code of this machine can be computed from the code of . The upper-bound construction is likewise effective from the code of .
A prescribed halting bound. Given rational , choose an integer with , and put . With probability , run the machine just constructed; otherwise halt with an independent fair output bit. This choice uses only finitely many fair coins. If , and are the new output masses, halting probability and signed gap, then
The sign is unchanged because . Thus any prescribed bound below one is possible. If instead, the correct output has unconditional probability greater than . 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
Each additional change reverses the accumulated bias and halves its magnitude. So the conditional advantage may have no computable positive lower bound, even though the halting probability never falls below .
A worked example
Suppose the initial guess is zero. The branch assigned to that guess has probability . The first change to one adds output-one mass , so one becomes the more likely output. A second change adds output-zero mass , making zero more likely again. Table 2 continues this calculation. The total halting probability increases, while the conditional advantage over one half decreases.
| Changes | Final guess | ||||
| 0 | 0 | 0 | 1 | ||
| 1 | 1 | ||||
| 2 | 0 | ||||
| 3 | 1 |
Table 2. Output probabilities after the last of changes, for an approximation starting at zero. Branches assigned to later changes run forever. The final guess is the correct answer, and 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 . 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 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 is the class of languages truth-table reducible to HALT.
Corollary 3.3 (The computable-margin boundary). . 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 , where 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 by setting if does not halt or produces an invalid description. Otherwise evaluate the returned table using its finitely many halting queries and let be the opposite bit. This defines a total HALT-computable set. If a total truth-table reduction with index computed , its value at would contradict the definition of . Thus .
So some languages in have no machine with a computable positive margin, although they have the 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 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 be a machine as in Definition 3.1, and let be a rational number in .
(H0) on every input.
(H) on every input. The number is then a halting floor.
(Hc) is a computable halting probability: a total algorithm, given and , outputs a rational within of .
(H1) on every input.
A computable floor is a total computable rational function with values in and on every input.
Definition 4.2 (Confidence guarantees). Let be the conditional correctness of , and let be a rational number in .
(C0) on every input: a strict majority.
(Cη) on every input. The number is then a confidence margin, and is the confidence. The case , that is , is zero error.
(Ceff) on every input for a total computable rational function with values in , a computable margin.
Requirement (H1) implies (Hc), and (H1) and every floor imply (H0). Requirement (Cη) implies (Ceff) when , and every confidence requirement implies (C0). A deterministic decider, viewed as a machine, satisfies (H1) together with zero error.
Throughout this section, is the probability of halting with output within transitions, an exactly computable dyadic rational (proof of Theorem 3.2), and . Both increase with , to and .
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 and a genuine program witnessing (Hc), one computes a decider. The converse transformation is effective as well.
Proof. Fix the input . Let be a computable rational with , supplied by the (Hc) witness. The two quantities
squeeze . The lower bound is clear. For the upper bound, and the error of is at least . The gap tends to zero:
each of the four terms tending to zero. Given , search for the first with and output . The search terminates, and . So is a computable real, uniformly in . Interchanging the roles of the two outputs shows the same for . Hence is computable to any precision.
Requirement (C0) gives , with the sign of . For compute with , and stop at the first with . Such a exists because for all large . At that stage, , so and share the sign, and .
For the converse, let a decider for run as a probabilistic machine that never consults its coins. Then and , 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 , and some run halts. Search the stages for the first with , find a coin string of length whose run halts within transitions, and output its answer. Conversely, a decider is a machine with and . □
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 be a language and an integer.
(1) with norm at most if and only if has a computable approximation with at most mind changes on every input.
(2) if and only if has a computable approximation whose number of mind changes is bounded by a computable function of .
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 the queries with and the truth table . Let if the run of halts within transitions, and otherwise. Each sequence is computable and nondecreasing and changes value at most once. Put . Then is a total computable approximation: the observed answers converge to the true oracle answers, so converges to . Every change of coincides with a change of some , so changes at most times.
Part (1), “if”. Let be a computable approximation with at most mind changes. For let be the program that hardwires and , ignores its input, simulates , and halts exactly when it observes the -th mind change. The query is the pair . It is answered positively exactly when , so the number of positively answered queries is . Boolean changes flip the value, so . The truth table returns on the true answer vector, and the map from to the queries and the table is total computable. For the approximation never changes, so is decidable and zero queries suffice.
Part (2), “only if”. The reduction computes, along with its queries, their number , and the above changes at most times, a computable bound. Part (2), “if”. Apply the construction of part (1) with , where is the computable bound. The number of queries then depends computably on , 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 -c.e. languages and is contained in the -c.e. languages (§ 2).
The second tool turns prescribed output masses into a machine. A mass program is a pair of total computable functions and with nonnegative rational values, nondecreasing in , with . Their limits are left-computably enumerable reals, uniformly in (§ 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 and on every input. The same holds with an oracle : if and are computed from , the machine is an oracle machine with oracle (Definition 5.1).
Proof. The machine reads fair coins one at a time, which defines a uniform random point of . After reading coins it knows the dyadic interval that contains . It computes and , halts with output 0 if , halts with output 1 if , and otherwise reads the next coin. The two intervals are disjoint because , and each transition uses at most one coin.
If , then for some and all large , while has length , so the run halts with output 0. It cannot halt earlier with output 1, because at every stage. Conversely, a halt with output 0 at stage gives . So the run outputs 0 exactly when . In the same way it outputs 1 when , and an output 1 forces . The single point has probability zero. Hence the output masses are and . With an oracle, the machine computes and 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 and , and put
The maximum exists because and , and is computed exactly by rational arithmetic. Equivalently, ; the rational form decides the case of equality without logarithms. In words: a floor and a margin together permit exactly halting questions fixed in advance.
Theorem 4.7 (Sharp halting-floor theorem). Let and be rationals, and . A language is decided by a machine under and if and only if it is truth-table reducible to HALT with at most queries on every input. Both directions are effective, from the code of the machine together with and , and from the code of the reduction.
Proof. Upper bound. Let satisfy and and decide . By Lemma 4.5(1) it suffices to compute an approximation of with at most mind changes. Since and depends continuously on , there are rationals and with
A search over and , , finds them. Call a stage -good if and . Since , no stage is good for both outputs.
Some stage is good. Indeed , and , where is the mass of the correct output . Let be the first stage that is good for some output, and define to be that output. For , put if stage is -good, and otherwise. All tests compare exactly computed dyadic rationals with fixed rationals, so is total computable.
The approximation converges to . The mass of the wrong output tends to , since . So from some stage on, every stage is good for the correct output and no stage is good for the wrong one, and settles on .
Now count the changes. Suppose the value is set at stage , either or a change, and the next change, to , happens at stage . Stage is -good, so . Stage is -good, so . The masses only grow, so
Each change multiplies the total mass by at least . After changes the total mass is at least , and it is at most one, so by the choice of and $a_0.
Lower bound. Let have a truth-table reduction to HALT with at most queries. Lemma 4.5(1) gives a computable approximation with at most mind changes. Let
be the number of changes of up to stage . Assign mass to the current guess and mass to the other output. The total is .
These masses never decrease. At a change the old guess becomes the new loser, and its mass stays the same, because . The new guess receives the released mass and moves from to . So is a mass program, and Lemma 4.6 turns it into a machine. If makes changes on , the machine has , and the correct output, which is the final guess, has conditional probability exactly . So and hold. The case is included: the total mass may then reach one.
Corollary 4.8 (Exact thresholds). Let and be rationals, and .
Under and the decided languages are exactly the decidable languages if and only if .
If , then , and the halting problem is decided under and .
The class can only grow as or decreases, and every norm occurs: for every . The union of the classes over all rational pairs is btt(HALT).
Pairs with different values of decide different classes: for every some language has a truth-table reduction to HALT with queries but none with queries.
Proof. (1) exactly when , that is , and a reduction with zero queries is a decider. If , then and the class contains HALT, which is undecidable. (2) If , then and . (3) The function does not increase in , and increases with . For we have and , so and . Every language in btt(HALT) has some norm , and Theorem 4.7 decides it with the pair ; conversely each pair gives a bounded norm.
(4) By Lemma 4.5(1) it suffices to build a computable approximation with at most mind changes whose limit has no computable approximation with at most changes. Enumerate the partial computable functions of two arguments, and identify inputs with natural numbers as in the proof of Corollary 3.3. At input and stage , let be the largest number such that all halt within steps with values in . If there is no such , put . Otherwise, if these values contain at most changes, put , and if they contain more, keep . The first value seen moves at most once, and each of the at most followed changes of moves it once; nothing moves it afterwards. So changes at most times and converges. If a total approximated the limit with at most changes, then at input the value would equal for all large , and the two limits would differ.
The excluded endpoints fit the same formula. As tends to the ratio grows without bound, and at no power with fits under one; in both cases , which matches Propositions 4.3 and 4.4.
An example. Take floor and margin , so and . Then and , so exactly two queries are needed. The lower-bound machine for an approximation that starts at 0 gives mass to output 0 and to output 1. A first change raises the mass of output 1 to , and a second change raises the mass of output 0 to . 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 and margin . Guess 0 with mass against ; when the queried run is seen to halt, raise the mass of output 1 to . By Corollary 4.8(1), no pair with 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 , the following are equivalent.
.
is decided under and .
is decided under together with or a computable floor, for some, equivalently every, rational .
is decided under a computable floor and .
is decided under and , for some, equivalently every, rational .
All transformations are effective.
Proof. From (2) to (1). Let satisfy and with margin . Search for the first stage with ; it exists by , and an algorithm finds it. Then is a computable floor with values in . Run the upper-bound construction of Theorem 4.7 on input with and in place of the constants. Every quantity in it is a total computable function of , so the result is a computable approximation with at most 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 .
From (1) to (3), for any prescribed . Lemma 4.5(2) gives an approximation with at most changes, computable. Put , a computable floor with . The lower-bound construction of Theorem 4.7, run input by input, gives a machine with and conditional correctness exactly .
From (1) to (5), for any prescribed . With as before, search for the least such that satisfies , where ; it exists because as grows. Then , and the lower-bound construction gives a machine under with computable margin . 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 , decide exactly [2 Proposition 9.2]. The factor two plays no special role.
Corollary 4.10 (Any fixed factor). Let be a real number. The languages decided by machines whose correct output is, on every input, more than times as likely as the wrong one are exactly the languages in .
Proof. Such a machine halts with positive probability, since otherwise both outputs have probability zero, and its conditional correctness satisfies . Choose a rational with . Then and hold, and Proposition 4.9 gives . Conversely, choose a rational with . By Proposition 4.9(3), every is decided by a machine with and conditional correctness exactly , so its correct output is more than times as likely as the wrong one.
For 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.
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).
For each prescribed pair of rationals and , the decided languages are exactly those with a truth-table reduction to of at most queries (Theorem 4.7). The union over all pairs is (Corollary 4.8).
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 (Proposition 4.9).
Under (C0) together with (H0) or any fixed floor , the decided languages are exactly (Theorem 3.2).
All transformations are effective, and each containment in
is strict by Proposition 4.12.
Proposition 4.12. The chain is strict at each step.
Proof. First, 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 of natural numbers, composing the input numbering from the proof of Corollary 3.3 with a computable pairing. Let be the following computable value. Simulate program on input for transitions. If the program has halted with a valid description of at most halting queries and a truth table , set . Here iff the run of halts within transitions; otherwise set . Put . Each sequence changes at most once, and the description appears at most once, so changes at most times at , a computable bound. The value converges: if program never returns a valid bounded description, is eventually . Let . Then by Lemma 4.5(2). Suppose a bounded truth-table reduction of norm , computed by program , decided . At the program halts with a valid description of at most queries, the observed answers stabilize at the true ones, and converges to . Then , contradicting .
Third, Corollary 3.3 constructs a language in outside , 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 -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 , and the mass never exceeds one.
Oracles, nesting and the arithmetic hierarchy
Every class of Section 4 sits between the decidable languages and . This section asks what an oracle changes. With an oracle , a function can be computed by an ordinary algorithm or by one that also consults . 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 is a finite-program machine as in Definition 3.1 whose transitions may also submit a query and then receive the exact bit in one step. At most one new coin is used per transition. On input , the numbers , and 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 . A floor or margin computable from is computed by an algorithm with oracle ; 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 .
Simulating transitions and answering every query with the oracle computes as a dyadic rational, and 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 and change nothing else.
Definition 5.2 (Iterates). The jump of a language is
the halting problem of oracle machines with oracle . Put and , and let be the class of languages Turing reducible to . A language is many-one reducible to , written , if a total computable satisfies 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 behaves exactly like the ordinary program obtained by answering every query with , and this replacement is computable. Hence HALT and 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 , as defined in § 2, is Turing reducibility to .
Who computes the reduction. For languages and we use three kinds of truth-table reductions to . In and an ordinary algorithm computes the queries, their number and table, as in § 2; is the part of with at most queries on every input. In an algorithm with oracle computes them. The superscript records who computes the questions, not which oracle is queried. It matters: with the help of one can write down questions that no ordinary algorithm can. Finally, is the class of languages with an approximation computable from that makes at most mind changes on every input, from a free start. By Lemma 4.5, . 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 , not by an ordinary algorithm.
Lemma 5.3 (Bridge lemma with an oracle). Let and be languages and .
(1) if and only if has a truth-table reduction to with at most queries, in which an ordinary algorithm computes the queries and an algorithm with oracle computes the table.
(2) .
(3) has an approximation computable from whose mind changes are bounded by a function computed by an ordinary algorithm if and only if . It has one with a bound computable from if and only if .
All directions are effective.
The extra query in part (2) is needed for the starting value. An approximation computable from may start at a value that only can compute, so an ordinary reduction must ask for it. For the two ends differ for every undecidable : is the class of languages computable from , while is the class of decidable languages. Appendix § 8 proves the lemma, together with the limit lemma relative to an oracle (Lemma A.2): is Turing reducible to if and only if has an approximation computable from .
The relativized classification
Theorem 5.4 (Relativized ladder). Fix a language and consider probabilistic oracle machines with oracle .
(1) Under (C0) with a halting probability computable from , and under (H0) with zero error, the decided languages are exactly those computable from .
(2) For each prescribed pair of rationals and , with , the decided languages are exactly . So they include and are included in , and their union over all pairs is .
(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 .
(4) Under (H0) with a fixed or computable margin, the decided languages are exactly . The same holds in row (3) when the floor or the margin is only computable from .
(5) Under (C0) with (H0) or a fixed floor , the decided languages are exactly those Turing reducible to .
All transformations are effective. For 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 , it gives an approximation computable from with at most 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 , not . In row (3) an ordinary algorithm computes the change bound ; in row (4) the floor comes from the first stage with positive halting mass, which needs the oracle.
| Halting requirement | Confidence requirement | Languages decided |
| computable from | (C0) | computable from |
| (H0) | zero error | computable from |
| the prescribed floor | the prescribed margin | , between and |
| some fixed floor | some fixed margin | |
| fixed or computable floor | computable margin, or fixed margin with a computable floor | |
| (H0), or a floor computable from | fixed or computable margin, or one computable from | |
| (H0) or a fixed floor | (C0) | Turing reducible to |
Table 3. The relativized classification of Theorem 5.4. The machine has oracle ; every reduction queries . “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 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- machines). A depth-one machine is a machine as in Definition 3.1. For , a depth- machine is a pair : is a depth- machine, which decides a language , and is a probabilistic oracle machine with oracle . The pair decides the language that decides. A row of guarantees holds at depth if satisfies the row relative to , as fixed after Definition 5.1, and the same row holds for at depth . 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 by Theorem 3.2, at any depth. Exact oracle answers are what let nesting climb the hierarchy.
Theorem 5.7 (Nesting). Consider depth- machines, with the rows of Theorem 5.4 read as in Definition 5.5. For every :
under (C0) with a computable halting probability, and under (H0) with zero error, the decided languages are the decidable ones;
for a prescribed pair with , the decided languages are the decidable ones if , and exactly if . The latter class lies between and , and it equals at . The union over all pairs is ;
under the computable guarantees of row (3), they are exactly ;
under (H0) with a fixed or computable margin, they are exactly , which is at ;
under (C0) with (H0) or a fixed floor , they are exactly .
Rows (3) to (5), and row (2) when , contain . All transformations are effective.
The proof, in Appendix A, is an induction on . For the upper bounds, the oracle of a depth- machine lies in a depth- class, hence is Turing reducible to , so an approximation computable from is computable from . For the lower bounds, take , which is decided at depth under every row except row (1) and row (2) with . This is where is needed: has an approximation computable from with one mind change, and none with zero.
Strictness, and what the oracle changes
Proposition 5.8. For every ,
At depth one the third and fourth classes coincide.
The first separation is witnessed by itself, the second repeats the diagonal of Proposition 4.12 relative to , and the last repeats the diagonal of Corollary 3.3 with oracle ; the details are in Appendix A. The third separation is the new one, and it follows from the next lemma with , which computes HALT when .
Lemma 5.9. If , then .
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 be the -th ordinary program. Define by an algorithm with oracle . On input , use to decide whether halts with a valid description of a list of queries to and a table . If it does, output the same queries with the table ; otherwise output no queries and the constant table 0. This is a truth-table reduction to computed with oracle , so . If computed an ordinary truth-table reduction of to , then would halt with a valid description, and .
At depth one, rows (3) and (4) give the same class: with or without a computable floor, a computable margin decides . 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 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 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 MC is as in Table 3. At rows four and five coincide.
| Guarantees at every depth | Languages decided at depth |
| (C0) and computable ; or (H0) and zero error | decidable |
| the prescribed pair , | decidable if ; if |
| some fixed pair | |
| computable guarantees of row (3) | |
| (H0) and a fixed or computable margin | |
| (C0), and (H0) or a fixed floor |
Table 4. Nested postselection of Theorem 5.7: the languages decided at depth 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 MC is as in Table 3. At 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 decides every language Turing reducible to , 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, at depth , 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 . Under postselection on halting, a fixed margin at depth reaches only the class of row (4), strictly inside , 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 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 of unitary matrices to named qubits; a qubit named for the first time starts in state . 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 and the bit flip . Every gate entry is a computable complex number, uniformly: an algorithm, given a gate, an entry position and , outputs rationals within of the real and imaginary parts. One constant bounds the number of qubits any instruction names. With an oracle , the control may also submit queries, as in Definition 5.1.
A history is a finite binary string driving a run. The control consumes one bit of 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 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 multiplies by the projector . The weight of is , and is a complete history when the driven run halts right after consuming its last bit. Define
and . 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 is nondecreasing in , with , and it is a computable real, uniformly in , and . With an oracle , it is computable from . Consequently the eventual masses and are left-computably enumerable reals, uniformly in (relative to 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 and 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 and on every input. With an oracle , the classical machine is an oracle machine with oracle .
Proof. By Lemma 6.2, compute rationals with , and put , so that . Let
These rationals are computable and nondecreasing in . Since is nondecreasing, , so , and is a mass program. Its limits are the eventual masses: , and . Lemma 4.6 turns the mass program into a classical machine with masses exactly and . With an oracle, every step is computed from .
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 of queries.
Proof. The answer rule and every guarantee are statements about the two mass functions and of a machine, and, in , about an algorithm that approximates their sum. By Lemmas 6.3 and 6.4, classical and quantum machines with oracle 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 . With bounded error the two rules part. Deutsch’s rule still gives , while postselection on halting gives the truth-table reductions to HALT, and with a prescribed floor and margin only 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 decides a class strictly inside (Proposition 5.8). Deutschian nesting with a fixed margin still decides every language Turing reducible to {[15 Theorem 1]}.
The polynomial-time setting provides a useful contrast. Let denote nondeterministic polynomial time, unbounded-error probabilistic polynomial time, and polynomial time with adaptive queries to an oracle. Beigel [25] constructs an oracle relative to which . Polynomial-time postselection with a strict conditional majority decides exactly : 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 , and the mass never exceeds one, so at most 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 tosses at most coins, for a polynomial . Then at most coin strings exist, the output masses change only when one of them halts, and the sign of changes at most 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 -th machine to run forever once it exceeds its coin bound. On input , follow the sign of the -th capped machine’s output difference and output the opposite value. This approximation changes at most times, so its limit is in tt(HALT), and it disagrees at input with the -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 changes, the machine of Theorem 3.2 needs only the branches ; letting the sampler run forever after tails in its second phase keeps every weight it uses and tosses at most coins.
Open questions
Sampled oracles. Replace exact oracle answers by samples. In a sampled depth-two machine , each query of is answered by a bit drawn with probability , where and are the masses of on . Every answer is a fresh sample, independent of the coins of and of all earlier answers, and every query returns. The masses of 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.
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) for every language , by a computable map. Hence whenever , and is undecidable for .
(2) If and , then . So .
Proof. (1) Let be the -oracle program that, on any input, queries and halts exactly if the answer is 1. Then if and only if , and is computable. Composing along the chain gives . If were decidable, then HALT would be decidable too, being many-one reducible to it, against Section 2.
(2) Let the -oracle program decide . Let be the -oracle program that computes and halts exactly if the value is 1. Then if and only if , computably in .
Lemma A.2 (Limit lemma with an oracle). A language is Turing reducible to if and only if has an approximation computable from . Both directions are effective.
Proof. Given a reduction, define by simulating it on for transitions. Answer each submitted query by running for 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 is computable from . If the run on halts within transitions, then for all large enough every simulated answer is the true one, so stabilizes at .
Conversely, let be an approximation computable from . Let be the -oracle program that hardwires and , simulates and halts when it finds a stage with . So halts exactly if changes after . A machine with oracle asks about for until the first answer no, say at ; the search stops because converges. It then computes with oracle , answering each -query by one further -query, of the kind in Lemma A.1(1). No change occurs after , so the output is . □
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 be an approximation computable from . For each and let be the -oracle program that hardwires and , ignores its input, simulates with oracle , and halts exactly when it observes the -th mind change. Let be the -oracle program that computes and halts exactly if the value is . An ordinary algorithm computes the indices of and from and . Boolean changes flip the value, so
where exactly when , and exactly when .
(1) If makes at most changes, query for and use the table . The queries are computed ordinarily and the table with oracle . Conversely, let a reduction with queries and table be computed with oracle . Each query asks whether an -oracle run halts. Let if the run of halts within transitions, and otherwise. Each sequence is computable from , nondecreasing, and changes at most once. So is computable from , changes at most times, and converges to .
(2) An ordinary reduction is a special case of part (1), which gives the first inclusion. For the second, add the query to those of part (1) and use the table , where is the answer to the new query. Now an ordinary algorithm computes the queries and the table, and there are queries.
(3) If bounds the changes of , query and for , and combine all answers by exclusive or. Only the length of the list may need the oracle; so the reduction lies in when is computed ordinarily, and in when is computed from . Conversely, a reduction with queries gives, as in part (1), an approximation computable from with at most changes, and is computed by the same kind of algorithm as the reduction. □
Proof of Theorem 5.4
Proof of Theorem 5.4. Throughout, the values and are dyadic rationals computed from by simulation, and Lemma 4.6 holds with oracle .
Row (1). The proof of Proposition 4.3 relativizes word for word. The witness for the halting probability is now an algorithm with oracle , the squeeze search terminates as before, and the sign of gives a decider computed from . The search in the proof of Proposition 4.4 also runs with oracle . Conversely, a decider with oracle , viewed as a machine that never tosses coins, has and .
Row (2). Let satisfy and . The upper-bound construction of Theorem 4.7 compares the values and with fixed rationals, so with oracle it gives an approximation computable from with at most changes. Its counting argument uses only the monotonicity of the masses and . So . Conversely, let be an approximation of computable from with at most changes. The masses of the lower-bound construction of Theorem 4.7 are then computed from , and Lemma 4.6 with oracle gives a machine with floor and conditional correctness exactly . The inclusions are Lemma 5.3(2). Every is for some pair (Corollary 4.8(3)), so the union over all pairs lies between and , both of which are .
Row (3). Let and 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 with these values. The relaxed thresholds and the bound depend only on and , so an ordinary algorithm computes them, while the approximation is computed from . Lemma 5.3(3) gives . Conversely, Lemma 5.3(3) gives an approximation computable from with changes bounded by an ordinarily computed . For a fixed margin , the floor is computable and . For a fixed floor , the margin , with least such that , 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 , and Lemma 4.6 give the machine.
Row (4). Under (H0), search with oracle for the first stage with ; it exists by (H0). The floor is computed from . Run the upper-bound construction with and the margin. The approximation and the bound are now computed from , and Lemma 5.3(3) gives . The same argument applies when the floor or the margin is given but computed only from . Conversely, Lemma 5.3(3) gives an approximation computable from with a bound computed from . For a prescribed margin , the floor is computed from , and the lower-bound construction with Lemma 4.6 gives a machine under (H0) with margin exactly ; its floor is computable from . For a fixed floor, choose the margin as in row (3), now with oracle .
Row (5). The approximation of the proof of Theorem 3.2 is computed from and converges to , so Lemma A.2 gives a Turing reduction to . Conversely, such a reduction gives an approximation computable from , and the machine of Theorem 3.2, with its padding and with oracle , decides under (C0) with any fixed floor .
For , by Lemma 4.5, and , since an algorithm with oracle is effectively an ordinary one. □
Proof of Theorem 5.7
Proof of Theorem 5.7. Each row is proved by induction on , both bounds together. At each row is the corresponding row of Theorem 5.4 with . Assume the row at depth , and let be a depth- machine, with deciding at depth and deciding .
Row (1). By induction is decidable, so computability from is ordinary computability, and row (1) of Theorem 5.4 with shows that is decidable. Conversely, a decider ignores coins and oracle, and any depth- machine under the row, such as one deciding the empty language, supplies .
Row (2) with is the same argument: by induction is decidable, and is the class of languages computable from .
For rows (2) with , (3), (4) and (5), the depth- class is contained in , by Lemma A.2 relative to and, in rows (3) and (4), because truth-table reductions are Turing reductions. So , and every function computable from is computable from .
Upper bounds. Apply the corresponding row of Theorem 5.4 to , relative to , and look at its proof. It gives an approximation of computable from , hence from . In row (2) it makes at most changes. In row (3) its changes have a bound computed ordinarily, and in row (4) a bound computed from , hence from . In row (5) there is no bound. Lemma 5.3, or Lemma A.2 in row (5), both relative to , places in , , or , respectively.
Lower bounds. Take . It has an approximation computable from that starts at 0 and changes at most once: simulate the run with the oracle and switch to 1 when it halts. So for , and lies in the depth- class of rows (3), (4) and (5) as well, by the one-query identity reduction. By induction a depth- machine decides under the row, with the same prescribed constants. The lower-bound direction of the corresponding row of Theorem 5.4, relative to , supplies for every in the depth- class, since .
The inclusions in row (2) are Lemma 5.3(2) with , and the union over all pairs is handled as in Theorem 5.4. For the last sentence of the theorem, , and 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, itself has the one-query identity reduction, and it is undecidable by Lemma A.1(1).
Second step. Write , so the oracle queried is , and repeat the diagonal of Proposition 4.12 with the simulations read relative to . At the input , simulate the ordinary program on for transitions. If it outputs a valid description of at most queries and a table , evaluate on the answers observed by stage . These are iff the -oracle run coded by query halts within transitions. Each is computable from , 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 , changes at most times, and converges, so its limit lies in by Lemma 5.3(3) with the ordinary bound . An ordinary bounded reduction of norm computed by program is contradicted at , exactly as in Proposition 4.12.
Third step. Lemma 5.9 with applies, because and by Lemma A.1(1).
Fourth step. Let and repeat the diagonal of Corollary 3.3 with oracle . On input , ask whether the -oracle program halts on input . If it does, run it, answering its -queries through by Lemma A.1(1). If it outputs a valid description, answer its queries with the oracle , each query asking whether a -oracle run halts, and output the opposite of the table value. Otherwise output 0. This is a total computation with oracle ; call its language , so is Turing reducible to . A truth-table reduction computed with oracle by program is contradicted at input .
At depth one, , 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 therefore gives total weight one to the histories that are complete within plus those that have consumed all their bits without halting. So the index sets of the sums increase with , and each is nondecreasing with total at most one.
For computability, fix , , , . A complete history within steps has length at most , and simulation decides membership, so the sum ranges over at most effectively enumerable terms. Each weight is the squared norm of a product of at most matrices of dimension at most , each with at most nonzero entries of modulus at most one per row. Approximate every gate entry within and write . Each row of a step matrix has at most 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 after steps satisfies , with . Since , this gives . A weight is a sum of at most squared moduli, each changed by at most , so each weight changes by at most . The sum over at most histories therefore changes by at most . With an oracle , the simulations answer their queries with .
Finally, is the limit of the nondecreasing sequence . The rationals built from it in the proof of Lemma 6.4 form a computable nondecreasing sequence with the same limit, so is left-computably enumerable, uniformly in .
Proof of Lemma 6.3. Keep the control, including any oracle queries. Replace each coin transition by three instructions: name a fresh qubit, apply , measure it, and branch on the outcome. The outcome has probability , and after the measurement the fresh qubit is in the basis state . Replace the halting transition that outputs by: apply to a fresh output qubit if , apply to a fresh flag qubit, and execute the halting test. The flag then returns and the output qubit returns , 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 coin bits has weight . The sums defining and agree.
References
- [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]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]Joseph R. Shoenfield. On degrees of unsolvability. Annals of Mathematics, 69(3):644–653, 1959. doi: 10.2307/1970028.
- [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]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]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]David Deutsch. Quantum mechanics near closed timelike lines. Physical Review D, 44(10):3197–3217, 1991. doi: 10.1103/PhysRevD.44.3197.DOI
- [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]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]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]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]H. G. Carstens. δ⁰-Mengen. Archiv für mathematische Logik und Grundlagenforschung, 18(1):55–65, 1977. doi: 10.1007/BF02007257.
- [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]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]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]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]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]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]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]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]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]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]Alexander Shen. Around Kolmogorov complexity: basic notions and results. arXiv:1504.04955, 2015. URL https://arxiv.org/abs/1504.04955.
- [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]Richard Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4(4):339–349, 1994. doi: 10.1007/BF01263422.DOI