Gray Codes with Constant Delay
and Constant Auxiliary Space

We first present tape machines, which are a kind of deterministic Turing machines that also resemble linear bounded automata [18]. Tape machines have a finite set of states, some of which are distinguished as output states, along with a single working tape and one head. The tape alphabet is $\{0,1\}$. The tape is initialized with the word $0^{\mathrm{\ell }}$ and stays of length $\mathrm{\ell }$ throughout. Like a Turing machine, a tape machine updates its tape based on its internal state and on the symbol under the head. It may then change the bit under the head, move its head left or right, and change its state. Note that the machine only has a single working tape, and no input or output tape. The word on the working tape is produced in unit time whenever an output state is reached.

This definition ensures that tape machines satisfy our constant-memory requirement: in addition to the working tape used to store the current word, the only auxiliary memory that they use is their internal state, from a constant-sized set of states which is independent from $\mathrm{\ell }$. Our goal is to design a Hamiltonian tape machine: for every word length $\mathrm{\ell }\ge 1$, when started on the word $0^{\mathrm{\ell }}$, the machine must produce all the words of ${\{0,1\}}^{\mathrm{\ell }}$ exactly once (i.e., each word is seen exactly once in an output state), and must then halt. Further, the machine must be constant-delay: there must be a constant $B$ independent from $\mathrm{\ell }$ such that the machine produces a new word after at most $B$ steps.

It is not obvious at all from the definition that Hamiltonian constant-delay tape machines exist, because they have no working memory beyond the tape used to store the words to be produced. In particular, the constant-delay requirement implies that the bits flipped from one word to the next must be at constant distance from one another (i.e., if we flip bit $i$ and then bit $j$ then the distance $|j-i|$ must be small). This latter requirement is not satisfied by the BRGC, but it is obeyed by some Gray codes, for instance, the $k$-skew-tolerant codes of [25] (attributed to [30]), where $k$ is the maximum distance between consecutively flipped bits. Our first contribution is to show that we can in fact design a Hamiltonian tape machine. What is more, we can strengthen the result and ensure that the machine is Hamming-1, i.e., the Hamming distance between any two successively produced words is 1: this property is satisfied by Gray codes such as the BRGC or the ones of [25]). Formally:

The result is intuitively established by implementing a traversal of a complete binary tree with the “even-odd trick” [17, 28], and refining it to make it Hamming-1. It turns out that our machine implements a code closely related to [25, Construction A] (with $k=3$), despite having no apparent relationship to the simple inductive definition of [25]. Thus, we can also see Theorem 1.1 as a construction showing that (a variant of) the code of [25, Construction A] can be implemented to use only constant delay and constant auxiliary memory. We explain how the two codes relate in [1, Appendix B]. We also show that our machine can implement counters by detailing the decrement function, and discuss rank and unrank functions in [1, Appendix B]. We relate our implementation to works using the DAT model [16, 6, 22], and show that it is competitive with the best counter implementations in the RAM model [14].

Our second contribution is to study a computational model that we call the deque machine, in line with other works studying machines augmented with deques [4, 21]. In this model, the word is stored in a double-ended queue, the machine can read the first and last bits of the word, and it can perform push and pop operations on the left and right endpoints. The motivation for this model is to ensure that the entire configuration of the machine consists of the current word plus the finite state, in contrast with tape machines that arguably hide $\lceil \log \mathrm{\ell }\rceil$ auxiliary memory bits in the position of the head. Moreover, deque machines are effective models to implement push-pop edits on words, as studied in [3] for enumeration of regular languages. Finally, allowing only endpoints modifications is natural in other contexts, such as enumerating walks in a graph, which is a core task in modern graph database query processing [12]. Indeed, the task of enumerating binary words studied in the present paper is a first step towards the efficient enumeration of walks in graphs: it corresponds to walk enumeration for the specific graph that has one vertex and two self-loops labeled 0 and 1.

It is known that we can indeed enumerate all binary words with constantly many endpoint modifications between each word, as follows from universal words [10] or Hamiltonian paths in so-called Shuffle Exchange networks [15]. So our second contribution is to design deque machines that can produce such codes while only using constant auxiliary memory:

The first step to show this result is to notice that the tape machine from Theorem 1.1 can be adapted into a constant delay deque machine that produces all binary words once but then continues to run indefinitely and produces duplicates. As it turns out, the main challenge is to detect when the enumeration is complete, for which we present two alternative techniques which we hope can be of independent interest.

Our third contribution is to show that the model of deque machine is “minimal” in the sense that further restricting the edit operations makes it impossible to design Hamiltonian machines. We first study queue machines, where insertion is only possible at the left endpoint. We remind that it is indeed possible to visit all words of ${\{0,1\}}^{\mathrm{\ell }}$ via left-push and right-pop using the construction of universal words, but show that this cannot be achieved by a queue machine (i.e., with constant auxiliary memory), even without the constant-delay requirement. We next study stack machines, where we push and pop at one end only, and show that in a sense such machines also cannot satisfy the constant-memory requirement.

In Section 2, we define our model of tape machines and construct one that proves Theorem 1.1. We do the same in Section 3 for deque machines and Theorem 1.2. Finally, in Section 4 we study weaker computation models (queue machines and stack machines) and show that Hamiltonian machines of this kind do not exist. We also provide implementations to run our tape and deque machines [2].

A tape machine is intuitively a variant of linear bounded Turing machines [18] where we additionally distinguish some states as output states. Formally, let $⊳$ and $⊲$ be fresh symbols to be used as left and right markers. A (deterministic) tape machine $ℳ=(Q,q_{\mathrm{i}},q_{\mathrm{h}},Q_{\mathrm{O}},\delta )$ consists of a set $Q$ of states, an initial state $q_{\mathrm{i}}\in Q$, a halting state $q_{\mathrm{h}}\in Q$, a set $Q_{\mathrm{O}}\subseteq Q$ of output states, and a transition function $\delta :(Q\setminus \{q_{\mathrm{h}}\})\times \{0,1,⊳,⊲\}\to Q\times \{0,1,⊳,⊲\}\times \{-1,0,+1\}$. The arguments to the function describe the current state and the tape symbol read; and the return value describes the next state, the tape symbol written, and the motion of the head. We require that when $ℳ$ reads the beginning-of-word marker symbol $⊳$ then it writes back $⊳$ and moves to the right, and likewise for $⊲$ moving to the left; further, $ℳ$ never writes the marker symbols otherwise. A configuration of $ℳ$ is a triple consisting of a state, the contents of the tape, and the position of the head: for brevity we will write them as a pair indicating the state and the tape contents with the head position written using a red mark. We sometimes use a gray mark to indicate the position of the head in the previous configuration.

