OctoInformBeta

OpenAI preprint, September 2026 · §11. Uniform controller implementation · §11

Lemma 11.5 [Inverse contour]: The contour predecessor undoes the successor on live incidences, and the walk from a root reaches every incidence of its tree and returns

The contour walk of an indexed forest is reversible.

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 machine with logarithmic work space cannot store the path from the root of a tree to the node it is visiting, yet it can walk around the tree’s contour. It keeps only the current node and a counter over that node’s children, and each step descends into a child, moves the counter on, or climbs back to the parent. Such walks run inside reversible small-space computations, where every step forward must be undone by a step back computed from the same local data. The question is whether the step back does undo the step forward, and whether the walk started at a root passes through every position of the root’s tree and comes back to where it began.

Indexed Forests

A node is a pair v=(a,b)v = (a, b) of natural numbers, and its label is its first coordinate, ℓ(v)=a\ell(v) = a.✦

An indexed forest F=(V,r,π,κ)F = (V, r, \pi, \kappa) consists of a finite set VV of nodes, a breadth function r:ℕ→ℕr\colon \mathbb{N} \to \mathbb{N}, a parent map π\pi that gives each node at most one parent node, and a child map κ\kappa that gives each node uu and index i∈ℕi \in \mathbb{N} at most one child node κ(u,i)\kappa(u, i), such that, with β(v)=r(ℓ(v))\beta(v) = r(\ell(v)) the breadth of a node vv, parents and children agree on VV: for all nodes u,vu, v and every index ii, v∈V,π(v)=u⇒u∈V,ℓ(u)<β(v),ℓ(v)<β(u),κ(u,ℓ(v))=v,u∈V,κ(u,i)=v⇒v∈V,π(v)=u,ℓ(v)=i.\begin{aligned} v \in V,\ \pi(v) = u \;&\Longrightarrow\; u \in V,\ \ell(u) < \beta(v),\ \ell(v) < \beta(u),\ \kappa(u, \ell(v)) = v,\\ u \in V,\ \kappa(u, i) = v \;&\Longrightarrow\; v \in V,\ \pi(v) = u,\ \ell(v) = i. \end{aligned}(1)✦

A root of FF is a node of VV with no parent. A node vv descends from a node SS in nn generations when there are nodes v=v0,v1,…,vn=Sv = v_0, v_1, \dots, v_n = S of VV with π(vj)=vj+1\pi(v_j) = v_{j+1} for every j<nj < n.✦

The Contour Walk

An incidence of FF is a pair (v,i)(v, i) of a node vv and a counter i∈ℕi \in \mathbb{N}✦; it is live when v∈Vv \in V and i≤β(v)i \le \beta(v).✦ An incidence (v,i)(v, i) lies in the tree of a node SS when it is live and vv descends from SS in some number of generations.✦

The contour successor of FF is the map σ\sigma on incidences given by σ(v,i)={(w,0)if i<β(v) and κ(v,i)=w,(v,i+1)if i<β(v) and v has no child at i,(u,ℓ(v)+1)if i≥β(v) and π(v)=u,(v,0)if i≥β(v) and v has no parent.\sigma(v, i) = \begin{cases} (w, 0) & \text{if } i < \beta(v) \text{ and } \kappa(v, i) = w,\\ (v, i+1) & \text{if } i < \beta(v) \text{ and } v \text{ has no child at } i,\\ (u, \ell(v)+1) & \text{if } i \ge \beta(v) \text{ and } \pi(v) = u,\\ (v, 0) & \text{if } i \ge \beta(v) \text{ and } v \text{ has no parent}. \end{cases}(2)✦

The contour predecessor of FF is the map τ\tau on incidences given by τ(v,i)={(u,ℓ(v))if i=0 and π(v)=u,(v,β(v))if i=0 and v has no parent,(w,β(w))if i≥1 and κ(v,i−1)=w,(v,i−1)if i≥1 and v has no child at i−1.\tau(v, i) = \begin{cases} (u, \ell(v)) & \text{if } i = 0 \text{ and } \pi(v) = u,\\ (v, \beta(v)) & \text{if } i = 0 \text{ and } v \text{ has no parent},\\ (w, \beta(w)) & \text{if } i \ge 1 \text{ and } \kappa(v, i-1) = w,\\ (v, i-1) & \text{if } i \ge 1 \text{ and } v \text{ has no child at } i-1. \end{cases}(3)✦

For a map ff from a set to itself, fnf^n is its nn-fold iterate, with f0f^0 the identity✦, and qq is reached from pp under ff, written p→f*qp \to_f^{*} q, when q=fn(p)q = f^n(p) for some n≥0n \ge 0.✦

The Claim

Theorem 1. Let FF be an indexed forest with contour successor σ\sigma and contour predecessor τ\tau. If pp is a live incidence of FF, then σ(p)\sigma(p) is live and τ(σ(p))=p.\tau(\sigma(p)) = p.(4)✦ If SS is a root of FF, then every incidence pp in the tree of SS satisfies (S,0)→σ*p,(S, 0) \to_\sigma^{*} p,(5)✦ and there is an n≥0n \ge 0 with σn+1(S,0)=(S,0).\sigma^{n+1}(S, 0) = (S, 0).(6)✦

In the paper, the result reads: for a finite deterministic graph as in Lemma 11.4 with a canonical success halt, the undirected component is a tree directed toward the halt, and there are mutually inverse next-mark and previous-mark operations on its contour, whose marks are the root sentinel and one occurrence of each canonical initiation, and these operations need only the current program state and bounded incidence control.

What Is Checked

The claim is stated over an indexed forest FF whose parent and child maps agree as in (1), over its contour successor (2) and contour predecessor (3) on incidences, and over live incidences, the trees of its roots and the iterates of σ\sigma.