Gray Codes With Constant Delay and Constant Auxiliary Space

Antoine Amarilli; Claire David; Mika\"el Monet; Nadime Francis; Victor Marsault; Yann Strozecki

arxiv: 2602.11791 · v2 · pith:GXZS4UVInew · submitted 2026-02-12 · 💻 cs.DS · cs.CC

Gray Codes With Constant Delay and Constant Auxiliary Space

Antoine Amarilli , Claire David , Nadime Francis , Victor Marsault , Mika\"el Monet , Yann Strozecki This is my paper

Pith reviewed 2026-05-22 11:15 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords Gray codesconstant delay enumerationconstant auxiliary spacetape machinesdeque machinesbinary string generationcombinatorial generation

0 comments

The pith

Binary strings of any length ℓ can be listed one by one in constant time per string using only constant extra memory.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces two new machine models, tape machines and deque machines, that can generate every possible binary string of length ℓ exactly once. Each new string is produced after a constant amount of work, and the machine needs only a fixed amount of memory beyond the ℓ bits that hold the current string. In the tape model a single head moves on a fixed-length tape and performs local edits before outputting the string. In the deque model the string sits in a double-ended queue and is changed only by constant-state push and pop operations at the ends. The authors also prove that simpler queue and stack models cannot complete the task even if delay is allowed to grow.

Core claim

The paper constructs a tape machine that produces a skew-tolerant quasi-Gray code with constant delay and a second tape machine that produces a true Gray code with constant delay. It further constructs deque machines that enumerate all binary words with constant delay. Both models enforce constant auxiliary space by definition because the only storage is the current word plus a constant-size head position or internal state. The main technical difficulty addressed is detecting termination correctly in the deque model.

What carries the argument

A tape machine or deque machine that stores the current binary word on a fixed-length structure and performs only local edits or endpoint push/pop operations while maintaining constant internal state and outputting each word in unit time.

If this is right

Gray-code sequences become feasible in memory-constrained environments such as embedded devices or streaming hardware.
Queue and stack models are provably insufficient for constant-auxiliary-space enumeration of binary strings.
The same models can be used to generate other combinatorial objects whose successive elements differ by local changes.
Termination detection in deque-based enumeration provides a template for bounded-memory streaming algorithms that must know when they have exhausted the space.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Hardware implementations could realize these machines with a small number of registers plus the string buffer, enabling constant-time generation on fixed-size circuits.
The approach may extend to enumerating strings over larger alphabets if the local-edit rules are generalized appropriately.
Similar constant-space models could be studied for generating de Bruijn sequences or other cyclic codes with bounded delay.

Load-bearing premise

The restricted operations of tape and deque machines still allow enough flexibility to reach every possible binary string while truly using only constant extra memory.

What would settle it

An explicit construction or proof showing that any machine obeying the tape or deque rules must sometimes take time linear in ℓ or must use auxiliary memory that grows with ℓ before producing the next output.

read the original abstract

We give the first two algorithms to enumerate all binary words of $\{0,1\}^\ell$ (like Gray codes) while ensuring that the delay and the auxiliary space is independent from $\ell$, i.e., constant time for each word, and constant memory in addition to the $\ell$ bits storing the current word. Our algorithms are given in two new computational models: tape machines and deque machines. We also study more restricted models, queue machines and stack machines, and show that they cannot enumerate all binary words with constant auxiliary space, even with unrestricted delay. A tape machine is a Turing machine that stores the current binary word on a single working tape of length $\ell$ (which never increases), using no other tape. The machine has a single head and must edit its tape to reach all possible words of $\{0,1\}^\ell$, and output them (in unit time, by entering special output states), with no duplicates. Hence a tape machine uses constant auxiliary space by definition (up to the head position). We construct a tape machine that achieves this task with constant delay between consecutive outputs, so that the machine implements a so-called skew-tolerant quasi-Gray code. We then construct a more involved tape machine that implements a Gray code. A deque machine stores the current binary word on a double-ended queue of length $\ell$, and stores a constant-size internal state. It works as a tape machine, except that it modifies the content of the deque by performing push and pop operations on the endpoints. Hence again a deque machine uses constant auxiliary space by definition. We construct deque machines that enumerate all words of $\{0,1\}^\ell$ with constant-delay. The main technical challenge in this model is to correctly detect when enumeration has finished.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit constructions for constant-delay full enumeration of the hypercube in two new constant-aux-space models, but the single-head tape version faces a plausible locality issue with head travel time.