For a given word length $\mathrm{\ell }\ge 1$, the machine $ℳ$ starts its execution in the initial configuration $c_{\mathrm{\ell }}≔(q_{\mathrm{i}},⊳\underset{\wedge }{0}{0}^{\mathrm{\ell }-1}⊲)$. The run of $ℳ$ from $c_{\mathrm{\ell }}$ is then the deterministic and potentially infinite sequence of configurations defined as expected. The only difference with Turing machines is the presence of output states: each time $ℳ$ visits an output state, it produces in unit time the word $w\in {\{0,1\}}^{\mathrm{\ell }}$ obtained from the current tape by discarding $⊳$ and $⊲$. (Note that the head position has no impact on the produced word $w$.)

We study tape machines satisfying some requirements. First, a tape machine $ℳ$ is Hamiltonian if, for every length $\mathrm{\ell }\ge 1$, the run of $ℳ$ from $c_{\mathrm{\ell }}$ terminates and produces each word of ${\{0,1\}}^{\mathrm{\ell }}$ exactly once. Note that we can always assume that $\mathrm{\ell }>\alpha$ for arbitrary constants $\alpha$, because codes for length $\le \alpha$ can be hardcoded as a subroutine of $ℳ$. Second, a tape machine $ℳ$ is constant-delay if there is a constant $B\in \mathbb{N}$ (depending only on $ℳ$ but not on the word length $\mathrm{\ell }$) that bounds the time before the first output, the delay between two consecutive outputs, and the time between the last output and the end of the run.

It is easy to see that Hamiltonian tape machines exist if we forgo the constant-delay requirement. For instance, we can follow the usual construction of the BRGC: start from the word $0^{\mathrm{\ell }}$, flip the rightmost bit on odd steps, and flip the bit that is to the left of the rightmost $1$ on even steps. This can be implemented by a tape machine whose state stores the parity of the step number. In odd steps, the machine moves the head to the rightmost symbol and flips it. In even steps, the machine moves the head to the rightmost symbol, scans leftwards until it finds the symbol to flip, and flips it. However, this tape machine has a delay that is not constant, i.e., it is not independent from the word length $\mathrm{\ell }$. Our challenge in this section is to build a tape machine that obeys the constant-delay requirement: this is not obvious because it implies in particular that tape modifications must be entirely guided by the symbols at constant distance from the head and based on the current state (which has constant size). We next present a tape machine that meets these requirements.

This is a first step towards proving Theorem 1.1, which we present for pedagogical reasons: it will help understand the Hamming-1 construction presented later, and also introduces key ideas used throughout the paper. For the sake of clarity, here and in other proofs, we describe the operation of a tape machine by specifying transitions that read and write multiple symbols in one go: for some constant $\rho \in \mathbb{N}$ (independent from the word length), the machine reads and writes the symbols left and right of the head in a window of size $\rho$ centered on the head. This can be encoded in the formal model presented above up to increasing the state space and the delay by some function of $\rho$: we can simply hardcode a constant-length sequence of transitions that reads all $\rho$ symbols around the head and then overwrites them. We will use $\rho =3$ in the proof below.

Let $\mathrm{\ell }\ge 1$ be the word length. When the run begins, we produce the word $0^{\mathrm{\ell }}$, and toggle the first bit to change the tape contents to $⊳\underset{\wedge }{1}{0}^{\mathrm{\ell }-1}⊲$. We then explain how we enumerate the remaining words, called non-zero words in what follows.

Let us construct a bijection between the non-zero words and the nodes of the complete ordered binary tree $B_{\mathrm{\ell }-1}$ of depth $\mathrm{\ell }-1$; we will then explain our enumeration in terms of the tree. By distinguishing the rightmost $1$, each non-zero word can be written as $w{10}^k$ for some binary word $w$ and some number $k$ of $0$’s. Hence the non-zero words are in bijection with the nodes of $B_{\mathrm{\ell }-1}$, that we illustrate in Figure 1(a) for $\mathrm{\ell }=4$ (ignoring for now the blue numbers and red marks). The root of $B_{\mathrm{\ell }-1}$ corresponds to the word ${10}^{\mathrm{\ell }-1}$. Now, for $k\ge 1$, if $w{10}^k$ is the word corresponding to an internal node $n$, then the 0-child of $n$ corresponds to the word $w{010}^{k-1}$ and its 1-child corresponds to the word $w{110}^{k-1}$. In summary, the word $w{10}^k$, where $0\le k\le \mathrm{\ell }-1$ and $|w|+1+k=\mathrm{\ell }$, encodes the node in $B_{\mathrm{\ell }-1}$ that is reachable from the root by the path $w$ (reading $w$ from left to right; $w$ is shown in orange in Figure 1(a)).

We enumerate the nodes of $B_{\mathrm{\ell }-1}$ in a way that ensures that consecutive nodes are at distance at most $3$ from each other. We do this via the “even-odd trick” [17, 28] (see also [29]): we do a depth-first traversal of $B_{\mathrm{\ell }-1}$ and produce the nodes in prefix or postfix order, depending on the parity of the depth (the root being at even depth). Formally, starting with the root, we do the following on every node $n$ with children $n_0$ and $n_1$:

• $\mathrm{■}$

  if the depth of $n$ is even then we produce $n$, then recurse into $n_0$, then recurse into $n_1$;

• $\mathrm{■}$

  if the depth is odd then we first recurse into $n_0$, then recurse into $n_1$, and then produce $n$.

The order in which nodes are enumerated by this procedure for $B_{4-1}$ is shown in blue in Figure 1(a) (starting at index $2$ because we produced the word $0^4$ at the beginning).

The correctness of the machine hinges on the following claim, which is easily proved by induction using the transition table of ${𝒯}_0$ given in Figure 1.

We now give a high level explanation of how ${𝒯}_0$ performs the traversal on $B_{\mathrm{\ell }-1}$. It maintains its head on the rightmost $1$, and memorizes with its state the parity of (the depth of the node corresponding to) the current word, and whether it is currently going up or down. Then, one may check that the following elementary tests/operations can be achieved by local reads/writes in a window of size $\rho =3$ centered on the head.

1. 1.

   Check whether the current tape encodes a leaf or not, by looking at the right symbol (which is always either $⊲$ or $0$).

2. 2.

   Check whether the current tape encodes the root (the symbol $b$ left of the head is $⊳$), a $0$-child ($b$ is $0$) or a $1$-child ($b$ is $1$).

3. 3.

   Go from one node to its $0$-child: $w\underset{\wedge }{1}{0}^k\stackrel{}{\rightsquigarrow }w\underset{\wedge }{0}\underset{\wedge }{1}{0}^{k-1}$, i.e., set to 0 the bit under the head, move the head right (the old head is shown in gray), and set to 1 the bit under the head.

4. 4.

   Go from a $0$-child to its sibling $1$-child: $w0\underset{\wedge }{1}{0}^k\stackrel{}{\rightsquigarrow }w1\underset{\wedge }{1}{0}^k$, i.e., flip the bit left of the head.

5. 5.

   Go from a $1$-child to its parent: $w1\underset{\wedge }{1}{0}^k\stackrel{}{\rightsquigarrow }w\underset{\wedge }{1}\underset{\wedge }{0}{0}^k$.

