OctoInformBeta

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

Polynomial clock of deterministic logspace deciders: On every input of length nn such a machine halts by time c(n+2)kc(n+2)^k, for constants c>0c>0 and kk fixed by the machine

Deterministic logspace deciders halt in polynomial 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

Take a deterministic Turing machine that reads an input word of length nn with a fixed number of heads, works within O(log⁡n)O(\log n) cells of a fixed number of binary work tapes, and decides a language AA. The question is how long it can run before its verdict: whether a polynomial in nn bounds that time, with constants that depend on the machine and not on the input. The library states such a bound for its model of probabilistic Turing machines, restricted to the ones that ignore their coins.

Machines and Their Runs

A binary word is a finite sequence of bits, and |x||x| is the length of the word xx.✦ A language is a set of binary words.✦ The input tape of a word of length nn has cells 00 to n+1n+1, the word with its two endmarkers, and an input tape symbol is the left endmarker, a bit, or the right endmarker. A head direction is one of the three 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, an output out(s)∈{0,1,⊥}\mathrm{out}(s) \in \{0,1,\bot\} for each state ss, and a transition function δ\delta.✦ The output 11 is accept, 00 is reject and ⊥\bot is no verdict; the states with a verdict are the halting states. From a state ss, the input symbols ι\iota under the hh input heads, the bits vv under the ww work heads and a coin bit rr, the transition function gives a machine action δ(s,ι,v,r)\delta(s,\iota,v,r), the instruction for one step: a next state, a bit to write on each work tape, and a direction for each work head and each input head.✦

A machine MM is deterministic when its transition function ignores the coin: for every state ss, input symbols ι\iota and work bits vv, δ(s,ι,v,0)=δ(s,ι,v,1).\delta(s,\iota,v,0) = \delta(s,\iota,v,1).(1)✦

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 γ\gamma is an infinite sequence of bits γ(0),γ(1),…\gamma(0),\gamma(1),\dots, one coin for each time step.✦ The run of MM on a word xx with coin tape γ\gamma is the sequence of configurations Ct(x,γ)C_t(x,\gamma) on inputs of length |x||x|, for t=0,1,…t = 0,1,\dots, in which C0(x,γ)C_0(x,\gamma) is the initial configuration of MM on xx and Ct+1(x,γ)C_{t+1}(x,\gamma) is the result of one step of MM from Ct(x,γ)C_t(x,\gamma) with coin γ(t)\gamma(t).✦ We write st(x,γ)s_t(x,\gamma) for the state of Ct(x,γ)C_t(x,\gamma).

Space, Deciding and Halting

The space St(x,γ)S_t(x,\gamma) used by the run of MM on xx with coin tape γ\gamma through time tt is the sum, over the work tapes, of the number of distinct cells the tape’s head visits at the times 00 to tt.✦ With pk(s)p_k(s) the position of the head of work tape kk in Cs(x,γ)C_s(x,\gamma), St(x,γ)=∑k=1w|{pk(s):0≤s≤t}|.S_t(x,\gamma) = \sum_{k=1}^{w} \bigl|\{\, p_k(s) : 0 \le s \le t \,\}\bigr|.(2)✦ A machine MM works in logarithmic space when there is an integer c>0c > 0 such that, for every word xx of length nn, every coin tape γ\gamma and every time tt, St(x,γ)≤c⌈log⁡2(n+2)⌉.S_t(x,\gamma) \le c\,\lceil \log_2(n+2) \rceil .(3)✦

A machine MM decides a language AA when for every word xx there is a time tt at which every run on xx gives the right verdict: out(st(x,γ))=[x∈A]for every coin tape γ,\mathrm{out}\bigl(s_t(x,\gamma)\bigr) = [x \in A] \quad \text{for every coin tape } \gamma,(4)✦ where [x∈A][x \in A] is 11 for x∈Ax \in A and 00 otherwise.

On a word xx, a machine MM halts by time tt when, for every coin tape γ\gamma, the state st(x,γ)s_t(x,\gamma) is a halting state.✦

The polynomial clock with coefficient cc and exponent kk is the function of the input length nn given by Tc,k(n)=c(n+2)k.T_{c,k}(n) = c\,(n+2)^k .(5)✦

The Claim

Theorem 1. Let MM be a deterministic machine that works in logarithmic space and decides a language AA. Then there are integers c>0c > 0 and k≥0k \ge 0 such that M halts by time Tc,k(|x|) on every binary word x.M \text{ halts by time } T_{c,k}(|x|) \text{ on every binary word } x .(6)✦

What Is Checked

The claim (6) is stated over probabilistic Turing machines with an input tape between endmarkers, binary work tapes and a coin tape, over their actions, configurations and runs, and over the space (2) a run uses, the logarithmic space bound (3), determinism (1), deciding a language (4), halting by a given time and the polynomial clock (5).