OctoInformBeta

OpenAI preprint, September 2026 · Lean results with no numbered counterpart

Two interleaved trials: One copy on the even coins, one on the odd; time doubles, space at most adds, and acceptance probability pp becomes 1−(1−p)21-(1-p)^2

Two interleaved trials square a halting machine’s rejection probability.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a randomized machine MM that halts within tt steps on an input xx, whatever its coins, and accepts xx with probability pp. Error reduction for one-sided error runs MM a second time on fresh coins and accepts when either trial accepts. In small space the two trials run side by side on separate tapes, and the single stream of coins, one bit per step, has to be shared out between them. The question is how to build the pair as one machine, and what it costs in time and space and gains in acceptance probability.

Machines, Runs and Coins

An input is a binary word x∈{0,1}*x \in \{0,1\}^* of length nn. An input symbol is the left endmarker, a bit, or the right endmarker, and the input tape of xx has n+2n+2 cells.✦

A randomized machine MM with states SS, work tapes indexed by WW and input heads indexed by HH consists of a start state s0∈Ss_0 \in S, a set of halting states, each accepting or rejecting, and a transition function; each work tape has one head, and each input head reads the input tape.✦ An action of MM is a next state together with a bit to write on each work tape and a direction (left, stay or right) for each work head and each input head.✦ The transition function maps a state, the input symbols under the input heads, the bits under the work heads and a coin bit to an action.

A configuration of MM on inputs of length nn consists of a state, one of the n+2n+2 input cells for each input head, an integer position for each work head, and the contents of each work tape, a bit at every integer cell.✦

A coin tape is an infinite sequence ω∈{0,1}ℕ\omega \in \{0,1\}^{\mathbb{N}} of coin bits, one for each time step.✦ The initial configuration of MM on xx is the configuration in the start state s0s_0 with each input head on the left endmarker, each work head at position 00 and every work cell holding 00. The run of MM on xx with coin tape ω\omega is the sequence of configurations CtM(x,ω)C^M_t(x,\omega), t≥0t \ge 0, that starts at the initial configuration and passes from CtM(x,ω)C^M_t(x,\omega) to Ct+1M(x,ω)C^M_{t+1}(x,\omega) by one step of MM with coin ω(t)\omega(t).✦ The machine MM halts on xx within tt steps if CtM(x,ω)C^M_t(x,\omega) is in a halting state for every coin tape ω\omega; Haltt(M)\mathrm{Halt}_t(M) is the set of such inputs.✦

For a bit string β∈{0,1}t\beta \in \{0,1\}^t, the coin tape βˆ\hat\beta of β\beta has coin β(u)\beta(u) at each time u<tu < t and coin 00 from time tt on.✦ The acceptance probability of MM on xx at time tt is the fraction of the strings β\beta whose run is in an accepting state after tt steps: ptM(x)=2−t|{β∈{0,1}t:CtM(x,βˆ) is in an accepting state}|.p^M_t(x) = 2^{-t}\,\bigl|\{\beta \in \{0,1\}^t : C^M_t(x,\hat\beta) \text{ is in an accepting state}\}\bigr|.(1)✦

When MM has finitely many work tapes, the space it uses on xx with coin tape ω\omega through time tt counts, for each work tape, the cells its head visits up to time tt: space⁡tM(x,ω)=∑k∈W|{hk(CuM(x,ω)):0≤u≤t}|,\operatorname{space}^M_t(x,\omega) = \sum_{k \in W} \bigl|\{h_k(C^M_u(x,\omega)) : 0 \le u \le t\}\bigr|,(2)✦ where hk(C)h_k(C) is the position of the head of work tape kk in the configuration CC.

The Doubled Machine

The doubled machine M(2)M^{(2)} runs two copies of MM on one coin tape. Its states are triples (s1,s2,r)(s_1, s_2, r) of two states of MM and a coin register r∈{⊥,0,1}r \in \{\bot, 0, 1\}, empty or holding one bit; its work tapes and input heads are two disjoint copies of those of MM, the first driven by s1s_1 and the second by s2s_2. It starts in (s0,s0,⊥)(s_0, s_0, \bot). A state (s1,s2,r)(s_1, s_2, r) is halting when r=⊥r = \bot and both s1s_1 and s2s_2 are halting, and it is accepting when moreover s1s_1 or s2s_2 is accepting.

The transitions of M(2)M^{(2)} are built from two actions of MM. At a state ss, the idle action keeps ss, writes back the bits under the work heads and moves no head✦; the stuttering step at ss is the step of MM when ss is not halting and the idle action when it is.✦ From a state (s1,s2,⊥)(s_1, s_2, \bot) with coin bb, M(2)M^{(2)} stores the coin: it passes to (s1,s2,b)(s_1, s_2, b) by an idle action. From (s1,s2,b)(s_1, s_2, b) with coin b′b', it takes the combined action of the first copy’s stuttering step from s1s_1 with coin bb and the second copy’s from s2s_2 with coin b′b': each copy writes and moves its own tapes and heads, and the register empties.

The even and odd coin tapes of a coin tape ω\omega are ωev(u)=ω(2u),ωod(u)=ω(2u+1)(u≥0).\omega^{\mathrm{ev}}(u) = \omega(2u), \qquad \omega^{\mathrm{od}}(u) = \omega(2u+1) \qquad (u \ge 0).(3)

For configurations CC and DD of MM on inputs of length nn and a register value rr, the joined configuration ⟨C,D⟩r\langle C, D\rangle_r is the configuration of M(2)M^{(2)} in the state (qC,qD,r)(q_C, q_D, r), with qCq_C and qDq_D the states of CC and DD, whose first copy of heads and tapes is as in CC and whose second copy is as in DD.✦

The Claim

Theorem 1. Let MM be a randomized machine, xx a binary word and t≥0t \ge 0. For every coin tape ω\omega, C2tM(2)(x,ω)=⟨CtM(x,ωev),CtM(x,ωod)⟩⊥,C^{M^{(2)}}_{2t}(x,\omega) = \bigl\langle C^M_t(x,\omega^{\mathrm{ev}}),\, C^M_t(x,\omega^{\mathrm{od}}) \bigr\rangle_{\bot},(4)✦ and, if MM has finitely many work tapes, space⁡tM(2)(x,ω)≤space⁡⌊t/2⌋M(x,ωev)+space⁡⌊t/2⌋M(x,ωod).\operatorname{space}^{M^{(2)}}_t(x,\omega) \le \operatorname{space}^M_{\lfloor t/2\rfloor}(x,\omega^{\mathrm{ev}}) + \operatorname{space}^M_{\lfloor t/2\rfloor}(x,\omega^{\mathrm{od}}).(5)✦ If MM halts on xx within tt steps, then x∈Halt2t(M(2))x \in \mathrm{Halt}_{2t}\bigl(M^{(2)}\bigr)(6)✦ and p2tM(2)(x)=1−(1−ptM(x))2.p^{M^{(2)}}_{2t}(x) = 1 - \bigl(1 - p^M_t(x)\bigr)^2.(7)✦

What Is Checked

The claim is stated over randomized machines with input heads on an endmarked input tape and binary work tapes infinite in both directions, their configurations and runs on a coin tape, halting within tt steps, the acceptance probability (1), the space (2), and the doubled machine M(2)M^{(2)} with the even and odd coin tapes (3) and the joined configuration.