OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): the simulated machine and its outcome: Finite control, one writable two-way tape, rr read-only heads on unit steps; halting is absorbing, and after nn steps heads lie in [−n,n][-n,n]

The simulated machine and its outcome at each 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

The machine to be simulated is deterministic, with a finite control, one alphabet, one writable tape infinite in both directions and carrying a single head, and a fixed number of read-only heads. Every head starts at the origin of its tape and moves by at most one cell per step. What the heads read is determined by the input: it fixes what the writable tape holds at the start and what each read-only head finds at each displacement from its origin, and as one function supplies all of this, what different heads see may be correlated in any way.

The library defines this machine, its run on an input, and the outcome of the run at each time nn.

Tapes, Moves and Configurations

The set DD of directions consists of 𝖫\mathsf L, 𝖭\mathsf N and 𝖱\mathsf R✦, and the displacement of a direction is the integer Δ(𝖫)=−1\Delta(\mathsf L) = -1, Δ(𝖭)=0\Delta(\mathsf N) = 0, Δ(𝖱)=1\Delta(\mathsf R) = 1.✦

A tape over an alphabet AA is a pair (p,w)(p, w) of a head position p∈ℤp \in \mathbb Z and contents w:ℤ→Aw\colon \mathbb Z \to A✦, and the symbol under its head is w(p)w(p).✦

A write-and-move pair over AA is a pair (a,d)(a, d) of a symbol a∈Aa \in A and a direction d∈Dd \in D.✦ Performing it on a tape (p,w)(p, w) gives the tape (p,w)⋅(a,d)=(p+Δ(d),w[p↦a]),(p, w) \cdot (a, d) = \bigl(p + \Delta(d),\ w[p \mapsto a]\bigr),(1)✦ where w[p↦a]w[p \mapsto a] takes the value aa at pp and agrees with ww elsewhere.

Let QQ be a set of states, AA an alphabet and rr a number of read-only heads. A configuration is a triple (q,(p,w),(p1,…,pr))\bigl(q, (p, w), (p_1, \dots, p_r)\bigr) of a state q∈Qq \in Q, a tape (p,w)(p, w) over AA, which is the writable tape with its head, and the positions p1,…,pr∈ℤp_1, \dots, p_r \in \mathbb Z of the read-only heads, each measured from that head’s origin.✦

The Claim

Definition 1. Let XX be a set, whose finite words x∈X*x \in X^* are the inputs. A multi-head Turing machine MM over XX consists of a finite set QQ of states with a start state q0∈Qq_0 \in Q, a halting flag η(q)∈{true,false}\eta(q) \in \{\mathrm{true}, \mathrm{false}\} for each state qq, a finite alphabet AA, a number rr of read-only heads, a program δ\delta and a sensor σ\sigma.✦ An action is a next state, a write-and-move pair for the writable tape and a direction for each read-only head, an element of Act(Q,A,r)=Q×(A×D)×Dr.\mathrm{Act}(Q, A, r) = Q \times (A \times D) \times D^r.(2)✦ The program δ:Q×A×Ar→Act(Q,A,r)\delta\colon Q \times A \times A^r \to \mathrm{Act}(Q, A, r) maps a state, the symbol under the writable head and the symbols under the read-only heads to an action. The sensor gives, for each input xx, each tag hh and each displacement j∈ℤj \in \mathbb Z, a symbol σh(x,j)∈A\sigma_h(x, j) \in A, where the tag hh is ⊥\bot for the initial writable tape or an index i∈{1,…,r}i \in \{1, \dots, r\} for read-only head ii. The transition with halting is the map δˆ\hat\delta given, for q∈Qq \in Q, a∈Aa \in A and s‾∈Ar\bar s \in A^r, by δˆ(q,a,s‾)={(q,(a,𝖭),(𝖭,…,𝖭))if η(q)=true,δ(q,a,s‾)otherwise.\hat\delta(q, a, \bar s) = \begin{cases} \bigl(q, (a, \mathsf N), (\mathsf N, \dots, \mathsf N)\bigr) & \text{if } \eta(q) = \mathrm{true},\\ \delta(q, a, \bar s) & \text{otherwise}. \end{cases}(3)✦ On input xx the initial configuration is C0(x)=(q0,(0,σ⊥(x,⋅)),(0,…,0)),C_0(x) = \bigl(q_0,\ (0, \sigma_\bot(x, \cdot)),\ (0, \dots, 0)\bigr),(4)✦ where σ⊥(x,⋅)\sigma_\bot(x, \cdot) is the contents j↦σ⊥(x,j)j \mapsto \sigma_\bot(x, j). One step on input xx takes a configuration C=(q,(p,w),(p1,…,pr))C = \bigl(q, (p, w), (p_1, \dots, p_r)\bigr), sets (q′,(a,d),(d1,…,dr))=δˆ(q,w(p),(σ1(x,p1),…,σr(x,pr)))\bigl(q', (a, d), (d_1, \dots, d_r)\bigr) = \hat\delta\bigl(q, w(p), (\sigma_1(x, p_1), \dots, \sigma_r(x, p_r))\bigr) and gives nextx(C)=(q′,(p,w)⋅(a,d),(p1+Δ(d1),…,pr+Δ(dr))).\mathrm{next}_x(C) = \bigl(q',\ (p, w) \cdot (a, d),\ (p_1 + \Delta(d_1), \dots, p_r + \Delta(d_r))\bigr).(5)✦ The configuration at time nn on input xx is Cn(x)C_n(x), starting from (4) with Cn+1(x)=nextx(Cn(x))C_{n+1}(x) = \mathrm{next}_x(C_n(x)).✦ The outcome of a state qq is out(q)=(q,η(q))∈Q×{true,false},\mathrm{out}(q) = (q, \eta(q)) \in Q \times \{\mathrm{true}, \mathrm{false}\},(6)✦ and the outcome at time nn on input xx is out(qn)\mathrm{out}(q_n) for the state qnq_n of Cn(x)C_n(x); its flag is false while the machine is still running at time nn.✦

In the paper, the result reads: the machine is a fixed deterministic one with finitely many states, a finite alphabet, one writable two-way tape with one head and a fixed number of read-only heads, moving by unit steps from fixed origins, with the symbol σh(x,j)\sigma_h(x, j) at displacement jj from the origin of tag hh independent of every space cap; its halting states are absorbing, and its outcome by time TT, the page’s nn, is the state of its finite control with the halting flag.

What Is Checked

The definition is stated over directions with their displacements, tapes with the symbol under the head, write-and-move pairs performed as in (1), configurations made of a state, a writable tape and the positions of the read-only heads, and outcomes pairing a state with its halting flag.

The library proves two facts about the run on an input xx. If the halting flag of the outcome at time nn is true, then for every d≥0d \ge 0 Cn+d(x)=Cn(x).C_{n+d}(x) = C_n(x).(7)✦ For every nn, the head positions of Cn(x)=(q,(p,w),(p1,…,pr))C_n(x) = \bigl(q, (p, w), (p_1, \dots, p_r)\bigr) satisfy p∈[−n,n]andpi∈[−n,n](1≤i≤r),p \in [-n, n] \quad\text{and}\quad p_i \in [-n, n] \quad (1 \le i \le r),(8)✦ where [−n,n][-n, n] is the interval of integers jj with −n≤j≤n-n \le j \le n.