OctoInformBeta

OpenAI preprint, September 2026 · §7. One witness for a halting computation

Lemma 7.1: Started with aa in nn input counters and 00 elsewhere, through a stack machine and a macro program whose steps the machine simulates

Counter machines recognize every recursively enumerable relation.

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 recursively enumerable relation R⊆ℕnR \subseteq \mathbb{N}^n: the composite numbers, say, or the pairs (a1,a2)(a_1, a_2) with a2=2a1a_2 = 2^{a_1}. The question is whether a machine that can only add one to a counter, or test a counter for zero and subtract one from it when it is not, recognizes RR: started with a1,…,ana_1, \dots, a_n in nn of its counters and 00 in the others, it should halt exactly when a=(a1,…,an)a = (a_1, \dots, a_n) lies in RR.

The library reaches counter machines through stack machines and macro programs: a stack machine is translated into a macro program, whose instructions include multiply-add and division, and a macro program is compiled into a counter machine.

Counter Machines

An instruction with states in QQ and counters in JJ is the halting instruction, an increment INC(j)→p\mathrm{INC}(j) \to p of a counter j∈Jj \in J with next state p∈Qp \in Q, or a test-and-decrement TESTDEC(j)→p0,p1\mathrm{TESTDEC}(j) \to p_0, p_1, with next state p0p_0 when jj is at 00 and p1p_1 when jj is decremented.✦ A counter machine MM with states QQ and counters JJ consists of an instruction M(q)M(q) for each state q∈Qq \in Q, an initial state q*q_* and a halt state hh, such that M(q)M(q) is the halting instruction exactly when q=hq = h.✦

