OctoInformBeta

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

Counter machines: Instructions INC\mathrm{INC} and TESTDEC\mathrm{TESTDEC}, the step and run from initial counter values dd, the first halting time TT and the base CC

Counter machines, their runs and the first halting time.

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

Every recursively enumerable relation R⊆ℕnR \subseteq \mathbb{N}^n is the set of inputs on which some counter machine halts, and a Diophantine representation of RR describes that halting computation by polynomial equations in the input aa and auxiliary unknowns ww.

A Diophantine representation of RR is single-fold when each a∈Ra \in R has exactly one auxiliary tuple ww, so the halting computation recorded in ww has to be one object fixed by aa. The item supplies that object: the run of a counter machine from given initial counter values, its first halting time, and a base of numeration CC fixed by the number of states and those values.

The Definition

Definition 1. Let QQ be a set of states and JJ a set of counters.

An instruction over QQ and JJ is an element of the set ℐ(Q,J)={HALT}∪{INC(j,p):j∈J,p∈Q}∪{TESTDEC(j,p0,p1):j∈J,p0,p1∈Q},\begin{aligned} \mathcal{I}(Q, J) = {}& \{\mathrm{HALT}\} \cup \{\mathrm{INC}(j, p) : j \in J,\ p \in Q\} \\ &\cup \{\mathrm{TESTDEC}(j, p_0, p_1) : j \in J,\ p_0, p_1 \in Q\}, \end{aligned}(1)✦ where jj is a counter and p,p0,p1p, p_0, p_1 are destination states.

A counter machine MM over QQ and JJ consists of an instruction Iq∈ℐ(Q,J)I_q \in \mathcal{I}(Q, J) at each state q∈Qq \in Q, an initial state q*∈Qq_* \in Q and a halt state h∈Qh \in Q, such that Iq=HALT⇔q=hfor every q∈Q.I_q = \mathrm{HALT} \iff q = h \qquad \text{for every } q \in Q.(2)✦

A configuration over QQ and JJ is a pair (q,v)∈Q×ℕJ(q, v) \in Q \times \mathbb{N}^J(3)✦ of a state qq and a vector vv of counter values.

The step of MM is the map σM\sigma_M from configurations to configurations given by σM(q,v)={(q,v)if Iq=HALT,(p,v+ej)if Iq=INC(j,p),(p0,v)if Iq=TESTDEC(j,p0,p1) and vj=0,(p1,v−ej)if Iq=TESTDEC(j,p0,p1) and vj>0,\sigma_M(q, v) = \begin{cases} (q, v) & \text{if } I_q = \mathrm{HALT},\\ (p, v + e_j) & \text{if } I_q = \mathrm{INC}(j, p),\\ (p_0, v) & \text{if } I_q = \mathrm{TESTDEC}(j, p_0, p_1) \text{ and } v_j = 0,\\ (p_1, v - e_j) & \text{if } I_q = \mathrm{TESTDEC}(j, p_0, p_1) \text{ and } v_j > 0, \end{cases}(4)✦ where ej∈ℕJe_j \in \mathbb{N}^J is the unit vector of counter jj.

The run of MM on initial counter values d∈ℕJd \in \mathbb{N}^J is the sequence of configurations (qt(d),vt(d))=σMt(q*,d),t∈ℕ,(q_t(d), v_t(d)) = \sigma_M^{\,t}(q_*, d), \qquad t \in \mathbb{N},(5)✦ with σMt\sigma_M^{\,t} the tt-fold iterate of σM\sigma_M.

A number T∈ℕT \in \mathbb{N} is the first halting time of MM on d∈ℕJd \in \mathbb{N}^J, and MM halts on dd at time TT, if qT(d)=handqt(d)≠h for every t<T.q_T(d) = h \quad \text{and} \quad q_t(d) \neq h \text{ for every } t < T.(6)✦

The halting relation of MM is Halt⁡(M)={d∈ℕJ:M halts on d at some time T∈ℕ},\operatorname{Halt}(M) = \{ d \in \mathbb{N}^J : M \text{ halts on } d \text{ at some time } T \in \mathbb{N} \},(7)✦

When QQ is finite with ss elements and JJ is finite, the base of numeration for initial counter values d∈ℕJd \in \mathbb{N}^J is C=1+s+∑j∈Jdj.C = 1 + s + \sum_{j \in J} d_j.(8)✦

In the paper, the result reads: a counter machine has finitely many states, with an initial state q*q_* and a halt state hh, and finitely many counters with values in ℕ\mathbb{N}; every state other than hh has one instruction INC(j)\mathrm{INC}(j) or TESTDEC(j)\mathrm{TESTDEC}(j) with its destinations, and the halt state has none; and C=1+s+∑jdjC = 1 + s + \sum_j d_j for ss states and initial counter values djd_j.

What Is Checked

The definitions are stated over a set QQ of states and a set JJ of counters, both arbitrary, with counter values in ℕ\mathbb{N}, and the base CC of (8) over finite QQ and JJ.