OctoInform Beta

OpenAI preprint, September 2026 · §4. Recursive procedures and unconditional termination · §4

§4 (setting): Procedure 4.1 [Repeated comparison] and Procedure 4.2 [Repeated orientation]: The two procedures as steps of a machine with a call stack; their raw median and majority represent the median and the combined orientation

Ask takes a median of JJ trials, OrientPlus a majority.

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

A solver input (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m) consists of a box I=(a,b;B)I=(a,b;B), with corners a≤ba\le b in ℤV\mathbb{Z}^V for the vertex set VV of the game, n=|V|n=|V|, and reference width B≥b−aB\ge b-a, and of budgets P=(α,β,k,m)P=(\alpha,\beta,k,m): positive rational support weights α,β\alpha,\beta and budgets k,mk,m. On such an input the randomized subroutine Solve returns a vector of II, and the randomized subroutine Orient returns an orientation OO for PP, which chooses YY or ZZ and carries a list E(O)E(O) of exceptional sets. Procedure 4.1 (Repeated comparison), called Ask, and Procedure 4.2 (Repeated orientation), called OrientPlus, amplify the two subroutines by repetition: each runs its subroutine for JJ trials, JJ the global trial parameter, and combines the JJ answers into one.

The library writes both as recursive procedures on raw data, that is, on data encoded as bit strings and unary counters, executed step by step by a machine with an explicit call stack, and states each step together with what the combined raw answer represents.

Raw Data, Medians and Majorities

Raw data are written in bits: a count as a unary counter, a counter of length tt standing for tt, an integer as a binary word, and a vector of ℤV\mathbb{Z}^V as a raw vector, the list of the words of its nn coordinates. We write yˆ⊳y\hat y\triangleright y when the raw datum yˆ\hat y represents the object yy. A raw solver input x=(Iˆ;Pˆ)x=(\hat I;\hat P) is a raw box Iˆ\hat I, whose parts include a raw lower corner aˆ\hat a with nn entries, together with raw budgets Pˆ\hat P. Lists are written [y1,…,yj][y_1,\dots,y_j], with [][\,] the empty list, y⋅Ly\cdot L the list LL with yy put in front, and L1L2⋯LjL_1L_2\cdots L_j the concatenation of L1,…,LjL_1,\dots,L_j in this order. A list of raw data represents a list of objects when the two lists have the same length and each entry represents the entry in the same place.

A raw orientation is a pair (c,M)(c,M) of a bit cc and a list MM of bit masks, each a bit string standing for one exceptional set.✦ A raw orientation (c,M)(c,M) represents an orientation OO for PP when cc is true exactly when OO chooses YY and M⊳E(O)M\triangleright E(O), the iith mask representing the iith exceptional set.✦

