OctoInform Beta

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

§4 (setting): the mutual recursion and its fresh bits: Ten jobs over a stack of frames, one random index per step, and a raw step on packed records that represents it

Solve, Ask, Orient and OrientPlus as one stack machine.

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

Let GG be a mean-payoff game on a set VV of nn vertices with integer edge weights w(e)w(e), transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1 and weight bound W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\}, and let B*=8nWB_*=8nW be the top width of (2.1). The randomized solver is built from four procedures, Solve, Ask, Orient and OrientPlus, which call one another on solver inputs (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m), made of a box with corners aa and bb in ℤV\mathbb{Z}^V, a reference width BB, support weights α,β\alpha,\beta and budgets k,mk,m. Two global parameters of (4.1) enter here, ss and JJ; ss is a power of two, so log⁡2s\log_2 s fair bits give a uniform index in {0,…,s−1}\{0,\dots,s-1\}.

The library runs the four procedures as one stack machine. Its states are calls of ten jobs, the four procedures and six auxiliary jobs, and returns of values to a stack of frames, and each step takes a random index jj below ss as an argument. A raw machine performs the same step on bit strings and unary counters packed into records.

The Stack Machine

A stack κ\kappa is a finite sequence of frames, with ε\varepsilon the empty stack and f⋅κf\cdot\kappa the stack with the frame ff on top; a frame holds what a job needs to continue once a subcall returns. A state of the machine is either a call state 𝖼𝖺𝗅𝗅(ι,κ)\mathsf{call}(\iota,\kappa), a job ι\iota to run above the stack κ\kappa, or a return state 𝗋𝖾𝗍(κ,v)\mathsf{ret}(\kappa,v), a value vv handed back to κ\kappa. For an index jj, the step Stepj\mathrm{Step}_j is the map on states that fixes every final state 𝗋𝖾𝗍(ε,v)\mathsf{ret}(\varepsilon,v), hands a returned value vv to the frame ff on top by the resumption Resumej(f,v,κ)\mathrm{Resume}_j(f,v,\kappa) described below, Stepj(𝗋𝖾𝗍(f⋅κ,v))=Resumej(f,v,κ),\mathrm{Step}_j(\mathsf{ret}(f\cdot\kappa,v))=\mathrm{Resume}_j(f,v,\kappa),(1)✦ and takes a call state either to a return of the job’s value to κ\kappa or to a call of a subjob above f⋅κf\cdot\kappa for a new frame ff. The resumption Resumej(f,v,κ)\mathrm{Resume}_j(f,v,\kappa) is likewise a return to κ\kappa or a call above κ\kappa with one or two new frames, computed from vv and the data in ff.✦ Frames come in 2222 kinds.

The jobs act on a box II with corners a≤ba\le b and on budgets PP; an orientation is a side, YY or ZZ, with a list of exception sets of vertices. Solve(P,I)(P,I) returns the small vector of II for PP when the parameter R=km∑i∈V1/(αiβi)R=k\,m\sum_{i\in V}1/(\alpha_i\beta_i) of P=(α,β,k,m)P=(\alpha,\beta,k,m) is below one, and the exact vector computed by the basic solver, the base procedure with step allowance 128ns128ns, when II has width at most 128s128s. Otherwise it calls Tighten on II, OrientPlus on the tightened box I′I', Reweight on I′I' with the side and the exception sets of the orientation found (all three are described below), and Solve on I′I' capped on that side; it returns the coordinatewise minimum, for side YY, or maximum, for side ZZ, of the last answer and the reweighted ones. Ask(P,I)(P,I) returns the coordinatewise median of the answers of JJ trials of Solve(P,I)(P,I).

Each box II carries a grid width δ\delta, and the cap width of II is the width of II minus δ\delta.

Update(P,I,q)(P,I,q) moves a center qq, a point of II: it asks twice on a narrow box centered at qq, first with the budget kk reduced and then with mm reduced, and returns the average of the two answers clipped to II. Centers(P,I,t,q)(P,I,t,q) applies Update tt times from qq and returns the t+1t+1 centers it passes through. When II has width at most 128s128s, Orient(P,I)(P,I) returns the base orientation of II. Otherwise it computes the centers c0,…,csc_0,\dots,c_s from the midpoint of II and the sets HH and NN of positive and negative displacement of csc_s, and returns side YY with exception set V\HV\setminus H if μP(H)>12\mu_P(H)>\frac12, or else side ZZ with V\NV\setminus N if μP(N)>12\mu_P(N)>\frac12, where μP\mu_P is the measure the budgets put on vertex sets. Failing both, it calls Orient on a box centered at cjc_j and appends HH and NN to the exception sets of the answer; this is the one place where the step reads jj. OrientPlus(P,I)(P,I) returns side YY when more than half of JJ trials of Orient(P,I)(P,I) choose YY and side ZZ otherwise, with the exception sets of all trials.

