OctoInformBeta

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

The indexed space calculus: One machine and one constant cc for every index: stacks within c(S(i)+1)c\,(S(i)+1) bits, computing bb from aa, and sizes linear in S+1S+1

Space bounds certified uniformly by a single stack 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

A space bound speaks of a family of computations. A function ff is computable in space SS when there is one machine and one constant such that on every input the machine computes ff and its work storage stays within the constant times SS, the read-only input not being counted. The library takes the family over an arbitrary index set II. At index ii the machine reads a public input word x(i)x(i) under the budget S(i)S(i); it is handed a number a(i)a(i) in binary and must leave a number b(i)b(i).

The machine is a deterministic stack machine, with read-only heads on the public input word and on argument words of bits, and with finitely many stacks of bits as its work storage; space is the length a stack reaches. The stacks of a machine are of two kinds: port stacks, which carry the data in and out, and hidden stacks, which are empty at the start and at the end.

Stack Machines

A head direction is one of the three moves LL (left), NN (stay) and RR (right).✦ A symbol with endmarkers over an alphabet AA is a symbol of AA, the left endmarker ⊳\triangleright or the right endmarker ⊲\triangleleft.✦ A head on a word w=w1⋯wnw = w_1 \cdots w_n over AA stands at a position p∈ℕp \in \mathbb{N}, and the mark it reads there is wˆ(p)={⊳if p=0,wpif 1≤p≤n,⊲if p>n.\hat w(p) = \begin{cases} \triangleright & \text{if } p = 0,\\ w_p & \text{if } 1 \le p \le n,\\ \triangleleft & \text{if } p > n. \end{cases}(1)✦ A head at position pp on ww moves by a direction: NN leaves it at pp, LL takes it to p−1p - 1 but leaves it at 00, and RR takes it to p+1p + 1 unless p>np > n, on the right endmarker, where it stays.✦

The machine inputs ξ\xi over an alphabet XX with argument tapes indexed by a set JJ consist of a public input word u∈X*u \in X^* and an argument word vj∈{0,1}*v_j \in \{0,1\}^* for each j∈Jj \in J, all of them read-only.✦ The input head positions rr are a position r0r_0 for the head on uu and a position rjr_j for the head on each vjv_j, all equal to 00 in the home position, where every head starts.✦ At rr the heads read the marks uˆ(r0)\hat u(r_0) and vˆj(rj)\hat v_j(r_j), j∈Jj \in J, of (1).✦ An input head advance is a direction for each head✦, and advancing the heads by it moves each one on its own word✦.

A stack is a word over {0,1}\{0,1\} read from the top, and ε\varepsilon is the empty stack. A stack operation is keep, push β\beta for a bit β\beta, or pop, four operations in all✦, acting on a stack ℓ\ell by keep(ℓ)=ℓ,pushβ(ℓ)=βℓ,pop(βℓ)=ℓ,pop(ε)=ε.\mathrm{keep}(\ell) = \ell, \qquad \mathrm{push}_\beta(\ell) = \beta\ell, \qquad \mathrm{pop}(\beta\ell) = \ell, \qquad \mathrm{pop}(\varepsilon) = \varepsilon.(2)✦

A store ss for argument tapes indexed by JJ and stacks indexed by a set KK, the stacks and head positions of a machine, consists of input head positions and a stack sks_k for each k∈Kk \in K.✦ The top of stack kk of ss is the first bit of sks_k, or nothing when sks_k is empty.✦ A stack change for argument tapes indexed by JJ and stacks indexed by KK consists of an input head advance and a stack operation for each k∈Kk \in K.✦ Performing a stack change on a store ss over machine inputs ξ\xi advances the heads of ss on ξ\xi by the input head advance of the change and applies to each sks_k the stack operation of the change for kk, by (2).✦

A stack machine MM with input alphabet XX, argument tapes indexed by JJ, stacks indexed by KK and halting labels in a set YY consists of a finite set QQ of states, a start state q0∈Qq_0 \in Q and a transition table δ\delta.✦ Given a state, the marks under the input heads and the top of each stack, δ\delta either halts with a label in YY or prescribes an action: a stack change and a next state.

Runs Within a Space Bound

A configuration of MM is a pair (q,s)(q, s) of a state and a store.✦ The step of MM on machine inputs ξ\xi at (q,s)(q, s) consults δ\delta at qq, at the marks under the heads of ss and at the tops of the stacks of ss. The step halts with a label yy when δ\delta halts with yy there; when δ\delta prescribes an action, the step moves to (q′,s′)(q', s'), with q′q' the next state of the action and s′s' the result of performing the change of the action on ss over ξ\xi.✦ A store fits within BB bits per stack when each of its stacks has length at most BB.✦

A deterministic halting run of a map ff, which at each configuration either halts with a label or moves to a next configuration, from CC to C′C' with label yy under an invariant PP, is a chain C=C0→C1→⋯→Cm=C′,m≥0,C = C_0 \to C_1 \to \cdots \to C_m = C', \qquad m \ge 0,(3)✦ in which ff moves each ClC_l to Cl+1C_{l+1} and halts at C′C' with label yy, every ClC_l, the last included, satisfying PP. A bounded run of MM on ξ\xi within BB bits is a run (3) of the step of MM on ξ\xi under the invariant that the store fits within BB bits per stack.✦ An execution of MM on ξ\xi within BB bits per stack from a store ss to a store tt with label yy, written M:s⇒Bξt/yM\colon s \Rightarrow^{\xi}_{B} t \,/\, y, is a bounded run from (q0,s)(q_0, s) to (q,t)(q, t) with label yy for some state qq.✦

The initial store with stack contents (dk)k∈K(d_k)_{k \in K} has every head at home and dkd_k on stack kk.✦ For a store ss with stacks indexed by LL and a set KK, the store s+Ks^{+K} with extra stacks indexed by KK has the head positions and the stacks of ss and an empty stack for each k∈Kk \in K.✦ A number nn as a stack is the initial store [n][n] with no argument tapes and a single stack holding the binary digits of nn, least significant on top and without leading zeros.✦ A word ww over XX as public input is the machine inputs ⟨w⟩\langle w \rangle with ww on the public tape and no argument tapes.✦

The Definition

Definition 1. Let II be a set and SS a family of natural numbers indexed by II, the space bound. Let xx be a family of machine inputs over XX with argument tapes indexed by JJ, aa and bb families of stores with port stacks indexed by LL, and yy a family of labels in YY, all indexed by II. The families xx, aa, bb and yy form a stack computation in space SS when there are a finite set KK of hidden stacks, a stack machine MM with input alphabet XX, argument tapes indexed by JJ, stacks indexed by L⊔KL \sqcup K and halting labels in YY, and a constant c∈ℕc \in \mathbb{N} such that M:a(i)+K⇒c(S(i)+1)x(i)b(i)+K/y(i)for every i∈I.M\colon a(i)^{+K} \Rightarrow^{x(i)}_{c\,(S(i)+1)} b(i)^{+K} \,/\, y(i) \qquad \text{for every } i \in I.(4)✦ The case of a single port stack is the computation of one number from another. For a family xx of words over XX and families aa and bb of natural numbers indexed by II, bb is computable from aa in space SS on public input xx when there are a finite set KK of hidden stacks, a stack machine MM with input alphabet XX, no argument tapes, one port stack besides those in KK and the single halting label *\ast, and a constant c∈ℕc \in \mathbb{N} such that M:[a(i)]+K⇒c(S(i)+1)⟨x(i)⟩[b(i)]+K/*for every i∈I.M\colon [a(i)]^{+K} \Rightarrow^{\langle x(i) \rangle}_{c\,(S(i)+1)} [b(i)]^{+K} \,/\, \ast \qquad \text{for every } i \in I.(5)✦ A family ff of natural numbers indexed by II is linear in S+1S + 1 when there is a constant c∈ℕc \in \mathbb{N} such that f(i)≤c(S(i)+1)for every i∈I.f(i) \le c\,(S(i)+1) \qquad \text{for every } i \in I.(6)✦ A family ff of natural numbers indexed by II satisfies the bit length bound for SS when its bit lengths |f(i)||f(i)|, the numbers of binary digits of the f(i)f(i), are linear in S+1S + 1, that is, when there is a constant c∈ℕc \in \mathbb{N} such that |f(i)|≤c(S(i)+1)for every i∈I.|f(i)| \le c\,(S(i)+1) \qquad \text{for every } i \in I.(7)✦

What Is Checked

The definitions (4) and (5) are stated over stack machines with read-only heads and stacks of bits, their executions within a bound on the length of every stack, stores extended by empty hidden stacks, numbers written in binary on one stack and words given as public input; (6) and (7) are stated over families of natural numbers alone.