OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1 (setting): the explicit scheduling problem and machine model: Explicit precedence instances and time-bounded computation on a fixed deterministic multitape Turing machine

Scheduling requests and their correct answers.

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 scheduling question concerns the number of time slots needed by unit jobs on three identical machines, subject to directed precedence constraints. Let n∈ℕn\in\mathbb N be the number of jobs and V={1,…,n}V=\{1,\ldots,n\} their names. A request has an optional deadline: d=⊥d=\bot denotes its absence, and d=Td=T its presence, for T∈ℕT\in\mathbb N.

Binary Words

Write b(m)b(m) for the underlying binary representation of a natural number mm. Juxtaposition denotes concatenation, and |b||b| denotes word length. The self-delimiting integer word e(m)e(m) and the length-prefixed list word ℓf(x1,…,xr)\ell_f(x_1,\ldots,x_r), for a map ff to binary words, are defined by (1). e(m)=1|b(m)|0b(m),ℓf(x1,…,xr)=e(r)f(x1)⋯f(xr).e(m)=1^{|b(m)|}0b(m),\qquad \ell_f(x_1,\ldots,x_r)=e(r)f(x_1)\cdots f(x_r).(1)

For an assignment τ:V→ℕ\tau:V\to\mathbb N, its schedule list 𝒔(τ)\mathbf s(\tau) records its values in job order.✦ The answer word A(a)A(a) for either the absence a=⊥a=\bot of a schedule or a list aa of slot numbers is the binary word defined in (2). 𝒔(τ)=(τ(1),…,τ(n)),A(a)={0,a=⊥,1ℓe(a),a is a list of natural numbers.\mathbf s(\tau)=(\tau(1),\ldots,\tau(n)),\qquad A(a)= \begin{cases} 0,&a=\bot,\\ 1\ell_e(a),&a\text{ is a list of natural numbers}. \end{cases}(2)

The Definition

Definition 1. A scheduling instance GG on nn jobs is a finite ordered list ℰ\mathcal E of precedence edges, as in (3), where a star denotes all finite lists. G=ℰ∈(V×V)*.G=\mathcal E\in(V\times V)^*.(3)✦ The precedence relation →G\to_G of a scheduling instance G=ℰG=\mathcal E is the binary relation on its jobs for which u→Gvu\to_G v holds when (u,v)(u,v) occurs in ℰ\mathcal E.✦ The reachability relation →G+\to_G^+ of a scheduling instance GG is the binary relation on its jobs defined by connection by a nonempty directed path in GG. An acyclic instance GG is an instance satisfying (4). acyclic⁡(G)quad⇔{v∈V:v→G+v}=⌀.\operatorname{acyclic}(G)quad\Longleftrightarrow\quad \{v\in V:v\to_G^+v\}=\varnothing.(4)✦

A feasible schedule τ:V→ℕ\tau:V\to\mathbb N for GG by deadline T∈ℕT\in\mathbb N is an assignment satisfying (5). Feas⁡G(T,τ)⇔{1≤τ(v)≤Tfor every v∈V,|{v∈V:τ(v)=t}|≤3for every t∈ℕ,τ(u)<τ(v)whenever u→Gv.\operatorname{Feas}_G(T,\tau)\quad\Longleftrightarrow\quad \begin{cases} 1\le\tau(v)\le T&\text{for every }v\in V,\\ |\{v\in V:\tau(v)=t\}|\le3&\text{for every }t\in\mathbb N,\\ \tau(u)<\tau(v)&\text{whenever }u\to_G v. \end{cases}(5)✦

The input word in⁡(G,d)\operatorname{in}(G,d) for an instance GG and request dd is the binary word in (6). in⁡(G,d)={0,d=⊥,1e(T),d=Tℓe(1,…,n)ℓ(u,v)↦e(u)e(v)(ℰ).\operatorname{in}(G,d)= \begin{cases} 0,&d=\bot,\\ 1e(T),&d=T \end{cases} \;\ell_e(1,\ldots,n)\, \ell_{(u,v)\mapsto e(u)e(v)}(\mathcal E).(6)✦

A correct output ww for GG and request dd is a binary word satisfying (7); schedule variables range over maps V→ℕV\to\mathbb N. Correct⁡G(d,w)⇔{∃T,τ:Feas⁡G(T,τ)∧T=min⁡{t∈ℕ:∃σFeas⁡G(t,σ)}∧w=A(𝒔(τ))d=⊥,(w=A(⊥)∧{τ:Feas⁡G(T,τ)}=⌀)∨∃τ:Feas⁡G(T,τ)∧w=A(𝒔(τ))d=T.\operatorname{Correct}_G(d,w)\quad\Longleftrightarrow\quad \begin{cases} \begin{aligned} \exists T,\tau:\ &\operatorname{Feas}_G(T,\tau)\\ &{}\land T=\min\{t\in\mathbb N:\exists\sigma\, \operatorname{Feas}_G(t,\sigma)\}\\ &{}\land w=A(\mathbf s(\tau)) \end{aligned} &d=\bot,\\[5pt] \begin{aligned} &\bigl(w=A(\bot)\ \land \{\tau:\operatorname{Feas}_G(T,\tau)\}=\varnothing\bigr)\\ &{}\lor\exists\tau:\ \operatorname{Feas}_G(T,\tau)\ \land w=A(\mathbf s(\tau)) \end{aligned} &d=T. \end{cases}(7)✦

For k,q,g∈ℕk,q,g\in\mathbb N, let I={0,…,k}I=\{0,\ldots,k\} index the tapes, let Q={0,…,q}Q=\{0,\ldots,q\} be the states, and let Γ={0,…,g+2}\Gamma=\{0,\ldots,g+2\} be the tape alphabet. A deterministic multitape Turing machine MM is a partial transition function of the form (8). M=δ:Q×ΓI⇀Q×(Γ×{𝖫,𝖱,𝖲})I.M=\delta:Q\times\Gamma^I\rightharpoonup Q\times\bigl(\Gamma\times\{\mathsf L,\mathsf R,\mathsf S\}\bigr)^I.(8)✦ Here 𝖫\mathsf L, 𝖱\mathsf R and 𝖲\mathsf S mean move left, move right and stay. Symbol 00 is blank; binary bits 00 and 11 are written as symbols 11 and 22, respectively.✦ A configuration CC of a deterministic multitape Turing machine MM is a state in QQ together with one tape with a head for each i∈Ii\in I.✦

The initial configuration C0(M,x)C_0(M,x) of a deterministic multitape Turing machine MM on a binary input word xx is the configuration with state 00, input xx on tape 00 with its head at the first symbol, and blank tapes elsewhere.✦ A single computation step from a configuration CC of MM exists exactly when δ\delta is defined at its current state and scanned symbols; the next configuration has the returned state, and on each tape the prescribed symbol is written before the prescribed head move is made.✦ A configuration CC of the machine MM is halted, denoted by H(C)H(C), when its transition function δ\delta is undefined at CC. For a deterministic multitape Turing machine MM, a binary input word xx and a time t∈ℕt\in\mathbb N, the run configuration Ct(M,x)C_t(M,x) is the configuration obtained by tt steps from C0(M,x)C_0(M,x), retaining a halted configuration unchanged.✦

Let R0(C)R_0(C) be the tape content from the head rightwards on tape 00, with trailing blanks identified, and let w¯\overline w be the symbol word for ww followed by blanks. The time-bounded output relation Produces⁡M(x,w,B)\operatorname{Produces}_M(x,w,B), for binary words x,wx,w and a bound B∈ℕB\in\mathbb N, is defined by (9). Produces⁡M(x,w,B)⇔∃t∈{0,…,B}:H(Ct(M,x))∧R0(Ct(M,x))=w¯.\operatorname{Produces}_M(x,w,B)\quad\Longleftrightarrow\quad \exists t\in\{0,\ldots,B\}: H(C_t(M,x))\ \land\ R_0(C_t(M,x))=\overline w.(9)✦

In the paper, the result reads: the input lists the vertices 1,…,n1,\ldots,n and edges of a finite directed acyclic graph with n≥1n\ge1, a supplied deadline is an integer 1≤T≤n1\le T\le n, and a feasible schedule assigns each unit job a slot in {1,…,T}\{1,\ldots,T\}, puts at most three jobs in each slot, and places every edge’s source in an earlier slot than its target.

What Is Checked

The definitions are stated over finite edge lists and binary words, with natural deadline and time bounds and fixed finite machine parameters k,q,gk,q,g.