Formally, the tape machine ${𝒯}_0$ described in Figure 1(b) starts by outputting $0^{\mathrm{\ell }}$ and reaching the configuration $⊳\underset{\wedge }{1}{0}^{\mathrm{\ell }-1}⊲$ via the first transition in the table: its tape corresponds to the root of $B_{\mathrm{\ell }-1}$ and the state is $(\downarrow ,\mathrm{𝖤𝗏𝖾𝗇})$. Then, ${𝒯}_0$ implements the above elementary tests/operations using the four middle transitions, in order to perform a full traversal of $B_{\mathrm{\ell }-1}$. This traversal ends when the configuration $⊳\underset{\wedge }{1}{0}^{\mathrm{\ell }-1}⊲$ is reached again, this time with state $(\uparrow ,\mathrm{𝖤𝗏𝖾𝗇})$, and then we take the last transition and end the run. $◀$

By analyzing the sequence of transitions between two words produced by ${𝒯}_0$, one can observe that the maximal distance between flipped bits is two. Further, the code changes at most 3 bits from one word produced to the next (between the 9^th word and the 10^th for instance). Because $3>1$, this code is technically not a Gray code but what some authors call a quasi-Gray code [6]. We now show how to fix this and build a Hamming-1 machine.

A tape machine $ℳ$ is Hamming-1 if, for any $\mathrm{\ell }\ge 1$, for any two consecutive words $w$ and $w^{\prime }$ that are produced in the run of $ℳ$ on $0^{\mathrm{\ell }}$, then the Hamming distance between $w$ and $w^{\prime }$ is $1$ (i.e., there is a single bit that changes).

Whenever a Gray code is implemented by a constant-delay tape machine, then the maximal distance between flipped bits is bounded by some constant $k$, a property called $k$-skew-tolerance [25]. Most Gray codes, such as the BRGC, are not skew-tolerant, and the existence of 1-skew-tolerant Gray code is an open question [20]. However, [25] give examples of $k$-skew-tolerant Gray codes for $k=3$ and $k=2$; the code for $k=3$, called construction A, is of particular interest to us. Indeed, we now show how to construct a machine that is Hamming-1, Hamiltonian and constant-delay, which turns out to implement a Gray code that is closely related to construction A; see [1, Appendix B] for details.

Let $\mathrm{\ell }\ge 2$ be the word length. We ignore for now the two words $0^{\mathrm{\ell }}$ and ${10}^{\mathrm{\ell }-1}$ that are enumerated first and last, respectively. All other words are of the form $ux{10}^k$ for $x\in \{0,1\}$ and $u\in {\{0,1\}}^{\mathrm{\ell }-k-2}$, by distinguishing the rightmost $1$ and the bit $x$ that precedes it. As it was the case for ${𝒯}_0$, the machine ${𝒯}_1$ maintains its head on the rightmost $1$, as can be seen by inspecting its transition table (Figure 2(a)). We use the notation $\overline{0}=1$ and $\overline{1}=0$.

Consider the complete ordered binary tree $B_{\mathrm{\ell }-2}$ of depth $\mathrm{\ell }-2$. To every node $n$ of depth $d$, we associate two words of length $\mathrm{\ell }$ : the bottom word $w_n^{\perp }$ and the top word $w_n^{\top }$. They have the form $w_n^{\perp }=u_n{x}_n\underset{\wedge }{1}{0}^k$ and $w_n^{\top }=u_n\overline{x_n}\underset{\wedge }{1}{0}^k$ where $d+2+k=\mathrm{\ell }$, and where $x_n\in \{0,1\},u_n\in {\{0,1\}}^d$ are defined as follows: $u_n$ is the path from the root to $n$ and $x_n$ is the parity of the number of $0$’s in $u_n$. For instance, the bottom word associated with the root $r$ is $w_r^{\perp }=0\underset{\wedge }{1}{0}^{\mathrm{\ell }-2}$ (i.e., $u_r$ is the empty word and $x_r=0$); and among $\{0110\underset{\wedge }{1},0111\underset{\wedge }{1}\}$, that are associated with the same node $n$, $0111\underset{\wedge }{1}$ is the bottom word (i.e., $x_n=1$ and $u_n=011$).

Let $n$ be any internal node having bottom word $w_n^{\perp }=u_n{x}_n\underset{\wedge }{1}{0}^{k+1}$ and top word $w_n^{\top }=u_n\overline{x_n}\underset{\wedge }{1}{0}^{k+1}$. We let $c$ denote the $x_n$-child of $n$ and $\overline{c}$ its $\overline{x_n}$-child. This implies that we have $u_c=u_n{x}_n$, we have $u_{\overline{c}}=u_n\overline{x_n}$, and we always have $x_c=1$ and $x_{\overline{c}}=0$.

Then, it may be observed that the following word pairs are at Hamming distance $1$:

1. 1.

   $w_c^{\perp }$ and $w_n^{\perp }$, that is the bottom word of $c$ and the bottom word of its parent;

2. 2.

   $w_c^{\top }$ and $w_{\overline{c}}^{\perp }$; that is the top word of $c$ and the bottom word of its sibling;

3. 3.

   $w_{\overline{c}}^{\top }$ and $w_n^{\top }$, that is the top word of $\overline{c}$ and the top word of its parent;

4. 4.

   $w_{\lambda }^{\perp }$ and $w_{\lambda }^{\top }$, for every leaf $\lambda$ (remark that this is true for every node more generally).

These claims are the basis of a traversal of $B_{\mathrm{\ell }-2}$, inductively defined as follows. Starting from the root, and letting $n$ be the current node, we first produce the word $w_n^{\perp }$, then recurse into the $x_n$-child of $n$, then recurse into the $\overline{x_n}$-child of $n$, then produce the word $w_n^{\top }$. Using a simple induction (item 4 for the base case and 1-3 for the induction; see also Figure 2(b)), one can show that this traversal induces a Gray code, when the missing words $0^{\mathrm{\ell }}$ and ${10}^{\mathrm{\ell }-1}$ are produced first and last, as we do.

The tape machine ${𝒯}_1$ then produces exactly this code, as follows from:

It is routine to prove this claim by induction on $B_{\mathrm{\ell }-2}$ (see Figure 2(b)), inspecting the transitions of ${𝒯}_1$. All that remains is to check the behavior on the root $r$ of $B_{\mathrm{\ell }-2}$:

• $\mathrm{■}$

  When ${𝒯}_1$ starts, it first produces the word $0^{\mathrm{\ell }}$ and then it reaches the configuration $(\downarrow ,⊳0\underset{\wedge }{1}{0}^{\mathrm{\ell }-2}⊲)$, that is with tape $w_r^{\perp }$ with its head on the rightmost $1$.