The raw median med⁡Iˆ(Q)\operatorname{med}_{\hat I}(Q) of a list Q=[qˆ1,…,qˆj]Q=[\hat q_1,\dots,\hat q_j] of raw vectors, with respect to a raw box Iˆ\hat I with lower corner aˆ\hat a, is aˆ\hat a when the list is empty, and otherwise the raw vector whose uuth entry is the median of the uuth entries qˆ1(u),…,qˆj(u)\hat q_1(u),\dots,\hat q_j(u), where the median of j≥1j\ge1 numbers is the entry in place ⌊j/2⌋\lfloor j/2\rfloor, counting from 00, of their list sorted in increasing order: med⁡Iˆ(Q)={aˆ,j=0,(median⁡(qˆ1(u),…,qˆj(u)))u=0,…,n−1,j≥1.\operatorname{med}_{\hat I}(Q)= \begin{cases} \hat a, & j=0,\\ \bigl(\operatorname{median}(\hat q_1(u),\dots,\hat q_j(u))\bigr)_{u=0,\dots,n-1}, & j\ge 1. \end{cases}(1) For vectors q1,…,qjq_1,\dots,q_j of a box I=(a,b;B)I=(a,b;B), their median Med⁡I(q1,…,qj)\operatorname{Med}_I(q_1,\dots,q_j) is the lower corner aa when j=0j=0, and otherwise the coordinatewise median, the vector whose uuth coordinate is the median of q1(u),…,qj(u)q_1(u),\dots,q_j(u); it is again a vector of II.

The raw majority maj⁡(R)\operatorname{maj}(R) of a list R=[(c1,M1),…,(cj,Mj)]R=[(c_1,M_1),\dots,(c_j,M_j)] of raw orientations is the raw orientation whose bit is true exactly when more than half of the bits cℓc_\ell are true, and whose masks are those of all entries, concatenated in order: maj⁡(R)=(c,M1M2⋯Mj),ctrue⇔2|{ℓ≤j:cℓtrue}|>j.\operatorname{maj}(R)=(c,\;M_1M_2\cdots M_j),\qquad c\ \text{true}\iff 2\,\bigl|\{\ell\le j : c_\ell\ \text{true}\}\bigr|>j.(2)✦ For orientations O1,…,OjO_1,\dots,O_j for PP, their combined orientation Maj⁡(O1,…,Oj)\operatorname{Maj}(O_1,\dots,O_j) is the orientation for PP that chooses YY exactly when 2|{ℓ≤j:OℓchoosesY}|>j2\,|\{\ell\le j : O_\ell\ \text{chooses}\ Y\}|>j, and whose list of exceptional sets is E(O1)E(O2)⋯E(Oj)E(O_1)E(O_2)\cdots E(O_j), the lists of all the OℓO_\ell concatenated in order.

The Machine

A frame of the machine is a record of registers: a raw solver input xx, a unary counter tt, two raw vectors, a list QQ of raw vectors, a raw orientation and a list RR of raw orientations; a register that a step does not set is empty.✦ A state ⟨F∣S⟩\langle F\mid S\rangle of the machine is a current frame FF above a stack SS of suspended frames, a list with its top first, so that G⋅SG\cdot S is SS with the frame GG pushed on top.✦ Every frame carries a label. The current frame is either labelled with the procedure it runs on its registers, written as that procedure applied to them, or is returning a value vv in a register, written 𝗋𝖾𝗍v\mathsf{ret}\,v; a suspended frame is labelled with the step that resumes it.

A step maps a state, read together with the environment, to the next state; we write s→s′s\longrightarrow s' when the step takes the state ss to the state s′s'. The environment is the arena of the game written as raw data, with four unary counters, the trial count JJ among them.✦ The label of the current frame chooses the step, and when that frame is returning, the label of the frame on top of the stack does.

The Claim

Definition 1 (Procedures 4.1 and 4.2). Let x=(Iˆ;Pˆ)x=(\hat I;\hat P) be a raw solver input, tt a unary counter and SS a stack. The procedure Ask on xx runs a procedure 𝖳𝗋𝗂𝖺𝗅𝗌\mathsf{Trials} on xx with counter JJ, below a frame 𝖬𝖾𝖽𝗂𝖺𝗇(x)\mathsf{Median}(x) that waits for its result: ⟨𝖠𝗌𝗄(x)∣S⟩→⟨𝖳𝗋𝗂𝖺𝗅𝗌(x,J)∣𝖬𝖾𝖽𝗂𝖺𝗇(x)⋅S⟩.\langle\mathsf{Ask}(x)\mid S\rangle\;\longrightarrow\; \langle\mathsf{Trials}(x,J)\mid\mathsf{Median}(x)\cdot S\rangle.(3)✦ The procedure 𝖳𝗋𝗂𝖺𝗅𝗌\mathsf{Trials} returns the empty list when t=0t=0, and otherwise runs Solve on xx below a frame 𝖧𝖾𝖺𝖽\mathsf{Head} that keeps the remaining count: ⟨𝖳𝗋𝗂𝖺𝗅𝗌(x,t)∣S⟩→{⟨𝗋𝖾𝗍[]∣S⟩,t=0,⟨𝖲𝗈𝗅𝗏𝖾(x)∣𝖧𝖾𝖺𝖽(x,t−1)⋅S⟩,t≥1.\langle\mathsf{Trials}(x,t)\mid S\rangle\;\longrightarrow\; \begin{cases} \langle\mathsf{ret}\,[\,]\mid S\rangle, & t=0,\\ \langle\mathsf{Solve}(x)\mid\mathsf{Head}(x,t-1)\cdot S\rangle, & t\ge 1. \end{cases}(4)✦ A raw vector qˆ\hat q returned to 𝖧𝖾𝖺𝖽(x,t)\mathsf{Head}(x,t) is kept in a frame 𝖯𝗋𝖾𝗉𝖾𝗇𝖽\mathsf{Prepend} while the remaining tt trials run, ⟨𝗋𝖾𝗍qˆ∣𝖧𝖾𝖺𝖽(x,t)⋅S⟩→⟨𝖳𝗋𝗂𝖺𝗅𝗌(x,t)∣𝖯𝗋𝖾𝗉𝖾𝗇𝖽(qˆ)⋅S⟩,\langle\mathsf{ret}\,\hat q\mid\mathsf{Head}(x,t)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{Trials}(x,t)\mid\mathsf{Prepend}(\hat q)\cdot S\rangle,(5)✦ and is put in front of their list QQ when it returns: ⟨𝗋𝖾𝗍Q∣𝖯𝗋𝖾𝗉𝖾𝗇𝖽(qˆ)⋅S⟩→⟨𝗋𝖾𝗍qˆ⋅Q∣S⟩.\langle\mathsf{ret}\,Q\mid\mathsf{Prepend}(\hat q)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{ret}\,\hat q\cdot Q\mid S\rangle.(6)✦ A list QQ returned to 𝖬𝖾𝖽𝗂𝖺𝗇(x)\mathsf{Median}(x) is replaced by its raw median (1) with respect to Iˆ\hat I: ⟨𝗋𝖾𝗍Q∣𝖬𝖾𝖽𝗂𝖺𝗇(x)⋅S⟩→⟨𝗋𝖾𝗍med⁡Iˆ(Q)∣S⟩.\langle\mathsf{ret}\,Q\mid\mathsf{Median}(x)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{ret}\,\operatorname{med}_{\hat I}(Q)\mid S\rangle.(7)✦ If Iˆ⊳I\hat I\triangleright I for a box II of reference width BB in dimension nn, and Q⊳[q1,…,qj]Q\triangleright[q_1,\dots,q_j] for vectors q1,…,qjq_1,\dots,q_j of II, then med⁡Iˆ(Q)⊳Med⁡I(q1,…,qj).\operatorname{med}_{\hat I}(Q)\triangleright\operatorname{Med}_I(q_1,\dots,q_j).(8)✦

The procedure OrientPlus follows the same scheme, with a procedure 𝖮𝖳𝗋𝗂𝖺𝗅𝗌\mathsf{OTrials} and frames 𝖮𝖧𝖾𝖺𝖽\mathsf{OHead}, 𝖮𝖯𝗋𝖾𝗉𝖾𝗇𝖽\mathsf{OPrepend} and 𝖢𝗈𝗆𝖻𝗂𝗇𝖾\mathsf{Combine}, running Orient in place of Solve and collecting raw orientations oˆ\hat o in a list RR, which it replaces by its raw majority (2): ⟨𝖮𝗋𝗂𝖾𝗇𝗍𝖯𝗅𝗎𝗌(x)∣S⟩→⟨𝖮𝖳𝗋𝗂𝖺𝗅𝗌(x,J)∣𝖢𝗈𝗆𝖻𝗂𝗇𝖾(x)⋅S⟩,\langle\mathsf{OrientPlus}(x)\mid S\rangle\;\longrightarrow\; \langle\mathsf{OTrials}(x,J)\mid\mathsf{Combine}(x)\cdot S\rangle,(9)✦ ⟨𝖮𝖳𝗋𝗂𝖺𝗅𝗌(x,t)∣S⟩→{⟨𝗋𝖾𝗍[]∣S⟩,t=0,⟨𝖮𝗋𝗂𝖾𝗇𝗍(x)∣𝖮𝖧𝖾𝖺𝖽(x,t−1)⋅S⟩,t≥1,\langle\mathsf{OTrials}(x,t)\mid S\rangle\;\longrightarrow\; \begin{cases} \langle\mathsf{ret}\,[\,]\mid S\rangle, & t=0,\\ \langle\mathsf{Orient}(x)\mid\mathsf{OHead}(x,t-1)\cdot S\rangle, & t\ge 1, \end{cases}(10)✦ ⟨𝗋𝖾𝗍oˆ∣𝖮𝖧𝖾𝖺𝖽(x,t)⋅S⟩→⟨𝖮𝖳𝗋𝗂𝖺𝗅𝗌(x,t)∣𝖮𝖯𝗋𝖾𝗉𝖾𝗇𝖽(oˆ)⋅S⟩,\langle\mathsf{ret}\,\hat o\mid\mathsf{OHead}(x,t)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{OTrials}(x,t)\mid\mathsf{OPrepend}(\hat o)\cdot S\rangle,(11)✦ ⟨𝗋𝖾𝗍R∣𝖮𝖯𝗋𝖾𝗉𝖾𝗇𝖽(oˆ)⋅S⟩→⟨𝗋𝖾𝗍oˆ⋅R∣S⟩,\langle\mathsf{ret}\,R\mid\mathsf{OPrepend}(\hat o)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{ret}\,\hat o\cdot R\mid S\rangle,(12)✦ ⟨𝗋𝖾𝗍R∣𝖢𝗈𝗆𝖻𝗂𝗇𝖾(x)⋅S⟩→⟨𝗋𝖾𝗍maj⁡(R)∣S⟩.\langle\mathsf{ret}\,R\mid\mathsf{Combine}(x)\cdot S\rangle\;\longrightarrow\; \langle\mathsf{ret}\,\operatorname{maj}(R)\mid S\rangle.(13)✦ If R=[(c1,M1),…,(cj,Mj)]R=[(c_1,M_1),\dots,(c_j,M_j)] represents a list [O1,…,Oj][O_1,\dots,O_j] of orientations for budgets PP, then maj⁡(R)⊳Maj⁡(O1,…,Oj),\operatorname{maj}(R)\triangleright\operatorname{Maj}(O_1,\dots,O_j),(14)✦ |{ℓ≤j:cℓtrue}|=|{ℓ≤j:OℓchoosesY}|,\bigl|\{\ell\le j : c_\ell\ \text{true}\}\bigr| =\bigl|\{\ell\le j : O_\ell\ \text{chooses}\ Y\}\bigr|,(15)✦ and M1M2⋯Mj⊳E(O1)E(O2)⋯E(Oj).M_1M_2\cdots M_j\triangleright E(O_1)E(O_2)\cdots E(O_j).(16)✦

In the paper, the result reads: for its given solver input, Ask runs JJ independent copies of Solve and returns their coordinatewise median, and for its given orientation input, OrientPlus runs JJ independent copies of Orient and returns the majority choice in {Y,Z}\{Y,Z\} together with the concatenation of all exceptional-set lists in trial order, retaining minority-trial lists and duplicate entries.

What Is Checked

The steps (3) to (7) and (9) to (13) are stated over states of the machine, with frames holding a raw solver input, a unary counter and raw vectors or raw orientations, and with JJ read from the environment; (8) and (14) to (16) are stated over a box II of reference width BB in dimension nn with a list of its vectors, and over budgets PP with a list of orientations for PP, all given with raw data that represent them.