The box centered at cjc_j on which Orient is called again has the width of II divided by 88.✦

Tighten(P,I)(P,I) asks on II with kk reduced. If the answer uu has ui−ai≥δu_i-a_i\ge\delta at some vertex ii, it calls Tighten on the box with corners uu and bb; otherwise it asks again with mm reduced and, if that answer uu has bi−ui≥δb_i-u_i\ge\delta at some ii, calls Tighten on the box with corners aa and uu, and else returns II. For exception sets H1,…,HrH_1,\dots,H_r, Reweight(P,I,Y,H1,…,Hr)(P,I,Y,H_1,\dots,H_r) asks on II once for each HiH_i with mm reweighted on HiH_i and returns the list of answers; with side ZZ it reweights kk instead. The remaining two jobs run a given number of trials of Solve and of Orient, counting down and collecting the answers.

The Raw Machine

Raw data are bit strings and unary counters, lists of units in which a counter of length ℓ\ell stands for ℓ\ell; |ρ||\rho| is the length of a counter ρ\rho. A pack zz is a record of eight raw registers: budgets 𝗉\mathsf{p}, a box 𝖻\mathsf{b}, a counter 𝗍\mathsf{t}, two vectors 𝗊\mathsf{q} and 𝗋\mathsf{r}, a list of vectors 𝗏𝗌\mathsf{vs}, an orientation 𝗈\mathsf{o} and a list of orientations 𝗈𝗌\mathsf{os}.✦ A raw orientation is a bit, true for YY, with a list of masks, one for each exception set.✦ A cell c=(τc,zc)c=(\tau_c,z_c) is a pack zcz_c with a tag τc\tau_c, a unary counter✦, and a raw state (c,γ)(c,\gamma) is a current cell cc above a raw stack γ\gamma, a list of cells.✦ The ten jobs carry the tags 00 to 99, in the order Solve, Ask, trials of Solve, Update, Centers, Orient, trials of Orient, OrientPlus, Tighten, Reweight; the current cell of a raw return carries the tag 1010; the 2222 kinds of frame carry the tags 00 to 2121.

A pack zz holds a job ι\iota when 𝗉\mathsf{p} and 𝖻\mathsf{b} of zz represent the budgets and the box of ι\iota and the other registers of zz represent its remaining data: the number of trials or of updates still to run as the length of 𝗍\mathsf{t}, the center in 𝗊\mathsf{q}, the side and the exception sets of Reweight in 𝗈\mathsf{o}.✦ A pack zz holds a value vv when the register of zz for the kind of vv represents it: a vector in 𝗊\mathsf{q}, a list of vectors in 𝗏𝗌\mathsf{vs}, an orientation in 𝗈\mathsf{o}, a list of orientations in 𝗈𝗌\mathsf{os}, a box in 𝖻\mathsf{b}.✦ A pack zz holds a frame ff when its registers represent the data that ff keeps.✦ A raw stack represents a stack frame by frame: the empty list represents ε\varepsilon, and d⋅γd\cdot\gamma represents f⋅κf\cdot\kappa when dd carries the tag of ff, zdz_d holds ff and γ\gamma represents κ\kappa.✦ A raw state (c,γ)(c,\gamma) represents a state σ\sigma, written σ∼(c,γ)\sigma\sim(c,\gamma), by two rules: 𝖼𝖺𝗅𝗅(ι,κ)∼(c,γ)when |τc|=tag(ι),zc holds ι and γ represents κ,𝗋𝖾𝗍(κ,v)∼(c,γ)when |τc|=10,zc holds v and γ represents κ.\begin{aligned} \mathsf{call}(\iota,\kappa)&\sim(c,\gamma)&&\text{when }|\tau_c|=\mathrm{tag}(\iota),\ z_c\text{ holds }\iota\text{ and }\gamma\text{ represents }\kappa,\\ \mathsf{ret}(\kappa,v)&\sim(c,\gamma)&&\text{when }|\tau_c|=10,\ z_c\text{ holds }v\text{ and }\gamma\text{ represents }\kappa. \end{aligned}(2)✦