• $\mathrm{■}$

  From the configuration $(\uparrow ,⊳1\underset{\wedge }{1}{0}^{\mathrm{\ell }-2}⊲)$, that is with tape $w_r^{\top }$ with its head on the rightmost $1$, the machine ${𝒯}_1$ produces ${10}^{\mathrm{\ell }-1}$ and then halts.

$◀$

Our results relate to known algorithms and lower bounds on the efficient implementation of quasi-Gray codes in the Decision Assignment Tree (DAT) model or bit-probe model [16, 6, 7, 22, 23]. In this model, the read and write operations performed on the memory are specified following a decision tree. However, the DAT model is a black-box model which does not restrict the computation that the machine performs, or the position in the word of the bits that are read and written. By contrast, in our model of tape machines, the next reads and writes must be decided by following a fixed transition table (independent from the current word length), and they must happen close to where the head is located. For this reason, the known algorithms for (quasi-)Gray codes in the DAT model do not imply the existence of tape machines that satisfy our requirements. Conversely, translating tape machines to the DAT model does not improve on the state of the art in that setting, because our tape machines implicitly store the position of their head: in the DAT model this amounts to $\lceil \log \mathrm{\ell }\rceil$ extra bits that can be arbitrarily read and written at each step. These extra bits are why tape machines do not contradict the known $\mathrm{\Omega }(\log \mathrm{\ell })$ lower bound on the number of bits read at each step in the DAT model (shown in Fredman [16] for Gray codes and claimed by Raskin [23] for quasi-Gray codes).

Our results also relate to a line of work that has studied the efficient implementation of counters in the RAM model, where algorithms are run on a machine featuring memory words of logarithmic size. In this model, [14] presents a counter that can perform increments and decrements in $O(1)$ time and using $O(1)$ additional memory words; this answered an open problem stated by Demaine [11]. The tape machines that we presented can easily be implemented as a RAM algorithm, where we store the current word in a table of $\mathrm{\ell }$ bits and keep one auxiliary word of $\lceil \log \mathrm{\ell }\rceil$ bits for the head position and a constant number of extra bits for the state. The increment operations are specified by the machines ${𝒯}_0$ and ${𝒯}_1$ and they can be performed in constant time. Further, ${𝒯}_0$’s and ${𝒯}_1$’s transition tables can be checked to be injective, so that we can also perform decrements in constant time simply by reversing the transitions. Hence, our constructions provide an alternative solution to Demaine’s problem, using a single auxiliary $\lceil \log \mathrm{\ell }\rceil$-bit word (instead of two in [14]), and additionally ensuring that the successive counter values form a Gray code. Another advantage is that our counter support integers of any size, since we can go from size $l$ bits to $l+1$ in constant time with the same machine. Hence, we could use it to replace an ad-hoc technical construction in [8, Section 6] used to detect large values of increasing size with constant overhead. We further discuss in [1, Appendix B] how to implement the rank and unrank operations.

A deque machine $ℳ=(Q,q_{\mathrm{i}},q_{\mathrm{h}},Q_{\mathrm{O}},\delta )$ consists of a set $Q$ of states, an initial state $q_{\mathrm{i}}\in Q$, a halting state $q_{\mathrm{h}}\in Q$, a set $Q_{\mathrm{O}}\subseteq Q$ of output states, and a transition function $\delta :(Q\setminus \{q_{\mathrm{h}}\})\times \{0,1\}\times \{0,1\}\to Q\times \{\mathrm{L},\mathrm{R}\}\times \{\mathrm{L},\mathrm{R}\}\times \{0,1\}$. The arguments to the transition function describe the current state and the symbols at the left and right endpoints of the word, and the return values describe the new state, the endpoint at which the machine pops a symbol, the endpoint at which the machine pushes a symbol, and which symbol it pushes. (If both endpoints are the same, then the machine simply overwrites the symbol at that endpoint.) Thus, a configuration of such a machine consists simply of a state and of a non-empty word. The semantics of deque machines is again defined as expected. Like in Section 2, for a word length $\mathrm{\ell }\ge 1$, we start the machine with the word $0^{\mathrm{\ell }}$ in state $q_{\mathrm{i}}$ and the machine produces the current word in unit time whenever it visits an output state. We will investigate machines that are Hamiltonian and constant-delay in the same sense as in Section 2.

One first idea to design deque machines would be to translate tape machines in a black-box fashion by taking the conjugate of the tape at the position of the head. Unfortunately, this naive approach does not work as-is [1, Appendix C]. Thus, the constructions presented in this section require new ideas on top of techniques from the previous section.

We will start by designing a deque machine which is almost Hamiltonian but fails to halt. Formally, a deque machine is prefix-Hamiltonian if it satisfies the following: for every length $\mathrm{\ell }\ge 1$, the $2^{\mathrm{\ell }}$ first words that it produces are all the words of ${\{0,1\}}^{\mathrm{\ell }}$ (without duplicates). After this, the machine can continue to run indefinitely, and in particular it is allowed to produce words that it has already produced. A Hamiltonian machine is of course prefix-Hamiltonian, but not vice-versa. The constant-delay requirement is unchanged: in particular it is imposed on the entire run. We now show:

Just like the tape machine ${𝒯}_0$ (Figure 1(b)) from Section 2, the deque machine ${𝒟}_0$ is based on the depth-first traversal of a complete binary tree. Once again $0^{\mathrm{\ell }}$ is treated independently and a word with one or more 1’s encodes a node in the complete binary tree of depth $\mathrm{\ell }-1$. However, the encoding is slightly different¹¹1In the tape machine $D_0$, recall that the tape $w\underset{\wedge }{1}{0}^k$ encodes the node reached by reading $w$ from the root (from left to right), and that we modify $w$ only on the right. On the other hand, a deque machine can only modify the endpoints of its deque. Hence the same node needs to be encoded either with $0^{k}1w$ or $\overleftarrow{w}{10}^k$, where $\overleftarrow{w}$ is the mirror of $w$. We chose the former encoding in order for the path from the root to the node to be consistently read from left to right.: the tape machine ${𝒯}_0$ from the previous section distinguished the rightmost 1 and the node reachable from the root by a path labeled $w$ was encoded by $w\underset{\wedge }{1}{0}^{\mathrm{\ell }-|w|-1}$, but the deque machine ${𝒟}_0$ will instead distinguish the leftmost 1 and encode that node by $0^{\mathrm{\ell }-|w|-1}1w$. The proof hinges on the analogue of ˜2.2 for ${𝒯}_0$:

See Figure 3(a) for the full binary tree in the case $\mathrm{\ell }=4$ and [1, Appendix C] for more details. $◀$

The machine ${𝒟}_0$ is not Hamiltonian because it does not halt at the correct time, due to the lack of left and right markers ($⊳$, $⊲$). Indeed, ${𝒟}_0$ should halt when it visits the root the second time (i.e., in the configuration $(\uparrow ,\mathrm{𝖤𝗏𝖾𝗇})0^{\mathrm{\ell }-1}1$). We did not find how to detect that the current deque is $0^{\mathrm{\ell }-1}1$: e.g., ${𝒟}_0$ cannot store the number of $1$’s in the current word, or the current number of leading $0$’s, because these numbers depend on $\mathrm{\ell }$ so they are not constant. This motivates the more complex techniques presented in the rest of this section.