read the letter

The main point is that this work supplies the first algorithms that enumerate every binary string of length ℓ with both delay and extra memory bounded by constants independent of ℓ, but only inside two freshly defined machine models: a single-head tape machine and a deque machine with constant internal state. They also prove that the more restricted queue and stack variants cannot do the job even if delay is allowed to grow. That separation is useful and cleanly stated. The constructions themselves are given directly rather than reduced to prior results, and the deque version explicitly tackles the termination-detection problem, which is the main technical hurdle they flag. If the proofs hold, this organizes a concrete open question about what resource bounds are possible for exhaustive generation in restricted models. Prior Gray-code literature typically permits logarithmic or linear auxiliary space or does not insist on constant delay, so the model definitions and the positive results are the actual novelty here. The impossibility results for queues and stacks add a nice negative counterpart. The soft spot is the constant-delay claim for the tape machine. A single head on a fixed tape of length ℓ must physically travel to edit a distant bit, and any complete enumeration will require flips whose positions differ by Ω(ℓ) at some steps. The paper treats head position as free auxiliary information, yet the number of transitions needed to move the head is still linear in the distance traveled. The stress-test concern therefore lands on the visible model definition; it would be good to see an explicit bound or an argument that the chosen enumeration order keeps all required head movements within a fixed constant. The deque construction may have a milder version of the same locality issue at the endpoints. This paper is aimed at researchers working on enumeration algorithms and constant-resource generation in restricted computational models. A reader already interested in fine-grained questions about Gray codes or space-bounded traversal would find the model distinctions and the impossibility results worth their time. It is coherent on its own terms and engages the literature directly, so it deserves a serious referee to verify the constructions and the delay bounds in detail. I would send it out for review.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to introduce the first algorithms for enumerating all binary words of length ℓ (i.e., all 2^ℓ strings) with constant delay between consecutive outputs and constant auxiliary space (beyond the ℓ bits of the current word) in two new models: tape machines (single-head Turing machine on a fixed-length tape) and deque machines (double-ended queue with constant-size internal state and endpoint push/pop operations). It provides explicit constructions achieving skew-tolerant quasi-Gray codes and full Gray codes in these models, along with impossibility results showing that queue machines and stack machines cannot enumerate all words even with unrestricted delay.

Significance. If the constructions and proofs hold, the result would be significant for combinatorial generation and the theory of Gray codes, as it achieves O(1) time per object and O(1) extra space in highly restricted computational models. The introduction of tape and deque machines as natural models for constant auxiliary space is a creative contribution, and the impossibility results for queue/stack machines help map the feasibility boundary. Credit is due for directly addressing the technical challenge of termination detection in the deque model.

major comments (2)

[Tape machine model definition] Tape machine model (abstract and presumed §2–3): the single-head restriction means each step moves the head by at most one cell. Any edit to a bit at distance d therefore requires Ω(d) steps. The constant-delay claim (independent of ℓ) is load-bearing for the central result, yet the model description treats head position as free auxiliary information without removing the movement cost. The construction must therefore ensure that every transition flips or edits only within a constant-radius window of the current head position while still visiting all 2^ℓ configurations without repetition; please supply the explicit transition function or invariant that enforces this locality bound.
[Deque machine construction] Deque machine construction (abstract): with only constant-size internal state, it is unclear how the machine tracks which of the 2^ℓ words have already been output or detects global termination. The abstract identifies termination detection as the main technical challenge, but the provided description does not sketch the state machine or invariant that solves it while preserving constant delay and no duplicates.

minor comments (2)

[Abstract] The term 'skew-tolerant quasi-Gray code' is used without a one-sentence definition or citation; adding this would improve readability for readers outside the immediate subfield.
[Notation] Notation for the length parameter is introduced as ℓ but should be checked for consistent use in all figure captions and pseudocode.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing the significance of the results for combinatorial generation and Gray codes. We address each major comment below and indicate the revisions planned for the next version of the manuscript.