The raw machine reads a raw state together with a random counter ρ\rho, a unary counter whose length |ρ||\rho| is the index jj of the step, and an environment η\eta, made of the arena of the game and four counters.✦ An environment η\eta represents the game GG when its arena is the code of the graph of GG with the transformed weights t(e)t(e) as binary words and its four counters have lengths log⁡2s\log_2 s, ss, JJ and at least 128ns128ns.✦ For each job ι\iota the raw machine has a code DιD_\iota✦, and for each kind of frame ff a code DfD_f, the two frames of Tighten that pass on a tightened box sharing one✦; each maps an environment, a random counter and a raw state to a raw state. The code of the frame where Orient compares μP(H)\mu_P(H) and μP(N)\mu_P(N) with 12\frac12 takes the center of index |ρ||\rho| from the list of centers in 𝗏𝗌\mathsf{vs}, and the midpoint of the box when there is none.

The Claim

Definition 1. Let η\eta be an environment, ρ\rho a random counter and (c,γ)(c,\gamma) a raw state. The resume code RR hands the raw state to the code of the frame named by the tag of the top cell of the stack: R(η,ρ,(c,γ))={Df(η,ρ,(c,γ))if γ=d⋅γ′ with |τd|=tag(f),(c,γ)if γ is empty, or γ=d⋅γ′ with |τd|≥22.R(\eta,\rho,(c,\gamma))= \begin{cases} D_f(\eta,\rho,(c,\gamma)) & \text{if }\gamma=d\cdot\gamma'\text{ with }|\tau_d|=\mathrm{tag}(f),\\ (c,\gamma) & \text{if }\gamma\text{ is empty, or }\gamma=d\cdot\gamma'\text{ with }|\tau_d|\ge 22. \end{cases}(3)✦ The raw step DD runs the code of the job named by the tag of the current cell: for a job ι\iota and |τc|=tag(ι)|\tau_c|=\mathrm{tag}(\iota), D(η,ρ,(c,γ))=Dι(η,ρ,(c,γ)).D(\eta,\rho,(c,\gamma))=D_\iota(\eta,\rho,(c,\gamma)).(4)✦ On a return, |τc|=10|\tau_c|=10, DD runs the code of the frame named by the tag of the top cell dd of the stack: for a frame ff with |τd|=tag(f)|\tau_d|=\mathrm{tag}(f), D(η,ρ,(c,d⋅γ))=Df(η,ρ,(c,d⋅γ)).D(\eta,\rho,(c,d\cdot\gamma))=D_f(\eta,\rho,(c,d\cdot\gamma)).(5)✦ On every other raw state, DD runs RR.✦

Theorem 1. Let η\eta be an environment that represents the game GG, let ρ\rho be a random counter, and let j=|ρ|j=|\rho|. If a raw state (c,γ)(c,\gamma) represents the call state 𝖼𝖺𝗅𝗅(ι,κ)\mathsf{call}(\iota,\kappa) in the sense of (2), then Stepj(𝖼𝖺𝗅𝗅(ι,κ))∼D(η,ρ,(c,γ)).\mathrm{Step}_j(\mathsf{call}(\iota,\kappa))\sim D(\eta,\rho,(c,\gamma)).(6)✦ If the pack of a cell dd holds a frame ff, the pack of a cell cc holds a value vv and a raw stack γ\gamma represents a stack κ\kappa, then Resumej(f,v,κ)∼Df(η,ρ,(c,d⋅γ)).\mathrm{Resume}_j(f,v,\kappa)\sim D_f(\eta,\rho,(c,d\cdot\gamma)).(7)✦ For every state σ\sigma and raw state xx with σ∼x\sigma\sim x, Stepj(σ)∼D(η,ρ,x).\mathrm{Step}_j(\sigma)\sim D(\eta,\rho,x).(8)✦

In the paper, the result reads: Solve, Ask, Orient and OrientPlus are mutually recursive; a permitted solver input is (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m) with a,b∈ℤVa,b\in\mathbb{Z}^V, a≤ba\le b, 1≤B≤B*1\le B\le B_*, b−a≤Bb-a\le B, positive rational support weights α,β\alpha,\beta and budgets k,mk,m; a subcall inherits every parameter it does not mention, and a changed parameter belongs to that subcall alone; each subcall uses fresh fair bits independent of its history before the call; and repetitions on a fixed input are independent.

What Is Checked

The claims are stated over the step Stepj\mathrm{Step}_j of (1) on the ten-job stack machine and its resumption Resumej\mathrm{Resume}_j, the raw step DD with the resume code RR and the codes DιD_\iota and DfD_f of jobs and frames, the representation (2) of states by raw states through packs that hold jobs, frames and values, and an environment that represents the game, with the index j=|ρ|j=|\rho| read off a random counter.