To present them, we will need to understand the behavior of ${𝒟}_0$ when it reaches the root for the second time, that is, in state $(\uparrow ,\mathrm{𝖤𝗏𝖾𝗇})$. This corresponds to the step where the machine has produced every word and “should” halt.

In the following, we improve ${𝒟}_0$ (Figure 3(b)) in order to make it Hamiltonian, i.e., to detect when the enumeration can halt. This hinges on the fact that, unlike the root, some nodes of the complete binary tree of depth $\mathrm{\ell }-1$ can be detected. Let ${\lambda }_0$ be the first leaf of the 0-subtree of the root (corresponding to the word ${100}^{\mathrm{\ell }-2}$), and ${\lambda }_1$ the first leaf of the 1-subtree (corresponding to the word ${110}^{\mathrm{\ell }-2}$). The nodes ${\lambda }_0$ and ${\lambda }_1$ are double-circled in Figure 3(a). Then:

Note that, within the constant-delay bound of our deque machines, at each step we can pop the two leftmost characters and push them back; so indeed our machines can detect whenever the words $10$ or $11$ appear for the first time at the left endpoint. Our future deque machines will leverage ˜3.4 as follows. The traversal starts at ${\lambda }_0$ (i.e., the word ${100}^{\mathrm{\ell }-2}$) instead of the root $r$. Then, they count the number of half-traversals since the start. One half-traversal spans either from ${\lambda }_0$ (i.e., ${100}^{\mathrm{\ell }-2}$) to ${\lambda }_1$ (i.e., ${110}^{\mathrm{\ell }-2}$), or conversely. The former visits the 0-subtree, minus the descent in the branch $r\to {\lambda }_0$, plus the descent in the branch $r\to {\lambda }_1$. The latter visits the remainder of the 1-subtree, plus the descent in the branch $r\to {\lambda }_0$. Unfortunately, we cannot simply build a machine that performs two half-traversals, because by ˜3.3 the parity is swapped when the root is visited, so that the incorrect parity during the descent in the branch $r\to {\lambda }_0$ would lead to duplicates. We will now show two alternative ways to use the above and modify ${𝒟}_0$ to a Hamiltonian machine: the double-traversal technique, and the lookahead technique.

We first build a Hamiltonian machine ${𝒟}_1$ from ${𝒟}_0$ with the double-traversal technique. The machine ${𝒟}_1$ will perform four half-traversals (i.e., two traversals) starting from ${\lambda }_0$, and then it will halt. Each of these two traversals has an opposite parity by ˜3.3. We build the machine to ensure that the two traversals partition the output (using the parity), even though the machine is not aware of the moment when the parity is swapped.

We sketch the proof of Proposition 3.5 in the rest of this paragraph, before turning to the alternative lookahead technique. Let $\mathrm{\ell }$ be the word length. We ignore the two words $0^{\mathrm{\ell }-1}1$ and $0^{\mathrm{\ell }-1}0$, that are handled in a special way (see ˜3.7). The machine ${𝒟}_1$ traverses the complete binary tree $B_{\mathrm{\ell }-2}$ of depth $\mathrm{\ell }-2$ (in contrast with ${𝒟}_0$, which used $B_{\mathrm{\ell }-1}$; we will explain this later). Like ${𝒟}_0$, the machine ${𝒟}_1$ stores whether it is currently going up or down the tree, along with a parity bit in the second component of its internal state. However, unlike ${𝒟}_0$, the machine ${𝒟}_1$ starts at ${\lambda }_0$ (the first leaf of the 0-subtree of the root, corresponding to the word ${100}^{\mathrm{\ell }-3}$). For this reason, the parity bit maintains the parity of the height instead of the depth: the correct parity of a node encoded by $0^{k}1w$ is $|k|mod2$. (In particular, the correct parity of ${\lambda }_0$ is $0$, represented as $\mathrm{𝖤𝗏𝖾𝗇}$ in the state of the machine.)

Moreover ${𝒟}_1$ maintains in its internal state the index of the current half-traversal ($\{1\text{<sup class="ltx\_sup">st</sup>},2\text{<sup class="ltx\_sup">nd</sup>},3\text{<sup class="ltx\_sup">rd</sup>},4\text{<sup class="ltx\_sup">th</sup>}\}$): the machine stops after reaching ${\lambda }_0$ in the 4^th half-traversal. The four half-traversals are regrouped into a first full traversal and a second full traversal, each going from ${\lambda }_0$ back to ${\lambda }_0$. Let us further split each full traversal in two parts called A and B:

• $\mathrm{■}$

  Part A is the majority of the traversal: starting at ${\lambda }_0$, traversing the tree until the root ($0^{\mathrm{\ell }-2}1$) is reached.

• $\mathrm{■}$

  Part B corresponds to the last descent from the root ($0^{\mathrm{\ell }-2}1$) down to ${\lambda }_0$ again, hence passing through all nodes of the form $0^k{10}^{\mathrm{\ell }-k-2}$.

Parts A and B are not aligned with half-traversals, though part B is always included in the second half of each traversal (i.e., the visit of ${\lambda }_1$ happens in part A). Let us stress that while ${𝒟}_1$ maintains the current half-traversal, it does not know whether it is in part A or part B of the current full traversal. Furthermore, due to ˜3.3, the parity bit is equal to the correct parity during part A of the first traversal and it is swapped during part B of the first traversal. On the other hand, the parity bit is swapped during part A of the second traversal and correct again during part B of the second traversal.

Altogether, each node is visited once in each of the four possible combinations of $\{\uparrow ,\downarrow \}\times \{\mathrm{𝖤𝗏𝖾𝗇},\mathrm{𝖮𝖽𝖽}\}$. In order to produce each word only once, ${𝒟}_1$ writes the current parity bit as the rightmost symbol of the current deque (with the convention $\mathrm{𝖤𝗏𝖾𝗇}=0$ and $\mathrm{𝖮𝖽𝖽}=1$). This special treatment of the rightmost symbol of the deque is why ${𝒟}_1$ performs traversals of the binary tree $B_{\mathrm{\ell }-2}$ instead of $B_{\mathrm{\ell }-1}$. (We note that, even though the parity bit is always written as the rightmost symbol of the deque, we still need to additionally keep track of parity in the internal state of ${𝒟}_1$, because the parity is part of the definition of which states are output states.)

The proof of Proposition 3.5 consists in showing that ${𝒟}_1$ has the invariants stated by Claims 3.6 and 3.7, given below. They are established by a simple inspection of the transition table (Figure 4).

An alternative way to make ${𝒟}_0$ Hamiltonian is to use the lookahead technique. We think it is more flexible though more technical than double traversal.