A configuration of MM is a pair (q,v)(q, v) of a state q∈Qq \in Q and counter values v∈ℕJv \in \mathbb{N}^J.✦ Writing v[j↦m]v[j \mapsto m] for vv with the value of jj replaced by mm, the step of MM is the map δM(q,v)={(p,v[j↦vj+1])if M(q)=INC(j)→p,(p0,v)if M(q)=TESTDEC(j)→p0,p1 and vj=0,(p1,v[j↦vj−1])if M(q)=TESTDEC(j)→p0,p1 and vj>0,(q,v)if M(q) is the halting instruction.\delta_M(q, v) = \begin{cases} (p, v[j \mapsto v_j + 1]) & \text{if } M(q) = \mathrm{INC}(j) \to p,\\ (p_0, v) & \text{if } M(q) = \mathrm{TESTDEC}(j) \to p_0, p_1 \text{ and } v_j = 0,\\ (p_1, v[j \mapsto v_j - 1]) & \text{if } M(q) = \mathrm{TESTDEC}(j) \to p_0, p_1 \text{ and } v_j > 0,\\ (q, v) & \text{if } M(q) \text{ is the halting instruction}. \end{cases}(1)✦ The partial step of MM is the map that agrees with δM\delta_M on the configurations (q,v)(q, v) for which M(q)M(q) is not the halting instruction and is undefined on the others. A configuration c′c' is reached from cc in one or more steps, written c→M+c′c \to^+_M c', when c′c' arises from cc by applying the partial step at least once.

On an input d∈ℕJd \in \mathbb{N}^J, the configuration after tt steps is δMt(q*,d)\delta_M^t(q_*, d)✦, and MM halts at step TT on dd when δMT(q*,d) is in state handδMt(q*,d) is not in state h for every t<T.\delta_M^T(q_*, d) \text{ is in state } h \quad\text{and}\quad \delta_M^t(q_*, d) \text{ is not in state } h \text{ for every } t < T.(2)✦ The machine MM halts on dd when it halts at some step T∈ℕT \in \mathbb{N}.✦

Macro Programs and Their Compilation

A macro instruction with states in QQ and registers in JJ is the halting instruction, a jump GOTOp\mathrm{GOTO}\,p, an increment INC(j)→p\mathrm{INC}(j) \to p, a test TEST(j)→p0,p1\mathrm{TEST}(j) \to p_0, p_1, a multiply-add MULADD(j,e)→p\mathrm{MULADD}(j, e) \to p with a digit e∈{0,…,4}e \in \{0, \dots, 4\}, or a division DIV(j,r)→p0,…,p4\mathrm{DIV}(j, r) \to p_0, \dots, p_4 with a radix r∈{2,5}r \in \{2, 5\} and a next state for each remainder.✦ A macro program PP with states QQ and registers JJ assigns a macro instruction P(q)P(q) to each q∈Qq \in Q. A macro configuration of PP is a pair (q,v)(q, v) of a state q∈Qq \in Q, or the mark ⊥\bot of a halted program, and register values v∈ℕJv \in \mathbb{N}^J.✦ The macro step of PP from a state qq with values vv is the macro configuration nextP(q,v)={(⊥,v)if P(q) is the halting instruction,(p,v)if P(q)=GOTOp,(p,v[j↦vj+1])if P(q)=INC(j)→p,(p0,v)if P(q)=TEST(j)→p0,p1 and vj=0,(p1,v)if P(q)=TEST(j)→p0,p1 and vj>0,(p,v[j↦5vj+e])if P(q)=MULADD(j,e)→p,(pvjmod⁡r,v[j↦⌊vj/r⌋])if P(q)=DIV(j,r)→p0,…,p4.\mathrm{next}_P(q, v) = \begin{cases} (\bot, v) & \text{if } P(q) \text{ is the halting instruction},\\ (p, v) & \text{if } P(q) = \mathrm{GOTO}\,p,\\ (p, v[j \mapsto v_j + 1]) & \text{if } P(q) = \mathrm{INC}(j) \to p,\\ (p_0, v) & \text{if } P(q) = \mathrm{TEST}(j) \to p_0, p_1 \text{ and } v_j = 0,\\ (p_1, v) & \text{if } P(q) = \mathrm{TEST}(j) \to p_0, p_1 \text{ and } v_j > 0,\\ (p, v[j \mapsto 5 v_j + e]) & \text{if } P(q) = \mathrm{MULADD}(j, e) \to p,\\ (p_{v_j \bmod r}, v[j \mapsto \lfloor v_j / r \rfloor]) & \text{if } P(q) = \mathrm{DIV}(j, r) \to p_0, \dots, p_4. \end{cases}(3)✦

The compiled machine Pˆ\widehat P of a macro program PP with an initial state q0q_0 is the counter machine whose counters are the registers in JJ, a scratch counter σ\sigma and a zero counter ζ\zeta.✦ Its states are a halt state halt\mathrm{halt} and, for each q∈Qq \in Q and digits i,ρ∈{0,…,4}i, \rho \in \{0, \dots, 4\}, the states main(q)\mathrm{main}(q), grow(q,i)\mathrm{grow}(q, i), copy(q,ρ)\mathrm{copy}(q, \rho), copy+(q,ρ)\mathrm{copy}^+(q, \rho), add(q,i)\mathrm{add}(q, i), quot(q,ρ)\mathrm{quot}(q, \rho), carry(q)\mathrm{carry}(q) and restore(q)\mathrm{restore}(q); its initial state is main(q0)\mathrm{main}(q_0).✦ A jump to a state uu is the instruction TESTDEC(ζ)→u,u\mathrm{TESTDEC}(\zeta) \to u, u.✦ The instruction of Pˆ\widehat P at main(q)\mathrm{main}(q) depends on P(q)P(q) as follows: halting instructionjump to halt,GOTOpjump to main(p),INC(j)→pINC(j)→main(p),TEST(j)→p0,p1TESTDEC(j)→main(p0),restore(q),MULADD(j,e)→pTESTDEC(j)→copy(q,0),grow(q,0),DIV(j,r)→p0,…,p4jump to quot(q,0).\begin{array}{ll} \text{halting instruction} & \text{jump to } \mathrm{halt},\\ \mathrm{GOTO}\,p & \text{jump to } \mathrm{main}(p),\\ \mathrm{INC}(j) \to p & \mathrm{INC}(j) \to \mathrm{main}(p),\\ \mathrm{TEST}(j) \to p_0, p_1 & \mathrm{TESTDEC}(j) \to \mathrm{main}(p_0), \mathrm{restore}(q),\\ \mathrm{MULADD}(j, e) \to p & \mathrm{TESTDEC}(j) \to \mathrm{copy}(q, 0), \mathrm{grow}(q, 0),\\ \mathrm{DIV}(j, r) \to p_0, \dots, p_4 & \text{jump to } \mathrm{quot}(q, 0). \end{array}(4)✦ At the other states, with jj, ee, rr and the next states read off P(q)P(q), it is grow(q,i)INC(σ)→grow(q,i+1) for i<4, and INC(σ)→main(q) for i=4,copy(q,ρ)TESTDEC(σ)→f(q,ρ),copy+(q,ρ),copy+(q,ρ)INC(j)→copy(q,ρ),add(q,i)INC(j)→add(q,i+1) for i<e, and a jump to main(p) for i≥e,quot(q,ρ)TESTDEC(j)→copy(q,ρ),carry(q) for ρ+1=r, and otherwise TESTDEC(j)→copy(q,ρ),quot(q,ρ′),carry(q)INC(σ)→quot(q,0),restore(q)INC(j)→main(p1),\begin{array}{ll} \mathrm{grow}(q, i) & \mathrm{INC}(\sigma) \to \mathrm{grow}(q, i + 1) \text{ for } i < 4, \text{ and } \mathrm{INC}(\sigma) \to \mathrm{main}(q) \text{ for } i = 4,\\ \mathrm{copy}(q, \rho) & \mathrm{TESTDEC}(\sigma) \to f(q, \rho), \mathrm{copy}^+(q, \rho),\\ \mathrm{copy}^+(q, \rho) & \mathrm{INC}(j) \to \mathrm{copy}(q, \rho),\\ \mathrm{add}(q, i) & \mathrm{INC}(j) \to \mathrm{add}(q, i + 1) \text{ for } i < e, \text{ and a jump to } \mathrm{main}(p) \text{ for } i \ge e,\\ \mathrm{quot}(q, \rho) & \mathrm{TESTDEC}(j) \to \mathrm{copy}(q, \rho), \mathrm{carry}(q) \text{ for } \rho + 1 = r, \text{ and otherwise } \mathrm{TESTDEC}(j) \to \mathrm{copy}(q, \rho), \mathrm{quot}(q, \rho'),\\ \mathrm{carry}(q) & \mathrm{INC}(\sigma) \to \mathrm{quot}(q, 0),\\ \mathrm{restore}(q) & \mathrm{INC}(j) \to \mathrm{main}(p_1), \end{array}(5)✦ where ρ′=(ρ+1)mod⁡5\rho' = (\rho + 1) \bmod 5✦ and the finishing state f(q,ρ)f(q, \rho) is add(q,0)\mathrm{add}(q, 0) when P(q)P(q) is a multiply-add, main(pρ)\mathrm{main}(p_\rho) when it is a division, and halt\mathrm{halt} otherwise.✦ Where P(q)P(q) is not of the kind its row uses, the instruction at copy+(q,ρ)\mathrm{copy}^+(q, \rho), add(q,i)\mathrm{add}(q, i), quot(q,ρ)\mathrm{quot}(q, \rho) or restore(q)\mathrm{restore}(q) is a jump to halt\mathrm{halt}.✦

For a state uu of Pˆ\widehat P, values v∈ℕJv \in \mathbb{N}^J and m∈ℕm \in \mathbb{N}, the configuration [u,v,m][u, v, m] is in state uu with the registers in JJ at vv, the scratch counter at mm and the zero counter at 00.✦ A macro configuration is represented in Pˆ\widehat P by enc(q,v)=[main(q),v,0]\mathrm{enc}(q, v) = [\mathrm{main}(q), v, 0] and enc(⊥,v)=[halt,v,0]\mathrm{enc}(\bot, v) = [\mathrm{halt}, v, 0].✦

Stack Machines

The stack machines here work over the set KK of the four stacks main\mathrm{main}, rev\mathrm{rev}, aux\mathrm{aux} and stack\mathrm{stack}, the alphabet Γ={γ1,γ2,γ3,γ4}\Gamma = \{\gamma_1, \gamma_2, \gamma_3, \gamma_4\} of two separators and the bits 00 and 11, in this order✦, and a store that holds a symbol of Γ\Gamma or is empty, ⌀\varnothing.✦ A statement over a set of labels Λ\Lambda is one of: a push of a symbol computed from the store onto a stack, a pop of the top symbol of a stack or a peek at it, setting the store from what was read, or an update of the store, each followed by a statement; a branch on the store between two statements; a jump to a label computed from the store; halt.✦ A stack machine 𝒮\mathcal S with labels Λ\Lambda assigns a statement 𝒮(ℓ)\mathcal S(\ell) to each label ℓ∈Λ\ell \in \Lambda. A set L⊆ΛL \subseteq \Lambda of labels supports 𝒮\mathcal S when every jump in a statement 𝒮(ℓ)\mathcal S(\ell) with ℓ∈L\ell \in L leads to a label in LL. Started at a label ℓ0\ell_0 on a∈ℕna \in \mathbb{N}^n, 𝒮\mathcal S executes 𝒮(ℓ0)\mathcal S(\ell_0) with the store empty, the main stack holding the code ⟨a⟩\langle a \rangle of the list (a1,…,an)(a_1, \dots, a_n) in Γ\Gamma and the other stacks empty; it halts on aa when its run reaches halt.

The macro program P𝒮P_{\mathcal S} of 𝒮\mathcal S and ℓ0\ell_0 has a register xkx_k for each stack k∈Kk \in K and a register yiy_i for each input coordinate i=1,…,ni = 1, \dots, n.✦ A symbol γρ\gamma_\rho has the digit dig(γρ)=ρ\mathrm{dig}(\gamma_\rho) = \rho✦; a digit ρ≥1\rho \ge 1 has the symbol sym(ρ)=γρ\mathrm{sym}(\rho) = \gamma_\rho, and sym(0)=⌀\mathrm{sym}(0) = \varnothing.✦ The states of P𝒮P_{\mathcal S}, its labels, are code(θ,β)\mathrm{code}(\theta, \beta) for a statement θ\theta and a store content β\beta, repush(k,ρ,θ,β)\mathrm{repush}(k, \rho, \theta, \beta) for a stack kk and a digit ρ\rho, and the labels of the start phase, which loads the input, among them start(i)\mathrm{start}(i) for 0≤i≤n0 \le i \le n.✦

At code(θ,β)\mathrm{code}(\theta, \beta), P𝒮P_{\mathcal S} carries out the first instruction of θ\theta and moves to code(θ′,β′)\mathrm{code}(\theta', \beta'), where θ′\theta' is the statement that follows and β′\beta' is the new store. A push of γ\gamma onto stack kk is MULADD(xk,digγ)\mathrm{MULADD}(x_k, \mathrm{dig}\,\gamma).✦ A pop from stack kk is DIV(xk,5)\mathrm{DIV}(x_k, 5), with the store set from sym(ρ)\mathrm{sym}(\rho) for the remainder ρ\rho; a peek is the same division, followed by repush(k,ρ,θ′,β′)\mathrm{repush}(k, \rho, \theta', \beta'), which applies MULADD(xk,ρ)\mathrm{MULADD}(x_k, \rho) when ρ≠0\rho \neq 0 and goes on at code(θ′,β′)\mathrm{code}(\theta', \beta').✦ Store updates, branches and jumps are GOTO\mathrm{GOTO} instructions, a jump to ℓ\ell going to code(𝒮(ℓ),β)\mathrm{code}(\mathcal S(\ell), \beta), and halt is the halting instruction.✦

The start phase begins at start(n)\mathrm{start}(n).✦ For i=n,…,1i = n, \dots, 1 it pushes the separator γ2\gamma_2 by MULADD(xmain,2)\mathrm{MULADD}(x_{\mathrm{main}}, 2), divides yiy_i by 22 until it is 00, applying MULADD(xrev,3)\mathrm{MULADD}(x_{\mathrm{rev}}, 3) for each remainder 00 and MULADD(xrev,4)\mathrm{MULADD}(x_{\mathrm{rev}}, 4) for each remainder 11, and then moves xrevx_{\mathrm{rev}} onto xmainx_{\mathrm{main}} by DIV(xrev,5)\mathrm{DIV}(x_{\mathrm{rev}}, 5) and MULADD(xmain,ρ)\mathrm{MULADD}(x_{\mathrm{main}}, \rho) until the remainder ρ\rho is 00.✦ From start(0)\mathrm{start}(0) it jumps to code(𝒮(ℓ0),⌀)\mathrm{code}(\mathcal S(\ell_0), \varnothing).✦

The statements of 𝒮\mathcal S on LL are the statements that occur in 𝒮(ℓ)\mathcal S(\ell) for some ℓ∈L\ell \in L, parts included✦, and a label of P𝒮P_{\mathcal S} is good when it belongs to the start phase or its statement θ\theta is one of them.✦ The restriction P𝒮LP^L_{\mathcal S} is the macro program on the finite set of good labels in which every jump to a label that is not good goes to start(n)\mathrm{start}(n) instead.✦ The counter machine M𝒮M_{\mathcal S} of 𝒮\mathcal S, ℓ0\ell_0 and LL is the compiled machine of P𝒮LP^L_{\mathcal S} with initial state main(start(n))\mathrm{main}(\mathrm{start}(n)); its counters are the xkx_k, the yiy_i, σ\sigma and ζ\zeta.✦ For a∈ℕna \in \mathbb{N}^n, the counter input d(a)d^{(a)} gives yiy_i the value aia_i for each ii and every other counter the value 00.✦

The Claim

Theorem 1. Let n∈ℕn \in \mathbb{N}.

(a) Let R⊆ℕnR \subseteq \mathbb{N}^n be a recursively enumerable relation. Then there is a counter machine MM with finitely many states, whose counters are xkx_k for k∈Kk \in K, y1,…,yny_1, \dots, y_n, σ\sigma and ζ\zeta, such that for every a∈ℕna \in \mathbb{N}^n a∈R⇔M halts on d(a).a \in R \iff M \text{ halts on } d^{(a)}.(6)✦

(b) Let 𝒮\mathcal S be a stack machine with labels Λ\Lambda, let ℓ0∈Λ\ell_0 \in \Lambda, and let L⊆ΛL \subseteq \Lambda be a finite set that contains ℓ0\ell_0 and supports 𝒮\mathcal S. Then for every a∈ℕna \in \mathbb{N}^n M𝒮 halts on d(a)⇔𝒮 started at ℓ0 halts on a.M_{\mathcal S} \text{ halts on } d^{(a)} \iff \mathcal S \text{ started at } \ell_0 \text{ halts on } a.(7)✦

(c) Let PP be a macro program with states QQ, registers JJ and an initial state, and let Pˆ\widehat P be its compiled machine. Then for every q∈Qq \in Q and every v∈ℕJv \in \mathbb{N}^J [main(q),v,0]→Pˆ+enc(nextP(q,v)).[\mathrm{main}(q), v, 0] \to^+_{\widehat P} \mathrm{enc}(\mathrm{next}_P(q, v)).(8)✦

In the paper, the result reads: for n≥1n \ge 1 and a recursively enumerable relation R⊆ℕnR \subseteq \mathbb{N}^n, there is a counter machine that, with its first nn counters set to a1,…,ana_1, \dots, a_n and the rest to 00, reaches its halt state exactly when a∈Ra \in R.

What Is Checked

Claim (6) is stated over recursively enumerable relations on ℕn\mathbb{N}^n and the halting of counter machines with finitely many states on the input d(a)d^{(a)}, claim (7) over stack machines with a finite supporting set of labels and the counter machine M𝒮M_{\mathcal S} compiled from the restriction P𝒮LP^L_{\mathcal S}, and claim (8) over the macro step of a macro program, its compiled machine Pˆ\widehat P and the representation enc\mathrm{enc} of macro configurations.