OctoInformBeta

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

§1 (setting): the machine model and the classes L, RL, BPL: Deterministic, one-sided error and two-sided error classes over machines with endmarked input, a coin bit per step and space counted in visited cells

Coin-flipping machines and the three logarithmic-space classes.

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 classes 𝖫\mathsf{L} (deterministic logarithmic space), 𝖱𝖫\mathsf{RL} (randomized logarithmic space) and 𝖡𝖯𝖫\mathsf{BPL} (bounded-error probabilistic logarithmic space) collect the languages decidable with logarithmically many bits of working memory, deterministically, with one-sided error and with two-sided error respectively. Stated exactly, each depends on the conventions of the machine model: how the input is delimited, how coins are read, what counts as a cell of space, when a run must stop and at which time the acceptance probability is taken. The library fixes these conventions in one concrete model and defines the three classes over it.

Words, Inputs and Machines

A binary word xx of length nn is a finite sequence of bits, x=x1x2⋯xn∈{0,1}*,|x|=n,x = x_1 x_2 \cdots x_n \in \{0,1\}^*, \qquad |x| = n,(1)✦ and a language AA is a set of binary words, A⊆{0,1}*.A \subseteq \{0,1\}^*.(2)✦

The input tape holds xx between a left endmarker ⊳\triangleright and a right endmarker ⊲\triangleleft: its cells 0,1,…,n+10, 1, \dots, n+1 carry xˆ=⊳x1⋯xn⊲\hat x = \triangleright\, x_1 \cdots x_n \,\triangleleft✦, so an input head reads a symbol of Σ={⊳,0,1,⊲}\Sigma = \{\triangleright, 0, 1, \triangleleft\}.✦ A head moves in a direction of D={−1,0,+1}D = \{-1, 0, +1\} (left, stay, right).✦ A machine reads the input with input heads and has work tapes, each indexed by ℤ\mathbb{Z} and scanned by a work head that moves freely on ℤ\mathbb{Z}; an input head that would leave the cells 0,…,n+10, \dots, n+1 stays where it is.✦

A machine MM with states Q={0,1,…,q}Q = \{0, 1, \dots, q\}, ww work tapes and hh input heads consists of an initial state s0∈Qs_0 \in Q, an output map out:Q→{0,1,⊥}\mathrm{out}\colon Q \to \{0, 1, \bot\} and a transition function δ:Q×Σh×{0,1}w×{0,1}→Q×{0,1}w×Dw×Dh.\delta\colon Q \times \Sigma^h \times \{0,1\}^w \times \{0,1\} \longrightarrow Q \times \{0,1\}^w \times D^w \times D^h.(3)✦ States with output 11 are accepting and states with output 00 are rejecting; together they are the halting states, and the states with output ⊥\bot are not halting.

Configurations and Runs

A configuration CC of MM on inputs of length nn is a quadruple C=(s,i,p,u)∈Q×{0,…,n+1}h×ℤw×({0,1}ℤ)wC = (s, i, p, u) \in Q \times \{0, \dots, n+1\}^h \times \mathbb{Z}^w \times \bigl(\{0,1\}^{\mathbb{Z}}\bigr)^w(4)✦ of a state, the cells of the hh input heads, the cells of the ww work heads and the contents of the ww work tapes, one bit in every cell of ℤ\mathbb{Z}. Its state is written s(C)s(C), and the cell of work head kk is written pk(C)p_k(C).