The deque machine ${𝒟}_2$, defined in Figure 5, implements this technique. More precisely, ${𝒟}_2$ performs two half-traversals (i.e., one full traversal) of $B_{\mathrm{\ell }-1}$, starting from ${\lambda }_0$. However, each time the machine visits a $1$-child $n$ and moves to the state $\downarrow$, it performs a “lookahead”: it descends to the leftmost leaf of $n$ and then ascends back to $n$, before continuing the traversal (and descending again to the leftmost leaf of $n$). This first upward return to $n$ is possible because ${𝒟}_2$ can detect the first node that is a $1$-child while moving upward in the tree.

This lookahead phase requires keeping track of the height of the current node modulo $4$, since in ${𝒟}_2$ each node is visited four times instead of twice as in ${𝒟}_0$. Concretely, a node of height $hmod4$ is output on its $h^{\text{th}}$ visit. Like ${𝒟}_1$, the machine ${𝒟}_2$ detects the second visit of ${\lambda }_0$. This event occurs during the lookahead initiated from the root $r$. Hence, ${𝒟}_2$ is able to detect that it is visiting the root after this lookahead phase. The machine is thus able to adjust the stored height modulo $4$ before performing the final descent in $r\to {\lambda }_0$. This allows to fix the issue from ˜3.3 and to produce the missing solutions in this branch.

We sketch the proof of Proposition 3.8 in the remainder of the paragraph. Let $\mathrm{\ell }$ be a word length. Once again, we ignore for now the word $0^{\mathrm{\ell }}$ which is handled in a special way, and focus on the other non-zero words. The top part of table Figure 5 describes a simplified version of the machine, that the reader should consider first. The actual machine is obtained by replacing the transition marked with $(\diamond )$ by the three transitions given at the bottom of Figure 5. We will explain this at the end of the proof, together with the purpose of the state special.

The deque machine ${𝒟}_2$ traverses the complete binary tree $B_{\mathrm{\ell }-1}$ of depth $\mathrm{\ell }-1$. We use the same bijection between nodes of $B_{\mathrm{\ell }-1}$ and nonzero words of length $\mathrm{\ell }$. The state of ${𝒟}_2$ contains three components:

• $\mathrm{■}$

  The first component of the state of ${𝒟}_2$ stores whether it is currently going up or down the tree with four different values $\{{\downarrow }_0,{\uparrow }_1,{\downarrow }_2,{\uparrow }_3\}$. The intuition is that ${\downarrow }_0,{\uparrow }_1,{\downarrow }_2$ correspond to the value $\downarrow$ of ${𝒟}_0$, whereas ${\uparrow }_3$ corresponds to the value $\uparrow$ of ${𝒟}_0$.

• $\mathrm{■}$

  The second component of the state of ${𝒟}_2$ stores the height modulo 4 of the current node (possibly with an offset after visiting the root, as we will explain).

• $\mathrm{■}$

  The third component of the state is in $\{1\text{<sup class="ltx\_sup">st</sup>},2\text{<sup class="ltx\_sup">nd</sup>},\text{last}\}$, which indicates the half-traversal that we are currently doing, as we explain below.

More precisely, for the third component, we want to use ˜3.4 to detect the end of the enumeration. The initial value used for the third component is $1\text{<sup class="ltx\_sup">st</sup>}$, which corresponds to the first half-traversal, i.e., the traversal of $B_{\mathrm{\ell }-1}$ between ${\lambda }_0$ (the first leaf of the 0-subtree of the root, corresponding to the word ${100}^{\mathrm{\ell }-2}$) and ${\lambda }_1$ (the first leaf of the 1-subtree of the root, corresponding to the word ${110}^{\mathrm{\ell }-2}$). When ${𝒟}_2$ traverses the leaf ${\lambda }_1$, it detects it by ˜3.4, and then transition ($†$) of Figure 5 is used to change the state to $2\text{<sup class="ltx\_sup">nd</sup>}$, indicating that the second half-traversal has started. Finally, when ${\lambda }_0$ is traversed a second time by ${𝒟}_2$, we detect it again by ˜3.4, and then transition ($\ast$) is used, which changes the state to last. The machine then enumerates some missing words of the form $0^{\ast }{10}^{\ast }$ (as we will explain at the end), and then halts.

We now explain the traversal in more detail. The machine ${𝒟}_2$ starts at ${\lambda }_0$ and mimic the traversal of $B_{\mathrm{\ell }-1}$ by ${𝒟}_0$. The only difference is that it does a “lookahead” when it starts to go down the tree from a node $n$ which is a $1$-child. More precisely, letting ${\lambda }_n$ be the leftmost leaf of the subtree rooted in $n$, the machine ${𝒟}_2$ traverses the path $n\to {\lambda }_n$ three times: first going down (state ${\downarrow }_0$), then up (state ${\uparrow }_1$) and finally down (state ${\downarrow }_2$). When the leaf ${\lambda }_n$ is reached in state ${\downarrow }_2$, ${𝒟}_2$ transitions to state ${\uparrow }_3$, which corresponds to the state $\uparrow$ in ${𝒟}_0$. To slightly simplify the machine, we maintain the opposite of the height (modulo 4), that is: when the machine goes up the height is decremented, and it is incremented when the machine goes down.

The correctness of ${𝒟}_2$ rely on Claims 3.9 and 3.10, which describe the configurations of $D_2$ when the tape contains at least two 0’s, and exactly one 0, respectively. Both are proved with straightforward inductions based on Table (Figure 5). The case of the tape $0^{\mathrm{\ell }}$ is treated separately.

The previous claim guarantees that the words are produced once, except for the words of the form $0^{\ast }{10}^{\ast }$: these are the words of the leftmost path, i.e., the path from the root (corresponding to the word $0^{\mathrm{\ell }-1}$) to the leftmost leaf ${\lambda }_0$ (corresponding to the word ${10}^{\mathrm{\ell }-1}$). We deal with the elements of this branch differently, since we know that their height is shifted by one when going over the root, by ˜3.3 (generalized to the present setting, where we keep track of the opposite of the height, and we do it modulo 4 instead of modulo 2). These words are first traversed when going up from a $1$-child, that is in state ${\uparrow }_3$, before the traversal has reached the root for the first time – hence with the correct height. Then, thanks to the lookahead, ${𝒟}_2$ first traverses the leftmost branch up and down in states ${\downarrow }_0$ and ${\uparrow }_1$, with a height shifted by one. When again at the root of the tree, it has transitioned to the state last thanks to the lookahead, with transition ($\ast$): this uses the analogue of ˜3.4 to argue that the machine detects that it has now revisited ${\lambda }_0$ after having visited ${\lambda }_1$. Hence, before ${𝒟}_2$ does the last descent along the leftmost path in state ${\downarrow }_2$, the height is again decremented by one to avoid duplicates, in transition $\diamond$. Hence, all the words of the leftmost path are enumerated exactly once, as precisely stated in the following claim.

