OctoInformBeta

OpenAI preprint, September 2026 · Lean results with no numbered counterpart

A register-program criterion for L: AA consists of the words xx where ff is nonzero with zeroed registers, when register programs with polynomially bounded registers set any register to ff

Languages decided by register-computable expressions are in LL..

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

A register program computes with registers r0,r1,…r_0,r_1,\dots that hold natural numbers. It changes a register by one at a time, and it consults the input xx only through the symbol in the input cell whose index a register holds, so that a register is a pointer into the input. Run on xx with every register zero, such a program produces a number, and the words on which that number is nonzero form a language. The question is whether every language that arises this way lies in the class LL of languages decided in deterministic logarithmic space when the registers stay below a polynomial in the length of the input.

Machines and the Class LL

A binary word is a finite sequence of bits✦, and a language is a set of binary words.✦ For an input word xx of length nn, the input tape has cells 00 to n+1n+1: cell 00 holds the left endmarker, cell ii holds the bit xix_i for 1≤i≤n1\le i\le n, and cell n+1n+1 holds the right endmarker.✦ An input tape symbol is the left endmarker, a bit, or the right endmarker.✦ A head direction is one of the moves left, stay and right.✦

A probabilistic Turing machine MM with states 0,…,q0,\dots,q, ww binary work tapes and hh input heads consists of an initial state, a transition function and an output map.✦ The output map gives each state either no verdict or a verdict, accept or reject; the states with a verdict are the halting states. The transition function maps a state, the hh symbols under the input heads, the ww bits under the work heads and a coin bit to an action: a next state, a bit to write on each work tape, and a head direction for each work head and each input head.

A configuration of MM on an input of length nn consists of a state, a position in {0,…,n+1}\{0,\dots,n+1\} for each input head, an integer position for each work head, and the contents of each work tape, a bit at every integer cell.✦ A coin tape is an infinite sequence γ=(γ(0),γ(1),…)\gamma=(\gamma(0),\gamma(1),\dots) of bits.✦ The run of MM on xx with coin tape γ\gamma is the sequence of configurations C0,C1,…C_0,C_1,\dots in which C0C_0 is the initial configuration of MM on xx, with the initial state and every head and tape in its starting position, and Ct+1C_{t+1} is the configuration that the transition function of MM gives from CtC_t with coin γ(t)\gamma(t).✦

The space sM(x,γ,t)s_M(x,\gamma,t) used through time tt is the sum, over the work tapes, of the number of distinct cells that the tape’s head visits in C0,…,CtC_0,\dots,C_t.✦ The machine MM runs in logarithmic space when there is a constant c>0c>0 with sM(x,γ,t)≤c⌈log⁡2(n+2)⌉for every word x,coin tape γ and time t.s_M(x,\gamma,t)\le c\,\lceil\log_2(n+2)\rceil \qquad\text{for every word } x,\ \text{coin tape } \gamma \text{ and time } t.(1)✦

The machine MM decides a language AA when for every word xx there are a time tt and a verdict bb, accept if x∈Ax\in A and reject if not, such that on every coin tape γ\gamma the state of CtC_t in the run with γ\gamma has verdict bb.✦ A probabilistic Turing machine MM is deterministic when its transition function does not depend on the coin bit.✦ The class LL is the set of languages decided by a deterministic machine that runs in logarithmic space.✦

Register Programs

A store aa is an assignment of a natural number aia_i, the content of register rir_i, to every register index i≥0i\ge 0; 𝟎\mathbf 0 is the store with every register zero.✦ A store aa fits below kk when ai<ka_i<k for every ii✦, and it is zero above ll when ai=0a_i=0 for every i≥li\ge l.✦ Two stores aa and bb agree below ll when ai=bia_i=b_i for every i<li<l.✦

Moving register ii of a store aa in a head direction gives the store that agrees with aa off ii and holds max⁡(ai−1,0)\max(a_i-1,0), aia_i or ai+1a_i+1 at ii, for the directions left, stay and right.✦ Putting a value vv into register ii of aa gives the store a[i:=v]a[i:=v] that holds vv at ii and agrees with aa at every other index.✦

