OctoInformBeta

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

Proposition 7.2: A system on digit strings in base B=2wB = 2^w is solvable exactly when the machine halts, and its one solution spells out the run

The halting relation of a counter machine is single-fold.

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 MM be a counter machine, started with the value dj∈ℕd_j \in \mathbb{N} in each counter jj. The relation “MM halts from dd” is recursively enumerable in dd, and by Matiyasevich’s theorem it is Diophantine. The question is whether it is single-fold: whether some Diophantine representation of it has exactly one auxiliary tuple for each dd from which MM halts.

A halting run of MM is a finite table that records, for each time up to the halt, the state and the values of the counters.

Counter Machines

An instruction over a set QQ of states and a set JJ of counters is the halting instruction, or INC(j)\mathrm{INC}(j) with a counter j∈Jj \in J and a next state p∈Qp \in Q, or TESTDEC(j)\mathrm{TESTDEC}(j) with a counter jj and two next states, p0p_0 for a zero counter and p1p_1 for a nonzero one.✦ A counter machine MM with a finite set QQ of ss states and a finite set JJ of counters is an assignment of an instruction to each state, with an initial state q*q_* and a halt state hh such that hh is the only state carrying the halting instruction.✦

A configuration of MM is a pair (q,x)(q, x) of a state q∈Qq \in Q and a vector x∈ℕJx \in \mathbb{N}^J of counter values.✦ For a counter j∈Jj \in J, let eje_j be the unit vector of counter jj. The step of MM is the map on configurations that fixes (q,x)(q, x) when qq carries the halting instruction, sends it to (p,x+ej)(p, x + e_j) when qq carries INC(j)\mathrm{INC}(j) with next state pp, and, when qq carries TESTDEC(j)\mathrm{TESTDEC}(j), sends it to (p0,x)(p_0, x) if xj=0x_j = 0 and to (p1,x−ej)(p_1, x - e_j) if xj>0x_j > 0.✦ The run of MM from d∈ℕJd \in \mathbb{N}^J is the sequence of configurations ct=(qt,xt)c_t = (q_t, x_t), t∈ℕt \in \mathbb{N}, with c0=(q*,d)c_0 = (q_*, d) and ct+1c_{t+1} the step of ctc_t; xt,jx_{t,j} is the value of counter jj at time tt.✦

The machine MM halts at time TT from dd when qT=handqt≠hfor every t<T,q_T = h \qquad \text{and} \qquad q_t \neq h \quad \text{for every } t < T,(1)✦ and it halts from dd when it halts at some time TT✦. The halting relation HaltM\mathrm{Halt}_M of MM is the set of vectors d∈ℕJd \in \mathbb{N}^J from which MM halts. The size bound of MM on dd is C=1+s+∑j∈JdjC = 1 + s + \sum_{j \in J} d_j.✦

Single-fold Relations