Finally, we must explain how to deal with the word $0^{\mathrm{\ell }}$, which is the purpose of the state called “special” and of the three transitions at the bottom of Figure 5 to replace transition $(\diamond )$. Observe that the machine ${𝒟}_2$ visits the word $0^{\mathrm{\ell }}$ only once in state $({\uparrow }_3,h,2\text{<sup class="ltx\_sup">nd</sup>})$, see ˜3.3. Hence, this word is produced by ${𝒟}_2$ if and only if $h=3$. The complete version of the transition table of Figure 5 ensures the following: when it visits the root in state $({\uparrow }_1,h,\text{last})$ before the last descent, it first produces $0^{\mathrm{\ell }}$ if $h\ne 3$. These are the transitions given at the bottom of Figure 5 to replace the transition $(\diamond )$: we distinguish two cases depending on whether $h=3$ (where we do the analogue of $(\diamond )$) or not (where we additionally output $0^{\mathrm{\ell }}$ via the special state).

We last argue why the machine satisfies the constant-delay requirement. For this, we observe that the second component of the state always stores the opposite of the current height modulo 4 plus some offset $b$, and the offset changes at only constantly many points in the enumeration (namely, the first time we visit the root where it is decremented, and the second time when it is fixed when revisiting the root after the lookahead). So it suffices to show the constant-delay guarantee whenever the offset does not change. We can also ignore the additional states mentioned at the end of the previous paragraph, as they are only visited once.

When the offset does not change, the machine simply performs a traversal of the complete binary tree $B_{\mathrm{\ell }-1}$, except that descents from a $1$-child are replaced by a back-and-forth successively involving the states ${\downarrow }_0,{\uparrow }_1,{\downarrow }_2$. If we stay in the same state for more than 3 steps, then we visit all values of the second component, and one of the states encountered must be an output state. So a long run without outputs must change states among ${\downarrow }_0,{\uparrow }_1,{\downarrow }_2,{\uparrow }_3$ every 3 steps at most. Looking at the possible transitions between states, these state transitions must include a transition from ${\downarrow }_0$ to ${\uparrow }_1$, or from ${\downarrow }_2$ to ${\uparrow }_3$. But these transitions only happen at leaves of $B_{\mathrm{\ell }-1}$, and since we assumed that we do not stay in the same state for more than 3 steps it easy to see that the time between the 4 visits of the leaf that are prescribed by ˜3.9 must happen within a constant time bound.

We define queue machines as a variant of deque machines that can only push to the left and pop to the right; but we still augment them with the ability to read the $\rho$ rightmost symbols of the word, for some constant $\rho >0$. For convenience, we assume without loss of generality that the current word $\mathrm{\ell }$ is no smaller than $\rho$. A queue machine $ℳ=(Q,q_{\mathrm{i}},q_{\mathrm{h}},Q_{\mathrm{O}},\rho ,\delta )$ is then defined similarly to a deque machine, with the transition function having signature $\delta :(Q\setminus \{q_{\mathrm{h}}\})\times {\{0,1\}}^{\rho }\to Q\times {\{0,1\}}^{\le \rho }$. The arguments to the transition function describe the current state and the $\rho$ rightmost bits of the word. The return values describe the new state and the word $w$ with length $0\le |w|\le \rho$ pushed to the left of the deque, with the $|w|$ rightmost characters being popped so that the word length stays the same. Note that the definition of queue machines does not allow them to read the leftmost bits of the deque, but they can be modified to do so without loss of generality, e.g., by remembering the $\rho$ most recently pushed bits as part of their internal state.

We investigate queue machines that are Hamiltonian and constant-delay in the same sense as in Section 2, and we show no such machines exist, even without bounding the delay:

The proof is by contradiction and uses a pumping-like argument: we start from the last state visited by the machine, we argue that this state cannot occur on any other word, and then successively eliminate more and more states by building longer and longer words. Note that the result applies even without requiring machines to be constant-delay, but that it would not apply if we could have unlimited auxiliary memory: indeed it is known that we can produce all binary words with left-push and right-pop operations.

For the sake of contradiction, assume there is a Hamiltonian queue machine $ℳ$ with set of states $Q$, which reads $\rho$ bits at a time. Let $n_0>\rho$ be some integer: we consider the word $w_0$ of size $n_0$, such that $c=(q_0,w_0)$ is the last configuration of $ℳ$ before reaching the halting state. Let us consider the words $0w_0$ and $1w_0$: they are both enumerated by $ℳ$ when generating the words of size $n_0+1$, in states $q$ and $q^{\prime }$ respectively. Remark that $q$ and $q^{\prime }$ cannot both be equal to $q_0$, because whenever $ℳ$ is in configuration $(q_0,w^{\prime }{w}_0)$ for some $w^{\prime }\in {\mathrm{\Sigma }}^{\ast }$ then it will reach the halting state (as the transition only depends on the last $\rho$ bits $w_0$ and on the current state $q_0$). W.l.o.g., we assume that we have $q\ne q_0$. Hence, let $q_1≔q$ and $u_1≔0w_0$. We consider the run of $ℳ$ from $(q_1,u_1)$ up to the moment when the halting state is reached, and we let $v_1$ be the word formed of all words pushed to the left of $u_1$ during this run of $ℳ$ until $ℳ$ halts. For instance, if $ℳ$ pushes $x_0$, then $x_1$, then $x_2$ and then halts, then $v_1=x_2{x}_1{x}_0$. Note that $v_1$ can be exponentially longer than $u_1$.

Notice now that the run of $ℳ$ on $(q_1,w{v}_1{u}_1)$, for any $w\in {\{0,1\}}^{\ast }$, will use exactly the same transitions (in the same order) as the run on $(q_1,u_1)$, and then it halts. Indeed, an easy induction shows that the leftmost $\rho$ bits will always be equal in both cases. In particular, all these runs have the same length $n_1$ (measured as the number of transitions performed). Let us now consider the four words $w{v}_1{u}_1$ for $w\in \{00,01,10,11\}$, and the run of $ℳ$ for words of length $\mathrm{\ell }=|w{v}_1{u}_1|$. For the same reason as before, at most one of these four words can be visited in state $q_0$ during that run. Moreover, only one of these four words can be visited in state $q_1$ during that run. Indeed, only one configuration can be at position $n_1$ from the end. Thus, pick a word $u_2=w{v}_1{u}_1$ with $w\in {\{0,1\}}^{\ast }$ which is visited in a state $q_2\notin \{q_0,q_1\}$ during the run of $ℳ$ from its initial configuration. We then let $v_2$ be the concatenation of all words pushed to the left of $u_2$ by $ℳ$ on the run from $(q_2,u_2)$ until $ℳ$ halts.

This method easily generalizes to build sequences $(u_0,u_1,\mathrm{\dots },u_k),(v_0,v_1,\mathrm{\dots },v_k)$ of words and $(q_0,q_1,\mathrm{\dots },q_k)$ of states that satisfies: for every , there is at most one word $w$ of length $\lceil \log (k+1)\rceil$ such that the run of $ℳ$ from its initial configuration reaches $(q_i,w{v}_i{u}_i)$. When $k$ equals the number of states in $ℳ$, we reach a contradiction. $◀$