A counter command is built by the grammar p::=step(i,δ)∣p;p∣𝒊𝒇τ(ri)𝒕𝒉𝒆𝒏p𝒆𝒍𝒔𝒆p∣𝒘𝒉𝒊𝒍𝒆τ(ri)𝒅𝒐p,p \;::=\; \mathrm{step}(i,\delta) \;\mid\; p\,;p \;\mid\; \mathbf{if}\ \tau(r_i)\ \mathbf{then}\ p\ \mathbf{else}\ p \;\mid\; \mathbf{while}\ \tau(r_i)\ \mathbf{do}\ p,(2)✦ where ii is a register index, δ\delta a head direction and τ\tau a Boolean test on input tape symbols. The input scan of xx at a position mm is the symbol in cell mm of the input tape when m≤n+1m\le n+1, and the right endmarker when m>n+1m>n+1.✦ The test τ(ri)\tau(r_i) holds at a store aa when τ\tau is true on the input scan of xx at position aia_i.✦

For an input xx and a bound kk, execution with registers below kk is the relation a→x,kpba\xrightarrow[x,k]{p}b between a command pp and stores aa and bb given by the following rules. A step step(i,δ)\mathrm{step}(i,\delta) takes aa to the store obtained by moving register ii of aa in direction δ\delta, when both stores fit below kk. For a sequence p;qp;q, the command takes aa to cc when pp takes aa to some bb and qq takes bb to cc. For commands pp and qq, the command 𝒊𝒇τ(ri)𝒕𝒉𝒆𝒏p𝒆𝒍𝒔𝒆q\mathbf{if}\ \tau(r_i)\ \mathbf{then}\ p\ \mathbf{else}\ q takes aa to bb when τ(ri)\tau(r_i) holds at aa and pp takes aa to bb, or τ(ri)\tau(r_i) fails at aa and qq takes aa to bb. For a command pp, the command 𝒘𝒉𝒊𝒍𝒆τ(ri)𝒅𝒐p\mathbf{while}\ \tau(r_i)\ \mathbf{do}\ p takes aa to aa when τ(ri)\tau(r_i) fails at aa and aa fits below kk; when τ(ri)\tau(r_i) holds at aa, it takes aa to cc when pp takes aa to some bb and the loop takes bb to cc.

Register-computable Expressions

A numeric expression ff is a function assigning a natural number f(x,a)f(x,a) to every input word xx and store aa✦; a store transformation TT is a function assigning a store T(x,a)T(x,a) to every xx and aa.✦ For a register index ii, setting register ii to ff is the store transformation (x,a)↦a[i:=f(x,a)](x,a)\mapsto a[i:=f(x,a)].✦ A numeric expression ff is local when there is a kk such that f(x,a)=f(x,b)f(x,a)=f(x,b) for every input xx and all stores aa and bb that agree below kk.✦

There is room for a store transformation TT at a threshold ll when there are a counter command pp and an exponent d>0d>0 such that, for every input xx, every bound B≥n+2B\ge n+2 and every store aa that fits below BB and is zero above ll, a→x,BdpT(x,a)andT(x,a)is zero above l.a\xrightarrow[x,\,B^d]{p} T(x,a) \qquad\text{and}\qquad T(x,a)\ \text{is zero above } l.(3)✦ The transformation TT is operable when there is an ll such that there is room for TT at every threshold r≥lr\ge l.✦ A numeric expression ff is register computable when it is local and, for every register index ii, setting register ii to ff is operable.✦

The Claim

Theorem 1. Let ff be a register-computable numeric expression and AA a language such that f(x,𝟎)≠0⇔x∈Afor every binary word x.f(x,\mathbf 0)\neq 0 \iff x\in A \qquad\text{for every binary word } x.(4)✦ Then AA belongs to LL.✦

The polynomial bound of the question is the bound BdB^d in (3).

What Is Checked

The claim is stated over the class LL of languages decided by deterministic machines within the space bound (1), and over register-computable expressions, defined through counter commands (2) executed with registers below BdB^d as in (3).