Introduction
Probabilistic Turing Machines (PTMs) with bounded space and bounded time are classic objects studied in computational complexity. The way of accessing randomness in such models may affect the computation power significantly. We mainly review the literature for bounded-error PTMs under two different settings of randomness accessing, with a special focus on the case of logspace machines.
The study of space-bounded randomness has developed along two related directions: computation with fresh random bits, equivalently read-once access to a random tape, and computation with two-way access to a persistent random tape. At logarithmic space and polynomial time, these models define BPL and BP · L, respectively. Gill’s foundational work [10 ] studied probabilistic Turing machines whose transitions use coin tosses, corresponding to the fresh-coin model. Aleliunas, Karp, Lipton, Lovász, and Rackoff [1 ] subsequently gave a randomized logarithmic-space algorithm for undirected connectivity using fresh random choices. For arbitrary space-bounded machines in this read-once randomness model, Borodin, Cook, and Pippenger [2 ] obtained deterministic simulations using quadratic space. The importance of the access convention was already apparent in work of Karpinski and Verbeek [16 , 17 ] , who studied two-way random tapes under space bounds without a polynomial-time restriction and established limitations on deterministic space simulation. Their resource convention differs from the polynomial-time two-way model defining BP · L. In the early 1990s, Nisan [21 ] constructed a pseudorandom generator with O ( log 2 n ) O(\log^2 n) O ( log 2 n ) seed length that fools polynomial-time, logarithmic-space computations with read-once access to randomness at inverse-polynomial error. Enumerating its seeds yields an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -space deterministic simulation; Nisan’s subsequent work [20 ] achieved polynomial time and O ( log 2 n ) O(\log^2 n) O ( log 2 n ) space simultaneously for the same read-once source model. In a separate comparison of randomness-access models [22 ] , he showed that every language in BPL admits a zero-error logarithmic-space algorithm with two-way access to randomness, and characterized BP · L as almost-L, the languages decidable in logarithmic space relative to almost every oracle. For read-once source computations using relatively few random bits, Nisan and Zuckerman [23 ] showed how to reduce poly ( S ) \operatorname{poly}(S) poly ( S ) fresh random bits to O ( S ) O(S) O ( S ) random bits while retaining O ( S ) O(S) O ( S ) space and approximately preserving the output distribution. Moving beyond read-once access, Impagliazzo, Nisan, and Wigderson [15 ] constructed pseudorandom generators for machines whose two-way random-tape head visits each cell only constantly many times. Their result gives O ( log 2 n ) O(\log^2 n) O ( log 2 n ) seed length for this bounded-local-rereading model at logarithmic space, polynomial time, and inverse-polynomial error. For read-once randomized computation, Saks and Zhou [SZ99] improved the deterministic space bound to O ( log 3 / 2 n ) O(\log^{3/2} n) O ( log 3/2 n ) , without a polynomial-time guarantee. Saks [Sak96] surveyed the different conventions for space-bounded randomness. For the unrestricted two-way randomness model, Klivans and van Melkebeek [18 ] obtained conditional derandomization through space-efficient hardness-versus-randomness constructions: an exponential circuit lower bound, at all sufficiently large input lengths, for a function computable in deterministic linear space implies B P ⋅ L = L BP \cdot L = L B P ⋅ L = L . Gutfreund and Viola [11 ] gave constructions yielding randomness-efficient error reduction for B P ⋅ L BP \cdot L B P ⋅ L , where the random description may be reread. For the specific problem of undirected connectivity, Reingold [Rei05] obtained a deterministic logarithmic-space algorithm. Applications of two-way randomness appeared in many algorithmic applications. For example the work of Flaxman and Frieze [8 ] considers a space-bounded computation which must reconstruct the same randomly perturbed graph on subsequent accesses. Healy [13 ] developed computationally efficient samplers and randomness-efficient error reduction in small uniform circuit classes, explicitly distinguishing rereadable randomness from the read-once setting. More recently, Hoza [14 ] improved the deterministic space bound for read-once randomized computation to O ( log 3 / 2 n / log log n ) O(\log^{3/2} n/\sqrt{\log\log n}) O ( log 3/2 n / log log n ) , again without a polynomial-time guarantee. Bisht, Gupta, Nimbhorkar, and Volkovich [3 ] placed arithmetic-formula polynomial identity testing in B P ⋅ L BP \cdot L B P ⋅ L , illustrating the role of persistent randomness in reusing a random evaluation point. For read-once randomness, the recent preprint of OpenAI [24 ] states a deterministic logarithmic-space simulation together with additive inverse-polynomial acceptance-probability approximation. For two-way randomness with a constant local visit bound, Cheng and Wu [4 ] obtained a deterministic simulation using polynomial time and O ( log 2 n ) O(\log^2 n) O ( log 2 n ) space, with an inverse-polynomial additive error for the acceptance probability. There is a natural question behind the development of studying the two random access models: as the permitted number of visits to each random-tape cell increases, when can the resulting computation still be simulated using read-once randomness without increasing its asymptotic space bound?
Towards addressing this question, we study the read-multiplicity model of Impagliazzo, Nisan, and Wigderson [15 ] . We use the following formal definition to describe such models. If we bound the number of visits for the cells in the random tape we come to the class of read-k k k PTMs.
Definition 1.1 (Locally Read-k k k Machine). Let k : N → N ≥ 1 k : \mathbb{N} \to\mathbb{N}_{\ge1} k : N → N ≥ 1 . A locally read-k k k machine is a probabilistic Turing machine with a two-way read-only input tape, a read–write work tape, and a read-only random tape satisfying the following conditions.
Local access to randomness. The random-tape cells are indexed by 1 , 2 , … 1,2,\ldots 1 , 2 , … and contain independent uniformly random bits. The random head starts at cell 1. At each step, it either stays at its current cell or moves to an adjacent cell, without moving left of cell 1. Once the random-tape contents are fixed, the computation is deterministic.
Bounded visits. A visit to a random-tape cell is a maximal consecutive period during which the random head remains at that cell. The initial placement at cell 1 begins its first visit. For every input of length n n n and every assignment to the random tape, each random-tape cell is visited at most k ( n ) k(n) k ( n ) times.
Definition 1.2 (LocalReadk _k k -BPTISP(T T T , S S S )). Let k k k , T T T , S : N → N ≥ 1 S : \mathbb{N} \to\mathbb{N}_{\ge1} S : N → N ≥ 1 . The class LocalReadk _k k -BPTISP(T T T , S S S ) consists of all languages L L L for which there exists a locally read-k k k machine M M M that halts within O ( T ( n ) ) O(T(n)) O ( T ( n )) time and uses O ( S ( n ) ) O(S(n)) O ( S ( n )) work space on every input of length n n n and every random tape. Moreover, for every input x x x ,
x ∈ L ⇒ Pr r [ M ( x ; r ) accepts ] ≥ 2 3 , x \in L \Rightarrow\Pr_{r}[M(x;r)\text{ accepts}] \ge\frac{2}{3}, x ∈ L ⇒ r Pr [ M ( x ; r ) accepts ] ≥ 3 2 , x ∉ L ⇒ Pr r [ M ( x ; r ) accepts ] ≤ 1 3 . x \notin L \Rightarrow\Pr_{r}[M(x;r)\text{ accepts}] \le\frac{1}{3}. x ∈ / L ⇒ r Pr [ M ( x ; r ) accepts ] ≤ 3 1 .
We write
LocalRead k -BPSPACE ( S ( n ) ) : = LocalRead k -BPTISP ( 2 O ( S ( n ) ) , S ( n ) ) . \operatorname{LocalRead}_k\text{-BPSPACE}(S(n)) := \operatorname{LocalRead}_k\text{-BPTISP}(2^{O(S(n))}, S(n)). LocalRead k -BPSPACE ( S ( n )) := LocalRead k -BPTISP ( 2 O ( S ( n )) , S ( n )) .
In particular,
LocalRead k -BPL : = LocalRead k -BPSPACE ( O ( log n ) ) . \operatorname{LocalRead}_k\text{-BPL} := \operatorname{LocalRead}_k\text{-BPSPACE}(O(\log n)). LocalRead k -BPL := LocalRead k -BPSPACE ( O ( log n )) .
An immediate question is whether locally read-k k k randomized machines can be simulated with read-once access to randomness while approximately preserving their acceptance probabilities and attaining a small asymptotic space bound, particularly when k k k is constant.
Our Results
We show the following simulation of read-k k k space bounded PTMs by read-once space bounded PTMs.
Theorem 1.3 (Fresh-Coin Simulation). Let k k k , T T T , S : N → N ≥ 1 S : \mathbb{N} \to\mathbb{N}_{\ge1} S : N → N ≥ 1 be logspace constructible functions. Let M M M *be a locally read-*k machine running in time O ( T ( n ) ) O(T(n)) O ( T ( n )) and space O ( S ( n ) ) O(S(n)) O ( S ( n )) on every input and every random tape. For every 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2 , there exists a probabilistic TM M ′ M' M ′ with a read-once random tape such that, on every input x x x of length n n n , the output distributions of M ( x ) M(x) M ( x ) and M ′ ( x ) M'(x) M ′ ( x ) have total variation distance at most ε \varepsilon ε . Moreover, M ′ M' M ′ runs in space
O ( k ( n ) 2 ( S ( n ) + log ( n + T ( n ) ) ) + log ( 1 / ε ) ) O\left(k(n)^2(S(n)+\log(n+T(n)))+\log(1/\varepsilon)\right) O ( k ( n ) 2 ( S ( n ) + log ( n + T ( n ))) + log ( 1/ ε ) ) and time
1 ε ⋅ 2 O ( k ( n ) 2 ( S ( n ) + log ( n + T ( n ) ) ) ) \frac{1}{\varepsilon}\cdot2^{O(k(n)^2(S(n)+\log(n+T(n))))} ε 1 ⋅ 2 O ( k ( n ) 2 ( S ( n ) + l o g ( n + T ( n )))) on every random tape.
For constant k k k , this yields the following equality of complexity classes.
Corollary 1.4. For every constant integer k ≥ 1 k \ge1 k ≥ 1 and every logspace constructible function S ( n ) ≥ log n S(n) \ge\log n S ( n ) ≥ log n ,
LocalRead k -BPSPACE ( S ( n ) ) = BPSPACE ( S ( n ) ) . \operatorname{LocalRead}_k\text{-BPSPACE}(S(n)) = \operatorname{BPSPACE}(S(n)). LocalRead k -BPSPACE ( S ( n )) = BPSPACE ( S ( n )) . In particular,
LocalRead k -BPL = BPL . \operatorname{LocalRead}_k\text{-BPL} = \operatorname{BPL}. LocalRead k -BPL = BPL .
Other Related Read-k k k Models
Several related models restrict repeated access in different ways. A k k k -pass random-tape machine scans the same random string at most k k k times, typically resetting its random head between successive left-to-right scans. David, Papakonstantinou, and Sidiropoulos [7 ] studied the applicability of Nisan’s generator to such multipass models; Mandal, Pavan, and Vinodchandran [19 ] investigated their derandomization, and Dixon, Mandal, Pavan, and Vinodchandran [DMPV16] studied their advice complexity. We note here that since the local read-k k k model can move their random tape heads freely, it can definitely simulate the k ′ k' k ′ -pass model, by setting k = 2 k ′ k = 2k' k = 2 k ′ . However, before this work, it is highly unclear how to simulate local read-k k k model by k ′ k' k ′ -pass models, as even for constant k k k , a straightforward simulation of read-k k k models may need Θ ( n ) \Theta(n) Θ ( n ) passes. Another extensively studied model is the read-k k k oblivious branching program. Here the variable queried at each layer is fixed independently of the input, and each variable occurs at most k k k times in this reading sequence. The sequence may jump arbitrarily between variables; there is no adjacent-cell head. Gurjar and Volk [12 ] constructed pseudorandom generators for read-k k k oblivious branching programs when the reading sequence is known to the generator, and Doron and Lang [5 ] subsequently improved the seed-length bounds. Knowledge of the reading order is a separate issue even for read-once programs, as illustrated by the unknown-order generator of Forbes and Kelley [9 ] . More general read-k k k branching programs allow the next queried variable to depend on the current state.
Technical Overview
Let M M M be a locally read-k k k randomized Turing machine running in time T T T and space S S S on inputs in { 0 , 1 } n \{0,1\}^n { 0 , 1 } n . For every 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2 , we will construct a randomized Turing machine M ′ M' M ′ with one-way access to its random tape. On inputs in { 0 , 1 } n \{0,1\}^n { 0 , 1 } n , the machine M ′ M' M ′ runs in space
O ( k 2 ( S + log ( n + T ) ) + log ( 1 / ε ) ) O(k^2(S + \log(n+T)) + \log(1/\varepsilon)) O ( k 2 ( S + log ( n + T )) + log ( 1/ ε ))
and time 2 O ( k 2 ( S + log ( n + T ) ) / ε 2^{O(k^2(S+\log(n+T))}/\varepsilon 2 O ( k 2 ( S + l o g ( n + T )) / ε . For every x ∈ { 0 , 1 } n x \in\{0,1\}^n x ∈ { 0 , 1 } n , the acceptance probabilities satisfy
∣ Pr [ M ′ ( x ) accepts ] − Pr [ M ( x ) accepts ] ∣ ≤ ε . \left|\Pr[M'(x)\text{ accepts}] - \Pr[M(x)\text{ accepts}]\right| \le\varepsilon. ∣ Pr [ M ′ ( x ) accepts ] − Pr [ M ( x ) accepts ] ∣ ≤ ε .
Decomposing executions using checkpoint transitions Fix an input x x x . We may assume k ≤ T + 1 k \le T + 1 k ≤ T + 1 . Let J 0 = { 1 , … , T + 1 } J_0 = \{1,\ldots,T+1\} J 0 = { 1 , … , T + 1 } contain all random-tape positions that M ( x ) M(x) M ( x ) may read. A visit is a maximal consecutive stay at a single random-tape cell. Because M M M is locally read-k k k , once the head leaves a cell after that cell’s k k k -th visit, it can never return to that cell. Consequently, the rest of the computation is confined to the side of the departed cell on which the head remains.
This observation lets us shrink the interval of accessible cells. Start with I = J 0 I = J_0 I = J 0 . In the remaining execution, consider the first departure that terminates the k k k -th visit to some cell v ∈ I v \in I v ∈ I , and mark that departure. If the computation continues, replace I I I by the connected component of I ∖ { v } I \setminus\{v\} I ∖ { v } that contains the head immediately after this departure, and repeat the same rule. The marked departures therefore split the execution into a nested sequence of intervals, each obtained from the previous one by removing a single cell and keeping the side containing the head.
The retained interval alone does not determine how the simulation should continue, since some bits inside the interval may already have been read. We therefore also record the execution’s boundary history : the chronological list of crossings of the interval’s boundary, together with their times, positions, and configurations (control state, input- and work-tape head positions, and work-tape contents). Given an assignment to the bits in the interval, we can reconstruct each portion of the past execution inside the interval from the recorded crossings that enter the interval, and we can check the reconstructed execution against the recorded crossings that leave it.
A checkpoint D = ( I D , H D ) D=(I_D,H_D) D = ( I D , H D ) consists of two objects. The interval I D I_D I D is the retained interval immediately after the marked departure, that is, the connected component of I ∖ { v } I\setminus\{v\} I ∖ { v } containing the head after it leaves v v v . The boundary history H D H_D H D is the chronological list of all crossings of the two boundaries of I D I_D I D , from the start of the computation through the marked departure, together with their times, positions, and configurations. We form the checkpoint at this departure, before the head begins its next visit. At that moment every cell in I D I_D I D has been visited fewer than k k k times: before the departure, every cell in I ∖ { v } I\setminus\{v\} I ∖ { v } had been visited fewer than k k k times, and I D ⊆ I ∖ { v } I_D\subseteq I\setminus\{v\} I D ⊆ I ∖ { v } . Since each boundary of I D I_D I D is crossed O ( k ) O(k) O ( k ) times, the history H D H_D H D has list size at most O ( k ) O(k) O ( k ) . A checkpoint transition is the passage from one checkpoint to the next, or from a checkpoint to the point where the computation stops.
Executions inside an interval. To carry out the consistency checks recursively, we simulate the computation inside an interval while using recorded crossing information to skip the intervening computation outside it. An execution constraint C C C on an interval J J J specifies an initial configuration, random-head position, and time; prescribed bit values and crossing histories; and boundary tables specifying exits from and returns to J J J .
For a fixed assignment u ∈ { 0 , 1 } J u\in\{0,1\}^{J} u ∈ { 0 , 1 } J , let Exec r ( C , u ) \operatorname{Exec}_{r}(C,u) Exec r ( C , u ) denote the stopping report of the following deterministic execution. Starting from the initial data specified by C C C , the execution follows M M M inside J J J , using u u u for random reads and checking the requirements of C C C . Each exit from J J J is handled by the boundary tables. When the boundary checks pass and a return is supplied, the execution skips the external computation and resumes at the prescribed configuration and time. The visit counts inside J J J are not reset when the execution returns to J J J . An attempted ( r + 1 ) (r+1) ( r + 1 ) -st visit causes overflow before the new visit is counted or its bit is read.
The execution stops at the first normal termination, overflow, or failed check. Its stopping report ρ \rho ρ records the configuration, head position, time, and reason for stopping, together with the details of a failed check when applicable. The requirements of C C C are checked during execution; the assignment u u u need not satisfy them in advance.
Distributions of transitions between checkpoints. Let 2 ≤ r ≤ k 2\leq r\leq k 2 ≤ r ≤ k and let C ∈ E r C\in\mathcal{E}_r C ∈ E r be an execution constraint on an interval L L L , where the families E r \mathcal{E}_r E r are defined in § 3.4 and include child constraints constructed from incorrect guesses. For each assignment u ∈ { 0 , 1 } L u\in\{0,1\}^{L} u ∈ { 0 , 1 } L , let D 0 , D 1 , … , D m D_0,D_1,\ldots,D_m D 0 , D 1 , … , D m be the successive checkpoints encountered by the constrained run of C C C with visit threshold r r r , where the start of the execution is the initial checkpoint D 0 = ( L , ( ) ) D_0=(L,()) D 0 = ( L , ( )) . Let ρ = Exec r ( C , u ) \rho=\operatorname{Exec}_r(C,u) ρ = Exec r ( C , u ) be the corresponding stopping report. The next outcome after D j D_j D j is O j = D j + 1 O_j=D_{j+1} O j = D j + 1 if j < m j<m j < m , and O m = ρ O_m=\rho O m = ρ .
Let U L U_L U L be uniform over { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L . Drawing u u u according to U L U_L U L induces a distribution on checkpoint paths and stopping reports. For a checkpoint D D D with Pr U L [ D j = D ] > 0 \Pr_{U_L}[D_j=D]>0 Pr U L [ D j = D ] > 0 , define
K j C , r ( D , o ) : = Pr U L [ O j = o ∣ D j = D ] . K_j^{C,r}(D,o):=\Pr_{U_L}[O_j=o\mid D_j=D]. K j C , r ( D , o ) := U L Pr [ O j = o ∣ D j = D ] .
We call K j C , r ( D , ⋅ ) K_j^{C,r}(D,\cdot) K j C , r ( D , ⋅ ) the transition distribution at D D D .
The Markov property of checkpoints. For a checkpoint D D D with Pr U L [ D j = D ] > 0 \Pr_{U_L}[D_j=D]>0 Pr U L [ D j = D ] > 0 , let I = I D I=I_D I = I D . Write U I U_I U I for the bits of U L U_L U L at positions in I I I . Conditioned on D j = D D_j=D D j = D , the internal assignment U I U_I U I is uniform over the assignments consistent with D D D . Conditioning on earlier checkpoints restricts only the bits of U L U_L U L outside I I I . The next outcome under C C C depends only on D D D and U I U_I U I . Thus, for every sequence of checkpoints d 0 , … , d j d_0,\ldots,d_j d 0 , … , d j with d j = D d_j=D d j = D that has positive probability,
Pr U L [ O j = o ∣ D 0 = d 0 , … , D j = d j ] = K j C , r ( D , o ) . (1) \Pr_{U_L}[O_j=o \mid D_0=d_0,\ldots,D_j=d_j]=K_j^{C,r}(D,o). \tag*{(1)} U L Pr [ O j = o ∣ D 0 = d 0 , … , D j = d j ] = K j C , r ( D , o ) . (1)
For any stopping report ρ \rho ρ , the chain rule of conditional probability now gives
Pr U L [ Exec r ( C , U L ) = ρ ] = ∑ m = 0 T + 1 ∑ D 0 , … , D m ( ∏ i = 0 m − 1 K i C , r ( D i , D i + 1 ) ) K m C , r ( D m , ρ ) . (2) \Pr_{U_L}[\operatorname{Exec}_r(C,U_L)=\rho]=\sum_{m=0}^{T+1}\ \sum_{D_0,\ldots,D_m}\left(\prod_{i=0}^{m-1}K_i^{C,r}(D_i,D_{i+1})\right)K_m^{C,r}(D_m,\rho). \tag*{(2)} U L Pr [ Exec r ( C , U L ) = ρ ] = m = 0 ∑ T + 1 D 0 , … , D m ∑ ( i = 0 ∏ m − 1 K i C , r ( D i , D i + 1 ) ) K m C , r ( D m , ρ ) . (2)
Here the inner sum ranges over checkpoint sequences of positive probability. Thus, to reproduce the stopping distribution, it suffices to sample the transition distributions K j C , r K_j^{C,r} K j C , r .
A recursive sampler for checkpoint transitions. We now replace direct simulation of each checkpoint transition by a recursive rejection-sampling procedure which uses only read-once randomness. At a current checkpoint, we first guess the next checkpoint or stopping report, together with the information needed to verify it. We then check this guess using a randomized execution with a smaller visit bound. If the check fails, we repeat both the guess and the check with fresh independent randomness. The verification is itself randomized: a fixed guess may pass for some assignments to the random tape and fail for others. We will implement this verification by recursively sampling the lower-level execution’s report.
Specifically, we construct a procedure Sampler r ( C ) \operatorname{Sampler}_r(C) Sampler r ( C ) that uses read-once randomness, terminates almost surely, and, for every C ∈ C r C\in\mathcal{C}_r C ∈ C r on an interval L L L and every stopping report ρ \rho ρ , satisfies
Pr [ Sampler r ( C ) = ρ ] = Pr U L [ Exec r ( C , U L ) = ρ ] . (3) \Pr[\operatorname{Sampler}_r(C)=\rho]=\Pr_{U_L}[\operatorname{Exec}_r(C,U_L)=\rho]. \tag*{(3)} Pr [ Sampler r ( C ) = ρ ] = U L Pr [ Exec r ( C , U L ) = ρ ] . (3)
For r = 1 r=1 r = 1 , follow Exec 1 \operatorname{Exec}_1 Exec 1 , drawing a fresh uniform bit when a position is first read and retaining that bit throughout the visit. A second visit cannot read the discarded bit: the execution returns overflow before that read, unless an earlier check has already returned a report. This gives the required report distribution. For r ≥ 2 r\ge2 r ≥ 2 , assume the claimed termination and distributional equality hold for every constraint in C r − 1 \mathcal{C}_{r-1} C r − 1 . Initialize the current checkpoint to D 0 D_0 D 0 , and consider a reachable current checkpoint D D D , with I = I D I=I_D I = I D .
We call the guessed data a candidate Y Y Y . It specifies a proposed next outcome π ( Y ) \pi(Y) π ( Y ) , which is either a checkpoint or a stopping report; the crossing histories needed to verify a proposed new checkpoint; and the information needed to complete an r r r -th visit, if one occurs before that outcome. The completion information is a pair ( v , β ) (v,\beta) ( v , β ) , where v ∈ I v\in I v ∈ I is the position of this visit and β \beta β is the guessed bit there, or a marker ⊥ \bot ⊥ indicating that the next outcome occurs without a new r r r -th visit.
The visit bound decreases because, at D D D , every position in I I I has been visited fewer than r r r times. Up to the first attempted r r r -th visit, the execution inside I I I therefore obeys visit bound r − 1 r-1 r − 1 , counting visits both before and after D D D . A capped-( r − 1 ) (r-1) ( r − 1 ) execution can reproduce this portion and stop immediately before that visit. Its stopping configuration, position, and time, together with the proposed bit and the history counters, suffice to complete the visit and determine the next outcome. It must also verify the history through D D D , since reaching D D D already restricts the bits in I I I .
Given Y Y Y , the procedure CreateConstraint ( C , D , Y ) \operatorname{CreateConstraint}(C,D,Y) CreateConstraint ( C , D , Y ) constructs a child constraint C Y C_Y C Y on I I I by combining the inherited requirements of C C C , the histories H D \mathcal{H}_D H D , and the requirements specified by Y Y Y . If the construction returns ⊥ \bot ⊥ , reject the trial. Otherwise, the child execution is specified as follows. The child retains the initial data of C C C if its initial position lies in I I I . Otherwise, the construction checks the first entrance into I I I recorded in H D \mathcal{H}_D H D , and starts the child immediately after that entrance. For a fixed assignment u ∈ { 0 , 1 } I u \in\{0,1\}^{I} u ∈ { 0 , 1 } I , the execution E x e c r − 1 ( C Y , u ) \mathbf{Exec}_{r-1}(C_Y,u) Exec r − 1 ( C Y , u ) follows M M M inside I I I , checks the requirements of C Y C_Y C Y , and uses its boundary tables for excursions outside I I I . It uses the same assignment u u u throughout and does not reset visit counts at D D D . It returns its first stopping report; an attempted r r r -th visit produces an overflow report before that visit is counted or its bit is read.
Given a child report ρ \rho ρ , define the deterministic check
χ Y ( ρ ) : = F i n i s h A n d C h e c k ( C , D , Y , C Y , ρ ) . \chi_Y(\rho) := \mathbf{FinishAndCheck}(C,D,Y,C_Y,\rho). χ Y ( ρ ) := FinishAndCheck ( C , D , Y , C Y , ρ ) .
This check first verifies that the child execution has reproduced the history through D D D . If Y Y Y proposes ( v , β ) (v,\beta) ( v , β ) , it requires ρ \rho ρ to be an overflow report immediately before an r r r -th visit to v v v . It recovers the history counters from the reported time using Theorem 3.8, completes that visit using β \beta β , and applies the prescribed departure and boundary rules to obtain the next outcome. It then compares this outcome with π ( Y ) \pi(Y) π ( Y ) . If Y Y Y proposes ⊥ \bot ⊥ , the check instead requires ρ \rho ρ itself to be the stopping report π ( Y ) \pi(Y) π ( Y ) . For a proposed new checkpoint, it also verifies the crossing histories supplied by Y Y Y .
Whenever C Y ≠ ⊥ C_Y \ne\bot C Y = ⊥ , it belongs to C r − 1 \mathcal{C}_{r-1} C r − 1 , including when Y Y Y is an incorrect guess. The induction hypothesis therefore allows us to sample the child report using read-once randomness and gives
Pr [ χ Y ( S a m p l e r r − 1 ( C Y ) ) = 1 ] = Pr U I [ χ Y ( E x e c r − 1 ( C Y , U I ) ) = 1 ] . (4) \Pr[\chi_Y(\mathbf{Sampler}_{r-1}(C_Y))=1] = \Pr_{U_I}[\chi_Y(\mathbf{Exec}_{r-1}(C_Y,U_I))=1]. \tag*{(4)} Pr [ χ Y ( Sampler r − 1 ( C Y )) = 1 ] = U I Pr [ χ Y ( Exec r − 1 ( C Y , U I )) = 1 ] . (4)
Thus the recursive call followed by χ Y \chi_Y χ Y implements the randomized verification of Y Y Y : although χ Y \chi_Y χ Y is deterministic given its report, that report is random.
Let Y r \mathcal{Y}_r Y r be the fixed space of candidate encodings, and put Q r = ∣ Y r ∣ Q_r = |\mathcal{Y}_r| Q r = ∣ Y r ∣ . Each valid encoding represents one candidate, and each candidate has a unique encoding. At D D D , perform independent trials of the following form:
Y ∼ Unif ( Y r ) , C Y ← C r e a t e C o n s t r a i n t ( C , D , Y ) , ρ ← S a m p l e r r − 1 ( C Y ) , o k ← χ Y ( ρ ) . \begin{aligned}
Y &\sim\operatorname{Unif}(\mathcal{Y}_r),\\
C_Y &\leftarrow\mathbf{CreateConstraint}(C,D,Y),\\
\rho&\leftarrow\mathbf{Sampler}_{r-1}(C_Y),\\
\mathrm{ok} &\leftarrow\chi_Y(\rho).
\end{aligned} Y C Y ρ ok ∼ Unif ( Y r ) , ← CreateConstraint ( C , D , Y ) , ← Sampler r − 1 ( C Y ) , ← χ Y ( ρ ) .
An invalid encoding or a construction returning ⊥ \bot ⊥ rejects the trial before the recursive call. Otherwise, accept precisely when o k = 1 \mathrm{ok}=1 ok = 1 . The proposal and the recursive call use independent fresh coins, and a rejected trial is repeated at the same D D D . For an accepted candidate, set o = π ( Y ) o = \pi(Y) o = π ( Y ) . If o o o is a checkpoint, update D ← o D \leftarrow o D ← o and repeat at that checkpoint; otherwise, return the stopping report o o o .
To determine the distribution of an accepted outcome, consider first a fixed assignment u u u to I I I . If u u u is consistent with D D D , exactly one candidate with C Y ≠ ⊥ C_Y \ne\bot C Y = ⊥ satisfies
χ Y ( E x e c r − 1 ( C Y , u ) ) = 1. \chi_Y(\mathbf{Exec}_{r-1}(C_Y,u))=1. χ Y ( Exec r − 1 ( C Y , u )) = 1.
It is the candidate formed from a capped-r r r execution under C \mathcal{C} C that reaches D D D with internal assignment u u u . Its next outcome, completion data, and crossing histories do not depend on the compatible assignment outside I I I . If u u u is inconsistent with D D D , no candidate passes. These assertions are proved in Theorems 3.10 and 3.11. Thus the randomized check accepts each candidate with probability equal to the probability that U I U_I U I is consistent with D D D and produces that candidate.
Let q D > 0 q_D > 0 q D > 0 be the probability that U I U_I U I is consistent with D D D . Summing over candidates that propose outcome o o o gives
q D K j C , r ( D , o ) = ∑ Y : π ( Y ) = o Pr U I [ χ Y ( Exec r − 1 ( C Y , U I ) ) = 1 ] , (5) q_D K_j^{C,r}(D,o) = \sum_{Y:\pi(Y)=o} \Pr_{U_I}\left[\chi_Y\left(\operatorname{Exec}_{r-1}(C_Y,U_I)\right)=1\right], \tag*{(5)} q D K j C , r ( D , o ) = Y : π ( Y ) = o ∑ U I Pr [ χ Y ( Exec r − 1 ( C Y , U I ) ) = 1 ] , (5)
where candidates with C Y = ⊥ C_Y = \bot C Y = ⊥ contribute zero. Each assignment consistent with D D D and producing o o o is counted in exactly one summand. Combining this identity with (4) and the uniform proposal probability 1 / Q r 1/Q_r 1/ Q r , one trial satisfies
Pr [ o k = 1 ∧ π ( Y ) = o ] = 1 Q r ∑ Y : π ( Y ) = o Pr [ χ Y ( S a m p l e r r − 1 ( C Y ) ) = 1 ] = q D Q r K j C , r ( D , o ) . (6) \begin{aligned}
\Pr[\mathrm{ok}=1 \land\pi(Y)=o] &= \frac{1}{Q_r}\sum_{Y:\pi(Y)=o}\Pr\left[\chi_Y\left(\mathbf{Sampler}_{r-1}(C_Y)\right)=1\right] \\
&= \frac{q_D}{Q_r}K_j^{C,r}(D,o). \tag*{(6)}
\end{aligned} Pr [ ok = 1 ∧ π ( Y ) = o ] = Q r 1 Y : π ( Y ) = o ∑ Pr [ χ Y ( Sampler r − 1 ( C Y ) ) = 1 ] = Q r q D K j C , r ( D , o ) . (6)
Summing over o o o , a trial succeeds with probability q D / Q r > 0 q_D/Q_r > 0 q D / Q r > 0 . Independent trials therefore accept almost surely, and dividing (6) by q D / Q r q_D/Q_r q D / Q r shows that the first accepted outcome has distribution K j C , r ( D , ⋅ ) K_j^{C,r}(D,\cdot) K j C , r ( D , ⋅ ) .
The sampler starts at the reachable checkpoint D 0 D_0 D 0 . At each subsequent stage, the accepted outcome is supported on actual next outcomes, so every checkpoint reached by the sampler is reachable by the capped execution. Each recursive call terminates almost surely by induction, and each continuation strictly shrinks the current interval. Hence the sampler also terminates almost surely. By (1) , the same transition distribution remains valid when conditioned on the entire preceding checkpoint sequence. Consequently, the sampler produces a checkpoint path D 0 , … , D m D_0,\ldots,D_m D 0 , … , D m followed by report ρ \rho ρ with probability
( ∏ i = 0 m − 1 K i C , r ( D i , D i + 1 ) ) K m C , η ( D m , ρ ) . \left(\prod_{i=0}^{m-1} K_i^{C,r}(D_i,D_{i+1})\right) K_m^{C,\eta}(D_m,\rho). ( i = 0 ∏ m − 1 K i C , r ( D i , D i + 1 ) ) K m C , η ( D m , ρ ) .
This equals the corresponding summand in (2) . Summing over paths proves (3) and completes the induction.
We now instantiate the construction at the original machine. Let C 0 C_0 C 0 be the constraint on J 0 = { 1 , … , T + 1 } J_0 = \{1,\ldots,T+1\} J 0 = { 1 , … , T + 1 } with no prescribed bit values, no prescribed crossings, and trivial boundary tables, so that E x e c k ( C 0 , U J 0 ) \mathbf{Exec}_k(C_0,U_{J_0}) Exec k ( C 0 , U J 0 ) is the stopping report of the original execution of M ( x ) M(x) M ( x ) on a uniformly random tape. By (3) with r = k r=k r = k and C = C 0 C=C_0 C = C 0 , the procedure S a m p l e r k ( C 0 ) \mathbf{Sampler}_k(C_0) Sampler k ( C 0 ) has the same stopping-report distribution as M ( x ) M(x) M ( x ) ; in particular, its acceptance probability equals that of M ( x ) M(x) M ( x ) . Put b = C 0 ( S + log ( n + T + 2 ) ) b = C_0(S+\log(n+T+2)) b = C 0 ( S + log ( n + T + 2 )) for a sufficiently large constant C 0 C_0 C 0 . We define M ′ M' M ′ to run S a m p l e r k ( C 0 ) \mathbf{Sampler}_k(C_0) Sampler k ( C 0 ) and, after 2 O ( k 2 b ) / ε 2^{O(k^2b)}/\varepsilon 2 O ( k 2 b ) / ε steps, to halt and return ⊥ \bot ⊥ .
Space and running time. At recursion level r r r , a boundary is crossed at most 2 r 2r 2 r times, so a checkpoint or candidate uses O ( r b ) O(rb) O ( r b ) bits, there are at most 2 O ( r b ) 2^{O(rb)} 2 O ( r b ) checkpoints per stage, and proposals can be generated with Q r = 2 O ( r b ) Q_r = 2^{O(rb)} Q r = 2 O ( r b ) . Inherited history lists are stored by reference; their references, cutoffs, and counters, together with inherited bit requirements, use O ( k b ) O(kb) O ( k b ) bits per level. Thus each level retains O ( ( r + k ) b ) O((r+k)b) O (( r + k ) b ) bits, and the workspace is
∑ r = 1 k O ( ( r + k ) b ) = O ( k 2 b ) . \sum_{r=1}^{k} O((r+k)b) = O(k^2b). r = 1 ∑ k O (( r + k ) b ) = O ( k 2 b ) .
For the running time, a small q D q_D q D may require many trials, but it also makes D D D unlikely. If p D p_D p D is the probability of reaching D D D at its stage, consistency of the internal assignment is necessary, so p D ≤ q D p_D \le q_D p D ≤ q D and
p D Q r q D ≤ Q r . (7) \frac{p_D Q_r}{q_D} \le Q_r. \tag*{(7)} q D p D Q r ≤ Q r . (7)
Hence each checkpoint contributes at most Q r Q_r Q r times the cost of a trial to the expected cost, and with 2 O ( r b ) 2^{O(rb)} 2 O ( r b ) checkpoints per stage and T + 1 T+1 T + 1 stages, level r r r costs 2 O ( r b ) 2^{O(rb)} 2 O ( r b ) times a trial in expectation. Unrolling over k k k levels yields expected time 2 O ( k 2 b ) 2^{O(k^2b)} 2 O ( k 2 b ) . By Markov’s inequality, truncating after 2 O ( k 2 b ) / ε 2^{O(k^2b)}/\varepsilon 2 O ( k 2 b ) / ε steps changes the acceptance probability by at most ε \varepsilon ε . The cutoff counter uses O ( k 2 b + log ( 1 / ε ) ) O(k^2b+\log(1/\varepsilon)) O ( k 2 b + log ( 1/ ε )) additional space, so M ′ M' M ′ runs in space O ( k 2 b + log ( 1 / ε ) ) O(k^2b+\log(1/\varepsilon)) O ( k 2 b + log ( 1/ ε )) and time 2 O ( k 2 b ) / ε 2^{O(k^2b)}/\varepsilon 2 O ( k 2 b ) / ε .
Fresh-Coin Simulation
Some basic definitions. A configuration of M M M consists of its input-tape head position, finite control state, work-tape head position, and work-tape contents. The random-tape head position is recorded separately. The initial configuration has time 0. After each application of M M M ’s transition function, the time increases by 1. Thus, the configuration at time t t t is the one reached after exactly t t t transitions. For q ≥ 1 q \ge1 q ≥ 1 , the cut q ∣ q + 1 q \mid q+1 q ∣ q + 1 is the boundary between random-tape positions q q q and q + 1 q+1 q + 1 . We also call it cut q q q for short. The random-tape head crosses this cut when it moves from q q q to q + 1 q+1 q + 1 or from q + 1 q+1 q + 1 to q q q . We also use cut 0 for the left boundary of cell 1; the random head never crosses this cut, so its history is empty. For an interval [ a , b ] [a,b] [ a , b ] of the random tape, we define ∂ [ a , b ] = { a − 1 , b } \partial[a,b]=\{a-1,b\} ∂ [ a , b ] = { a − 1 , b } , ∂ L [ a , b ] = a − 1 \partial_L[a,b]=a-1 ∂ L [ a , b ] = a − 1 and ∂ R [ a , b ] = b \partial_R[a,b]=b ∂ R [ a , b ] = b .
A probability distribution on a finite set Ω \Omega Ω is a function μ : Ω → [ 0 , 1 ] \mu:\Omega\to[0,1] μ : Ω → [ 0 , 1 ] satisfying ∑ ω ∈ Ω μ ( ω ) = 1 \sum_{\omega\in\Omega}\mu(\omega)=1 ∑ ω ∈ Ω μ ( ω ) = 1 . We write X ∼ μ X\sim\mu X ∼ μ when X X X has distribution μ \mu μ , and L ( X ) \mathcal{L}(X) L ( X ) for the distribution of a random variable X X X . The uniform distribution on Ω \Omega Ω is denoted by Unif ( Ω ) \operatorname{Unif}(\Omega) Unif ( Ω ) . For a finite set J J J , the uniform distribution on { 0 , 1 } J \{0,1\}^{J} { 0 , 1 } J is denoted by U J U_J U J .
Fix an input x ∈ { 0 , 1 } n x\in\{0,1\}^{n} x ∈ { 0 , 1 } n and a locally read-k k k machine M M M using time at most T T T and work space at most S S S . All configurations below use at most S S S work-tape cells. When simulating a transition from any such configuration, an attempted access beyond these cells instead enters a fixed rejecting state, leaves all tape heads and work-tape contents unchanged, and advances time by one. We use this convention throughout, including in executions under constraints. It does not change any computation of M M M from its original initial configuration, and ensures that simulations from guessed configurations obey the same space bound. All intervals below are contained in { 1 , … , T + 1 } \{1,\ldots,T+1\} { 1 , … , T + 1 } ; random-head positions in records and reports belong to { 1 , … , T + 2 } \{1,\ldots,T+2\} { 1 , … , T + 2 } , allowing one step beyond the right endpoint. All timestamps belong to { 0 , … , T } \{0,\ldots,T\} { 0 , … , T } . Let
b : = C 0 ( S + log ( n + T + 2 ) ) , b := C_0(S+\log(n+T+2)), b := C 0 ( S + log ( n + T + 2 )) ,
where C 0 C_0 C 0 is a sufficiently large constant depending only on M M M . This budget suffices to encode a configuration, a random-head position, and a timestamp.
Organization of this section. In § 3.1 , we define capped-r r r executions under constraints and show that the initial constraint reproduces the computation of M M M . In § 3.3 , we construct a recursive sampler using read-once randomness. We prove equality of its return-report distribution with that of the corresponding capped execution in § 3.4 . Finally, § 3.5 bounds its space and expected running time, and imposes a time cutoff to prove the main theorem.
Capped-r r r Executions under Constraints
We first define crossing histories, execution constraints, return reports, and checkpoints, and then use them to define capped-r r r executions. Crossing histories record movements across specified cuts; execution constraints prescribe the initial data, bit and crossing requirements, and boundary histories used by the execution.
Definition 3.1 (Crossing History). A crossing history is a finite ordered sequence of records
L = ( ( s j , x j , y j , c j ) ) j = 1 ℓ . L = ((s_j,x_j,y_j,c_j))_{j=1}^{\ell}. L = (( s j , x j , y j , c j ) ) j = 1 ℓ . Here 0 ≤ s 1 < ⋯ < s ℓ < T 0 \le s_1 < \cdots< s_\ell< T 0 ≤ s 1 < ⋯ < s ℓ < T and x j , y j x_j,y_j x j , y j are indices of the random tape s.t. ∣ x j − y j ∣ = 1 \lvert x_j-y_j\rvert=1 ∣ x j − y j ∣ = 1 . c j c_j c j is a configuration of M M M running on x x x . One can think that a record ( s j , x j , y j , c j ) (s_j,x_j,y_j,c_j) ( s j , x j , y j , c j ) means that the random-tape head is at position x j x_j x j at time s j s_j s j , and that one transition moves it to position y j y_j y j and produces configuration c j c_j c j at time s j + 1 s_j+1 s j + 1 . The empty history (L L L being empty) is allowed.
A record ( s j , x j , y j , c j ) (s_j,x_j,y_j,c_j) ( s j , x j , y j , c j ) crosses a cut q ∣ q + 1 q \mid q+1 q ∣ q + 1 if { x j , y j } = { q , q + 1 } \{x_j,y_j\}=\{q,q+1\} { x j , y j } = { q , q + 1 } . If every record of L L L crosses the cut q ∣ q + 1 q \mid q+1 q ∣ q + 1 , then say L L L is a crossing history at the cut q ∣ q + 1 q \mid q+1 q ∣ q + 1 .
Definition 3.2 (Execution Constraint). An execution constraint is a tuple
C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) . C=(J,\sigma_0,i_0,t_0,\mathcal{H},\mathcal{B},H_L,H_R). C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) . where:
J = [ a , b ] ⊆ { 1 , … , T + 1 } J=[a,b]\subseteq\{1,\ldots,T+1\} J = [ a , b ] ⊆ { 1 , … , T + 1 } is a nonempty integer interval of random-tape positions.
( σ 0 , i 0 , t 0 ) (\sigma_0,i_0,t_0) ( σ 0 , i 0 , t 0 ) specifies an initial configuration, random-head position, and a timestamp, with i 0 ∈ J i_0\in J i 0 ∈ J and 0 ≤ t 0 ≤ T 0\le t_0\le T 0 ≤ t 0 ≤ T .
H = { ( q , L q , τ q ) : q ∈ Q } \mathcal{H}=\{(q,L_q,\tau_q):q\in Q\} H = {( q , L q , τ q ) : q ∈ Q } is a collection of crossing requirements , where Q ⊆ { 0 , … , T + 1 } Q\subseteq\{0,\ldots,T+1\} Q ⊆ { 0 , … , T + 1 } is a set of cut indices. Each entry has t 0 ≤ τ q ≤ T t_0\le\tau_q\le T t 0 ≤ τ q ≤ T , and L q L_q L q is a crossing history at cut q q q whose records all have timestamps in [ t 0 , τ q ) [t_0,\tau_q) [ t 0 , τ q ) . It prescribes the complete crossing history at that cut during this interval. Each cut has at most one entry in H \mathcal{H} H ; cuts need not lie inside J J J .
B \mathcal{B} B is a finite collection of pairs ( v , β ) ∈ J × { 0 , 1 } (v,\beta)\in J\times\{0,1\} ( v , β ) ∈ J × { 0 , 1 } .
One can think that B \mathcal{B} B is used to remember that the bit at position v v v of the random tape is β \beta β .
H L , H R H_L,H_R H L , H R are two crossing histories at a − 1 ∣ a a-1\mid a a − 1 ∣ a and b ∣ b + 1 b\mid b+1 b ∣ b + 1 , respectively, with the restriction that for any ( s j , x j , y j , c j ) (s_j,x_j,y_j,c_j) ( s j , x j , y j , c j ) in H L H_L H L or in H R H_R H R , the s j s_j s j has to be in [ t 0 , T ) [t_0,T) [ t 0 , T ) .
Note that one can use H L , H R H_L,H_R H L , H R to supply some information about those computations of M M M that depend on the randomness out of J J J .
A return report records where and why the execution stops, together with the details of a failed check when applicable.
Definition 3.3 (Return Report). Given an execution constraint C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) C=(J,\sigma_0,i_0,t_0,\mathcal{H},\mathcal{B},H_L,H_R) C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) , a return report is a tuple
R = ( κ , σ , i , t , γ ) , κ ∈ { H A L T , O V E R F L O W , F A I L } . R=(\kappa,\sigma,i,t,\gamma),\qquad\kappa\in\{\mathrm{HALT},\mathrm{OVERFLOW},\mathrm{FAIL}\}. R = ( κ , σ , i , t , γ ) , κ ∈ { HALT , OVERFLOW , FAIL } . Here σ \sigma σ is a configuration, i i i is a random-head position, and t t t is a timestamp. The tag κ \kappa κ will be used to indicate a normal termination, an overflow situation, or a violation of a requirement of C C C , respectively.
For κ ∈ { H A L T , O V E R F L O W } \kappa\in\{\mathrm{HALT},\mathrm{OVERFLOW}\} κ ∈ { HALT , OVERFLOW } , we set γ = ⊥ \gamma=\bot γ = ⊥ . For κ = F A I L \kappa=\mathrm{FAIL} κ = FAIL , using history, bit, boundary as 3 fixed labels, the field γ \gamma γ has one of the following forms:
(history, q q q , e e e ), identifying an entry ( q , L q , τ q ) ∈ H (q,L_q,\tau_q) \in\mathcal{H} ( q , L q , τ q ) ∈ H . Here e e e is a crossing record involved in a disagreement with L q L_q L q , or a prescribed record of L q L_q L q left unconsumed.
(bit, v v v , β \beta β ), identifying a prescribed bit pair ( v , β ) ∈ B (v,\beta) \in\mathcal{B} ( v , β ) ∈ B whose requirement is violated.
(boundary, s s s , e e e ), identifying a boundary history H s H_s H s , where s ∈ { L , R } s \in\{L,R\} s ∈ { L , R } . Here e e e is an exit or entrance record involved in the violation, with e = ⊥ e = \perp e =⊥ if a required entrance record is absent.
For simplicity of description, we also use the terminology “return κ \kappa κ at ( σ , i , t ) (\sigma,i,t) ( σ , i , t ) with γ \gamma γ ” to alternatively denote returning a report ( κ , σ , i , t , γ ) (\kappa,\sigma,i,t,\gamma) ( κ , σ , i , t , γ ) .
A nonterminal checkpoint stores the current interval and its boundary histories.
Definition 3.4 (Nonterminal Checkpoint). Fix an execution constraint C \mathcal{C} C with interval J J J and initial time t 0 t_0 t 0 . A noninitial nonterminal checkpoint is
D = ( I D , H D ) , D = (I_D,\mathcal{H}_D), D = ( I D , H D ) , such that
I D I_D I D is a nonempty interval contained in J J J .
H D = { ( q , L q , D , t D ) : q ∈ ∂ I D } \mathcal{H}_D = \{(q,L_{q,D},t_D) : q \in\partial I_D\} H D = {( q , L q , D , t D ) : q ∈ ∂ I D } .
L q , D L_{q,D} L q , D is a crossing history at q ∈ ∂ I D q \in\partial I_D q ∈ ∂ I D , with every timestamp in [ t 0 , t D ) [t_0,t_D) [ t 0 , t D ) ;
The two histories contain at least one record in total, and their latest record is unique. Set t D = 1 + max { s : ( s , x , y , c ) ∈ L q , D , q ∈ ∂ I D } t_D = 1 + \max\{s : (s,x,y,c) \in L_{q,D},\ q \in\partial I_D\} t D = 1 + max { s : ( s , x , y , c ) ∈ L q , D , q ∈ ∂ I D } .
We define the initial checkpoint of C \mathcal{C} C as D 0 = ( J , ∅ ) D_0 = (J,\varnothing) D 0 = ( J , ∅ ) , with t D 0 : = t 0 t_{D_0} := t_0 t D 0 := t 0 .
Definition 3.5 (Capped Execution under a Constraint). We define the capped-r r r execution of M M M on input C \mathcal{C} C and z J z_J z J , which is denoted as Exec r ( C , z J ) \operatorname{Exec}_r(\mathcal{C},z_J) Exec r ( C , z J ) , as follows.
The input C \mathcal{C} C is an execution constraint denoted as C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) \mathcal{C} = (J,\sigma_0,i_0,t_0,\mathcal{H},\mathcal{B},H_L,H_R) C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) . The input z J z_J z J is a (random) string over { 0 , 1 } J \{0,1\}^J { 0 , 1 } J . The parameter r r r is an integer with r ≥ 1 r \ge1 r ≥ 1 .
The output is a report ( κ , σ , i , t , γ ) (\kappa,\sigma,i,t,\gamma) ( κ , σ , i , t , γ ) defined by Theorem 3.3. We emphasize that the execution will stop immediately after returning a report.
We also emphasize here that in our algorithm description, a visit to a position of the random tape refers to the procedure of a maximal consecutive stay at that position. The initial placement at an initial position i 0 i_0 i 0 is considered as the first visit to i 0 i_0 i 0 . In a capped-r r r execution, a position v ∈ J v \in J v ∈ J is called exhausted once its r r r -th visit has ended.
The execution is formally described as follows. It first performs the initialization in Item 1 and then runs the repeated transition rule in Item 2 until a report is returned. Item 3, Item 4, and Item 5 define auxiliary checking rules that are invoked by the first two items.
Initialization. Set
( σ , i , t ) = ( σ 0 , i 0 , t 0 ) . (\sigma,i,t) = (\sigma_0,i_0,t_0). ( σ , i , t ) = ( σ 0 , i 0 , t 0 ) . For each v ∈ J v \in J v ∈ J , let N v N_v N v count the number of visits to v v v . Initialize
N i 0 = 1 , N v = 0 ( v ∈ J ∖ { i 0 } ) . N_{i_0} = 1,\qquad N_v = 0\quad(v \in J \setminus\{i_0\}). N i 0 = 1 , N v = 0 ( v ∈ J ∖ { i 0 }) . Associate history counters j q j_q j q ( q ∈ Q ) (q \in Q) ( q ∈ Q ) , j L , j R j_L,j_R j L , j R with L q L_q L q , H L , H R H_L,H_R H L , H R , respectively. Each history counter gives the index of the next unused record in its list. Initialize j q = 1 j_q = 1 j q = 1 for every q ∈ Q q \in Q q ∈ Q , and set j L = j R = 1 j_L = j_R = 1 j L = j R = 1 .
If r ≥ 2 r \ge2 r ≥ 2 , set I = J I=J I = J and record the initial checkpoint
D 0 = ( J , ∅ ) , t D 0 = t 0 . D_0=(J,\varnothing),\qquad t_{D_0}=t_0. D 0 = ( J , ∅ ) , t D 0 = t 0 .
For every ( i 0 , β ) ∈ B (i_0,\beta)\in\mathcal{B} ( i 0 , β ) ∈ B , check z i 0 = β z_{i_0}=\beta z i 0 = β . If any bit check fails, return FAIL for the failed bit check at ( σ 0 , i 0 , t 0 ) (\sigma_0,i_0,t_0) ( σ 0 , i 0 , t 0 ) with γ = ( b i t , i 0 , β ) \gamma=(\mathrm{bit},i_0,\beta) γ = ( bit , i 0 , β ) . Otherwise, apply the normal-termination rule defined in Item 3.
Repeated Transition. From ( σ , i , t ) (\sigma,i,t) ( σ , i , t ) , use z i z_i z i and the transition rule of M M M to compute e = ( t , i , i ′ , σ ′ ) e=(t,i,i',\sigma') e = ( t , i , i ′ , σ ′ ) . Here i ′ i' i ′ is the random-head position after the transition, and σ ′ \sigma' σ ′ is the resulting configuration.
Check e e e and ( j q ) q ∈ Q (j_q)_{q\in Q} ( j q ) q ∈ Q against H \mathcal{H} H , according to Item 5. If the check fails with report γ \gamma γ , return FAIL at ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) with γ \gamma γ . Otherwise, apply the normal-termination rule in Item 3 to ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) . Then:
If i ′ ∈ J i'\in J i ′ ∈ J , perform the following checkpoint update when r ≥ 2 r\ge2 r ≥ 2 : if i ∈ I i\in I i ∈ I , N i = r N_i=r N i = r , and i ′ ∈ I ∖ { i } i'\in I\setminus\{i\} i ′ ∈ I ∖ { i } , write I = [ a , b ] I=[a,b] I = [ a , b ] and set
I ′ = { [ a , i − 1 ] , i ′ < i , [ i + 1 , b ] , i ′ > i . I'=
\begin{cases}
[a,i-1], & i'<i,\\
[i+1,b], & i'>i.
\end{cases} I ′ = { [ a , i − 1 ] , [ i + 1 , b ] , i ′ < i , i ′ > i .
Record the checkpoint
D = ( I ′ , { ( q , L q , D , t + 1 ) : q ∈ ∂ I ′ } ) , t D = t + 1 , D=\left(I',\{(q,L_{q,D},t+1):q\in\partial I'\}\right),\qquad t_D=t+1, D = ( I ′ , {( q , L q , D , t + 1 ) : q ∈ ∂ I ′ } ) , t D = t + 1 ,
where L q , D L_{q,D} L q , D is the crossing history at cut q q q generated by this execution during [ t 0 , t + 1 ) [t_0,t+1) [ t 0 , t + 1 ) , including the current transition whenever it crosses q q q . Set I ← I ′ I\leftarrow I' I ← I ′ . In every case, apply Item 4 to ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) when i ′ ≠ i i'\ne i i ′ = i . If no report is returned, set
( σ , i , t ) ← ( σ ′ , i ′ , t + 1 ) . (\sigma,i,t)\leftarrow(\sigma',i',t+1). ( σ , i , t ) ← ( σ ′ , i ′ , t + 1 ) .
If i ′ ∉ J i'\notin J i ′ ∈ / J , let s ∈ { L , R } s\in\{L,R\} s ∈ { L , R } be the exit side to J J J and let j s j_s j s be the corresponding counter.
If j s > ∣ H s ∣ j_s>|H_s| j s > ∣ H s ∣ , return OVERFLOW at ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) with γ = ⊥ \gamma=\bot γ = ⊥ . Otherwise, test H s [ j s ] = e H_s[j_s]=e H s [ j s ] = e . If this comparison fails, return FAIL for the failed boundary-history check at ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) with γ = ( b o u n d a r y , s , e ) \gamma=(\mathrm{boundary},s,e) γ = ( boundary , s , e ) . Then set j s ← j s + 1 j_s\leftarrow j_s+1 j s ← j s + 1 .
The next record of H s H_s H s must have the form
e i n = ( u , i ′ , i , c ) , u ≥ t + 1. e_{\mathrm{in}}=(u,i',i,c),\qquad u\ge t+1. e in = ( u , i ′ , i , c ) , u ≥ t + 1.
If the next record does not exist or does not have this form, then return FAIL for the failed boundary-history check at ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) , where we take γ = ( b o u n d a r y , s , H s [ j s ] ) \gamma=(\mathrm{boundary},s,H_s[j_s]) γ = ( boundary , s , H s [ j s ]) if the record exists, and we take γ = ( b o u n d a r y , s , ⊥ ) \gamma=(\mathrm{boundary},s,\bot) γ = ( boundary , s , ⊥ ) if otherwise.
Run Item 5 to check e i n e_{\mathrm{in}} e in and ( j q ) q ∈ Q (j_q)_{q\in Q} ( j q ) q ∈ Q against H \mathcal{H} H . If the check fails with report γ \gamma γ , return FAIL at ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) with γ \gamma γ .
Set j s ← j s + 1 j_s\leftarrow j_s+1 j s ← j s + 1 . Set
( σ , i , t ) ← ( c , i , u + 1 ) . (\sigma,i,t)\leftarrow(c,i,u+1). ( σ , i , t ) ← ( c , i , u + 1 ) .
Apply Item 3 to ( σ , i , t ) (\sigma,i,t) ( σ , i , t ) . Apply Item 4 to ( σ , i , t ) (\sigma,i,t) ( σ , i , t ) .
The Recursive Sampling Algorithm
Normal termination. For a given triple ( σ , i , t ) (\sigma, i, t) ( σ , i , t ) , apply the following normal termination rule. Intuitively, this checks whether the execution must stop at ( σ , i , t ) (\sigma, i, t) ( σ , i , t ) .
The normal termination rule to ( σ , i , t ) (\sigma, i, t) ( σ , i , t ) is defined as:
If σ \sigma σ is not halting and t < T t < T t < T , continue the execution without returning a report.
If σ \sigma σ is halting or t = T t = T t = T , inspect the unused records of all L q L_q L q , q ∈ Q q \in Q q ∈ Q . If any remain, choose a record e ∗ e_* e ∗ with the smallest timestamp, breaking ties by the smallest cut q q q , and return FAIL at ( σ , i , t ) (\sigma, i, t) ( σ , i , t ) with γ = ( history , q , e ∗ ) \gamma= (\text{history}, q, e_*) γ = ( history , q , e ∗ ) . If none remain, return HALT at ( σ , i , t ) (\sigma, i, t) ( σ , i , t ) with γ = ⊥ \gamma= \perp γ =⊥ .
Check a new visit. This rule checks a new visit inside J J J . For a given triple ( σ , v , t ) (\sigma, v, t) ( σ , v , t ) with v ∈ J v \in J v ∈ J , first check whether N v = r N_v = r N v = r . If so, return OVERFLOW at ( σ , v , t ) (\sigma, v, t) ( σ , v , t ) with γ = ⊥ \gamma= \perp γ =⊥ . Otherwise, set N v ← N v + 1 N_v \leftarrow N_v + 1 N v ← N v + 1 and check z v = β z_v = \beta z v = β for every ( v , β ) ∈ B (v, \beta) \in B ( v , β ) ∈ B . If this check fails, return FAIL for the failed bit check at ( σ , v , t ) (\sigma, v, t) ( σ , v , t ) with γ = ( bit , v , β ) \gamma= (\text{bit}, v, \beta) γ = ( bit , v , β ) , where β \beta β is the prescribed value in the failed bit check.
Check e e e and ( j q ) q ∈ Q (j_q)_{q\in Q} ( j q ) q ∈ Q against H \mathcal{H} H . Given a record e = ( s , x , y , c ) e = (s, x, y, c) e = ( s , x , y , c ) , indices ( j q ) q ∈ Q (j_q)_{q\in Q} ( j q ) q ∈ Q with 1 ≤ j q ≤ ∣ L q ∣ + 1 1 \leq j_q \leq|L_q| + 1 1 ≤ j q ≤ ∣ L q ∣ + 1 , and H \mathcal{H} H we define “check e e e and ( j q ) q ∈ Q (j_q)_{q\in Q} ( j q ) q ∈ Q against H \mathcal{H} H ” as follows. Consider the cuts q ∈ Q q \in Q q ∈ Q in increasing order. If e e e crosses q ∣ q + 1 q \mid q + 1 q ∣ q + 1 with s < τ q s < \tau_q s < τ q , or if j q ≤ ∣ L q ∣ j_q \leq|L_q| j q ≤ ∣ L q ∣ and the j q j_q j q -th record L q [ j q ] L_q[j_q] L q [ j q ] has timestamp at most s s s , the check requires that
j q ≤ ∣ L q ∣ and L q [ j q ] = e . j_q \leq|L_q| \qquad\text{and} \qquad L_q[j_q] = e. j q ≤ ∣ L q ∣ and L q [ j q ] = e .
If any required comparison fails, the check fails. Let q q q be the first failing cut in the prescribed order and set
γ = ( history , q , e ∗ ) , e ∗ = { L q [ j q ] , j q ≤ ∣ L q ∣ , e , j q > ∣ L q ∣ . \gamma= (\text{history}, q, e_*), \qquad e_* =
\begin{cases}
L_q[j_q], & j_q \leq|L_q|,\\
e, & j_q > |L_q|.
\end{cases} γ = ( history , q , e ∗ ) , e ∗ = { L q [ j q ] , e , j q ≤ ∣ L q ∣ , j q > ∣ L q ∣.
The check succeeds if all required comparisons succeed. After a successful check, increment j q j_q j q for every cut at which a comparison was required. We call this consuming the matched records; all other counters remain unchanged.
Lemma 3.6. Let J 0 = { 1 , 2 , … , T + 1 } J_0 = \{1, 2, \ldots, T + 1\} J 0 = { 1 , 2 , … , T + 1 } , and let
C 0 = ( J 0 , σ s t a r t , 1 , 0 , ∅ , ∅ , ∅ , ∅ ) C_0 = (J_0, \sigma_{\mathrm{start}}, 1, 0, \varnothing, \varnothing, \varnothing, \varnothing) C 0 = ( J 0 , σ start , 1 , 0 , ∅ , ∅ , ∅ , ∅ ) be the initial constraint, where σ s t a r t \sigma_{\mathrm{start}} σ start is the initial configuration of M M M . For every fixed z J 0 ∈ { 0 , 1 } J 0 z_{J_0} \in\{0, 1\}^{J_0} z J 0 ∈ { 0 , 1 } J 0 , the capped-k k k execution under C 0 C_0 C 0 returns a HALT report whose configuration records the output of M M M on the same random tape. Consequently, extracting this output from Exec k ( C 0 , U J 0 ) \operatorname{Exec}_k(C_0, U_{J_0}) Exec k ( C 0 , U J 0 ) gives exactly the output distribution of M M M .
Proof. Fix z J 0 z_{J_0} z J 0 . The constraint C 0 C_0 C 0 contains no checks, so the capped execution cannot return FAIL. Since M M M visits every random-tape position at most k k k times, it never attempts a ( k + 1 ) (k+1) ( k + 1 ) -st visit, so the capped execution cannot overflow inside J 0 J_0 J 0 . Moreover, the head starts at position 1, moves by at most one cell per step, and runs for at most T T T steps. It therefore never leaves J 0 J_0 J 0 , so boundary overflow is also impossible.
Thus the capped execution runs until M M M halts. At every step, the two executions read the same random bit and apply the same transition rule. They consequently have the same configuration and random-head position throughout, so the returned configuration records the output of M M M . Taking uniform U J 0 U_{J_0} U J 0 proves the claim about their output distributions.
The Recursive Sampling Algorithm
We now construct Sampler r ( C ) _r(C) r ( C ) , a randomized algorithm that uses read-once randomness and outputs a return report. For the constraint families defined in § 3.4 , we will prove that its return-report distribution equals that of the corresponding capped execution on a uniform assignment U J U_J U J :
L ( S a m p l e r r ( C ) ) = L ( E x e c r ( C , U J ) ) . \mathcal{L}(\mathop{\mathrm{Sampler}}\nolimits_r(C))=\mathcal{L}(\mathop{\mathrm{Exec}}\nolimits_r(C,U_J)). L ( Sampler r ( C )) = L ( Exec r ( C , U J )) .
Write
C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) . C=(J,\sigma_0,i_0,t_0,\mathcal{H},B,H_L,H_R). C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) .
At a current checkpoint D D D under constraint C C C , the sampler guesses the next checkpoint or return report, together with the information needed to verify it. We call this tuple a candidate .
Definition 3.7 (Candidate). Given a checkpoint D = ( I D , H D ) D=(I_D,\mathcal{H}_D) D = ( I D , H D ) and an execution constraint C C C , writing I D = [ a , b ] I_D=[a,b] I D = [ a , b ] , a rank-r r r candidate is defined to be a tuple
Y = ( θ , v , d , β , H Y ) Y=(\theta,v,d,\beta,\mathcal{H}_Y) Y = ( θ , v , d , β , H Y ) with the following requirements.
The field θ \theta θ is either the label CONTINUE or a report ( κ , σ , i , t , γ ) (\kappa,\sigma,i,t,\gamma) ( κ , σ , i , t , γ ) in the format of Theorem 3.3.
The field v v v is a position of I D I_D I D or ⊥ \perp ⊥ , and β ∈ { 0 , 1 } \beta\in\{0,1\} β ∈ { 0 , 1 } . If v = ⊥ v=\perp v =⊥ , then β = 0 \beta=0 β = 0 . The field d d d belongs to { L , R , ⊥ } \{L,R,\perp\} { L , R , ⊥ } .
If θ = \theta= θ = CONTINUE, then we require v ≠ ⊥ v\ne\perp v = ⊥ and d ∈ { L , R } d\in\{L,R\} d ∈ { L , R } . Define
I ′ = { [ a , v − 1 ] , d = L , [ v + 1 , b ] , d = R , I'=\begin{cases}
[a,v-1], & d=L,\\
[v+1,b], & d=R,
\end{cases} I ′ = { [ a , v − 1 ] , [ v + 1 , b ] , d = L , d = R , and require I ′ ≠ ∅ I'\ne\varnothing I ′ = ∅ . Let S Y = ∂ I ′ ∪ { v − 1 , v } S_Y=\partial I'\cup\{v-1,v\} S Y = ∂ I ′ ∪ { v − 1 , v } be a set of cuts, i.e. it includes the cuts which are at the boundaries of I ′ I' I ′ and the cuts before and after v v v . For every q ∈ S Y q\in S_Y q ∈ S Y , let L q , Y L_{q,Y} L q , Y be a crossing history at q ∣ q + 1 q\mid q+1 q ∣ q + 1 containing at most 2 r 2r 2 r records. Every record has timestamp at least t 0 t_0 t 0 , and these crossing histories contain at least one record in total. Define
t Y = 1 + max { s : ( s , x , y , c ) ∈ L q , Y , q ∈ S Y } t_Y=1+\max\{s:(s,x,y,c)\in L_{q,Y},\ q\in S_Y\} t Y = 1 + max { s : ( s , x , y , c ) ∈ L q , Y , q ∈ S Y } and
H Y = { ( q , L q , Y , t Y ) : q ∈ S Y } . \mathcal{H}_Y=\{(q,L_{q,Y},t_Y):q\in S_Y\}. H Y = {( q , L q , Y , t Y ) : q ∈ S Y } . By the definition of t Y t_Y t Y , some record has timestamp t Y − 1 t_Y-1 t Y − 1 . Require this record to be unique and to have the form ( t Y − 1 , v , w , c ) (t_Y-1,v,w,c) ( t Y − 1 , v , w , c ) for some w ∈ I ′ w\in I' w ∈ I ′ .
If θ \theta θ is a return report ( κ , σ , i , t , γ ) (\kappa,\sigma,i,t,\gamma) ( κ , σ , i , t , γ ) , then we require d = ⊥ d=\perp d =⊥ , H Y = ∅ \mathcal{H}_Y=\varnothing H Y = ∅ , and t Y = t t_Y=t t Y = t .
Since ∣ S Y ∣ ≤ 4 |S_Y|\le4 ∣ S Y ∣ ≤ 4 , the candidate has an O ( r b ) O(rb) O ( r b ) -bit canonical encoding.
The algorithm proceeds as follows. Starting from D 0 D_0 D 0 , the sampler repeatedly proposes a candidate for the next checkpoint or return report. A proposed checkpoint includes the position whose r r r -th visit ends, its random bit, and the crossing histories specifying the checkpoint. To verify the guess, the sampler recursively samples the return report of a capped-( r − 1 ) (r-1) ( r − 1 ) execution that replays the computation through the current checkpoint. If necessary, the proposed r r r -th visit is then completed and its result is compared with the guess. If verification fails, the sampler repeats the trial using fresh independent coins. Otherwise, it updates the current checkpoint to the one specified by the accepted candidate, or returns the accepted report and terminates.
Samplerr _r r (C). We now give the formal description of the algorithm Samplerr _r r (C). The sampler takes an execution constraint C C C and a visit cap r ≥ 1 r \ge1 r ≥ 1 , and outputs a return report. It proceeds as follows, while the subprocedures DirectSample , NextGuess , CreateConstraint , FinishAndCheck will be defined immediately after Sampler . Write C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) C = (J, \sigma_0, i_0, t_0, H, B, H_L, H_R) C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) ,
Base case. If r = 1 r = 1 r = 1 , return DirectSample ( C ) (C) ( C ) .
Initialize the current checkpoint. Let J J J and t 0 t_0 t 0 be the interval and initial time specified by C C C . Let
D 0 = ( J , ∅ ) , t D 0 = t 0 , D_0 = (J, \varnothing), \qquad t_{D_0} = t_0, D 0 = ( J , ∅ ) , t D 0 = t 0 ,
be the initial checkpoint specified by C C C . Set D ← D 0 D \leftarrow D_0 D ← D 0 .
Sample a candidate. At the current checkpoint D D D , repeat the following trial until it is accepted. In each trial, the proposal and the recursive call use independent fresh coins. Whenever a trial is rejected, skip its remaining steps and begin a new trial using the same D D D .
(a) Propose a candidate. Set Y ← Y \leftarrow Y ← NextGuess r ( C , D ) _r(C,D) r ( C , D ) . If Y = ⊥ Y = \bot Y = ⊥ , reject the trial.
(b) Prepare the child constraint. Set
C ′ ← CreateConstraint ( C , D , Y ) . C' \leftarrow\textbf{CreateConstraint}(C,D,Y). C ′ ← CreateConstraint ( C , D , Y ) .
If C ′ = ⊥ C' = \bot C ′ = ⊥ , reject the trial.
(c) Sample the child report. Set R ← R \leftarrow R ← Sampler r − 1 ( C ′ ) _{r-1}(C') r − 1 ( C ′ ) .
(d) Verify the candidate. Run
FinishAndCheck ( C , D , Y , C ′ , R ) . \textbf{FinishAndCheck}(C,D,Y,C',R). FinishAndCheck ( C , D , Y , C ′ , R ) .
Accept the trial if it outputs 1 1 1 ; otherwise reject the trial.
Return a report or continue. Let Y = ( θ , v , d , β , H Y ) Y = (\theta, v, d, \beta, H_Y) Y = ( θ , v , d , β , H Y ) be the accepted candidate (i.e. the candidate corresponding to the accepted trial).
If θ \theta θ is a return report, return θ \theta θ . Otherwise, we know θ = CONTINUE \theta= \text{CONTINUE} θ = CONTINUE . Denote the interval I D I_D I D of D D D as I D = [ a , b ] I_D = [a,b] I D = [ a , b ] and set
I ′ = { [ a , v − 1 ] , d = L , [ v + 1 , b ] , d = R . I' =
\begin{cases}
[a,v-1], & d = \mathrm{L},\\
[v+1,b], & d = \mathrm{R}.
\end{cases} I ′ = { [ a , v − 1 ] , [ v + 1 , b ] , d = L , d = R .
Form the new checkpoint by setting
D ← ( I ′ , { ( q , L q , Y , t Y ) : q ∈ ∂ I ′ } ) . D \leftarrow(I', \{(q,L_{q,Y},t_Y):q \in\partial I'\}). D ← ( I ′ , {( q , L q , Y , t Y ) : q ∈ ∂ I ′ }) .
Go to Step 3 to continue.
We next define the subprocedures.
NextGuess r ( C , D ) _r(C,D) r ( C , D ) . Fix a binary encoding space of size Q r = 2 O ( r b ) Q_r = 2^{O(rb)} Q r = 2 O ( r b ) , assigning exactly one canonical encoding to every rank-r r r candidate for C , D C,D C , D . This procedure samples a uniformly random string from this space. Return the corresponding candidate if the string is its canonical encoding and satisfies Theorem 3.7; otherwise, return ⊥ \bot ⊥ .
CreateConstraint ( C , D , Y ) (C,D,Y) ( C , D , Y ) . On input ( C , D , Y ) (C,D,Y) ( C , D , Y ) , the procedure returns either ⊥ \bot ⊥ or a constraint C ′ C' C ′ on I D I_D I D (which will be used to start the sampling for rank r − 1 r-1 r − 1 ). Write
C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) , D = ( I D , H D ) , Y = ( θ , v , d , β , H Y ) , C=(J,\sigma_0,i_0,t_0,\mathcal{H},\mathcal{B},H_L,H_R), \qquad D=(I_D,\mathcal{H}_D), \qquad Y=(\theta,v,d,\beta,\mathcal{H}_Y), C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) , D = ( I D , H D ) , Y = ( θ , v , d , β , H Y ) ,
and set I : = I D I:=I_D I := I D . When D ≠ D 0 D\ne D_0 D = D 0 , write
H D = { ( q , L q , D , t D ) : q ∈ ∂ I D } . \mathcal{H}_D=\{(q,L_{q,D},t_D):q\in\partial I_D\}. H D = {( q , L q , D , t D ) : q ∈ ∂ I D } .
When θ \theta θ is a return report, write θ = ( κ , σ , i , t , γ ) \theta=(\kappa,\sigma,i,t,\gamma) θ = ( κ , σ , i , t , γ ) . Perform the following steps.
Check compatibility of Y Y Y with C C C and D D D . If θ = C O N T I N U E \theta=\mathrm{CONTINUE} θ = CONTINUE , require t D < t Y ≤ T t_D<t_Y\le T t D < t Y ≤ T . Otherwise (θ \theta θ is a return report) require t D ≤ t Y ≤ T t_D\le t_Y\le T t D ≤ t Y ≤ T .
If θ \theta θ is a return report and κ = F A I L \kappa=\mathrm{FAIL} κ = FAIL , then require γ \gamma γ to have one of the following forms, with the corresponding condition satisfied:
γ = ( h i s t o r y , q , e ) \gamma=(\mathrm{history},q,e) γ = ( history , q , e ) : there is an entry ( q , L q , τ q ) ∈ H (q,L_q,\tau_q)\in\mathcal{H} ( q , L q , τ q ) ∈ H .
γ = ( b i t , u , α ) \gamma=(\mathrm{bit},u,\alpha) γ = ( bit , u , α ) : ( u , α ) ∈ B (u,\alpha)\in\mathcal{B} ( u , α ) ∈ B .
γ = ( b o u n d a r y , s , e ) \gamma=(\mathrm{boundary},s,e) γ = ( boundary , s , e ) : s ∈ { L , R } s\in\{L,R\} s ∈ { L , R } , referring to the boundary history H s H_s H s of C C C .
Return ⊥ \bot ⊥ if any check fails.
Choose an entrance and bit checks. If i 0 ∈ I i_0\in I i 0 ∈ I , set ( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( σ 0 , i 0 , t 0 ) (\sigma'_0,i'_0,t'_0)=(\sigma_0,i_0,t_0) ( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( σ 0 , i 0 , t 0 ) . Otherwise, require the earliest record among the lists L q , D L_{q,D} L q , D to be an entrance e 0 = ( s , x , y , c ) e_0=(s,x,y,c) e 0 = ( s , x , y , c ) with x ∉ I x\notin I x ∈ / I and y ∈ I y\in I y ∈ I , and set ( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) (\sigma'_0,i'_0,t'_0)=(c,y,s+1) ( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) . Return ⊥ \bot ⊥ if no such entrance exists. Let B ′ \mathcal{B}' B ′ be the checks of B \mathcal{B} B whose positions lie in I I I , together with ( v , β ) (v,\beta) ( v , β ) when v ≠ ⊥ v\ne\bot v = ⊥ .
Construct the crossing requirements. Start with the entries of H \mathcal{H} H . For an entry ( q , L q , τ q ) (q,L_q,\tau_q) ( q , L q , τ q ) whose cut lies entirely outside I I I , delete from L q L_q L q every record with timestamp less than t D t_D t D . Merge the resulting entries with all entries of H D \mathcal{H}_D H D and, when θ = C O N T I N U E \theta=\mathrm{CONTINUE} θ = CONTINUE , all entries of H Y \mathcal{H}_Y H Y .
The merge retains one entry per cut. To merge ( q , L 1 , τ 1 ) (q,L_1,\tau_1) ( q , L 1 , τ 1 ) and ( q , L 2 , τ 2 ) (q,L_2,\tau_2) ( q , L 2 , τ 2 ) , assume τ 1 ≤ τ 2 \tau_1\le\tau_2 τ 1 ≤ τ 2 . Require
L 1 = L 2 ↾ < τ 1 , L_1=L_2\mathbin{\upharpoonright}_{<\tau_1}, L 1 = L 2 ↾ < τ 1 ,
where L 2 ↾ < τ 1 L_2\mathbin{\upharpoonright}_{<\tau_1} L 2 ↾ < τ 1 consists of the records of L 2 L_2 L 2 with timestamp less than τ 1 \tau_1 τ 1 . If the equality holds, retain ( q , L 2 , τ 2 ) (q,L_2,\tau_2) ( q , L 2 , τ 2 ) ; otherwise return ⊥ \bot ⊥ . Denote the resulting set of entries by H ′ \mathcal{H}' H ′ .
Construct the boundary histories. For s ∈ { L , R } s\in\{L,R\} s ∈ { L , R } , set
H s ′ = { H s , ∂ s I = ∂ s J , L ∂ s I , D , ∂ s I ≠ ∂ s J . H'_s=
\begin{cases}
H_s, & \partial_s I=\partial_s J,\\
L_{\partial_s I,D}, & \partial_s I\ne\partial_s J.
\end{cases} H s ′ = { H s , L ∂ s I , D , ∂ s I = ∂ s J , ∂ s I = ∂ s J .
Check the entrance and prepare the child’s histories. If i 0 ∈ I i_0\in I i 0 ∈ I , skip this step. Otherwise, let e 0 = ( s , x , y , c ) e_0=(s,x,y,c) e 0 = ( s , x , y , c ) be the entrance chosen in Step 2, so that
( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) . (\sigma'_0,i'_0,t'_0)=(c,y,s+1). ( σ 0 ′ , i 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) .
The child starts immediately after e 0 e_0 e 0 and therefore will not process this entrance itself. We check e 0 e_0 e 0 against the crossing and boundary histories before passing their remaining records to the child.
Write H ′ = { ( q , L q , τ q ) : q ∈ Q ′ } \mathcal{H}'=\{(q,L_q,\tau_q):q\in Q'\} H ′ = {( q , L q , τ q ) : q ∈ Q ′ } . Initialize the crossing counters j q = 1 j_q=1 j q = 1 for all q ∈ Q ′ q\in Q' q ∈ Q ′ and the boundary counters j L = j R = 1 j_L=j_R=1 j L = j R = 1 . Perform the following operations. (a) Apply the crossing check to e 0 e_0 e 0 . Apply the crossing check in item 5 of Theorem 3.5 to e 0 e_0 e 0 , ( j q ) q ∈ Q ′ (j_q)_{q\in Q'} ( j q ) q ∈ Q ′ , and H ′ \mathcal{H}' H ′ . Return ⊥ \perp ⊥ if the check fails.
(b) Account for e 0 e_0 e 0 in the boundary history. Let η ∈ { L , R } \eta\in\{L,R\} η ∈ { L , R } be the side through which e 0 e_0 e 0 enters I I I . As in the supplied-entrance handling in item 2 of Theorem 3.5, the entrance record must be consumed before the computation starts at its resulting configuration. Require
j η ≤ ∣ H η ′ ∣ and H η ′ [ j η ] = e 0 . j_\eta\leq\lvert\mathcal{H}'_\eta\rvert\qquad\text{and}\qquad\mathcal{H}'_\eta[j_\eta]=e_0. j η ≤ ∣ H η ′ ∣ and H η ′ [ j η ] = e 0 .
Return ⊥ \perp ⊥ if either requirement fails; otherwise, increment j η j_\eta j η . Require every remaining record of H L ′ \mathcal{H}'_L H L ′ and H R ′ \mathcal{H}'_R H R ′ to have timestamp at least t 0 ′ t'_0 t 0 ′ . Return ⊥ \perp ⊥ if this requirement fails.
(c) Retain the records still to be checked. For each ( q , L q , τ q ) ∈ H ′ (q,L_q,\tau_q)\in\mathcal{H}' ( q , L q , τ q ) ∈ H ′ , delete the first j q − 1 j_q-1 j q − 1 records of L q L_q L q . If the resulting list is empty and τ q ≤ t 0 ′ \tau_q\leq t'_0 τ q ≤ t 0 ′ , remove this entry from H ′ \mathcal{H}' H ′ . Retain every other entry with its cutoff unchanged. In particular, an empty list with τ q > t 0 ′ \tau_q>t'_0 τ q > t 0 ′ still forbids crossings at cut q q q during [ t 0 ′ , τ q ) [t'_0,\tau_q) [ t 0 ′ , τ q ) . Delete the consumed entrance record from H η ′ \mathcal{H}'_\eta H η ′ , leaving the other boundary history unchanged.
The child then initializes at ( σ 0 ′ , i 0 ′ , t 0 ′ ) (\sigma'_0,i'_0,t'_0) ( σ 0 ′ , i 0 ′ , t 0 ′ ) according to item 1 of Theorem 3.5. Its initial bit checks and the normal-termination check are performed during that initialization.
Return the child constraint. Return
C ′ = ( I , σ 0 ′ , i 0 ′ , t 0 ′ , H ′ , B ′ , H L ′ , H R ′ ) . C'=(I,\sigma'_0,i'_0,t'_0,\mathcal{H}',\mathcal{B}',\mathcal{H}'_L,\mathcal{H}'_R). C ′ = ( I , σ 0 ′ , i 0 ′ , t 0 ′ , H ′ , B ′ , H L ′ , H R ′ ) .
FinishAndCheck ( C , D , Y , C ′ , R ) (C,D,Y,C',R) ( C , D , Y , C ′ , R ) . For a rank-r r r call with r ≥ 2 r\geq2 r ≥ 2 , the procedure takes the parent constraint C C C , the current checkpoint D D D , the candidate Y Y Y , the child constraint C ′ ≠ ⊥ C'\ne\perp C ′ = ⊥ produced by CreateConstraint ( C , D , Y ) (C,D,Y) ( C , D , Y ) in the current trial, and the report R R R returned by Sampler r − 1 ( C ′ ) _{r-1}(C') r − 1 ( C ′ ) . It returns 1 if the checks below succeed and 0 otherwise. Let J J J be the interval of C C C , and write
D = ( I D , H D ) , I = I D , Y = ( θ , v , d , β , H Y ) , R = ( κ R , σ R , i R , s , γ R ) . D=(I_D,\mathcal{H}_D),\qquad I=I_D,\qquad Y=(\theta,v,d,\beta,\mathcal{H}_Y),\qquad R=(\kappa_R,\sigma_R,i_R,s,\gamma_R). D = ( I D , H D ) , I = I D , Y = ( θ , v , d , β , H Y ) , R = ( κ R , σ R , i R , s , γ R ) .
A completion result is either a return report or a tuple ( C O N T I N U E , σ ′ , i ′ , t ′ , ⊥ ) (\mathrm{CONTINUE},\sigma',i',t',\perp) ( CONTINUE , σ ′ , i ′ , t ′ , ⊥ ) describing a nonterminal departure from the proposed r r r -th visit into I ∖ { v } I\setminus\{v\} I ∖ { v } . Perform the following operations to verify that the child sampling reaches D D D , determine the next outcome by completing the proposed r r r -th visit when necessary, and check that this outcome agrees with Y Y Y .
Verify that the child sampling reaches D D D . If D = D 0 D=D_0 D = D 0 , skip this step. Otherwise, let ( t D − 1 , v D , i D , σ D ) (t_D-1,v_D,i_D,\sigma_D) ( t D − 1 , v D , i D , σ D ) be the unique latest record in H D \mathcal{H}_D H D . Return 0 if s < t D s<t_D s < t D , since the child stopped before the checkpoint was reached. If s > t D s>t_D s > t D , proceed to Step 2. If s = t D s=t_D s = t D , require the report to be either
R = ( O V E R F L O W , σ D , i D , t D , ⊥ ) R=(\mathrm{OVERFLOW},\sigma_D,i_D,t_D,\perp) R = ( OVERFLOW , σ D , i D , t D , ⊥ )
or
R = ( F A I L , σ D , i D , t D , ( b i t , i D , β D ) ) . R=(\mathrm{FAIL},\sigma_D,i_D,t_D,(\mathrm{bit},i_D,\beta_D)). R = ( FAIL , σ D , i D , t D , ( bit , i D , β D )) .
for a bit requirement ( i D , β D ) (i_D,\beta_D) ( i D , β D ) of C ′ C' C ′ . Return 0 if neither form applies.
Construct a completion result R ′ R' R ′ . The child runs a sampling of level r − 1 r-1 r − 1 , while the parent runs a sampling of level r r r . Thus the child may stop immediately before an r r r -th visit that the parent is still allowed to perform. In this case, resume from the child’s stopping configuration and complete that one visit using the bit β \beta β supplied by Y Y Y . Otherwise, use the child’s report directly. Denote the resulting outcome by R ′ R' R ′ and distinguish the following two cases.
(a) No new r r r -th visit is proposed (v = ⊥ v = \bot v = ⊥ ). Return 0 if R R R is an OVERFLOW report at a position of I I I ; otherwise, set R ′ = R R' = R R ′ = R .
(b) An r r r -th visit to v v v is proposed (v ≠ ⊥ v \ne\bot v = ⊥ ). Perform the following operations to verify that the child stopped immediately before this visit, restore the history counters, and complete the visit under the parent’s execution.
i. Require
R = ( OVERFLOW , σ R , v , s , ⊥ ) and t D ≤ s ≤ t Y . R = (\operatorname{OVERFLOW}, \sigma_R, v, s, \bot) \qquad\text{and}\qquad t_D \le s \le t_Y. R = ( OVERFLOW , σ R , v , s , ⊥ ) and t D ≤ s ≤ t Y .
Return 0 if either requirement fails.
ii. Complete the proposed r r r -th visit to v v v . Let H ′ H' H ′ and B ′ B' B ′ be the crossing and bit requirements of C ′ C' C ′ , respectively, and let Q ′ Q' Q ′ be the set of cuts in H ′ H' H ′ . Whenever a report is produced below, stop this substep and pass that report, including a FAIL report, to Step 2(b)iii.
1 + ∣ { e ∈ L : time ( e ) < s } ∣ , 1+\lvert\{e\in L:\operatorname{time}(e)<s\}\rvert, 1 + ∣{ e ∈ L : time ( e ) < s }∣ ,
where time ( e ) \operatorname{time}(e) time ( e ) is the timestamp of e e e . Denote the crossing counters by ( j q ) q ∈ Q ′ (j_q)_{q\in Q'} ( j q ) q ∈ Q ′ and the boundary counters by j L , j R j_L,j_R j L , j R .
( σ , i , t ) = ( σ R , v , s ) , N v = r − 1. (\sigma,i,t)=(\sigma_R,v,s),\qquad N_v=r-1. ( σ , i , t ) = ( σ R , v , s ) , N v = r − 1.
Apply the new-visit check in item 4 of Theorem 3.5 to ( σ , v , t ) (\sigma,v,t) ( σ , v , t ) , with visit bound r r r , visit counter N v N_v N v , random-tape bit z v = β z_v=\beta z v = β , and bit requirements B ′ B' B ′ . This increments N v N_v N v to r r r and checks β = α \beta=\alpha β = α for every ( v , α ) ∈ B ′ (v,\alpha)\in B' ( v , α ) ∈ B ′ .
From ( σ , v , t ) (\sigma,v,t) ( σ , v , t ) , use β \beta β and the transition rule of M M M to compute
e = ( t , v , i ′ , σ ′ ) . e=(t,v,i',\sigma'). e = ( t , v , i ′ , σ ′ ) .
Apply the crossing check in item 5 of Theorem 3.5 to the record e e e , the current counters ( j q ) q ∈ Q ′ (j_q)_{q\in Q'} ( j q ) q ∈ Q ′ , and the crossing requirements H ′ H' H ′ . If this check fails with identifier γ \gamma γ , produce the report
( FAIL , σ ′ , i ′ , t + 1 , γ ) . (\operatorname{FAIL},\sigma',i',t+1,\gamma). ( FAIL , σ ′ , i ′ , t + 1 , γ ) .
If the crossing check succeeds, apply the normal-termination rule in item 3 of Theorem 3.5 to ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) , using time bound T T T , crossing requirements H ′ H' H ′ , and the updated counters ( j q ) q ∈ Q ′ (j_q)_{q\in Q'} ( j q ) q ∈ Q ′ .
If no report is produced and i ′ = v i'=v i ′ = v , set ( σ , i , t ) = ( σ ′ , v , t + 1 ) (\sigma,i,t)=(\sigma',v,t+1) ( σ , i , t ) = ( σ ′ , v , t + 1 ) and repeat. If no report is produced and i ′ ≠ v i'\ne v i ′ = v , stop this substep and pass the departure configuration ( σ ′ , i ′ , t + 1 ) (\sigma',i',t+1) ( σ ′ , i ′ , t + 1 ) to Step 2(b)iii. Do not yet apply a new-visit check at i ′ i' i ′ or any boundary rule.
iii. If these checks produce a report, set R ′ R' R ′ to that report. Otherwise, handle the departure from v v v . If the head enters i ′ ∈ I ∖ { v } i'\in I\setminus\{v\} i ′ ∈ I ∖ { v } with configuration σ ′ \sigma' σ ′ at time t ′ t' t ′ , set
R ′ = ( CONTINUE , σ ′ , i ′ , t ′ , ⊥ ) R'=(\operatorname{CONTINUE},\sigma',i',t',\bot) R ′ = ( CONTINUE , σ ′ , i ′ , t ′ , ⊥ )
before the visit to i ′ i' i ′ begins. If the head enters i ′ ∈ J ∖ I i' \in J \setminus I i ′ ∈ J ∖ I with configuration σ ′ \sigma' σ ′ at time t ′ t' t ′ , set
R ′ = ( O V E R F L O W , σ ′ , i ′ , t ′ , ⊥ ) . R' = (\mathrm{OVERFLOW}, \sigma', i', t', \bot). R ′ = ( OVERFLOW , σ ′ , i ′ , t ′ , ⊥ ) .
If the head leaves J J J , apply the boundary rules of C C C using the corresponding inherited boundary history in C ′ C' C ′ and its restored counter, while retaining the current crossing checks. Set R ′ R' R ′ to any report produced by these rules, including normal termination upon return. If they instead resume at v v v without terminating, set R ′ R' R ′ to the OVERFLOW report for the attempted ( r + 1 ) (r+1) ( r + 1 ) -st visit.
Verify that the outcome agrees with Y Y Y . Let t ′ t' t ′ be the time recorded in R ′ R' R ′ . Return 0 if t ′ ≠ t Y t' \ne t_Y t ′ = t Y . During the completion above, also return 0 if the current simulated time exceeds t Y t_Y t Y before a completion result is produced. Check the proposed outcome as follows.
R ′ = ( C O N T I N U E , σ ′ , i ′ , t Y , ⊥ ) , i ′ ∈ I ′ . R' = (\mathrm{CONTINUE}, \sigma', i', t_Y, \bot), \qquad i' \in I'. R ′ = ( CONTINUE , σ ′ , i ′ , t Y , ⊥ ) , i ′ ∈ I ′ .
where I ′ I' I ′ is the retained interval specified by Y Y Y . Require the unique latest record in H Y \mathcal{H}_Y H Y to be ( t Y − 1 , v , i ′ , σ ′ ) (t_Y - 1, v, i', \sigma') ( t Y − 1 , v , i ′ , σ ′ ) , and require every entry of H Y \mathcal{H}_Y H Y to have been completely checked through time t Y t_Y t Y . These checks verify both the new checkpoint and its proposed crossing histories.
Return 1 if all these requirements hold; otherwise, return 0.
DirectSample( C ) (C) ( C ) . Run Exec 1 ( C , U J ) _1(C, U_J) 1 ( C , U J ) , supplying the random-tape bits on demand. Whenever the execution first reads a position v v v , draw one fresh uniform bit and use it for every read at v v v during that visit. Discard the bit when the random head leaves v v v . Return the report produced by Exec 1 _1 1 .
Correctness
We analyze Sampler r _r r before imposing the time cutoff. We may assume k ≤ T + 1 k \le T + 1 k ≤ T + 1 : otherwise, use T + 1 T + 1 T + 1 as the visit bound throughout the construction, since a computation with at most T T T transitions makes at most T + 1 T + 1 T + 1 visits. The resulting bounds are no larger than those stated in terms of the original k k k . Fix the input and the initial constraint C 0 C_0 C 0 from Theorem 3.6. Define families of constraints C k , … , C 1 \mathcal{C}_k,\ldots,\mathcal{C}_1 C k , … , C 1 recursively as follows. Set C k = { C 0 } \mathcal{C}_k = \{C_0\} C k = { C 0 } . For 2 ≤ r ≤ k 2 \le r \le k 2 ≤ r ≤ k , let C r − 1 \mathcal{C}_{r-1} C r − 1 consist of all non-⊥ \bot ⊥ outputs
CreateConstraint ( C , D , Y ) , C ∈ C r , \operatorname{CreateConstraint}(C,D,Y), \qquad C \in\mathcal{C}_r, CreateConstraint ( C , D , Y ) , C ∈ C r ,
where D D D is a checkpoint reached by Exec r ( C , z J ) _r(C,z_J) r ( C , z J ) for some assignment z J z_J z J , including the initial checkpoint, and Y Y Y ranges over all rank-r r r candidates for the constraint C C C and checkpoint D D D , as defined in Theorem 3.7. The candidate may incorrectly describe the next checkpoint or return report of an execution that reaches D D D . Thus these families include child constraints constructed from incorrect guesses. Their definition uses only the deterministic execution and constraint-construction procedures, and does not assume correctness or termination of the sampler.
Lemma 3.8 (Boundary histories and counter recovery). For every 1 ≤ r ≤ k 1 \le r \le k 1 ≤ r ≤ k and every
C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) ∈ C r , C = (J, \sigma_0, i_0, t_0, \mathcal{H}, \mathcal{B}, H_L, H_R) \in\mathcal{C}_r, C = ( J , σ 0 , i 0 , t 0 , H , B , H L , H R ) ∈ C r , the following statements hold.
Each nonempty boundary history H η H_\eta H η in the constraint tuple C C C , where η ∈ { L , R } \eta\in\{L,R\} η ∈ { L , R } denotes the left or right boundary, is a prefix of L q L_q L q for some entry ( q , L q , τ q ) ∈ H (q,L_q,\tau_q) \in\mathcal{H} ( q , L q , τ q ) ∈ H at the same boundary cut q q q . Every record of H η H_\eta H η has timestamp less than τ q \tau_q τ q .
Suppose a capped-r r r execution under C C C reaches a nonterminal checkpoint or returns OVERFLOW at a position inside its interval, at time s s s . For every crossing or boundary history L L L of C C C , its next-unused-record counter is
1 + ∣ { e ∈ L : time ( e ) < s } ∣ , (8) 1 + \lvert\{e \in L : \operatorname{time}(e) < s\}\rvert, \tag*{(8)} 1 + ∣{ e ∈ L : time ( e ) < s }∣ , (8) where time ( e ) \operatorname{time}(e) time ( e ) denotes the timestamp of the record e e e .
Proof. First statement: boundary histories. We use descending induction on r r r . For r = k r=k r = k , the only constraint is C 0 C_0 C 0 , whose boundary histories are empty, so the statement holds. Fix 2 ≤ r ≤ k 2 \le r \le k 2 ≤ r ≤ k and assume the statement holds for every constraint in C r \mathcal{C}_r C r . Every constraint in C r − 1 \mathcal{C}_{r-1} C r − 1 is a non-⊥ \perp ⊥ output
C ′ = C r e a t e C o n s t r a i n t ( C , D , Y ) C' = \mathbf{CreateConstraint}(C,D,Y) C ′ = CreateConstraint ( C , D , Y )
for some C ∈ C r C \in\mathcal{C}_r C ∈ C r , reachable checkpoint D D D , and rank-r r r candidate Y Y Y . Fix such a construction and write I = I D I=I_D I = I D . All construction steps cited in this part of the proof are steps of CreateConstraint .
First consider the histories after Step 4, before Step 5 removes any records. Fix a side η ∈ { L , R } \eta\in\{L,R\} η ∈ { L , R } for which H η ′ H'_\eta H η ′ is nonempty, and let q = ∂ η I q=\partial_\eta I q = ∂ η I be its boundary cut. The definition of H η ′ H'_\eta H η ′ gives two cases.
If q = ∂ η J q=\partial_\eta J q = ∂ η J , then the child inherits this boundary from the parent, and Step 4 sets H η ′ = H η H'_\eta=H_\eta H η ′ = H η . By the induction hypothesis, there is an entry ( q , L , τ ) ∈ H (q,L,\tau) \in\mathcal{H} ( q , L , τ ) ∈ H such that H η H_\eta H η is a prefix of L L L and every record of H η H_\eta H η has timestamp less than τ \tau τ . One of the positions q , q + 1 q,q+1 q , q + 1 belongs to I I I , so this cut does not lie entirely outside I I I . Thus Step 3 includes ( q , L , τ ) (q,L,\tau) ( q , L , τ ) in the merge without deleting any of its records.
If q ≠ ∂ η J q\ne\partial_\eta J q = ∂ η J , then this is a new boundary, and Step 4 sets H η ′ = L q , D H'_\eta=L_{q,D} H η ′ = L q , D . The entry ( q , L q , D , t D ) (q,L_{q,D},t_D) ( q , L q , D , t D ) belongs to H D \mathcal{H}_D H D and is included in the merge in Step 3. Set L = L q , D L=L_{q,D} L = L q , D and τ = t D \tau=t_D τ = t D . Then H η ′ = L H'_\eta=L H η ′ = L , and every record of H η ′ H'_\eta H η ′ has timestamp less than τ \tau τ by Theorem 3.4.
In either case, the merge receives an entry ( q , L , τ ) (q,L,\tau) ( q , L , τ ) with the required prefix relation and timestamp bound. Whenever two entries at q q q have cutoffs τ 1 ≤ τ 2 \tau_1 \le\tau_2 τ 1 ≤ τ 2 , a successful merge requires
L 1 = L 2 ↾ < τ 1 L_1 = L_2 \mathbin{\upharpoonright}_{<\tau_1} L 1 = L 2 ↾ < τ 1
and retains ( q , L 2 , τ 2 ) (q,L_2,\tau_2) ( q , L 2 , τ 2 ) . Because the records are ordered by timestamp, L 1 L_1 L 1 is a prefix of L 2 L_2 L 2 . Thus each successful merge preserves both input lists as prefixes of the retained list and never decreases either cutoff. Since C ′ ≠ ⊥ C' \ne\perp C ′ = ⊥ , all merges succeed. The resulting entry ( q , L q ′ , τ q ′ ) ∈ H ′ (q,L'_q,\tau'_q) \in\mathcal{H}' ( q , L q ′ , τ q ′ ) ∈ H ′ therefore has H η ′ H'_\eta H η ′ as a prefix of L q ′ L'_q L q ′ , with every record of H η ′ H'_\eta H η ′ having timestamp less than τ q ′ \tau'_q τ q ′ .
It remains to check the changes in Step 5. If i 0 ∈ I i_0 \in I i 0 ∈ I , this step is skipped, so the claim already holds for the returned constraint. Otherwise, let e 0 e_0 e 0 be the prescribed entrance, let η 0 \eta_0 η 0 be its entrance side, and let q 0 = ∂ η 0 I q_0=\partial_{\eta_0}I q 0 = ∂ η 0 I . The successful boundary check in Step 5b requires H η 0 ′ [ 1 ] = e 0 H'_{\eta_0}[1]=e_0 H η 0 ′ [ 1 ] = e 0 . By the prefix relation proved above, L q 0 ′ [ 1 ] = e 0 L'_{q_0}[1] = e_0 L q 0 ′ [ 1 ] = e 0 as well. Hence Step 5a and Step 5b consume the first record of L q 0 ′ L'_{q_0} L q 0 ′ and H η 0 ′ H'_{\eta_0} H η 0 ′ , respectively. No other crossing record is consumed: every consumed record must equal e 0 e_0 e 0 , and e 0 e_0 e 0 crosses only cut q 0 q_0 q 0 .
Consequently, Step 5c deletes the same first record from these two lists. Their remaining suffixes still satisfy the prefix relation. For the other boundary, neither its history nor the list at its cut loses any record. All retained cutoffs are unchanged, so the timestamp bounds also remain valid. This step can remove an entire crossing entry only when its remaining list is empty and its cutoff has expired. A nonempty boundary history cannot be a prefix of an empty list; thus no entry needed for a nonempty boundary history is removed. This proves the first statement for C ′ C' C ′ and completes the induction. The argument uses only the successful construction of C ′ C' C ′ , and does not require Y Y Y to describe the actual next outcome.
Second statement: recovery of the counters. Fix C ∈ C r C \in\mathcal{C}_r C ∈ C r and a capped-r r r execution under C C C . Every counter starts at 1 and advances by one whenever its next record is consumed. It therefore suffices to prove that, at the point specified in the lemma, the consumed records of each list are exactly those with timestamp less than s s s .
At the initial checkpoint, s = t 0 s = t_0 s = t 0 . All stored records have timestamp at least t 0 t_0 t 0 , and no record has been consumed, so the assertion holds. Now consider any other checkpoint or an internal overflow at time s s s . By item 2 of Theorem 3.5, the configuration at this point is reached by a transition or a supplied entrance with timestamp s − 1 s - 1 s − 1 . Its crossing check has succeeded; otherwise the execution would already have returned FAIL.
Consider any crossing list L q L_q L q . Immediately before this check, its next unused record, if it has timestamp at most s − 1 s - 1 s − 1 , must equal the record being checked, by item 5 of Theorem 3.5. In particular, its timestamp must be exactly s − 1 s - 1 s − 1 , and the successful check consumes it. Since timestamps within L q L_q L q are strictly increasing, every record left unused after this check has timestamp greater than s − 1 s - 1 s − 1 . Moreover, no record with timestamp at least s s s has been consumed: a crossing record is consumed only when it equals the transition or supplied entrance being checked, and all such records processed so far have timestamp at most s − 1 s - 1 s − 1 . Thus the consumed records of L q L_q L q are exactly those with timestamp less than s s s .
Next consider a nonempty boundary history H η H_\eta H η at cut q = ∂ η J q = \partial_\eta J q = ∂ η J . By the first statement, it is a prefix of a crossing list L q L_q L q . Every record of H η H_\eta H η with timestamp less than s s s has therefore been matched by a successful crossing check. Such a record describes either an exit from J J J or a supplied entrance into J J J . In the exit case, item 2 of Theorem 3.5 then compares the same record with the next unused record of H η H_\eta H η and consumes it. If this boundary check failed, or if the required record were absent, the execution would stop outside J J J before reaching the checkpoint or internal overflow under consideration. In the entrance case, the boundary record is consumed after its successful crossing check and before its resulting configuration is installed. Hence every boundary record with timestamp less than s s s has also been consumed in its boundary history.
It remains to show that no boundary record with timestamp at least s s s has been consumed. Let e e e be any boundary record already consumed at the checkpoint or internal overflow under consideration, and let u u u be its timestamp. If e e e is an exit record, it is consumed after the transition from time u u u to time u + 1 u + 1 u + 1 . If e e e is a supplied entrance record, it is consumed immediately before the configuration at time u + 1 u + 1 u + 1 is installed; no checkpoint or internal overflow is produced between these two operations. In either case, since time never decreases, the checkpoint or internal overflow under consideration must satisfy s ≥ u + 1 s \ge u + 1 s ≥ u + 1 . Hence u < s u < s u < s .
Thus the consumed boundary records are exactly those with timestamp less than s s s . An empty boundary history has counter 1 throughout. Together with the argument for crossing histories, this proves (8) .
For the next three lemmas, fix 2 ≤ r ≤ k 2 \le r \le k 2 ≤ r ≤ k and C ∈ E r C \in\mathcal{E}_r C ∈ E r on J J J . For the analysis only, number the stages by j j j . Stage 0 starts at the initial checkpoint D 0 = ( J , ∅ ) D_0=(J,\varnothing) D 0 = ( J , ∅ ) , and each accepted CONTINUE candidate advances to the next stage. Rejected trials do not advance j j j . For Exec r _r r , each recorded checkpoint after D 0 D_0 D 0 likewise advances the stage by one.
Drawing the random assignment U J U_J U J induces a random checkpoint path (a sequence of checkpoints). Let D j D_j D j be its checkpoint at stage j j j , with D 0 = ( J , ∅ ) D_0=(J,\varnothing) D 0 = ( J , ∅ ) , and set D j = ⊥ D_j=\bot D j = ⊥ if stage j j j is not reached. On the event D j ≠ ⊥ D_j\ne\bot D j = ⊥ , let O j O_j O j be the next outcome: D j + 1 D_{j+1} D j + 1 if the execution continues, and its return report if it stops. Fix a stage j j j and a checkpoint D D D reachable at that stage, and define
A j , D = { z J ∈ { 0 , 1 } J : Exec r ( C , z J ) reaches D at stage j } , I = I D . A_{j,D}=\{z_J\in\{0,1\}^{J}:\textbf{Exec}_r(C,z_J)\text{ reaches }D\text{ at stage }j\},\qquad I=I_D. A j , D = { z J ∈ { 0 , 1 } J : Exec r ( C , z J ) reaches D at stage j } , I = I D .
Thus U J ∈ A j , D U_J\in A_{j,D} U J ∈ A j , D is the event that the capped execution reaches D D D at stage j j j . For every I ⊆ J I\subseteq J I ⊆ J , write U I : = U J ∣ I U_I:=U_J|_I U I := U J ∣ I . We write L ( U I ∣ A j , D ) \mathcal{L}(U_I\mid A_{j,D}) L ( U I ∣ A j , D ) for the conditional distribution of U I U_I U I given the event U J ∈ A j , D U_J\in A_{j,D} U J ∈ A j , D . Equivalently, choose an assignment z J z_J z J uniformly from A j , D A_{j,D} A j , D and return its restriction z J ∣ I z_J|_I z J ∣ I . Since D D D is reachable at stage j j j , the set A j , D A_{j,D} A j , D is nonempty. Thus, for every u ∈ { 0 , 1 } I u\in\{0,1\}^{I} u ∈ { 0 , 1 } I ,
Pr [ U I = u ∣ U J ∈ A j , D ] = ∣ { z J ∈ A j , D : z J ∣ I = u } ∣ ∣ A j , D ∣ . \Pr[U_I=u\mid U_J\in A_{j,D}]=\frac{\left|\{z_J\in A_{j,D}:z_J|_I=u\}\right|}{|A_{j,D}|}. Pr [ U I = u ∣ U J ∈ A j , D ] = ∣ A j , D ∣ ∣ { z J ∈ A j , D : z J ∣ I = u } ∣ .
We first determine the conditional distribution of the random bits in the current interval after the execution reaches D D D .
Lemma 3.9. There are sets E D ⊆ { 0 , 1 } I E_D\subseteq\{0,1\}^{I} E D ⊆ { 0 , 1 } I and F D ⊆ { 0 , 1 } J ∖ I F_D\subseteq\{0,1\}^{J\setminus I} F D ⊆ { 0 , 1 } J ∖ I such that
A j , D = { z J ∈ { 0 , 1 } J : z J ∣ I ∈ E D , z J ∣ J ∖ I ∈ F D } . (9) A_{j,D}=\{z_J\in\{0,1\}^{J}:z_J|_I\in E_D,\ z_J|_{J\setminus I}\in F_D\}. \tag*{(9)} A j , D = { z J ∈ { 0 , 1 } J : z J ∣ I ∈ E D , z J ∣ J ∖ I ∈ F D } . (9) Consequently, with q D = Pr [ U I ∈ E D ] > 0 q_D=\Pr[U_I\in E_D]>0 q D = Pr [ U I ∈ E D ] > 0 , we have Pr [ U J ∈ A j , D ] ≤ q D \Pr[U_J\in A_{j,D}]\le q_D Pr [ U J ∈ A j , D ] ≤ q D and
L ( U I ∣ A j , D ) = Unif ( E D ) . (10) \mathcal{L}(U_I\mid A_{j,D})=\operatorname{Unif}(E_D). \tag*{(10)} L ( U I ∣ A j , D ) = Unif ( E D ) . (10)
Proof. We proceed in three steps.
Define the two sets. Let
E D = { z J ∣ I : z J ∈ A j , D } , F D = { z J ∣ J ∖ I : z J ∈ A j , D } . E_D=\{z_J|_I:z_J\in A_{j,D}\},\qquad F_D=\{z_J|_{J\setminus I}:z_J\in A_{j,D}\}. E D = { z J ∣ I : z J ∈ A j , D } , F D = { z J ∣ J ∖ I : z J ∈ A j , D } .
Since D D D is reachable at stage j j j , the set A j , D A_{j,D} A j , D is nonempty, and hence so are E D E_D E D and F D F_D F D . By definition, every assignment in A j , D A_{j,D} A j , D restricts to an element of E D E_D E D on I I I and an element of F D F_D F D on J ∖ I J\setminus I J ∖ I . This proves the left-to-right inclusion in (9) .
Prove the reverse inclusion. If D = D 0 D=D_0 D = D 0 , then j = 0 j=0 j = 0 , I = J I=J I = J , and A 0 , D 0 = { 0 , 1 } J A_{0,D_0}=\{0,1\}^{J} A 0 , D 0 = { 0 , 1 } J , so the reverse inclusion is immediate. Suppose D ≠ D 0 D\ne D_0 D = D 0 . Fix u ∈ E D u\in E_D u ∈ E D and u ′ ∈ F D u'\in F_D u ′ ∈ F D . Choose z , z ~ ∈ A j , D z,\widetilde{z}\in A_{j,D} z , z ∈ A j , D such that z ∣ I = u z|_I=u z ∣ I = u and z ~ ∣ J ∖ I = u ′ \widetilde{z}|_{J\setminus I}=u' z ∣ J ∖ I = u ′ , and define w w w by
w ∣ I = z ∣ I = u , w ∣ J ∖ I = z ~ ∣ J ∖ I = u ′ . w|_I=z|_I=u,\qquad w|_{J\setminus I}=\widetilde{z}|_{J\setminus I}=u'. w ∣ I = z ∣ I = u , w ∣ J ∖ I = z ∣ J ∖ I = u ′ .
We show that the capped-r r r execution on w w w reaches D D D at stage j j j . Both executions on z z z and z ~ \widetilde{z} z reach D = ( I , H D ) D=(I,\mathcal{H}_D) D = ( I , H D ) . For each q ∈ ∂ I q\in\partial I q ∈ ∂ I , the checkpoint therefore records the same complete crossing history L q , D L_{q,D} L q , D during [ t 0 , t D ) [t_0,t_D) [ t 0 , t D ) . In particular, a boundary crossing with record ( s , x , y , c ) (s,x,y,c) ( s , x , y , c ) occurs in both executions and leaves both at the same triple ( c , y , s + 1 ) (c,y,s+1) ( c , y , s + 1 ) . Starting from the common initial data of C C C , follow the execution on z z z inside I I I and the execution on z ~ \widetilde{z} z outside I I I . Between boundary crossings, the bits read agree with w w w . At an exit from I I I , perform the departure from the execution on z z z ; its resulting triple agrees with that of z ~ \tilde{z} z ~ , so continue with the latter execution outside I I I . At an entrance into I I I , follow the entrance from z ~ \tilde{z} z ~ ; its resulting triple agrees with that of z z z , so continue with the latter execution inside I I I . Excursions outside J J J use the fixed boundary histories of C C C . Those crossing a boundary of I I I have the common exit and entrance records just described; all others belong to the unchanged exterior execution on z ~ \tilde{z} z ~ .
We check that this combined computation obeys the execution rules. At each position in I I I , its visits and random bit are those of z z z ; at each position in J ∖ I J \setminus I J ∖ I , they are those of z ~ \tilde{z} z ~ . At a cut entirely inside I I I , its crossing history is that of z z z ; at a cut entirely outside I I I , it is that of z ~ \tilde{z} z ~ ; at a boundary of I I I , it is the common history in H D \mathcal{H}_D H D . Thus the visit and bit checks, crossing checks, and boundary rules needed to reach the checkpoint update at time t D t_D t D all succeed, as in the corresponding original executions. No earlier normal termination occurs, since each configuration and its timestamp come from an original execution before it reaches D D D . The combined computation is therefore the capped-r r r execution under C C C on w w w up to this update.
To identify its checkpoint, first observe that no position of I I I completes its r r r -th visit before D D D in either original execution. Such a departure would either produce a checkpoint excluding that position from every later interval, or cause a return report before another checkpoint could be recorded. Both possibilities contradict reaching D D D with that position still in I I I . All departures completing an r r r -th visit through time t D t_D t D consequently occur in J ∖ I J \setminus I J ∖ I . In the combined computation, these departures have exactly the same times, positions, and directions as in the execution on z ~ \tilde{z} z ~ . The checkpoint update rule therefore produces the same sequence of retained intervals and reaches I I I at stage j j j and time t D t_D t D . Its crossing histories at the boundaries of I I I are H D \mathcal{H}_D H D , so its checkpoint at that stage is exactly D D D . Hence w ∈ A j , D w \in A_{j,D} w ∈ A j , D . Since u u u and u ′ u' u ′ were arbitrary, this proves the reverse inclusion and establishes (9) .
Compute the probabilities. By (9) , pairing any assignment in E D E_D E D with any assignment in F D F_D F D gives an assignment in A j , D A_{j,D} A j , D , and every assignment in A j , D A_{j,D} A j , D is obtained uniquely in this way. Thus ∣ A j , D ∣ = ∣ E D ∣ ∣ F D ∣ |A_{j,D}| = |E_D|\,|F_D| ∣ A j , D ∣ = ∣ E D ∣ ∣ F D ∣ . Since U J U_J U J is uniform and q D = ∣ E D ∣ / 2 ∣ I ∣ q_D = |E_D|/2^{|I|} q D = ∣ E D ∣/ 2 ∣ I ∣ ,
Pr [ U J ∈ A j , D ] = ∣ E D ∣ ∣ F D ∣ 2 ∣ J ∣ = q D ∣ F D ∣ 2 ∣ J ∖ I ∣ ≤ q D . \Pr[U_J \in A_{j,D}] = \frac{|E_D|\,|F_D|}{2^{|J|}} = q_D\frac{|F_D|}{2^{|J\setminus I|}} \le q_D. Pr [ U J ∈ A j , D ] = 2 ∣ J ∣ ∣ E D ∣ ∣ F D ∣ = q D 2 ∣ J ∖ I ∣ ∣ F D ∣ ≤ q D .
For each fixed u ∈ E D u \in E_D u ∈ E D , there are exactly ∣ F D ∣ |F_D| ∣ F D ∣ assignments in A j , D A_{j,D} A j , D whose restriction to I I I is u u u , one for each assignment in F D F_D F D . Therefore
Pr [ U I = u ∣ U J ∈ A j , D ] = ∣ F D ∣ ∣ A j , D ∣ = 1 ∣ E D ∣ . \Pr[U_I = u \mid U_J \in A_{j,D}] = \frac{|F_D|}{|A_{j,D}|} = \frac{1}{|E_D|}. Pr [ U I = u ∣ U J ∈ A j , D ] = ∣ A j , D ∣ ∣ F D ∣ = ∣ E D ∣ 1 .
For u ∉ E D u \notin E_D u ∈ / E D , the conditional probability is 0. Hence L ( U I ∣ A j , D ) = Unif ( E D ) \mathcal{L}(U_I \mid A_{j,D}) = \operatorname{Unif}(E_D) L ( U I ∣ A j , D ) = Unif ( E D ) , proving (10) .
We next specify how to form a candidate from an execution that reaches D D D , and prove that the resulting candidate depends only on the random bits in I D I_D I D .
Lemma 3.10 (Determination of the canonical candidate). Fix 2 ≤ r ≤ k 2 \le r \le k 2 ≤ r ≤ k , a constraint C ∈ C r C \in\mathcal{C}_r C ∈ C r , and a checkpoint D D D reachable at stage j j j . Write I = I D I = I_D I = I D . Fix z I ∈ E D z_I \in E_D z I ∈ E D . For each extension z J ∈ A j , D z_J \in A_{j,D} z J ∈ A j , D with z J ∣ I = z I z_J|_I = z_I z J ∣ I = z I , follow Exec r ( C , z J ) \operatorname{Exec}_r(C,z_J) Exec r ( C , z J ) through D D D to its next checkpoint or return report, and form the rank-r r r candidate specified in item 3 of the proof. This candidate is independent of the chosen extension. We call it the canonical candidate for C , D , z I C,D,z_I C , D , z I .
Proof. By Theorem 3.9 , every z I ∈ E D z_I \in E_D z I ∈ E D has an extension in A j , D A_{j,D} A j , D . Fix any two such extensions z , z ~ z,\tilde{z} z , z ~ . We first identify the portions of their executions that agree, and then specify the candidate fields.
Determine the execution inside I I I through D D D . If i 0 ∈ I i_0 \in I i 0 ∈ I , both executions start with the initial data of C \mathcal{C} C and read the same bits z I z_I z I . Otherwise, both first enter I I I according to the same earliest entrance record in H D \mathcal{H}_D H D . Each subsequent entrance recorded in H D \mathcal{H}_D H D also places both executions at the same configuration, position, and time. Between entrances and exits, the transitions inside I I I are determined by these data and z I z_I z I . Hence the executions have the same visits to every position of I I I and the same crossing histories at every cut inside I I I through D D D . Their configuration, head position, and time at D D D agree, and their visit counters in I I I agree at that point. By Theorem 3.8, all crossing and boundary counters of C \mathcal{C} C also agree, since they are determined by the stored lists and t D t_D t D .
Determine the next outcome after D D D . Resume the execution from D D D , including any checks still pending at that checkpoint. While the head stays in I I I , both executions use the same bits, configurations, visit counters, and history counters, so they perform the same transitions and checks. Any entry into J ∖ I J \setminus I J ∖ I must first reach a position v v v adjacent to I I I . This position has already completed its r r r -th visit, so N v = r N_v=r N v = r . Unless the preceding crossing checks or normal-termination rule have already returned a report, the new-visit check in item 4 of Theorem 3.5 returns OVERFLOW before reading z v z_v z v . Thus the execution reads no random bit in J ∖ I J \setminus I J ∖ I after reaching D D D . An excursion outside J J J uses the fixed boundary histories of C \mathcal{C} C with the same counters in both executions. Consequently, the two executions agree until they reach the next checkpoint or produce a return report, including all fields of that report.
Specify every field of the candidate. Set θ = C O N T I N U E \theta=\mathrm{CONTINUE} θ = CONTINUE if the next outcome is a checkpoint, and otherwise let θ \theta θ be the return report. If an r r r -th visit to a position of I I I begins at or after D D D before this outcome is produced, let v v v be that position and set β = ( z I ) v \beta=(z_I)_v β = ( z I ) v ; otherwise, set v = ⊥ v=\perp v =⊥ and β = 0 \beta=0 β = 0 . There is at most one such visit: its departure either records the next checkpoint or leads to a return report before another r r r -th visit in I I I can begin. These fields agree by the preceding step. If θ \theta θ is a return report, set d = ⊥ d=\perp d =⊥ and H Y = ∅ \mathcal{H}_Y=\varnothing H Y = ∅ , as in Theorem 3.7. Otherwise, let d d d be the actual departure direction from v v v , and let H Y \mathcal{H}_Y H Y contain the actual crossing histories at the cuts in S Y S_Y S Y during [ t 0 , t Y ) [t_0,t_Y) [ t 0 , t Y ) , where t Y t_Y t Y is the new checkpoint time. Every cut in S Y S_Y S Y lies inside I I I or at a boundary of I I I . Its history before D D D is determined by the first step and H D \mathcal{H}_D H D , and its subsequent records are determined by the second step. Thus these histories also agree. The resulting tuple satisfies Theorem 3.7; in particular, each relevant cut has at most 2 r 2r 2 r crossings before this nonterminal outcome.
Therefore all fields of the canonical candidate are independent of the chosen extension of z I z_I z I . □
For z I ∈ E D z_I\in E_D z I ∈ E D , write g D ( z I ) g_D(z_I) g D ( z I ) for the canonical candidate specified by Theorem 3.10, with C \mathcal{C} C understood from the context. Set g D ( z I ) = ⊥ g_D(z_I)=\perp g D ( z I ) =⊥ when z I ∉ E D z_I\notin E_D z I ∈ / E D . For a candidate Y = ( θ , v , d , β , H Y ) Y=(\theta,v,d,\beta,\mathcal{H}_Y) Y = ( θ , v , d , β , H Y ) , let π ( Y ) \pi(Y) π ( Y ) be the next checkpoint specified by Y Y Y when θ = C O N T I N U E \theta=\mathrm{CONTINUE} θ = CONTINUE , and the return report θ \theta θ otherwise. Set π ( ⊥ ) = ⊥ \pi(\perp)=\perp π ( ⊥ ) =⊥ .
We next analyze CreateConstraint and FinishAndCheck for a fixed assignment z I z_I z I . For a candidate Y Y Y , write C ′ = CreateConstraint ( C , D , Y ) \mathcal{C}'=\textbf{CreateConstraint}(\mathcal{C},D,Y) C ′ = CreateConstraint ( C , D , Y ) . The following lemma proves that C ′ ≠ ⊥ \mathcal{C}'\ne\perp C ′ = ⊥ whenever Y = g D ( z I ) Y=g_D(z_I) Y = g D ( z I ) . Whenever C ′ ≠ ⊥ \mathcal{C}'\ne\perp C ′ = ⊥ , it also proves that FinishAndCheck , given the child report E x e c r − 1 ( C ′ , z I ) \mathbf{Exec}_{r-1}(\mathcal{C}',z_I) Exec r − 1 ( C ′ , z I ) , returns 1 if and only if Y = g D ( z I ) Y=g_D(z_I) Y = g D ( z I ) .
Lemma 3.11 (Exact verification of a candidate). Fix 2 ≤ r ≤ k 2 \le r \le k 2 ≤ r ≤ k , a constraint C ∈ C r C \in\mathcal{C}_r C ∈ C r , a checkpoint D D D reachable at stage j j j , and a rank-r r r candidate Y Y Y . Write I = I D I=I_D I = I D and let
C ′ = CreateConstraint ( C , D , Y ) . C'=\operatorname{CreateConstraint}(C,D,Y). C ′ = CreateConstraint ( C , D , Y ) . If g D ( z I ) = Y g_D(z_I)=Y g D ( z I ) = Y for some z I ∈ E D z_I \in E_D z I ∈ E D , then C ′ ≠ ⊥ C' \ne\bot C ′ = ⊥ . Whenever C ′ ≠ ⊥ C' \ne\bot C ′ = ⊥ , we have C ′ ∈ C r − 1 C' \in\mathcal{C}_{r-1} C ′ ∈ C r − 1 and, for every z I ∈ { 0 , 1 } I z_I \in\{0,1\}^{I} z I ∈ { 0 , 1 } I ,
FinishAndCheck ( C , D , Y , C ′ , Exec r − 1 ( C ′ , z I ) ) = 1 ⟺ g D ( z I ) = Y . (11) \operatorname{FinishAndCheck}(C,D,Y,C',\operatorname{Exec}_{r-1}(C',z_I))=1 \quad\Longleftrightarrow\quad g_D(z_I)=Y. \tag*{(11)} FinishAndCheck ( C , D , Y , C ′ , Exec r − 1 ( C ′ , z I )) = 1 ⟺ g D ( z I ) = Y . (11)
Proof. We first prove that a canonical candidate gives C ′ ≠ ⊥ C' \ne\bot C ′ = ⊥ , and that every non-⊥ \bot ⊥ child constraint belongs to C r − 1 \mathcal{C}_{r-1} C r − 1 . We then prove the two implications in (11) separately.
The construction succeeds for a canonical candidate. Suppose g D ( z I ) = Y g_D(z_I)=Y g D ( z I ) = Y . By Theorem 3.10, choose an extension w ∈ A j , D w \in A_{j,D} w ∈ A j , D with w ∣ I = z I w|_I=z_I w ∣ I = z I . The candidate formed from this execution is Y Y Y . We verify the checks in CreateConstraint , as defined in § 3.3 , using the capped-r r r execution Exec r ( C , w ) _r(C,w) r ( C , w ) .
(a) Compatibility with C C C and D D D . In Step 1 of CreateConstraint , the time inequalities hold because Y Y Y records the next outcome after D D D : a subsequent checkpoint has t Y > t D t_Y>t_D t Y > t D , and a return report has t Y ≥ t D t_Y\ge t_D t Y ≥ t D . Every reported time is at most T T T by Theorem 3.5. If the report has tag FAIL, it is a report of Exec r ( C , w ) _r(C,w) r ( C , w ) . By Theorem 3.3, its identifier γ \gamma γ identifies an entry ( q , L q , τ q ) ∈ H (q,L_q,\tau_q)\in\mathcal{H} ( q , L q , τ q ) ∈ H , a bit requirement ( u , α ) ∈ B (u,\alpha)\in B ( u , α ) ∈ B , or a boundary history H η H_\eta H η with η ∈ { L , R } \eta\in\{L,R\} η ∈ { L , R } . Thus γ \gamma γ satisfies the corresponding condition in this step.
(b) The initial data and bit requirements. Consider Step 2 of CreateConstraint . If i 0 ∈ I i_0\in I i 0 ∈ I , the original initial data are retained. Otherwise, since the execution reaches D D D with its head in I I I , it must first enter I I I . Its earliest boundary record in H D \mathcal{H}_D H D is precisely that entrance e 0 = ( s , x , y , c ) e_0=(s,x,y,c) e 0 = ( s , x , y , c ) . Thus the required entrance exists and specifies ( σ 0 ′ , v 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) (\sigma'_0,v'_0,t'_0)=(c,y,s+1) ( σ 0 ′ , v 0 ′ , t 0 ′ ) = ( c , y , s + 1 ) . When v ≠ ⊥ v\ne\bot v = ⊥ , the additional bit requirement is ( v , w v ) (v,w_v) ( v , w v ) , since Y Y Y is canonical. Forming B ′ B' B ′ involves no further check.
(c) Compatibility of the crossing histories. Consider Step 3 of CreateConstraint . Every cut in H D \mathcal{H}_D H D or H Y \mathcal{H}_Y H Y has an endpoint in I I I . Hence the deletion of records at cuts entirely outside I I I does not change any entry that will be merged with these histories. The lists supplied by D D D are complete actual crossing histories up to t D t_D t D . When θ = C O N T I N U E \theta=\mathrm{CONTINUE} θ = CONTINUE , those supplied by Y Y Y are complete actual histories up to the next checkpoint time t Y t_Y t Y . By the crossing check in item 5 of Theorem 3.5, the inherited requirements agree with these actual histories throughout their common time intervals: before a checkpoint is reached, every prescribed record whose timestamp precedes it has been matched, and every crossing before its prescribed cutoff has been checked. Therefore, whenever two entries at the same cut have cutoffs τ 1 ≤ τ 2 \tau_1\le\tau_2 τ 1 ≤ τ 2 , their lists satisfy
L 1 = L 2 ∣ < τ 1 . L_1=L_2\mathbin{|}_{<\tau_1}. L 1 = L 2 ∣ < τ 1 .
This is exactly the equality required by the merge. Retaining the entry with the larger cutoff preserves this agreement for subsequent merges, so all merges succeed.
(d) The entrance checks and remaining histories. The boundary histories are assigned in Step 4 of CreateConstraint without any rejection. If i 0 ∈ I i_0\in I i 0 ∈ I , Step 5 is skipped. Suppose i 0 ∉ I i_0\notin I i 0 ∈ / I , and use the entrance e 0 e_0 e 0 from the preceding argument. Let q 0 q_0 q 0 be its cut, let η \eta η be its entrance side, and write H ′ = { ( q , L q ′ , τ q ′ ) : q ∈ Q ′ } \mathcal{H}'=\{(q,L'_q,\tau'_q):q\in Q'\} H ′ = {( q , L q ′ , τ q ′ ) : q ∈ Q ′ } . No crossing of a cut having an endpoint in I I I occurs before this first entrance. At cuts entirely outside I I I , all records with timestamp less than t D t_D t D have already been deleted. Since t 0 ′ = s + 1 ≤ t D t'_0=s+1\le t_D t 0 ′ = s + 1 ≤ t D , the merged lists satisfy
L q ′ ↾ < t 0 ′ = { ( e 0 ) , q = q 0 , ( ) , q ≠ q 0 . L'_q\mathbin{\upharpoonright}_{<t'_0} =
\begin{cases}
(e_0), & q=q_0,\\
(), & q\ne q_0.
\end{cases} L q ′ ↾ < t 0 ′ = { ( e 0 ) , ( ) , q = q 0 , q = q 0 .
Moreover, the entry from H D \mathcal{H}_D H D at q 0 q_0 q 0 ensures τ q 0 ′ ≥ t D > s \tau'_{q_0}\ge t_D>s τ q 0 ′ ≥ t D > s . Thus the crossing check in item 5 of Theorem 3.5, applied to e 0 e_0 e 0 with all counters initialized to 1, matches exactly the first record of L q 0 ′ L'_{q_0} L q 0 ′ . This proves that Step 5a of CreateConstraint succeeds. Since i 0 ∈ J ∖ I i_0\in J\setminus I i 0 ∈ J ∖ I and every supplied excursion outside J J J returns to the endpoint from which it exited, as specified in item 2 of Theorem 3.5, the first entrance e 0 e_0 e 0 crosses a new boundary of I I I . Thus H η ′ = L q 0 , D H'_\eta=L_{q_0,D} H η ′ = L q 0 , D begins with e 0 e_0 e 0 . Any other newly assigned boundary history is also taken from H D \mathcal{H}_D H D and has no record before t 0 ′ t'_0 t 0 ′ . For an inherited boundary history, Theorem 3.8 implies that all records with timestamp less than t D t_D t D have been consumed in the parent execution. Since no crossing of that boundary occurs before the first entrance into I I I , it likewise has no record before t 0 ′ t'_0 t 0 ′ . Hence, after e 0 e_0 e 0 is removed, every remaining boundary record has timestamp at least t 0 ′ t'_0 t 0 ′ . These are exactly the requirements in Step 5b of CreateConstraint . Finally, Step 5c of that procedure only deletes consumed records and expired empty entries, so it cannot reject.
All checks in CreateConstraint therefore succeed, and Step 6 of that procedure returns C ′ ≠ ⊥ C'\ne\bot C ′ = ⊥ . This proves the first assertion of the lemma. Independently of whether Y Y Y is canonical, whenever C ′ ≠ ⊥ C'\ne\bot C ′ = ⊥ , the definition of the constraint families gives C ′ ∈ C r − 1 C'\in\mathcal{C}_{r-1} C ′ ∈ C r − 1 . For the remaining two parts, fix a candidate with C ′ ≠ ⊥ C'\ne\bot C ′ = ⊥ and an arbitrary z I ∈ { 0 , 1 } I z_I\in\{0,1\}^I z I ∈ { 0 , 1 } I , and write
R = Exec r − 1 ( C ′ , z I ) . R=\operatorname{Exec}_{r-1}(C',z_I). R = Exec r − 1 ( C ′ , z I ) .
Acceptance implies Y = g D ( z I ) Y=g_D(z_I) Y = g D ( z I ) . Assume
FinishAndCheck ( C , D , Y , C ′ , R ) = 1. \operatorname{FinishAndCheck}(C,D,Y,C',R)=1. FinishAndCheck ( C , D , Y , C ′ , R ) = 1.
We first show that z I ∈ E D z_I\in E_D z I ∈ E D , and then identify every field of the accepted candidate.
(a) The parent execution reaches D D D . Fix w ∗ ∈ A j , D w^*\in A_{j,D} w ∗ ∈ A j , D and define w w w by
w ∣ I = z I , w ∣ J ∖ I = w ∗ ∣ J ∖ I . w|_I=z_I,\qquad w|_{J\setminus I}=w^*|_{J\setminus I}. w ∣ I = z I , w ∣ J ∖ I = w ∗ ∣ J ∖ I .
If D = D 0 D=D_0 D = D 0 , then I = J I=J I = J and w ∈ A 0 , D 0 w\in A_{0,D_0} w ∈ A 0 , D 0 follows immediately. Suppose D ≠ D 0 D\ne D_0 D = D 0 . By Step 2 of CreateConstraint , the child starts with the parent’s initial data when i 0 ∈ I i_0\in I i 0 ∈ I , and otherwise immediately after the first prescribed entrance into I I I . In the latter case, Step 5 of that procedure checks and consumes this entrance. The remaining records of H D \mathcal{H}_D H D are prescribed by the child’s crossing requirements, and its boundary histories supply the prescribed exits and entrances through time t D t_D t D . Since the test accepts, Step 1 of FinishAndCheck succeeds. In particular, the child cannot return before t D t_D t D , so it does not attempt an r r r -th visit inside I I I before that time. The check in item 5 of Theorem 3.5 requires each record of H D \mathcal{H}_D H D to be matched at its timestamp. A transition inconsistent with its last record gives a history failure at time t D t_D t D , which the reach-checkpoint step rejects. A supplied entrance is checked before its resulting configuration is installed. If that entrance skips a required record, the failure is reported at the time immediately after the preceding exit, so it cannot certify that the skipped checkpoint was reached. If the child stops exactly at t D t_D t D , the permitted report forms specify the configuration and position of D D D and allow only an internal overflow or a bit failure at that position.
Hence the child’s execution inside I I I joins the execution on w ∗ w^* w ∗ outside I I I at the records of H D \mathcal{H}_D H D . As in the proof of Theorem 3.9 , these portions form the parent execution on w w w through D D D at stage j j j : all earlier departures ending an r r r -th visit occur outside I I I and agree with those of w ∗ w^* w ∗ . Thus w ∈ A j , D w \in A_{j,D} w ∈ A j , D and z I ∈ E D z_I \in E_D z I ∈ E D . By Theorem 3.10, the next canonical candidate of this parent execution is g D ( z I ) g_D(z_I) g D ( z I ) .
(b) Identify the report returned by the child execution. The report R R R is the output of Exec r − 1 ( C ′ , z I ) _{r-1}(C', z_I) r − 1 ( C ′ , z I ) . We show that, under the assumed acceptance of FinishAndCheck , it satisfies one of the following two conditions:
If R = ( O V E R F L O W , σ , p , s , ⊥ ) R = (\mathrm{OVERFLOW}, \sigma, p, s, \bot) R = ( OVERFLOW , σ , p , s , ⊥ ) with p ∈ I p \in I p ∈ I , then Exec r ( C , w ) _r(C, w) r ( C , w ) reaches the same triple ( σ , p , s ) (\sigma, p, s) ( σ , p , s ) immediately before its first new r r r -th visit in I I I at or after D D D .
Otherwise, R R R is exactly the next return report of Exec r ( C , w ) _r(C, w) r ( C , w ) after D D D , produced before any new r r r -th visit in I I I begins.
The preceding item identifies their execution portions inside I I I through D D D . In particular, they reach the configuration and position recorded by D D D at the same time, with the same preceding visits to every position in I I I . Records already consumed in preparing C ′ C' C ′ are accounted for by Step 5 of CreateConstraint .
We first account for the requirements added to C ′ C' C ′ by D D D and Y Y Y . The records prescribed by H D \mathcal{H}_D H D have been checked through D D D , and their cutoffs are t D t_D t D , so they impose no additional requirement after D D D . If θ = C O N T I N U E \theta= \mathrm{CONTINUE} θ = CONTINUE , then v ≠ ⊥ v \ne\bot v = ⊥ by Theorem 3.7. Acceptance therefore requires an internal overflow report in Step 2(b)i of FinishAndCheck ; a child failure caused by a requirement from H Y \mathcal{H}_Y H Y or by the added bit requirement ( v , β ) (v,\beta) ( v , β ) cannot pass. If θ \theta θ is a return report, no requirements from H Y \mathcal{H}_Y H Y are added. When v ≠ ⊥ v \ne\bot v = ⊥ , the same internal-overflow check excludes a child failure of ( v , β ) (v,\beta) ( v , β ) ; when v = ⊥ v = \bot v = ⊥ , no bit requirement is added. Thus, under the acceptance assumption, an added requirement cannot make the child return FAIL before a corresponding parent event.
We now follow the rules of the two capped executions from the point specified by D D D , including any pending initialization or new-visit check. Suppose both are at ( σ , p , t ) (\sigma,p,t) ( σ , p , t ) with p ∈ I p \in I p ∈ I and are about to perform a transition. Since w p = ( z I ) p w_p = (z_I)_p w p = ( z I ) p , item 2 of Theorem 3.5 computes the same record e = ( t , p , p ′ , σ ′ ) e = (t,p,p',\sigma') e = ( t , p , p ′ , σ ′ ) in both executions. The unconsumed records of every inherited crossing requirement are preserved in C ′ C' C ′ : Step 3 of CreateConstraint deletes only earlier records at cuts outside I I I , and each merge retains the prescribed prefix of the inherited list. The entrance processing removes only records already accounted for before the child starts. Consequently, the remaining inherited requirements are the same, although their list indices may differ because consumed prefixes have been deleted. The check in item 5 of Theorem 3.5 applies the same inherited requirements to e e e . The normal-termination rule in item 3 is then applied at the same triple ( σ ′ , p ′ , t + 1 ) (\sigma',p',t+1) ( σ ′ , p ′ , t + 1 ) . If θ = C O N T I N U E \theta= \mathrm{CONTINUE} θ = CONTINUE , any failure or normal termination would contradict the required internal overflow. If θ \theta θ is a return report, H Y \mathcal{H}_Y H Y is empty and the requirements from H D \mathcal{H}_D H D have expired and been consumed. The remaining crossing requirements, including the order used to identify a failure, are therefore exactly the parent’s remaining requirements. Thus a crossing failure or normal termination gives the same report, including its identifier. If no report is returned, the remaining rules have the following effects.
If p ′ = p p'=p p ′ = p , neither execution begins a new visit, and both continue from ( σ ′ , p , t + 1 ) (\sigma',p,t+1) ( σ ′ , p , t + 1 ) . If p ′ ∈ I ∖ { p } p' \in I \setminus\{p\} p ′ ∈ I ∖ { p } , apply the new-visit rule in item 4 of Theorem 3.5. When fewer than r − 1 r-1 r − 1 visits to p ′ p' p ′ have occurred, both executions admit the new visit and check the same inherited bit requirements. When exactly r − 1 r-1 r − 1 visits have occurred, the child returns ( O V E R F L O W , σ ′ , p ′ , t + 1 , ⊥ ) (\mathrm{OVERFLOW},\sigma',p',t+1,\perp) ( OVERFLOW , σ ′ , p ′ , t + 1 , ⊥ ) , while the parent is allowed to begin its r r r -th visit at that same triple. The same reasoning applies to a new-visit check pending at D D D or following a supplied entrance.
If p ′ ∈ J ∖ I p' \in J \setminus I p ′ ∈ J ∖ I , the child has left I I I through a new boundary cut q q q . Its boundary history L q , D L_{q,D} L q , D has no unused record after D D D , so the boundary rule in item 2 of Theorem 3.5 returns ( O V E R F L O W , σ ′ , p ′ , t + 1 , ⊥ ) (\mathrm{OVERFLOW},\sigma',p',t+1,\perp) ( OVERFLOW , σ ′ , p ′ , t + 1 , ⊥ ) . In the parent execution, p ′ p' p ′ is the adjacent position removed when its r r r -th visit ended. Its new-visit check therefore returns the same report before reading w p ′ w_{p'} w p ′ .
If p ′ ∉ J p' \notin J p ′ ∈ / J , both executions use the same inherited boundary history in item 2 of Theorem 3.5. They either return the same boundary report or use the same supplied entrance record. All future inherited crossing requirements are retained, so the check of that entrance cannot skip a requirement in either execution. If the entrance is accepted, both install the same configuration, position, and time, apply normal termination, and then apply the new-visit rule just described.
Induction over transitions and supplied entrances now proves the two asserted cases for R R R . The comparison uses only the common execution inside I I I through D D D and the absence of failures caused by the added requirements. It therefore also applies when those requirements are known to agree with the parent execution, as in the reverse implication below. During the later completion, the additional bit requirement ( v , β ) (v,\beta) ( v , β ) is satisfied by the bit β \beta β used there. A failure of a requirement from H Y \mathcal{H}_Y H Y would produce a failure report instead of the proposed continuation and be rejected by Step 3 of FinishAndCheck . Hence completion also cannot turn an additional requirement’s failure into an accepted parent failure.
(c) Every field of Y Y Y is the canonical one. If v = ⊥ v=\perp v =⊥ , Step 2a of FinishAndCheck excludes an internal child overflow. The preceding comparison therefore identifies R R R with the parent’s next return report, produced before a new r r r -th visit begins. If v ≠ ⊥ v\ne\perp v = ⊥ , Step 2(b)i of that procedure requires the child to stop immediately before the first new r r r -th visit, at position v v v . Since r ≥ 2 r\ge2 r ≥ 2 , the child has already made r − 1 r-1 r − 1 visits to v v v and checked ( v , β ) (v,\beta) ( v , β ) without returning a failure, so β = ( z I ) v \beta=(z_I)_v β = ( z I ) v . By Theorem 3.8, the counters restored in Step 2(b)ii of FinishAndCheck are the child’s actual counters at this overflow. The completion therefore performs the parent’s allowed r r r -th visit with the correct bit and remaining requirements.
The checks of the crossing requirements and the normal-termination rule are applied before a departure is classified. If they produce no report, Step 2(b)iii of FinishAndCheck sets R ′ R' R ′ to a CONTINUE tuple for a departure within I I I , before checking the new visit at the destination. This is exactly where item 2 of Theorem 3.5 records the next checkpoint. For entry into J ∖ I J \setminus I J ∖ I , the adjacent destination has already completed r r r visits, so both procedures return overflow. Upon leaving J J J , both use the inherited boundary history and apply the crossing and normal-termination checks prescribed in item 2 of Theorem 3.5. If these rules return no report, the supplied entrance returns to v v v ; both then return overflow before a ( r + 1 ) (r+1) ( r + 1 ) -st visit. Thus, in an accepting test, R ′ R' R ′ describes the parent’s next checkpoint or return report. Finally, Step 3 of that procedure verifies this outcome and its time. For a continuation, it also verifies the departure direction and every history in H Y \mathcal{H}_Y H Y ; for a return report, Theorem 3.7 fixes d = ⊥ d = \bot d = ⊥ and H Y = ∅ \mathcal{H}_Y = \varnothing H Y = ∅ . Hence all fields agree with the construction in item 3 of the proof of Theorem 3.10. Therefore Y = g D ( z I ) Y = g_D(z_I) Y = g D ( z I ) , proving the forward implication.
Y = g D ( z I ) Y = g_D(z_I) Y = g D ( z I ) implies acceptance. Suppose Y = g D ( z I ) Y = g_D(z_I) Y = g D ( z I ) . Since Y Y Y is a candidate rather than ⊥ \bot ⊥ , the definition of g D g_D g D gives z I ∈ E D z_I \in E_D z I ∈ E D . Choose an extension w ∈ A j , D w \in A_{j,D} w ∈ A j , D with w ∣ I = z I w|_I = z_I w ∣ I = z I . By Theorem 3.10, the next canonical candidate of Exec r ( C , w ) _r(C,w) r ( C , w ) is Y Y Y . The first part of this proof gives C ′ ≠ ⊥ C' \ne\bot C ′ = ⊥ . We show directly that each part of FinishAndCheck succeeds.
(a) The reach-checkpoint check succeeds. The child uses the same bits on I I I as the parent. Its initial data and boundary histories reproduce the parent’s portions inside I I I through D D D . No position of I I I starts its r r r -th visit before D D D : for D ≠ D 0 D \ne D_0 D = D 0 , any such visit would end before the entrance recorded at D D D , removing that position from the retained interval or stopping the execution before D D D ; for D = D 0 D = D_0 D = D 0 , there are no earlier visits to consider. The smaller visit cap therefore does not stop the child before D D D . The added histories are actual histories of this parent execution, and the added bit, when present, is ( z I ) v (z_I)_v ( z I ) v , so these requirements cause no failure before D D D . If the child stops at D D D , it either returns internal overflow before an allowed r r r -th visit or reports the parent’s bit failure at that position, both permitted by Step 1 of FinishAndCheck . For D = D 0 D = D_0 D = D 0 , that step is skipped. Thus the reach-checkpoint check succeeds.
(b) The completion produces the actual next outcome. The preceding item establishes agreement through D D D . Every requirement added from D D D or Y Y Y prescribes an actual history or bit of the parent execution up to the proposed outcome. Thus these requirements cause no failure during this portion of the execution. The transition, crossing-check, normal-termination, new-visit, and boundary cases proved in item 2b of this proof therefore apply. If v = ⊥ v = \bot v = ⊥ , the parent produces its next return report before beginning a new r r r -th visit in I I I . The case without an internal child overflow gives exactly the same return report, so Step 2a of FinishAndCheck sets R ′ = R R' = R R ′ = R without rejecting. If v ≠ ⊥ v \ne\bot v = ⊥ , the child returns internal overflow immediately before the parent’s first new r r r -th visit to v v v , at a time between t D t_D t D and t Y t_Y t Y . Thus Step 2(b)i of FinishAndCheck succeeds. The restored counters are correct by Theorem 3.8, and β = ( z I ) v \beta= (z_I)_v β = ( z I ) v by the construction of the canonical candidate. Hence each transition of the completion uses the parent’s bit at v v v and its remaining requirements. The departure cases in item 2c of this proof then give the parent’s next checkpoint or return report. No added requirement fails, so none of these operations rejects.
(c) The final comparison succeeds. The outcome just obtained occurs at t Y t_Y t Y and agrees with θ \theta θ , since both are taken from the same parent execution. For a continuation, d d d is its actual departure direction and H Y \mathcal{H}_Y H Y consists of its actual crossing histories through the new checkpoint; these records have been checked during the child execution and completion, including any initial entrance checked by CreateConstraint . For a return report, all fields of R ′ R' R ′ equal those of θ \theta θ . Hence Step 3 of FinishAndCheck succeeds, and
FinishAndCheck ( C , D , Y , C ′ , R ) = 1. \operatorname{FinishAndCheck}(C,D,Y,C',R)=1. FinishAndCheck ( C , D , Y , C ′ , R ) = 1.
This proves the reverse implication.
Together, the last two parts prove (11) .
We now combine the conditional distribution above with the exact candidate test to prove correctness by induction on the visit cap.
Lemma 3.12 (Exact Sampling). For every 1 ≤ r ≤ k 1 \le r \le k 1 ≤ r ≤ k and every C ∈ C r C \in\mathcal{C}_r C ∈ C r on J J J , Sampler r ( C ) _r(C) r ( C ) terminates almost surely and satisfies
L ( Sampler r ( C ) ) = L ( Exec r ( C , U J ) ) . (12) \mathcal{L}(\operatorname{Sampler}_r(C)) = \mathcal{L}(\operatorname{Exec}_r(C,U_J)). \tag*{(12)} L ( Sampler r ( C )) = L ( Exec r ( C , U J )) . (12)
Proof. Induction on the visit cap. We prove the statement for all C ∈ C r C \in\mathcal{C}_r C ∈ C r simultaneously by induction on r r r . For r = 1 r = 1 r = 1 , DirectSample follows Exec 1 _1 1 and draws a fresh uniform bit when a position is first read. Conditioned on all preceding reads, this bit is independent and uniform, exactly as under U J U_J U J , and it is reused throughout the current visit. An attempted second visit returns overflow before reading the bit again, unless a preceding crossing check or normal-termination rule has already returned a report. Thus no discarded bit is needed. The two procedures apply the same checks, boundary rules, and stopping rules, so their return-report distributions agree. Simulated time strictly increases at each transition or supplied entrance and is bounded by T T T , which guarantees termination.
Suppose the result holds for all constraints in C r − 1 \mathcal{C}_{r-1} C r − 1 , and fix C ∈ C r C \in\mathcal{C}_r C ∈ C r .
The conditional distribution of the next outcome. Fix a stage j j j and a checkpoint D D D reachable at that stage, and write I = I D I = I_D I = I D . Use the map g D g_D g D defined by Theorem 3.10. For each candidate y y y , define
a D , y : = Pr [ g D ( U I ) = y ] , a_{D,y} := \Pr[g_D(U_I) = y], a D , y := Pr [ g D ( U I ) = y ] ,
and for each possible next checkpoint or return report o o o , define
K j ( D , o ) : = Pr [ π ( g D ( U I ) ) = o ∣ U I ∈ E D ] . K_j(D,o) := \Pr[\pi(g_D(U_I)) = o \mid U_I \in E_D]. K j ( D , o ) := Pr [ π ( g D ( U I )) = o ∣ U I ∈ E D ] .
By Theorem 3.9 , conditioned on D j = D D_j = D D j = D , the assignment U I U_I U I is uniform on E D E_D E D . By Theorem 3.10, its next outcome is π ( g D ( U I ) ) \pi(g_D(U_I)) π ( g D ( U I )) , regardless of which compatible exterior assignment produced D D D . Hence
K j ( D , o ) = Pr [ O j = o ∣ D j = D ] . (13) K_j(D,o) = \Pr[O_j = o \mid D_j = D]. \tag*{(13)} K j ( D , o ) = Pr [ O j = o ∣ D j = D ] . (13)
The same statement remains true after conditioning on the earlier checkpoints. To prove this, fix a positive-probability prefix p = ( d 0 , … , d j ) p = (d_0,\ldots,d_j) p = ( d 0 , … , d j ) with d j = D d_j = D d j = D , let A p A_p A p be the set of assignments producing this prefix, and let F p F_p F p be its projection onto J ∖ I J \setminus I J ∖ I . We claim that
A p = { z J : z J ∣ I ∈ E D , z J ∣ J ∖ I ∈ F p } . A_p = \{z_J : z_J|_I \in E_D,\ z_J|_{J \setminus I} \in F_p\}. A p = { z J : z J ∣ I ∈ E D , z J ∣ J ∖ I ∈ F p } .
The forward inclusion follows from A p ⊆ A j , D A_p \subseteq A_{j,D} A p ⊆ A j , D . For the reverse inclusion, choose u ∈ E D u \in E_D u ∈ E D and u ′ ∈ F p u' \in F_p u ′ ∈ F p . There are witnesses z ∈ A j , D z \in A_{j,D} z ∈ A j , D and z ~ ∈ A p \widetilde{z} \in A_p z ∈ A p with z ∣ I = u z|_I = u z ∣ I = u and z ~ ∣ J ∖ I = u ′ \widetilde{z}|_{J \setminus I} = u' z ∣ J ∖ I = u ′ . Splice these witnesses as in Theorem 3.9 . The exterior portions through time t D t_D t D remain those of z ~ \widetilde{z} z . As established in the proof of Theorem 3.9 , no position in I I I completes its r r r -th visit before D D D . Every earlier checkpoint is therefore formed by a departure ending an r r r -th visit outside I I I , at the same time and with the same retained interval as in the execution on z ~ \widetilde{z} z . Moreover, each earlier retained interval contains I I I . Its boundary cuts therefore either lie entirely outside I I I , where the execution is unchanged, or coincide with a boundary of I I I , where the crossings are fixed by H D \mathcal{H}_D H D . All earlier checkpoint histories are consequently unchanged. The spliced assignment produces the entire prefix p p p , proving the claim. Each assignment in E D E_D E D consequently has exactly ∣ F p ∣ |F_p| ∣ F p ∣ extensions in A p A_p A p . As in the final step of Theorem 3.9 , this gives L ( U I ∣ U J ∈ A p ) = Unif ( E D ) \mathcal{L}(U_I \mid U_J \in A_p) = \operatorname{Unif}(E_D) L ( U I ∣ U J ∈ A p ) = Unif ( E D ) . The canonical-candidate lemma applies to every such extension, so the next outcome is still π ( g D ( U I ) ) \pi(g_D(U_I)) π ( g D ( U I )) . Therefore
Pr [ O j = o ∣ D 0 = d 0 , … , D j = d j ] = K j ( D , o ) . (14) \Pr[O_j = o \mid D_0 = d_0,\ldots,D_j = d_j] = K_j(D,o). \tag*{(14)} Pr [ O j = o ∣ D 0 = d 0 , … , D j = d j ] = K j ( D , o ) . (14)
This is the Markov property of the checkpoint process.
We will use (14) to compare the probabilities of complete checkpoint sequences.
The distribution of an accepted trial. Since g D g_D g D is a candidate exactly on E D E_D E D , the definitions of a D , y a_{D,y} a D , y and K j K_j K j give
q D K j ( D , o ) = ∑ y : π ( y ) = o a D , y , ∑ y a D , y = q D > 0. q_D K_j(D,o)=\sum_{y:\,\pi(y)=o} a_{D,y}, \qquad\sum_y a_{D,y}=q_D>0. q D K j ( D , o ) = y : π ( y ) = o ∑ a D , y , y ∑ a D , y = q D > 0.
One trial of Sampler r _r r at D D D has the form
Y ← N e x t G u e s s r ( C , D ) , C ′ ← C r e a t e C o n s t r a i n t ( C , D , Y ) , R ← S a m p l e r r − 1 ( C ′ ) , o k ← F i n i s h A n d C h e c k ( C , D , Y , C ′ , R ) . \begin{aligned}
Y &\leftarrow\mathbf{NextGuess}_r(C,D),\\
C' &\leftarrow\mathbf{CreateConstraint}(C,D,Y),\\
R &\leftarrow\mathbf{Sampler}_{r-1}(C'),\\
\mathrm{ok} &\leftarrow\mathbf{FinishAndCheck}(C,D,Y,C',R).
\end{aligned} Y C ′ R ok ← NextGuess r ( C , D ) , ← CreateConstraint ( C , D , Y ) , ← Sampler r − 1 ( C ′ ) , ← FinishAndCheck ( C , D , Y , C ′ , R ) .
Here Y Y Y is the random candidate produced by NextGuess , C ′ C' C ′ is the resulting child constraint, and R R R is the child report. If either of the first two lines returns ⊥ \perp ⊥ , the remaining lines are skipped and we set o k = 0 \mathrm{ok}=0 ok = 0 . Otherwise, the trial is accepted exactly when o k = 1 \mathrm{ok}=1 ok = 1 .
For a fixed candidate y y y such that C y : = C r e a t e C o n s t r a i n t ( C , D , y ) C_y:=\mathbf{CreateConstraint}(C,D,y) C y := CreateConstraint ( C , D , y ) is not ⊥ \perp ⊥ , the definition of the families gives C y ∈ C r − 1 C_y\in\mathcal{C}_{r-1} C y ∈ C r − 1 . The induction hypothesis applied to the child call in Step 3c of Sampler r _r r gives
L ( S a m p l e r r − 1 ( C y ) ) = L ( E x e c r − 1 ( C y , U I ) ) . \mathcal{L}(\mathbf{Sampler}_{r-1}(C_y))=\mathcal{L}(\mathbf{Exec}_{r-1}(C_y,U_I)). L ( Sampler r − 1 ( C y )) = L ( Exec r − 1 ( C y , U I )) .
Applying Theorem 3.11 gives
Pr [ F i n i s h A n d C h e c k ( C , D , y , C y , E x e c r − 1 ( C y , U I ) ) = 1 ] = Pr [ g D ( U I ) = y ] = a D , y . \Pr[\mathbf{FinishAndCheck}(C,D,y,C_y,\mathbf{Exec}_{r-1}(C_y,U_I))=1]=\Pr[g_D(U_I)=y]=a_{D,y}. Pr [ FinishAndCheck ( C , D , y , C y , Exec r − 1 ( C y , U I )) = 1 ] = Pr [ g D ( U I ) = y ] = a D , y .
If a D , y > 0 a_{D,y}>0 a D , y > 0 , some z I ∈ E D z_I\in E_D z I ∈ E D satisfies g D ( z I ) = y g_D(z_I)=y g D ( z I ) = y . The first assertion of Theorem 3.11 then gives C y ≠ ⊥ C_y\ne\perp C y = ⊥ . Thus a candidate for which the construction returns ⊥ \perp ⊥ has a D , y = 0 a_{D,y}=0 a D , y = 0 . Malformed encodings are also rejected.
Each candidate has a unique canonical encoding in the encoding space used by NextGuess r _r r . Since that procedure samples uniformly from its Q r Q_r Q r encodings, one trial satisfies
Pr [ o k = 1 and π ( Y ) = o ] = 1 Q r ∑ y : π ( y ) = o a D , y = q D Q r K j ( D , o ) , \Pr[\mathrm{ok}=1\text{ and }\pi(Y)=o]=\frac{1}{Q_r}\sum_{y:\,\pi(y)=o}a_{D,y}=\frac{q_D}{Q_r}K_j(D,o), Pr [ ok = 1 and π ( Y ) = o ] = Q r 1 y : π ( y ) = o ∑ a D , y = Q r q D K j ( D , o ) ,
Pr [ o k = 1 ] = q D Q r . \Pr[\mathrm{ok}=1]=\frac{q_D}{Q_r}. Pr [ ok = 1 ] = Q r q D .
Write p D = q D / Q r > 0 p_D=q_D/Q_r>0 p D = q D / Q r > 0 . For each h ≥ 1 h\ge1 h ≥ 1 , the probability that the first accepted trial is trial h h h and its outcome is o o o equals
( 1 − p D ) h − 1 p D K j ( D , o ) . (1-p_D)^{h-1}p_DK_j(D,o). ( 1 − p D ) h − 1 p D K j ( D , o ) .
Summing over h h h shows that the accepted outcome has distribution K j ( D , ⋅ ) K_j(D,\cdot) K j ( D , ⋅ ) . The probability of rejecting the first h h h trials is ( 1 − p D ) h (1-p_D)^h ( 1 − p D ) h , which tends to zero. Each child call terminates almost surely by induction, so each reached stage terminates almost surely.
Termination and equality of the output distributions. We prove by induction on j j j that the sampler and the capped execution assign the same probability to every checkpoint prefix ( d 0 , … , d j ) (d_0,\ldots,d_j) ( d 0 , … , d j ) . For j = 0 j=0 j = 0 , both start at D 0 D_0 D 0 with probability 1 1 1 . Suppose the assertion holds through stage j j j , and fix a prefix of positive probability ending at D = d j D=d_j D = d j . By the induction hypothesis, D D D is reachable by the capped execution, so every child constraint constructed at this stage belongs to C r − 1 \mathcal{C}_{r-1} C r − 1 . The preceding trial calculation therefore applies. Fresh coins make the sampler’s next-outcome distribution, even conditioned on this prefix, equal to K j ( D , ⋅ ) K_j(D,\cdot) K j ( D , ⋅ ) . Equation (14) gives the same conditional distribution for the capped execution. For every possible next checkpoint d j + 1 d_{j+1} d j + 1 , both probabilities of the extended prefix are consequently the common prefix probability multiplied by K j ( D , d j + 1 ) K_j(D,d_{j+1}) K j ( D , d j + 1 ) . This proves the induction step; a prefix of probability zero cannot produce a positive-probability extension in either process.
Likewise, for every such prefix ending at D D D and every return report ρ \rho ρ , the probability of producing that prefix followed by ρ \rho ρ is the common prefix probability multiplied by K j ( D , ρ ) K_j(D,\rho) K j ( D , ρ ) in both processes. Each continuation removes at least one position from the current nonempty interval, so at most ∣ J ∣ |J| ∣ J ∣ stages are reached. Since each reached stage terminates almost surely, the sampler terminates almost surely as well. The events consisting of a checkpoint prefix followed by ρ \rho ρ are disjoint, and their union is the event that the output is ρ \rho ρ . Summing their equal probabilities gives
Pr [ S a m p l e r r ( C ) = ρ ] = Pr [ E x e c r ( C , U J ) = ρ ] . \Pr[\mathbf{Sampler}_r(C)=\rho]=\Pr[\mathbf{Exec}_r(C,U_J)=\rho]. Pr [ Sampler r ( C ) = ρ ] = Pr [ Exec r ( C , U J ) = ρ ] .
This proves (12) .
Space, Expected Time and Truncation
We first analyze the ideal sampler before applying the global time cutoff.
Lemma 3.13 (Space and Expected Time). Let C 0 C_0 C 0 be the initial constraint from Theorem 3.6. Then Sampler k ( C 0 ) _k(C_0) k ( C 0 ) uses O ( k 2 b ) O(k^2b) O ( k 2 b ) space and has expected running time 2 O ( k 2 b ) 2^{O(k^2b)} 2 O ( k 2 b ) .
Recall that
b : = C 0 ( S + log ( n + T + 2 ) ) , b := C_0(S+\log(n+T+2)), b := C 0 ( S + log ( n + T + 2 )) ,
where C 0 C_0 C 0 is a sufficiently large constant depending only on M M M . Thus b b b bits suffice to encode a configuration, a random-head position, and a timestamp, as fixed at the beginning of § 3 .
Proof. At visit cap r r r , the current checkpoint D D D and candidate Y Y Y each contain O ( r ) O(r) O ( r ) crossing records of O ( b ) O(b) O ( b ) bits. Each constraint construction adds only constantly many crossing requirements and at most one bit requirement. Thus a frame has O ( k ) O(k) O ( k ) inherited requirements. Store their lists by references to the enclosing frames: merging selects one existing list, and deleting a consumed prefix changes only its starting index. Each reference, cutoff, and history counter uses O ( b ) O(b) O ( b ) bits. These references remain valid while the enclosing call is suspended. The frame therefore uses O ( r b ) O(rb) O ( r b ) bits for D D D , Y Y Y and O ( k b ) O(kb) O ( k b ) bits for inherited requirements, counters, configurations, and reports. Rejected trials reuse this storage. The work-space guard specified at the beginning of § 3 ensures that the same configuration bound applies even when a trial uses an incorrect guess.
In DirectSample , the positions visited inside its interval form an interval, because the head moves locally and every supplied outside excursion returns to the endpoint from which it exited. Store the two endpoints of the visited interval and the bit used during the current visit. An entry into a previously visited position is then detected using O ( log ( T + 2 ) ) O(\log(T+2)) O ( log ( T + 2 )) space, without storing a visit counter for every position. The transition checks and normal-termination rule retain their prescribed precedence over this test. Consequently, the total space is
∑ r = 1 k O ( ( r + k ) b ) = O ( k 2 b ) . \sum_{r=1}^{k} O((r+k)b)=O(k^2b). r = 1 ∑ k O (( r + k ) b ) = O ( k 2 b ) .
For the expected running time, use the families E r \mathcal{E}_r E r defined in § 3.4 and define
A r : = sup C ∈ E r E [ Time ( S a m p l e r r ( C ) ) ] . A_r:=\sup_{C\in\mathcal{E}_r}\mathbb{E}[\operatorname{Time}(\mathbf{Sampler}_r(C))]. A r := C ∈ E r sup E [ Time ( Sampler r ( C ))] .
The supremum is also taken over the representations of these constraints by enclosing frames. The expectation includes the fresh coins used by the call and all of its descendants. Thus A r − 1 A_{r-1} A r − 1 uniformly bounds the recursive part of every trial at visit cap r r r .
Let H H H bound the deterministic work in one trial outside its recursive call. A direct implementation may rescan at most k k k active frames and simulate at most T T T transitions, so we may take
H : = ( n + T + k + b + 2 ) O ( k ) . H := (n + T + k + \mathfrak{b} + 2)^{O(k)}. H := ( n + T + k + b + 2 ) O ( k ) .
Since k ≤ T + 1 k \le T + 1 k ≤ T + 1 and b = Ω ( log ( n + T + 2 ) ) \mathfrak{b} = \Omega(\log(n+T+2)) b = Ω ( log ( n + T + 2 )) , we have H = 2 O ( k b ) H = 2^{O(k\mathfrak{b})} H = 2 O ( k b ) . The base procedure DirectSample makes no recursive call, so A 1 ≤ H A_1 \le H A 1 ≤ H .
A candidate encoding has O ( r b ) O(r\mathfrak{b}) O ( r b ) bits, so the code-space size fixed in NextGuess satisfies
Q r = 2 O ( r b ) . Q_r = 2^{O(r\mathfrak{b})}. Q r = 2 O ( r b ) .
A checkpoint also has O ( r b ) O(r\mathfrak{b}) O ( r b ) bits. Let N r N_r N r denote the number of possible checkpoints at a fixed stage; then N r = 2 O ( r b ) N_r = 2^{O(r\mathfrak{b})} N r = 2 O ( r b ) as well.
We derive the recurrence for A r A_r A r by induction, with A 1 ≤ H A_1 \le H A 1 ≤ H as the base case. Assume A r − 1 < ∞ A_{r-1} < \infty A r − 1 < ∞ . Fix a stage j j j and a reachable checkpoint D D D . By the calculation in the proof of Theorem 3.12, one trial succeeds with probability q D / Q r q_D/Q_r q D / Q r . Its expected cost is at most A r − 1 + H A_{r-1} + H A r − 1 + H . To bound the total cost, index the trials by h ≥ 1 h \ge1 h ≥ 1 . Trial h h h is reached with probability ( 1 − q D / Q r ) h − 1 (1-q_D/Q_r)^{h-1} ( 1 − q D / Q r ) h − 1 . Its fresh coins are independent of the preceding trials, so its expected cost, conditioned on being reached, is at most A r − 1 + H A_{r-1} + H A r − 1 + H . Summing over h h h gives expected cost at most
Q r q D ( A r − 1 + H ) . \frac{Q_r}{q_D}(A_{r-1}+H). q D Q r ( A r − 1 + H ) .
at D D D . The probability that stage j j j reaches D D D is Pr [ U J ∈ A j , D ] \Pr[U_J \in A_{j,D}] Pr [ U J ∈ A j , D ] . By Theorem 3.9 , this probability is at most q D q_D q D . Hence the expected cost of stage j j j , averaged over its possible checkpoints, is at most
∑ D : Pr [ U J ∈ A j , D ] > 0 Pr [ U J ∈ A j , D ] Q r q D ( A r − 1 + H ) ≤ N r Q r ( A r − 1 + H ) . \sum_{D:\Pr[U_J\in A_{j,D}]>0}
\Pr[U_J \in A_{j,D}] \frac{Q_r}{q_D}(A_{r-1}+H)
\le N_rQ_r(A_{r-1}+H). D : P r [ U J ∈ A j , D ] > 0 ∑ Pr [ U J ∈ A j , D ] q D Q r ( A r − 1 + H ) ≤ N r Q r ( A r − 1 + H ) .
There are at most T + 1 T + 1 T + 1 stages in one call. Therefore, for an absolute constant C C C ,
A r ≤ C ( T + 1 ) N r Q r ( A r − 1 + H ) . A_r \le C(T+1)N_rQ_r(A_{r-1}+H). A r ≤ C ( T + 1 ) N r Q r ( A r − 1 + H ) .
Since N r Q r = 2 O ( r b ) N_rQ_r = 2^{O(r\mathfrak{b})} N r Q r = 2 O ( r b ) and log ( T + 1 ) = O ( b ) \log(T+1) = O(\mathfrak{b}) log ( T + 1 ) = O ( b ) , iterating this recurrence from A 1 ≤ H A_1 \le H A 1 ≤ H gives
log ( A k + H ) ≤ O ( k b ) + ∑ r = 2 k O ( r b ) = O ( k 2 b ) . \log(A_k+H) \le O(k\mathfrak{b}) + \sum_{r=2}^{k} O(r\mathfrak{b}) = O(k^2\mathfrak{b}). log ( A k + H ) ≤ O ( k b ) + r = 2 ∑ k O ( r b ) = O ( k 2 b ) .
Taking r = k r = k r = k and the initial constraint C 0 C_0 C 0 gives the claimed expected-time bound. Together with the space bound above, this proves the lemma. □
We finally truncate the running time of the ideal sampler to obtain a worst-case-time simulation and prove Theorem 1.3 .
Proof of Theorem 1.3 . Fix an input x x x of length n n n , and let M M M be a locally read-k k k machine running in time T T T and space S S S . Let C 0 C_0 C 0 be the initial constraint from Theorem 3.6, and let U J 0 U_{J_0} U J 0 be uniform on { 0 , 1 } ℓ 0 \{0,1\}^{\ell_0} { 0 , 1 } ℓ 0 . By Theorem 3.6, Exec k ( C 0 , U J 0 ) \operatorname{Exec}_k(C_0,U_{J_0}) Exec k ( C 0 , U J 0 ) returns a HALT report whose configuration contains the output of M M M on the same random tape. Furthermore, by Theorem 3.12,
L ( Sampler k ( C 0 ) ) = L ( Exec k ( C 0 , U J 0 ) ) . \mathcal{L}(\operatorname{Sampler}_k(C_0)) = \mathcal{L}(\operatorname{Exec}_k(C_0,U_{J_0})). L ( Sampler k ( C 0 )) = L ( Exec k ( C 0 , U J 0 )) .
Thus, returning the output recorded in the ideal sampler’s halting configuration gives exactly the output distribution of M M M , using only fresh random bits.
By Theorem 3.13, choose a sufficiently large constant C 3 C_3 C 3 so that A : = 2 C 3 k 2 b A := 2^{C_3 k^2 b} A := 2 C 3 k 2 b bounds the expected running time of the ideal sampler, and put E : = ⌈ log 2 ( 1 / ε ) ⌉ E := \lceil\log_2(1/\varepsilon) \rceil E := ⌈ log 2 ( 1/ ε )⌉ .
Define M ′ M' M ′ by running the ideal sampler for at most A 2 E A2^E A 2 E steps. If it returns in time, output the value recorded in its halting configuration; otherwise, output a fixed value. Markov’s inequality gives
Pr [ M ′ times out ] ≤ A A 2 E ≤ ε . \Pr[M' \text{ times out}] \le\frac{A}{A2^E} \le\varepsilon. Pr [ M ′ times out ] ≤ A 2 E A ≤ ε .
Couple M ′ M' M ′ and the ideal sampler using the same fresh random bits. Their outputs agree unless M ′ M' M ′ times out, so their output distributions have total variation distance at most ε \varepsilon ε . Since the ideal sampler has the same output distribution as M M M , the same bound holds between the output distributions of M ′ M' M ′ and M M M .
By Theorem 3.13, the ideal sampler uses O ( k 2 b ) O(k^2b) O ( k 2 b ) space. A counter for the time limit uses
O ( log ( A 2 E ) ) = O ( k 2 b + E ) O(\log(A2^E)) = O(k^2b + E) O ( log ( A 2 E )) = O ( k 2 b + E )
additional bits and can be maintained in amortized constant time per simulated step. Since 2 E ≤ 2 / ε 2^E \le2/\varepsilon 2 E ≤ 2/ ε , the worst-case running time of M ′ M' M ′ is
O ( A 2 E ) = 1 ε ⋅ 2 O ( k 2 b ) . O(A2^E) = \frac{1}{\varepsilon} \cdot2^{O(k^2b)}. O ( A 2 E ) = ε 1 ⋅ 2 O ( k 2 b ) .
Substituting b = O ( S + log ( n + T + 2 ) ) b = O(S + \log(n + T + 2)) b = O ( S + log ( n + T + 2 )) and E = O ( log ( 1 / ε ) ) E = O(\log(1/\varepsilon)) E = O ( log ( 1/ ε )) gives space
O ( k 2 ( S + log ( n + T + 2 ) ) + log ( 1 / ε ) ) O(k^2(S + \log(n + T + 2)) + \log(1/\varepsilon)) O ( k 2 ( S + log ( n + T + 2 )) + log ( 1/ ε ))
and worst-case time
1 ε ⋅ 2 O ( k 2 ( S + log ( n + T + 2 ) ) ) . \frac{1}{\varepsilon} \cdot2^{O(k^2(S+\log(n+T+2)))}. ε 1 ⋅ 2 O ( k 2 ( S + l o g ( n + T + 2 ))) .
These bounds prove the theorem.
To deduce Theorem 1.4, we must verify that the time bound T ( n ) = 2 O ( S ( n ) ) T(n) = 2^{O(S(n))} T ( n ) = 2 O ( S ( n )) can be initialized within the claimed resources, since logspace constructibility of S S S does not necessarily imply logspace constructibility of T T T .
Proof of Theorem 1.4. For the read-once class BPSPACE ( S ) \operatorname{BPSPACE}(S) BPSPACE ( S ) , we use the same 2 O ( S ) 2^{O(S)} 2 O ( S ) time convention as in the definition of LocalRead k -BPSPACE ( S ) \operatorname{LocalRead}_k\text{-BPSPACE}(S) LocalRead k -BPSPACE ( S ) . Fix a constant k ≥ 1 k \ge1 k ≥ 1 and a logspace constructible function S ( n ) ≥ log n S(n) \ge\log n S ( n ) ≥ log n . The inclusion BPSPACE ( S ) ⊆ LocalRead k -BPSPACE ( S ) \operatorname{BPSPACE}(S) \subseteq\operatorname{LocalRead}_k\text{-BPSPACE}(S) BPSPACE ( S ) ⊆ LocalRead k -BPSPACE ( S ) follows because a read-once random tape is locally read-1.
For the reverse inclusion, let M M M witness membership in LocalRead k -BPSPACE ( S ) \operatorname{LocalRead}_k\text{-BPSPACE}(S) LocalRead k -BPSPACE ( S ) . Choose a constant integer c ≥ 1 c \ge1 c ≥ 1 such that T ( n ) : = 2 c S ( n ) T(n) := 2^{cS(n)} T ( n ) := 2 c S ( n ) bounds its running time. Apply the construction in the proof of Theorem 1.3 with this time bound and ε = 1 / 12 \varepsilon= 1/12 ε = 1/12 . For this choice of T T T , the required parameter initialization can be performed in O ( S ( n ) ) O(S(n)) O ( S ( n )) space and 2 O ( S ( n ) ) 2^{O(S(n))} 2 O ( S ( n )) time: compute S ( n ) S(n) S ( n ) using its logspace construction, form the binary representation of T ( n ) T(n) T ( n ) , which has c S ( n ) + 1 cS(n) + 1 c S ( n ) + 1 bits, and initialize the simulation’s clocks. The same bounds accommodate the parameter computations, since S ( n ) ≥ log n S(n) \ge\log n S ( n ) ≥ log n . Thus the construction is uniform within the claimed resources, without requiring a logspace construction of T ( n ) T(n) T ( n ) .
Since k k k is constant and log ( n + T ( n ) + 2 ) = O ( S ( n ) ) \log(n + T(n) + 2) = O(S(n)) log ( n + T ( n ) + 2 ) = O ( S ( n )) , the resulting read-once machine uses O ( S ( n ) ) O(S(n)) O ( S ( n )) space and 2 O ( S ( n ) ) 2^{O(S(n))} 2 O ( S ( n )) time. Its acceptance probability is at least 7 / 12 7/12 7/12 on yes-instances and at most 5 / 12 5/12 5/12 on no-instances. A constant number of independent repetitions followed by a majority vote reduces the error to at most 1 / 3 1/3 1/3 , preserving both resource bounds. This proves the reverse inclusion and hence the equality. Taking S ( n ) = Θ ( log n ) S(n) = \Theta(\log n) S ( n ) = Θ ( log n ) gives LocalRead k -BPL = BPL \operatorname{LocalRead}_k\text{-BPL} = \text{BPL} LocalRead k -BPL = BPL .
Statement of AI use
We formulated the research topics and questions of this work. We used ChatGPT (GPT-6 Astra) to assist with proof development and proof checking, making substantial use of the tool for both tasks. The tool materially affected the proofs throughout all technical sections of the paper. The manuscript was written by the authors with assistance from the same tool. The authors take full responsibility for the correctness of the work.