Note that the proof above also rules out the existence of Hamiltonian queue machines in somewhat more powerful models, e.g., if the machine is also allowed to edit in-place the $\rho$ leftmost and rightmost characters for some constant $\rho$ without changing the length.

We now move from queue machines to stack machines. Stack machines are defined like queue machines, except that they can only push and pop on the right endpoint.

Formally, a stack machine is a tuple $ℳ=(Q,q_{\mathrm{i}},q_{\mathrm{h}},Q_{\mathrm{O}},\delta )$ with $q_{\mathrm{i}}$ and $q_{\mathrm{h}}$ respectively the initial state and halting state, with $Q_{\mathrm{O}}$ the output states, and $\delta :(Q\setminus \{q_{\mathrm{h}}\})\times \{0,1,⊳\}\to Q\times (\{\text{pop}\}\cup (\{\text{push}\}\times \{0,1\}))$, where $⊳$ signals that the stack is empty. The semantics are defined as expected: based on the current state and the rightmost bit of the current word (or the $⊳$ marker), the machine transitions to some state and either pops the rightmost bit or pushes a bit to the right of the word. (Popping on the empty word has no effect.)

With this definition, stack machines obviously cannot achieve constant-delay enumeration of ${\{0,1\}}^{\mathrm{\ell }}$ for arbitrary $\mathrm{\ell }\in \mathbb{N}$. Indeed, for any delay bound $B\in \mathbb{N}$, the machine will not have time to change the bits at distance greater than $B/2$ from the right endpoint, which is problematic as soon as $\mathrm{\ell }>B$. However, one can ask whether Hamiltonian stack machines can exist without the constant-delay requirement. The answer is negative.

To prove Proposition 4.2, we first prove a general lemma reminiscent of pumping lemmas:

Intuitively, we show that we must reach on one word $u^{\prime }$ on a state $q$ and reach a larger word $v^{\prime }$ on the same state $q$ without having popped any bit from $u^{\prime }$. Once this has happened the sequence repeats indefinitely. The formal proof is below:

Fix a word $u$ of length $n$ visited at a time $s$ and $v$ a word of length $n+k$ visited at a time $t>s$, with all words between $s$ and $t$ having length $>n$. Define a sequence of timestamps $s,\mathrm{\dots },s_k$ and corresponding visited words $u_0,\mathrm{\dots },u_k$ in the following way: $s_0≔s$ and $u_0≔u$, then $s_1$ is the moment where we visit a word $u_1$ which is the last word of length $n+1$ visited between $s_0$ and $t$, and $s_2$ is the last moment where we visit a word $u_2$ which is the last word of length $n+2$ visited between $u_1$ and $v$, and so on. At the end, the time $s_k$ is such that $s_k\le t$ and $u_k$ is a word of length $n+k$ which is the last word of length $n+k$ visited between $u_{k-1}$ and $v$, so it must be the case that $s_k≔t$ and $u_k≔v$. Further note that the definition ensures that the $u_i$ are successive prefixes of one another: each $u_i$ with $0\le i\le k$ is a prefix of length $n+i$ of $v$

By the pigeonhole principle, there are two indices such that the state reached by the machine at time $s_i$ and $s_j$ (reaching words $u_i$ and $u_j$ respectively) is the same state $q$. Recall that we have $u_i=u(v_{n+1}\mathrm{\cdots }{v}_{n+i})$ and $u_j=u(v_{n+1}\mathrm{\cdots }{v}_{n+j})=u_{i}x$ with $x=(v_{n+i+1}\mathrm{\cdots }{v}_{n+j})$.

Now, consider the execution of the machine from time $s_j$ onwards. At $s_i$, the machine was in the same state, and it followed a sequence of transitions that never popped below depth $n+i$ until reaching $s_j$: indeed $s_i$ is the last visit of a word of length $n+i$ between $s$ and $t$ so if the machine popped below $n+i$ between $s_i$ and $s_j$ then it would visit a word of length $n+i$ again before $t$ and this would contradict the definition of $u_i$. Then, from $s_j$, the machine will replay the same sequence of transitions, in particular not popping below $n+j$, until we reach after time $s_j-s_i$ the state $q$ and the word $u_i{x}^2$. We can repeat this argument indefinitely to show that the machine never halts and all words produced from that point onwards start with $u_i$, hence with $u$. $◀$

We can now prove Proposition 4.2:

We reason by contradiction. Let $ℳ$ be a stack machine, let $k$ be the number of states of $ℳ$, let $\mathrm{\ell }≔k+2$ as in the statement, and assume by way of contradiction that $ℳ$ visits all words of length $\mathrm{\ell }$.

Consider the first word $u$ of length $k+2$ that $ℳ$ visits whose first two bits $xy$ are different from $00$, and consider the moment where $ℳ$ last visited the word $xy$ before visiting $u$ (this must have happened because the initial tape starts with $00$ so $ℳ$ must have changed them and visited $u$). From Lemma 4.3 we know that all words visited afterwards start with $xy$. But, letting $x^{\prime }{y}^{\prime }$ be a sequence of two bits such that $x^{\prime }{y}^{\prime }\ne xy$ and $x^{\prime }{y}^{\prime }\ne 00$, we know that no word of length $\ge k+2$ starting with $x^{\prime }{y}^{\prime }$ was visited, so $ℳ$ cannot visit all words of length $\mathrm{\ell }$. $◀$

This result also implies that prefix-Hamiltonian stack machines do not exist, or even stack machines that visit all words of length $\mathrm{\ell }$ for sufficiently large $\mathrm{\ell }$ (in particular they cannot output all such words, even with duplicates). This also rules out the existence of stack machines to enumerate other languages than ${\{0,1\}}^{\mathrm{\ell }}$, for instance ${\{0,1\}}^{\le l}$ (the binary words of length up to $\mathrm{\ell }$), or the infinite language ${\{0,1\}}^{\ast }$.

However, with unlimited memory, some languages can be enumerated in constant delay by performing push-right and pop-right operations. Since we cannot enumerate ${\{0,1\}}^{\mathrm{\ell }}$ in constant-delay, we focus on other languages.

We first note that enumeration can easily be done in constant-delay for the language ${\{0,1\}}^{\le \mathrm{\ell }}$ in constant delay with push-right and pop-right operations. This contrasts with the inexistence of stack machines for this language (as follows from Proposition 4.2).

This is simply by exploring the complete binary tree of depth $\mathrm{\ell }$ and using again the even-odd trick. $\mathrm{⊲}$

We last point out that the above is not possible if we want to produce the infinite sequence of the words of ${\{0,1\}}^{\ast }$ (i.e., of arbitrary length). This is intuitively because we must eventually produce all short words and then we can no longer change the first bits of the word. This is made formal in [3, Theorem 6.2].