The step of MM on input xx with coin bit bb is the map on configurations that fixes every configuration in a halting state and sends any other C=(s,i,p,u)C = (s, i, p, u) to stepx,b(C)=(s′,i+e,p+d,u′),(s′,β,d,e)=δ(s,xˆ(i),u(p),b).\mathrm{step}_{x,b}(C) = (s', i + e, p + d, u'), \qquad (s', \beta, d, e) = \delta\bigl(s, \hat x(i), u(p), b\bigr).(5)✦ Here xˆ(i)=(xˆi1,…,xˆih)\hat x(i) = (\hat x_{i_1}, \dots, \hat x_{i_h}) are the symbols under the input heads, u(p)=(u1(p1),…,uw(pw))u(p) = (u_1(p_1), \dots, u_w(p_w)) are the bits under the work heads, u′u' is uu with the bit βk\beta_k written in cell pkp_k of work tape kk, and the input heads move by ee under the endmarker rule.

A coin tape rr is an infinite sequence of bits r0r1r2⋯r_0 r_1 r_2 \cdots.✦ The initial configuration CinitC_{\mathrm{init}} of MM on inputs of length nn is the configuration in the initial state s0s_0 with every input head and every work head at its starting cell and the work tapes in their starting contents. The run of MM on a word xx with coin tape rr is the sequence of configurations Ct(x,r)C_t(x, r) that starts at CinitC_{\mathrm{init}} of MM on inputs of length |x||x| and spends the coin rtr_t on the step from time tt to time t+1t+1: C0(x,r)=Cinit,Ct+1(x,r)=stepx,rt(Ct(x,r)).C_0(x, r) = C_{\mathrm{init}}, \qquad C_{t+1}(x, r) = \mathrm{step}_{x, r_t}\bigl(C_t(x, r)\bigr).(6)✦

Space, Time and Acceptance

The space spaceM(x,r,t)\mathrm{space}_M(x, r, t) used by MM on xx with coin tape rr through time tt is the number of distinct cells its work heads visit up to time tt, counted tape by tape: spaceM(x,r,t)=∑k=1w|{pk(Cτ(x,r)):0≤τ≤t}|.\mathrm{space}_M(x, r, t) = \sum_{k=1}^{w} \bigl|\{\, p_k(C_\tau(x, r)) : 0 \le \tau \le t \,\}\bigr|.(7)✦

A machine MM runs in logarithmic space when there is an integer c≥1c \ge 1 such that for every word xx, coin tape rr and time tt spaceM(x,r,t)≤c⌈log⁡2(|x|+2)⌉.\mathrm{space}_M(x, r, t) \le c \, \lceil \log_2(|x| + 2) \rceil.(8)✦

The machine MM is deterministic when its transition function ignores the coin bit: δ(s,σ,v,0)=δ(s,σ,v,1)for all s∈Q,σ∈Σh,v∈{0,1}w.\delta(s, \sigma, v, 0) = \delta(s, \sigma, v, 1) \qquad \text{for all } s \in Q,\ \sigma \in \Sigma^h,\ v \in \{0,1\}^w.(9)✦

On a word xx, the machine MM halts by time tt when its run is in a halting state at time tt whatever the coins: out(s(Ct(x,r)))∈{0,1}for every coin tape r.\mathrm{out}\bigl(s(C_t(x, r))\bigr) \in \{0, 1\} \qquad \text{for every coin tape } r.(10)✦

The machine MM decides a language AA when on every word xx there is a time tt at which, whatever the coins, it has halted with the right answer: out(s(Ct(x,r)))=𝟏A(x)for every coin tape r,\mathrm{out}\bigl(s(C_t(x, r))\bigr) = \mathbf{1}_A(x) \qquad \text{for every coin tape } r,(11)✦ where 𝟏A(x)\mathbf{1}_A(x) is 11 for x∈Ax \in A and 00 for x∉Ax \notin A.

The acceptance probability PM(x,t)P_M(x, t) of MM on xx at time tt is the fraction of coin strings β∈{0,1}t\beta \in \{0,1\}^t whose run, on the coin tape β\beta followed by zeros, is in an accepting state at time tt: PM(x,t)=2−t|{β∈{0,1}t:out(s(Ct(x,β0∞)))=1}|.P_M(x, t) = 2^{-t} \, \bigl|\{\, \beta \in \{0,1\}^t : \mathrm{out}\bigl(s(C_t(x, \beta 0^\infty))\bigr) = 1 \,\}\bigr|.(12)✦

The polynomial clock Tc,kT_{c,k} with constants c,k∈ℕc, k \in \mathbb{N} is the time bound on inputs of length nn Tc,k(n)=c(n+2)k.T_{c,k}(n) = c\,(n+2)^k.(13)✦

The Definition

Definition 1. The class 𝖫\mathsf{L} is the set of languages 𝖫={A:some deterministic machine running in logarithmic space decides A}.\mathsf{L} = \bigl\{\, A : \text{some deterministic machine running in logarithmic space decides } A \,\bigr\}.(14)✦ A language AA is in 𝖱𝖫\mathsf{RL} when there are a machine MM running in logarithmic space and integers c≥1c \ge 1 and k≥0k \ge 0 such that, on every word xx of length nn, MM halts by time T=Tc,k(n)T = T_{c,k}(n) and PM(x,T)≥12 if x∈A,PM(x,T)=0 if x∉A.P_M(x, T) \ge \tfrac12 \ \text{ if } x \in A, \qquad P_M(x, T) = 0 \ \text{ if } x \notin A.(15)✦ A language AA is in 𝖡𝖯𝖫\mathsf{BPL} when the same holds with the acceptance condition replaced by PM(x,T)≥23 if x∈A,PM(x,T)≤13 if x∉A.P_M(x, T) \ge \tfrac23 \ \text{ if } x \in A, \qquad P_M(x, T) \le \tfrac13 \ \text{ if } x \notin A.(16)✦

In the paper, the definitions read: a machine has a finite control, an endmarked read-only input, finitely many work tapes and fresh fair coin bits, and its space counts the work cells it traverses; 𝖫\mathsf{L} consists of the languages decided by deterministic machines in space O(log⁡(n+2))O(\log(n+2)), 𝖱𝖫\mathsf{RL} of those decided by randomized machines running in polynomial time in this space with acceptance probability 00 on inputs outside the language and at least 1/21/2 on inputs in it, and 𝖡𝖯𝖫\mathsf{BPL} of those decided by the same machines with acceptance probability at most 1/31/3 on inputs outside the language and at least 2/32/3 on inputs in it.

What Is Checked

The classes (14), (15) and (16) are stated over binary words (1) and languages (2), the machine (3) with its configurations (4), steps (5) and runs (6), and the notions built on it: the space used (7), running in logarithmic space (8), determinism (9), halting by a time (10), deciding a language (11), the acceptance probability (12) and the polynomial clock (13).