A single-fold representation of a relation RR on tuples a∈ℕIa \in \mathbb{N}^I, for an index set II, is a polynomial P(a,z)P(a, z) with integer coefficients in the input variables aa and finitely many auxiliary variables zz, all ranging over ℕ\mathbb{N}, such that a∈R⇔P(a,z)=0 for some z,P(a,z)=P(a,z′)=0⟹z=z′.a \in R \iff P(a, z) = 0 \text{ for some } z, \qquad P(a, z) = P(a, z') = 0 \implies z = z'.(2)✦ A relation is single-fold when it has a single-fold representation, and SF\mathrm{SF} is the class of single-fold relations.✦

The Witness System

For natural numbers xx and yy, the relation x≼yx \preceq y holds when every binary digit 11 of xx is 11 in yy.✦

A witness vv for MM is a tuple of natural numbers made of seven numbers ww, BB, bb, kk, HH, LL, UU; for each state qq, a state string SqS_q, a zero branch ZqZ_q, a nonzero branch NqN_q and a complement Z‾q\bar Z_q; and three numbers XjX_j, fjf_j, rjr_j for each jj in J∪{τ}J \cup \{\tau\}, where the clock τ\tau is an index outside JJ.✦ The base of vv is BB and its length is kk.

Each branch of an instruction has a destination and, in a witness vv, an arc weight: the one branch of INC(j)\mathrm{INC}(j) at qq leads to its next state with weight SqS_q, and TESTDEC(j)\mathrm{TESTDEC}(j) at qq has a zero branch to p0p_0 of weight ZqZ_q and a nonzero branch to p1p_1 of weight NqN_q. The incoming weight IpI_p of a state pp in vv is the sum of the arc weights of the branches with destination pp.✦ The increment weight ιj\iota_j and the decrement weight δj\delta_j of a counter j∈Jj \in J in vv are ιj=∑q carries INC(j)Sq,δj=∑q carries TESTDEC(j)Nq.\iota_j = \sum_{q \text{ carries } \mathrm{INC}(j)} S_q, \qquad \delta_j = \sum_{q \text{ carries } \mathrm{TESTDEC}(j)} N_q.(3)

The witness system of MM on dd is the system of conditions on a witness vv, with CC the size bound of MM on dd, made of the scale conditions B=2w=4b,2C<B,k≥1,H=Bk=BL,(B−1)U=H−1;B = 2^w = 4b, \qquad 2C < B, \qquad k \ge 1, \qquad H = B^k = BL, \qquad (B - 1)\,U = H - 1;(4) the state conditions, for every state qq, with εq\varepsilon_q equal to 11 for q=q*q = q_* and to 00 otherwise, Sq≼U,∑p∈QSp=U,Sq=εq+BIq;S_q \preceq U, \qquad \sum_{p \in Q} S_p = U, \qquad S_q = \varepsilon_q + B\,I_q;(5) the branch conditions Zq≼Sq,Nq≼Sq,Zq+Nq=Sq,Zq+Z‾q=UZ_q \preceq S_q, \qquad N_q \preceq S_q, \qquad Z_q + N_q = S_q, \qquad Z_q + \bar Z_q = U(6) for every state qq carrying TESTDEC\mathrm{TESTDEC}, and Zq=Nq=Z‾q=0Z_q = N_q = \bar Z_q = 0 for the other states; the counter conditions, for every j∈J∪{τ}j \in J \cup \{\tau\}, Xj≼(2b−1)U,Xj=fjL+rj,rj<L;X_j \preceq (2b - 1)\,U, \qquad X_j = f_j L + r_j, \qquad r_j < L;(7) the update and zero-test conditions, for every counter j∈Jj \in J, Xj+Bδj=dj+B(rj+ιj),Xj≼(B−1)Z‾qfor every q carrying TESTDEC(j);X_j + B\,\delta_j = d_j + B\,(r_j + \iota_j), \qquad X_j \preceq (B - 1)\,\bar Z_q \quad \text{for every } q \text{ carrying } \mathrm{TESTDEC}(j);(8) and the clock conditions Xτ+BL=C+B(rτ+U),b≤fτ,2fτ<B.X_\tau + BL = C + B\,(r_\tau + U), \qquad b \le f_\tau, \qquad 2 f_\tau < B.(9)✦

The witness relation 𝒲M\mathcal{W}_M of MM is the set of pairs (d,v)(d, v) of a vector d∈ℕJd \in \mathbb{N}^J and a witness vv that solves the witness system of MM on dd.

For a witness with base BB, the digit of a natural number xx at position tt is [x]t=⌊x/Bt⌋mod⁡B[x]_t = \lfloor x / B^t \rfloor \bmod B.✦

The Claim

Theorem 1. Let MM be a counter machine with a finite set QQ of states and a finite set JJ of counters. Then HaltM∈SF\mathrm{Halt}_M \in \mathrm{SF}(10)✦ and 𝒲M∈SF.\mathcal{W}_M \in \mathrm{SF}.(11)✦ Let d∈ℕJd \in \mathbb{N}^J. If MM halts from dd, then some witness vv satisfies (d,v)∈𝒲M.(d, v) \in \mathcal{W}_M.(12)✦ If vv and uu are witnesses with (d,v)(d, v) and (d,u)(d, u) in 𝒲M\mathcal{W}_M, then v=u.v = u.(13)✦ If (d,v)∈𝒲M(d, v) \in \mathcal{W}_M and vv has length kk, then for every time t<kt < k, every state qq and every counter j∈Jj \in J, the digits in the base of vv satisfy [Sq]t={1if q=qt,0if q≠qt,[Xj]t=xt,j,[S_q]_t = \begin{cases} 1 & \text{if } q = q_t,\\ 0 & \text{if } q \neq q_t, \end{cases} \qquad [X_j]_t = x_{t,j},(14)✦ and MM halts from dd at time TT with T=k−1.T = k - 1.(15)✦ For every positive integer ℓ\ell, exactly one natural number ww satisfies 2ℓ<2w≤4ℓ.2\ell < 2^w \le 4\ell.(16)✦

In the paper, the result reads: for n≥1n \ge 1 and a deterministic counter machine with instructions INC(j)\mathrm{INC}(j) and TESTDEC(j)\mathrm{TESTDEC}(j) and one halt state, whose counter jj starts at djd_j, a fixed coordinate aia_i of an input a∈ℕna \in \mathbb{N}^n or 00, there is a finite system of polynomial equations with integer coefficients in aa and auxiliary natural numbers whose complete auxiliary tuple has exactly one solution when the machine halts and none when it does not.

What Is Checked

The theorem is stated over counter machines with instructions INC(j)\mathrm{INC}(j) and TESTDEC(j)\mathrm{TESTDEC}(j) and a single halt state, their runs and halting times from an initial counter vector dd, the witness system with its size bound CC, its base B=2wB = 2^w and its clock, and single-fold representations by polynomials with integer coefficients.