read point-by-point responses

Referee: [Tape machine model definition] Tape machine model (abstract and presumed §2–3): the single-head restriction means each step moves the head by at most one cell. Any edit to a bit at distance d therefore requires Ω(d) steps. The constant-delay claim (independent of ℓ) is load-bearing for the central result, yet the model description treats head position as free auxiliary information without removing the movement cost. The construction must therefore ensure that every transition flips or edits only within a constant-radius window of the current head position while still visiting all 2^ℓ configurations without repetition; please supply the explicit transition function or invariant that enforces this locality bound.

Authors: We agree that the single-head movement cost must be explicitly bounded to support the constant-delay claim. In the tape-machine construction (Section 3), the enumeration follows a recursive segment-traversal strategy in which the head is always kept within a constant number of cells of the next bit to be flipped; each output transition therefore consists of a bounded number of head moves and local flips. The head position is not treated as free auxiliary information; its movement is charged to the delay and is provably bounded by a constant independent of ℓ via an invariant that the active region is always a fixed-size window around the current head. We will revise the manuscript to include the explicit finite-control transition table and a formal statement of the locality invariant. revision: yes
Referee: [Deque machine construction] Deque machine construction (abstract): with only constant-size internal state, it is unclear how the machine tracks which of the 2^ℓ words have already been output or detects global termination. The abstract identifies termination detection as the main technical challenge, but the provided description does not sketch the state machine or invariant that solves it while preserving constant delay and no duplicates.

Authors: We thank the referee for emphasizing the need for a clearer exposition of the termination mechanism. The deque-machine construction encodes the enumeration phase in the constant-size internal state together with the symbols at the two endpoints of the deque. An invariant ensures that the combination of state and endpoint symbols uniquely determines the next push/pop operation and whether the full set has been generated; termination occurs precisely when the deque and state return to the initial configuration after a complete cycle. This avoids storing any global history. We will expand the revised manuscript with an explicit sketch of the finite state machine and the key invariants that guarantee constant delay, absence of duplicates, and correct termination detection. revision: yes

Circularity Check

0 steps flagged

No circularity: direct algorithmic constructions in explicitly defined models

full rationale

The paper defines tape machines and deque machines with constant auxiliary space by construction (single head on fixed tape or constant-state deque with endpoint operations), then presents explicit constructions that achieve constant-delay enumeration of all 2^ℓ binary words. No equations, fitted parameters, or predictions appear; the results are algorithmic existence proofs rather than reductions of outputs to inputs. No self-citation chains or uniqueness theorems are invoked to justify the central claims. The models are stated up front as the intended formalization of constant auxiliary space, so the constructions are self-contained against external benchmarks and do not reduce by definition to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claim rests on the standard definition of Turing-machine tapes and queue/deque operations plus the new restriction that auxiliary space must remain constant independent of ell. No numerical free parameters are introduced. The two machine models are invented entities whose independent evidence is the explicit constructions claimed in the paper.

axioms (2)

standard math Standard single-tape Turing machine semantics with fixed tape length ell and unit-time output states.
Invoked when defining the tape machine model in the abstract.
domain assumption Deque operations (push/pop at endpoints) preserve the current word while using only constant internal state.
Core modeling choice for the deque machine.

invented entities (2)

tape machine no independent evidence
purpose: Model a constant-auxiliary-space enumerator with single-head fixed-length tape.
New model introduced to achieve the constant-delay result.
deque machine no independent evidence
purpose: Model a constant-auxiliary-space enumerator using endpoint push/pop operations.
Second new model for the constant-delay enumeration.

pith-pipeline@v0.9.0 · 5868 in / 1504 out tokens · 44037 ms · 2026-05-22T11:15:45.975580+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We construct a tape machine that achieves this task with constant delay between consecutive outputs... We then construct a more involved tape machine that implements a Gray code.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

A deque machine stores the current binary word on a double-ended queue of length ℓ, and stores a constant-size internal state.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.