OctoInformBeta

OpenAI preprint, September 2026 · The space calculus (no numbered counterpart in the preprint)

Compiling the calculus to Turing machines: When a label’s code is computable in space SS, one Turing machine outputs it within c(S+1)c\,(S+1) work bits, from a binary argument or none

Stack computations of a label compile to one Turing machine.

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 library measures space in a calculus of stack machines, which compute a number from a number on a public input, uniformly over an indexed family of instances. Space-bounded complexity states its theorems for Turing machines with read-only input tapes and work tapes, space counted in work bits. The question is whether the first compiles to the second: when the number computed is the code of a label from a finite set, is there one multitape Turing machine that reads the starting number in binary on a read-only argument tape, or reads only the public input when that number is 00, and halts with the label within a constant times the same space?

Read-only Inputs and Turing Machines

A head direction is one of left LL, stay NN and right RR✦; its displacement is δ(L)=−1\delta(L) = -1, δ(N)=0\delta(N) = 0 and δ(R)=+1\delta(R) = +1✦. A read-only head on a word w=w1⋯wnw = w_1 \cdots w_n over an alphabet AA sees ww between a left endmarker ⊢{\vdash} and a right endmarker ⊣{\dashv}✦, and the mark read at a position p≥0p \ge 0 is w‾(p)={⊢,p=0,wp,1≤p≤n,⊣,p>n.\bar w(p) = \begin{cases} {\vdash}, & p = 0,\\ w_p, & 1 \le p \le n,\\ {\dashv}, & p > n. \end{cases}(1)✦ Moved left, a head at pp goes to max⁡(p−1,0)\max(p-1, 0); moved right, it goes to p+1p+1 unless p>np > n, where it stays on the right endmarker; under NN it stays.✦

The machine inputs over XX with argument tapes indexed by a set JJ are a public word vv over XX and, for each j∈Jj \in J, an argument word zjz_j of bits, written (v;z)(v; z).✦ For a natural number nn, bin⁡(n)\operatorname{bin}(n) is the word of its binary digits, least significant first, without leading zeros. For a public word vv over XX and a function f:J→ℕf \colon J \to \mathbb{N}, the machine input with binary arguments f(j)f(j) is (v;(bin⁡f(j))j∈J)(v; (\operatorname{bin} f(j))_{j \in J}).✦ The word vv as public input is the machine input with public word vv and no argument tapes.✦

A multitape Turing machine MM over a public input alphabet XX, with binary argument tapes indexed by JJ and outputs in a set YY, consists of a finite set QQ of states with a start state q0q_0, a finite set KK of work tapes, for each k∈Kk \in K a finite alphabet WkW_k with a blank symbol, and a transition table.✦ Given the state, the marks under the input heads (one head on the public word and one on each argument word) and the symbol under each work head, the table either halts with an output in YY or prescribes an action: a next state, a direction for each input head, and for each work tape a symbol to write and a direction to move.

Work tapes are two-way infinite: a work tape over WkW_k is a content σ:ℤ→Wk\sigma \colon \mathbb{Z} \to W_k with a head position p∈ℤp \in \mathbb{Z}✦, and writing aa and moving in direction DD replaces σ(p)\sigma(p) by aa and puts the head at p+δ(D)p + \delta(D)✦. A configuration of MM consists of the state, the positions of the input heads and the work tapes.✦ The initial configuration has state q0q_0, every input head at 00 on the left endmarker, and every work tape blank with its head at 00.✦ A step applies the table to the current configuration; it halts with the output the table gives, or enters the next state of the action, with the input heads moved and each work tape written and moved as it prescribes.✦

Let ff be a step map that at each configuration either halts with a label or gives a next configuration, and PP a property of configurations. A halting run of ff under PP from ss to tt with label yy is a sequence s=s0,s1,…,sn=ts = s_0, s_1, \ldots, s_n = t of configurations with sj+1=f(sj)s_{j+1} = f(s_j) for j<nj < n, each sjs_j, tt included, satisfying PP, and ff halting at tt with label yy.✦

Space is counted on a window. A window ww of MM is a choice, for each work tape kk, of an interval [−lk,hk][-l_k, h_k] of cells with lkl_k and hkh_k natural numbers.✦ A configuration of MM lies inside ww when every work head is in its interval.✦ Tape kk has width⁡k=max⁡{1,ℓ(|Wk|−1)}\operatorname{width}_k = \max\{1, \ell(|W_k| - 1)\} bits per symbol, where ℓ(m)\ell(m) is the number of binary digits of mm✦, and the size of ww in bits is ∥w∥=∑k∈K(lk+hk+1)width⁡k.\|w\| = \sum_{k \in K} (l_k + h_k + 1)\,\operatorname{width}_k .(2)✦ A multitape Turing machine MM computes the output yy on inputs uu within SS bits when, for some window ww whose size (2) is at most SS, the step of MM on uu has a halting run from the initial configuration, under the property of lying inside ww, with label yy.

Stack Machines and the Space Calculus

In the calculus, a stack is a word of bits read from its top. A stack operation is keep, push bb for a bit bb, or pop, which removes the top bit and leaves an empty stack empty.✦ A stack machine with input alphabet XX, argument tapes indexed by JJ, stacks indexed by KK and labels in YY consists of a finite set of states with a start state and a transition table.✦ Given the state, the marks under the input heads and the top bit of each stack, or none when it is empty, the table either halts with a label in YY or prescribes an action: a direction for each input head, an operation for each stack and a next state.

A store consists of the positions of the input heads and the contents of the stacks✦, and a configuration of a stack machine is a state with a store✦. The step of a stack machine on a configuration reads the table as for a Turing machine, and an action takes the configuration to the next state, with the input heads moved and each stack changed by its operation.✦ A bounded run within BB bits is a halting run of the step under the property that every stack has length at most BB.✦ An execution of the machine on inputs uu within BB bits from a store ss to a store tt with label yy is a bounded run on uu within BB bits from the start state with ss that halts with label yy in some state with tt.✦

Let xx be a family of machine inputs over XX with argument tapes indexed by JJ, SS a family of space bounds, aa and bb families of stores with stacks indexed by LL, and yy a family of labels, all indexed by a set II. The families xx, SS, aa, bb and yy form a stack computation in space SS when there are a stack machine MM whose stacks are those of LL and finitely many extra ones, and a constant cc, such that for every i∈Ii \in I the machine MM has an execution on x(i)x(i) within c(S(i)+1)c\,(S(i)+1) bits per stack from a(i)a(i) to b(i)b(i), its extra stacks empty at both ends, with label y(i)y(i).✦

The number nn as a stack is the store with no argument tapes, the input head at 00 on the left endmarker and a single stack holding bin⁡(n)\operatorname{bin}(n).✦ For a family xx of words over XX and families SS, aa, bb of natural numbers, all indexed by II, the family bb is computable from aa in space SS on public inputs xx when the words x(i)x(i) as public inputs, the numbers a(i)a(i) as stacks and the numbers b(i)b(i) as stacks form a stack computation in space SS, halting with the same label at every index.✦

The Claim

Theorem 1. Let II be a set of indices, xx a family of words over an alphabet XX, SS a family of natural numbers, YY a nonempty finite set of labels with an injective code d:Y→ℕd \colon Y \to \mathbb{N}, and yy a family of labels, all families indexed by II.

  1. If aa is a family of natural numbers indexed by II and the codes d(y(i))d(y(i)) are computable from aa in space SS on public inputs xx, there are a multitape Turing machine MM over XX with one binary argument tape and outputs in YY, and a constant cc, such that for every i∈Ii \in I M computes y(i) on (x(i);bin⁡a(i)) within c(S(i)+1) bits.M \text{ computes } y(i) \text{ on } \bigl(x(i); \operatorname{bin} a(i)\bigr) \text{ within } c\,(S(i)+1) \text{ bits}.(3)✦

  2. If the codes d(y(i))d(y(i)) are computable from the constant family 00 in space SS on public inputs xx, there are a multitape Turing machine MM over XX with no argument tapes and outputs in YY, and a constant cc, such that for every i∈Ii \in I M computes y(i) on public input x(i) within c(S(i)+1) bits.M \text{ computes } y(i) \text{ on public input } x(i) \text{ within } c\,(S(i)+1) \text{ bits}.(4)✦

What Is Checked

The claims (3) and (4) are stated over computability in space SS by stack computations, with numbers held as stacks of binary digits, and over multitape Turing machines with a read-only public input and binary argument tapes, whose space is the size in bits of a window of cells of the work tapes.