source_limit.tex

\section{Generation in the Limit with Replay}
\label{sec:limit}

We first construct an algorithm that matches the computational guarantees of the standard setting for all countable classes under replay~(\Cref{thmt@@thmlimitreplaymqonly}).
Then, in~\Cref{thmt@@thmseparationlimitreplay}, we present a hard (necessarily uncountable) hypothesis class demonstrating a separation between generation in the limit with and without replay.
See also the corresponding row of~\Cref{tab:replay-separation-classes}.

\subsection{A Computable Algorithm to Generate in the Limit Any Countable Class under Replay}

\citet{kleinberg2024language} show that all countable hypothesis classes are generatable in the limit \emph{without} replay and give a universal membership-query-only generator.
The next theorem shows that replay does not change this picture.

\begin{restatable}{theorem}{thmlimitreplaymqonly}
    \label{thm:limit_replay_mq_only}
    There exists a generator that, given any \emph{countable} binary hypothesis class \(\cH=\bc{h_1,h_2,\ldots}\) over a countable domain \(\cX\) satisfying the UUS property, generates in the limit with replay every target \(h^\star\in\cH\) using only membership queries.
\end{restatable}

The proof is constructive.
Building on the algorithm of \citet{kleinberg2024language}, we propose \textsc{WP} (\emph{Witness Protection};~\Cref{alg:computable-wp}), a universal membership-query-only algorithm that generates in the limit with replay any countable hypothesis class $\cH$.
To prove this, we first need some additional notation.
Since the domain $\cX$ is countable, we may assume without loss of generality that $\cX=\bN$.
The algorithm maintains a growing prefix length \(m\) over the elements of the domain \(\cX\).
For \(h\in\cH\) and \(m\in\bN\), write \[\supp{h}[m]\coloneqq \supp{h}\cap \bc{1,\ldots,m};\] restricting hypotheses to this prefix yields a surrogate for set inclusion that is computable with membership queries alone.\footnote{
    That is, for any \(i,j,m\in\bN\) we can establish whether \(\supp{h_i}[m]\subseteq \supp{h_j}[m]\) using only a finite number of membership queries
}
Fix a target hypothesis \(h^\star\in\cH\).
In the replay model, each example \(x_t\) is either an element of \(\supp{h^\star}\) or a replay of a past output.
Let \(O_t\coloneqq\bc{o_1,\ldots,o_t}\) with \(O_0 = \emptyset\), and define the \emph{sure} set 
\[S_t \coloneqq \bc{x_s : 1\le s\le t,\ x_s\notin O_{s-1}},\]
i.e., the examples that cannot be explained as replay and hence must lie in \(\supp{h^\star}\), so that \(S_t\subseteq \supp{h^\star}\).
We relax the notion of criticality from \citet{kleinberg2024language} to ignore previously output elements.
Fix an ordering of the hypotheses of the countable class \(\cH\), i.e., write \(\cH = \bc{h_1,h_2,\ldots}\).
\begin{definition}[\((t,m)\)-critical with replay]\label{def:tm-critical-replay}
    Fix \(t,m\in\bN\). We say that \(h_n\in\cH\) is \emph{\((t,m)\)-critical with replay} if\looseness=-1
    \begin{enumerate}
        \item \(S_t \subseteq \supp{h_n}\); and
        \item for every \(i<n\) with \(S_t\subseteq \supp{h_i}\) we have \(\supp{h_n}[m] \subseteq \supp{h_i}[m] \cup O_{t-1}\).
    \end{enumerate}
\end{definition}
\noindent Condition 1 requires that \(h_n\) is consistent with the \emph{sure} examples, i.e., examples that must belong to \(\supp{h^\star}\).
Condition 2 enforces that on the finite prefix \(\bc{1,\ldots,m}\) of the domain, any earlier hypothesis \(h_i\) that is also consistent with \(S_t\) must contain every element of \(\supp{h_n}[m]\) except possibly those that could be explained as replays.
Both conditions can be checked using finitely many membership queries.

At each step \(t\), the algorithm considers the active set of consistent hypotheses \[V_t \coloneqq \bc{ i\le t : S_t\subseteq \supp{h_i}}.\]
From \(V_t\), it selects the \((t,m)\)-critical hypothesis with the largest index \(n^{(t,m)}\) and attempts to output an element from \[\supp{h_{n^{(t,m)}}}[m]\setminus\br{S_t\cup O_{t-1}\cup W^{(t,m)}},\] where \(W^{(t,m)}\) is the active \emph{witness} set; the algorithm increases \(m\) until a suitable element is found and then outputs it.
To construct \(W^{(t,m)}\), for any prefix \(m\), active candidate set \(V_t\), and pair \(i,j\in V_t\) with \(j<i\), define the witness \(w_{ij}^{(t,m)}\) as the minimal unobserved element distinguishing \(h_i\) and \(h_j\) within the prefix \(\bc{1,\ldots,m}\): \[w_{ij}^{(t,m)}\coloneqq \min \Delta_{ij}^{(t,m)} \quad \text{where} \quad \Delta_{ij}^{(t,m)} \coloneqq \supp{h_i}[m]\setminus\br{\supp{h_j}[m] \cup O_{t-1}},\] when the set \(\Delta_{ij}^{(t,m)}\) is not empty; otherwise, \(w_{ij}^{(t,m)} = \bot\).
The active witness set \(W^{(t,m)}\) is then the collection of all such witnesses: \[W^{(t,m)} \coloneqq \bc{w_{ij}^{(t,m)} \mid i,j\in V_t,\,j<i} \setminus \bc{\bot}.\]
Since the algorithm never outputs an active witness \(w_{ij}^{(t,m)}\), if \(w_{ij}^{(t,m)}\) appears in the example stream, it cannot be a replay and hence joins the sure set \(S_t\), permanently ruling out \(h_j\) from \(V_t\).\looseness=-1  

\begin{algorithm}[!htbp]
\caption{\textsc{Witness Protection (WP)}}
\label{alg:computable-wp}
\begingroup
\setlength{\baselineskip}{1.05\baselineskip}
    \begin{algorithmic}[1]
        \Require \(\cH = \bc{h_1, h_2, \ldots}\) over \(\cX=\bc{1,2,\ldots}\)
        \State \(S_0 \gets \emptyset\); \(O_0 \gets \emptyset\); \(m\gets 0\)
        \For{\(t = 1,2,\ldots\)}
            \State Receive a new example \(x_t\)
            \If{\(x_t \notin O_{t-1}\)}
                \State\(S_t \gets S_{t-1} \cup \bc{x_t}\)
            \Else
                \State \(S_t \gets S_{t-1}\)
            \EndIf
            \State \(V_t \gets \bc{\,i \le t \mid S_t \subseteq \supp{h_i}\,}\)
            \State \(o_t\gets \bot\)
            \If{\(V_t\neq\emptyset\)}
                \State \(m \gets \max\bc{m, x_t}\)
                \Repeat
                    \State \(m \gets m + 1\)
                    \State \(W^{(t,m)} \gets \emptyset\)
                    \For{\(i,j \in V_t \text{ with } j < i\)}
                        \State \(\Delta_{ij}^{(t,m)} \gets \supp{h_i}[m]\setminus\br{\supp{h_j}[m] \cup O_{t-1}}\)
                        \If{\(\Delta_{ij}^{(t,m)} \neq \emptyset\)}
                            \State \(w_{ij}^{(t,m)} \gets \min \Delta_{ij}^{(t,m)}\)
                            \State \(W^{(t,m)} \gets W^{(t,m)} \cup \bc{w_{ij}^{(t,m)}}\) 
                        \EndIf
                    \EndFor
                    \State \(n^{(t,m)} \gets \max \bc{\,i \le t \mid h_i \text{ is } (t,m)\text{-critical with replay}\,}\)
                    \For{\(x \in \supp{h_{n^{(t,m)}}}[m]\)}
                        \If{\(x \notin S_t \cup O_{t-1} \cup W^{(t,m)}\)}
                            \State \(o_t \gets x\); \;\textbf{break}
                        \EndIf
                    \EndFor
                \Until{\(o_t \ne \bot\)}
            \Else
                \State Choose \(o_t \in S_t\) arbitrarily
            \EndIf
            \State Output \(o_t\); \;\(O_t \gets O_{t-1} \cup \bc{o_t}\)
        \EndFor
    \end{algorithmic}
\endgroup
\end{algorithm}

Let \(z\) be the first index with \(h^\star=h_z\) in the given enumeration of \(\cH\).
We prove the correctness of \Cref{alg:computable-wp} via three lemmas: (i) Lemma~\ref{lem:wp-eventual-critical} shows that \(h_z\) eventually becomes \((t,m)\)-critical with replay and stays so; (ii) Lemma~\ref{lem:wp-terminates} shows that each round of \Cref{alg:computable-wp} terminates and the inner repeat-until loop finds an output in finite time; and finally (iii) Lemma~\ref{lem:wp-eventual-valid} shows that there exists a finite stabilization time \(t^\star\) such that, for all steps after that, every output is fresh and valid for \(h_z\).


\begin{lemma}[Eventual criticality]\label{lem:wp-eventual-critical}
There exists \(t^\star<\infty\) such that for all \(t\ge t^\star\) and all \(m\in\bN\), the hypothesis \(h_z\) is \((t,m)\)-critical with replay.
\end{lemma}

\begin{proof}
Consider step \(t=z\) of \Cref{alg:computable-wp}.
Fix \(j<z\) with \(S_z\subseteq \supp{h_j}\) and define
\[
\Delta_{zj}^{(z,\infty)} \coloneqq \supp{h_z}\setminus\br{\supp{h_j}\cup O_{z-1}}.
\]
If \(\Delta_{zj}^{(z,\infty)} = \emptyset\), then \(h_z\) already satisfies \(\supp{h_z}\subseteq \supp{h_j}\cup O_{z-1}\).
Otherwise, let \(w_j\coloneqq \min \Delta_{zj}^{(z,\infty)}\) (which is well-defined under the identification \(\cX\simeq\bN\)).
Let \[B\coloneqq\bc{\,j<z : S_z\subseteq \supp{h_j}\text{ and }\Delta_{zj}^{(z,\infty)}\neq\emptyset\,}.\]
Note that \(|B|\le z-1<\infty\). 
Also, recall that, since \(h_z\) is the true hypothesis, \(z\in V_t\) for all \(t\).

We claim that, for every \(j\in B\), \(w_j\notin O_{t}\) as long as \(j\in V_t\).
We prove this by induction.
For the base case \(t=z-1\), if \(j\in B\), then by definition \(w_j\notin O_{z-1}\).
Now, consider any \(t\geq z\).
By the induction hypothesis, \(w_j \notin O_{t-1}\).
Thus, when \(m \ge w_j\), \textsc{WP} sets \[w_{zj}^{(t,m)} = \min \bc{x\le m : x\in\supp{h_z}\setminus\br{\supp{h_j}\cup O_{t-1}}} = w_j.\]
Since the output-selection rule forbids outputting any element of \(W^{(t,m)}\), step \(t\) does not output \(w_j\), i.e., \(w_j \notin O_{t}\).
Otherwise, if \(m<w_j\), then every output considered by the algorithm lies in \(\{1,\dots,m\}\), and hence cannot equal \(w_j\).
Thus, \(w_j\notin O_{t}\) for any step \(t\) where \(j \in V_t\).

Since \(w_j\in\supp{h_z}\), any enumeration with replay for \(h_z\) and \textsc{WP} must eventually present \(w_j\) at a finite time \(t_j\) as some example \(x_{t_j}\).
There are two possibilities: either \(j\) was already permanently evicted from \(V_t\) at some time prior to \(t_j\) (due to another distinguishing element), or \(j \in V_{t_j}\).
If \(j \in V_{t_j}\), then \(w_j\notin O_{t_j-1}\) and thus \(w_j\) enters the sure set \(S_{t_j}\).
Consequently, \(h_j\) is permanently ruled out from \(V_t\) for all \(t\ge t_j\).
In either case, every \(j\in B\) is evicted from \(V_t\) by some finite time.

Let \(t^\star\coloneqq \max\bc{t_j : j\in B}\), with the convention \(t^\star=z\) if \(B=\emptyset\).
Then, for all \(t\ge t^\star\) and all \(j<z\), if \(S_t\subseteq\supp{h_j}\), necessarily \(j\notin B\) %
and hence \(\supp{h_z}\subseteq \supp{h_j}\cup O_{z-1}\subseteq \supp{h_j}\cup O_{t-1}\).
Intersecting with \(\bc{1,\ldots,m}\) yields \(\supp{h_z}[m]\subseteq \supp{h_j}[m]\cup O_{t-1}\) for all \(m\in\bN\).
Since we also have that \(S_t\subseteq\supp{h_z}\) for all \(t\), the hypothesis \(h_z\) satisfies Definition~\ref{def:tm-critical-replay} for all \(t\ge t^\star\) and \(m\in\bN\).
\end{proof}


\begin{lemma}[Per-round termination]\label{lem:wp-terminates}
For every \(t\in\bN\), Algorithm~\ref{alg:computable-wp} outputs \(o_t\) after finitely many iterations of the repeat-until loop.
\end{lemma}

\begin{proof}
Fix \(t\in\bN\).
If \(V_t=\emptyset\), the algorithm outputs some \(o_t\in S_t\) and terminates.
Assume \(V_t\neq\emptyset\).
Then, for each \(m\), there exists at least one \((t,m)\)-critical hypothesis: the minimal index in \(V_t\) is \((t,m)\)-critical with replay, since condition (ii) of Definition~\ref{def:tm-critical-replay} is vacuous in this case. \looseness=-1

As \(m\) increases, the predicate ``\(h_i\) is \((t,m)\)-critical with replay'' is monotone: once false for a certain \(m'\), it remains false for all \(m\geq m'\).\footnote{
        Indeed, condition 1 of~Definition~\ref{def:tm-critical-replay} is independent of \(m\). 
        Moreover, if condition 2 fails at some prefix \(m'\), then there exist \(j<i\) with \(S_t\subseteq\supp{h_j}\) and some \(x\le m'\) such that \(x\in\supp{h_i}\) and \(x\notin\supp{h_j}\cup O_{t-1}\).
        The same \(x\) belongs to every larger prefix, so condition 2 also fails for every \(m\ge m'\).
        Therefore, the set of \((t,m)\)-critical hypotheses can only shrink as \(m\) increases, and \(n^{(t,m)}\) is nonincreasing in \(m\).
    } 
Thus, \(n^{(t,m)}\) is nonincreasing in \(m\).
Additionally, it takes values in the finite set \(\bc{1,\ldots,t}\).
Hence, there exists \(m_0<\infty\) such that \(n^{(t,m)}=\bar n\) for all \(m\ge m_0\).

Fix any \(m\ge m_0\).
The excluded set in the output-selection loop,
\[
E^{(t,m)} \coloneqq S_t \cup O_{t-1} \cup W^{(t,m)},
\]
is finite and has size at most \(|S_t|+|O_{t-1}|+|V_t|\br{|V_t|-1}/2 \le 2t+t^2\).
Since \(\supp{h_{\bar n}}\) is infinite, the cardinality of \(\supp{h_{\bar n}}[m]\) diverges with \(m\).
Therefore, for all sufficiently large \(m\ge m_0\) we have
\[
\supp{h_{\bar n}}[m]\setminus E^{(t,m)} \neq \emptyset.
\]
For such an \(m\), the for-loop finds an admissible \(x\) and sets \(o_t\neq\bot\), causing the repeat-until loop to terminate.\looseness=-1
\end{proof}


\begin{lemma}[Eventual validity]\label{lem:wp-eventual-valid}
There exists \(t^\star<\infty\) such that for all \(t\ge t^\star\) the output satisfies
\[
o_t \in \supp{h_z}\setminus \bc{x_1,\ldots,x_t}.
\]
\end{lemma}

\begin{proof}
Let \(t^\star\) be as in Lemma~\ref{lem:wp-eventual-critical} and fix \(t\ge t^\star\).
The branch \(V_t=\emptyset\) cannot occur since \(h_z\) is always consistent with \(S_t\) and hence \(z\in V_t\).
Thus, \(V_t\neq\emptyset\) and the algorithm outputs some \(o_t\in \supp{h_{n^{(t,m)}}}[m]\setminus \br{S_t\cup O_{t-1} \cup W^{(t,m)}}\) for the final value of \(m\) in the repeat-until loop.

Since \(h_z\) is \((t,m)\)-critical, we have \(n^{(t,m)} \geq z\).
If \(n^{(t,m)}=z\), then \(o_t\in\supp{h_z}\) immediately.
If \(n^{(t,m)}>z\), applying condition (ii) of Definition~\ref{def:tm-critical-replay} to the pair \((i,n)=(z,n^{(t,m)})\) yields
\[
\supp{h_{n^{(t,m)}}}[m] \subseteq \supp{h_z}[m] \cup O_{t-1}.
\]
Because \(o_t\notin O_{t-1}\) by construction, it follows that \(o_t\in \supp{h_z}\).
Finally, \(o_t\notin S_t\) and \(o_t\notin O_{t-1}\) implies \(o_t\notin \bc{x_1,\ldots,x_t}\), since every observed example is either sure (hence in \(S_t\)) or a replay (hence in \(O_{t-1}\)).
Thus, \(o_t\in \supp{h_z}\setminus\bc{x_1,\ldots,x_t}\), as claimed.
\end{proof}


We can finally provide a proof of Theorem~\ref{thm:limit_replay_mq_only}.

\begin{proof}[Proof of Theorem~\ref{thm:limit_replay_mq_only}]
    \Cref{alg:computable-wp} only requires membership queries to evaluate \(h_i(x)\) for \(i\le t\) and \(x\leq m\), where \(t,m\) are finite.
    Additionally, Lemma~\ref{lem:wp-terminates} shows that, at every time \(t\), \Cref{alg:computable-wp} outputs some \(o_t\) after finitely many operations.
    Hence, \Cref{alg:computable-wp} is a computable procedure that can be implemented using membership queries alone.
    Now, fix any target \(h^\star \in \cH\).
    For any enumeration with replay for \(h^\star\) and \textsc{WP}, Lemma~\ref{lem:wp-eventual-valid} gives a time \(t^\star\) after which every output is fresh and valid for \(h^\star\).
    Therefore, \Cref{alg:computable-wp} generates \(h^\star\) in the limit with replay.
    Since \(h^\star\in\cH\) was arbitrary, the theorem follows.
\end{proof}


\subsection{Separation Between Generation in the Limit With and Without Replay}
\label{subsec:separation-with-without-replay}

While the previous result shows that replay does not impose additional hardness on the generatability in the limit of countable hypothesis classes, it leaves open whether replay can ever make generation strictly harder. 
The following theorem answers this in the affirmative: there are (uncountable) classes that are generatable in the limit in the standard sense but not generatable in the limit when replay is allowed.

\begin{restatable}{theorem}{thmseparationlimitreplay}
\label{thm:separation-lim-with-replay}
There exists a hypothesis class \(\cH\) that is generatable in the limit but is not generatable in the limit with replay.
\end{restatable}

We prove~\Cref{thm:separation-lim-with-replay} by an explicit construction loosely based on \citet{bai2025language}. 
First, we need to introduce some additional notation.
Let the domain be \(\cX \coloneqq \bZ \cup \bc{*^n \mid n \in \bN}\). 
Strings of the form \(*^n\) act as ``special tokens'' that will index the relevant subclass.
For \(b \in \bN_0\), define
\begin{align*}
\cH^b_1 &\coloneqq \bc{ h \in \bc{0,1}^{\cX} \,\Big|\, \supp{h}=\bc{b}\cup A \cup \bc{x\in\bZ : x>j} \text{ for some } A\subseteq \bZ,\ j>b},\\
\cH^b_2 &\coloneqq \bc{ h \in \bc{0,1}^{\cX} \,\Big|\, \supp{h}=\bc{x\in\bZ : x<b}\cup A \text{ for some } A\subseteq \bZ\setminus\bc{b}},
\end{align*}
and let \(\cH^b \coloneqq \cH^b_1 \cup \cH^b_2\).
Informally, \(\cH^b_1\) contains hypotheses whose support includes \(b\) and contains all integers larger than some cutoff \(j>b\), whereas \(\cH^b_2\) contains hypotheses that omit \(b\) but include every integer less than \(b\).
Both classes also include an arbitrary subset \(A\) of the remaining integers.\footnote{
    We note that $\mathcal{H}^b$ is generatable in the limit but not generatable in the limit with a single omission (i.e., by omitting $b$), as shown by \citet{bai2025language} (where they set $b=0$).
    However, $\mathcal{H}^b$ is generatable in the limit with replay: the generator of \citet{bai2025language} that works in the standard setting can be adapted to the replay setting by restricting it from outputting the crucial string $b$.
    Therefore, in order to show a separation between generation in the limit with and without replay, we will need a more involved construction.
    }

Next, for \(i\in\bc{1,2}\) define
\[
\widetilde{\cH}^b_i \coloneqq \bc{ \tilde h \in \bc{0,1}^{\cX} \,\Big|\, \supp{\tilde h}=\supp{h}\cup \bc{*^k : 1\le k\le b} \text{ for some } h\in \cH^b_i},
\]
and let \(\widetilde{\cH}^b \coloneqq \widetilde{\cH}^b_1 \cup \widetilde{\cH}^b_2\).
Thus, \(\widetilde{\cH}^b_i\) is obtained from \(\cH^b_i\) by adding the marker strings \(*^1,\ldots,*^b\) to the support of each hypothesis.
Finally, define the class
\[
\cH \coloneqq \bc{h^{\mathrm{mk}}} \cup \bigcup_{b\in\bN_0}\widetilde{\cH}^b
\quad \text{with} \quad h^{\mathrm{mk}}\coloneqq \mathbf{1}\bc{*^n \mid n \in \bN}.
\]
That is, \(\cH\) contains the all-marker hypothesis \(h^{\mathrm{mk}}\) together with all the padded classes \(\widetilde{\cH}^b\).

To prove~\Cref{thm:separation-lim-with-replay}, Lemma~\ref{lem:H-gen-limit} shows that \(\cH\) is generatable in the limit, while Lemma~\ref{lem:H-not-gen-replay} shows that \(\cH\) is not generatable in the limit with replay.
Interestingly, the separation relies on only a single replayed example.


\begin{lemma}\label{lem:H-gen-limit}
The class \(\cH\) is generatable in the limit.
\end{lemma}

\begin{proof}
Fix \(b\in\bN_0\). Let \(\cG^b\) be the generator from \citet{bai2025language} that generates \(\cH^b\) in the limit.
We briefly recall its definition:
\[\cG^b(x_1,\ldots,x_t)\coloneqq
\begin{cases}
    \max\bc{t,o_1,\ldots,o_{t-1},x_1,\ldots,x_t} + 1 & \text{if } b\in\bc{x_1,\ldots,x_t},\\
    \min\bc{b,o_1,\ldots,o_{t-1},x_1,\ldots,x_t} - 1 & \text{otherwise.}
\end{cases}\]
Essentially, if $h^\star\in\cH^b_1$ then \(\cG^b\) will observe \(b\) and eventually output unseen integers larger than the cutoff $j$; otherwise, if $h^\star\in\cH^b_2$ then \(\cG^b\) will always take the second branch and output unseen integers smaller than $b$.
Since \(\widetilde{\cH}^b\) only augments each \(h\in\cH^b\) by the same finite set of \(*\)-strings, the same generator \(\cG^b\) (ignoring the \(*\)-strings in its input) generates \(\widetilde{\cH}^b\) in the limit. 

We now use this to define a single generator \(\cG\) for \(\cH\).
Given a history \((x_1,\ldots,x_t)\), define
\[m(t)\coloneqq \max \bc{k\in\bN : *^k \in \bc{x_1,\ldots,x_t}},\]
with \(m(t)=0\) if no \(*\)-string has appeared.
Let \(Z_t \coloneqq \br{x_s \colon x_s \in \bZ,\ 1 \le s \le t}\) denote the subsequence of integer-valued examples in $x_{1:t}$, and set
\[\cG(x_1,\ldots,x_t)\coloneqq
\begin{cases}
    *^{m(t)+1} & \text{if } \bc{x_1,\ldots,x_t}\subseteq \bc{*^n\mid n\in\bN},\\
    \cG^{m(t)}\br{Z_t} & \text{otherwise.}
\end{cases}\]
Thus, if \(h^\star=\mathbf{1}\bc{*^n\mid n\in\bN}\) then the output of \(\cG\) is always an unseen \(*\)-string, so \(\cG\) generates \(h^\star\) in the limit.
Otherwise, for any \(h^\star\in\bigcup_{b}\widetilde{\cH}^b\), note that \[b^\star \coloneqq \max\bc{k : *^k \in\supp{h^\star}}\] equals the unique index such that \(h^\star\in \widetilde{\cH}^{b^\star}\).
Hence, on any enumeration \(\br{x_t}_{t\ge 1}\) of \(\supp{h^\star}\), the value of \(m(t)\) is nondecreasing and stabilizes to \(b^\star\) after the finite time \(t^\prime\) when \(*^{b^\star}\) appears in the enumeration.
Moreover, since \(\supp{h^\star} \cap \bZ\) is infinite, any enumeration of \(\supp{h^\star}\) must present an integer at some finite time \(t^{\prime\prime}\); after that time, \(\cG\) always takes the second branch.
Therefore, \(\cG\) copies \(\cG^{b^\star}\) for all \(t \geq \tilde{t}\coloneqq\max\bc{t^\prime, t^{\prime\prime}}\).
Since \(\cG^{b^\star}\) generates \(\widetilde{\cH}^{b^\star}\) in the limit, there exists $t^\star\in\bN$ such that \(\cG^{b^\star}\br{Z_t}\in\supp{h^\star}\setminus\bc{x_1,\ldots,x_t}\) for all \(t\ge t^\star\).
Thus, \(\cG\br{x_1,\ldots,x_t}\) is guaranteed to be a valid output for all \(t\geq\max\bc{\tilde{t},t^\star}\).
\end{proof}


\begin{lemma}\label{lem:H-not-gen-replay}
The class \(\cH\) is not generatable in the limit with replay.
\end{lemma}

\begin{proof}
Assume for the sake of contradiction that there exists a generator \(\cG\) that generates \(\cH\) in the limit with replay.
We construct an adversarial enumeration with replay \((x_t)_{t\ge 1}\) adaptively.
Since \(\cG\) is deterministic, the adversary can choose the next input based on \(\cG\)'s outputs while maintaining a nonempty set of candidate target hypotheses consistent with the observed prefix stream.
The construction identifies a hypothesis \(h^\star \in \cH\) that remains consistent with the entire realized stream \((x_t)_{t\ge 1}\) and for which \(\cG\) outputs infinitely many invalid elements.
Write \(o_t\coloneqq \cG(x_{1:t})\).
The enumeration is defined in two steps.

In the first step, the adversary forces the generator to output a ``long'' \(*-\)string marker.
Let \(h^{\mathrm{mk}}\coloneqq \mathbf{1}\bc{*^n \mid n \in \bN}\).
The adversary begins enumerating the support of \(h^{\mathrm{mk}}\) by presenting the sequence \(x_t\coloneqq *^t\).
Since \(\cG\) generates \(\cH\) in the limit with replay, there exists a time step \(\tau\) such that \(o_\tau \in \supp{h^{\mathrm{mk}}}\setminus\{x_1,\ldots,x_\tau\}\).
Let the output be \(o_\tau=*^z\) for some \(z>\tau\).
The adversary then extends the input sequence by displaying all \(*-\)strings until \(*^z\) by setting \(x_{\tau+1}\coloneqq
*^{\tau+1},\ldots,x_z\coloneqq *^z\).
Let \(J_0\coloneqq z\).\footnote{
    At a high level, note that since we are in the replay setting, $\mathcal{G}$ cannot know whether $*^z$ belongs to the support of the target hypothesis $h^\star$ or not.
    Hence, even upon observing $z-1$, $\cG$ does not know whether $h^\star \in \widetilde{\cH}^{z-1}$---in which case $h^\star \in \widetilde{\cH}^{z-1}_1$ and $\supp{h^\star}$ necessarily contains all integers larger than some cutoff $j$---or $h^\star \in \widetilde{\cH}^z$, in which case observing $z-1$ is uninformative, as $h^\star$ could belong to either $\widetilde{\cH}^z_1$ or $\widetilde{\cH}^z_2$. The second step of our construction relies on this observation to force infinitely many mistakes.
}

In the second step, the adversary forces infinitely many mistakes in multiple phases.
For each \(n\in\bN\), at the beginning of phase \(n\), the adversary presents the integer \(z-n\), and then presents the increasing tail \(J_{n-1}+1,J_{n-1}+2,\ldots\) until the first time \(t_n\) at which \(\cG\) outputs an integer \(o_{t_n}\) satisfying \(o_{t_n} > J_{n-1}\) and \(o_{t_n}\notin \bc{x_1,\ldots,x_{t_n}}\).
The adversary then sets \(J_n\coloneqq o_{t_n}\) and proceeds to phase \(n+1\), never presenting \(J_n\) as an element of the sequence.
\begin{claim}\label{claim:infinite-mistakes}
Each phase terminates, i.e., \(t_n<\infty\) for all \(n\in\bN\).
\end{claim}

We prove this claim later. 
First, we show how the adversary can use this fact to force infinitely many mistakes. 
Let \(S \subseteq \bZ\) be the set of all integers ever presented by the above construction during the second step, and define \[\supp{h^\star} \coloneqq S \cup \bc{*^k:1\le k\le z} = \bigcup_{t\ge 1}\bc{x_t}.\] 
Since \emph{every} integer smaller than \(z\) appears in the enumeration \((x_t)_{t\ge 1}\) as \(z-n\) for some \(n\in\bN\), we can write \[S = \bc{x\in\bZ:x<z} \cup A \quad \text{where} \quad A \coloneqq \bc{x\in S : x>z} \subseteq \bZ\setminus\bc{z}.\]
This shows that the example sequence \((x_t)_{t\ge 1}\) enumerates the support of a hypothesis \(h^\star\) that belongs to \(\widetilde{\cH}^{z}_2\).
However, by construction, \(o_{t_n}=J_n\notin \supp{h^\star}\) for each \(n\in\bN\).
Hence, $\br{t_n}_{n\ge 1}$ is an infinite sequence of time steps at which $\cG$ makes a mistake, contradicting that \(\cG\) generates \(\cH\) in the limit with replay.
\end{proof}


\begin{proof}[Proof of~\Cref{claim:infinite-mistakes}.]
Fix \(n\in\bN\). 
Suppose, for the sake of contradiction, that phase \(n\) does not terminate, i.e., the adversary keeps presenting \(J_{n-1}+1,J_{n-1}+2,\ldots\), but the generator never outputs a fresh integer larger than \(J_{n-1}\).
Let \(\hat{h}\) be the hypothesis whose support is enumerated by such an example sequence, excluding the (potentially replayed) string \(*^z\). 
Denote by \(X_{<n}\subseteq \bZ\) the finite set of integers that appear \emph{before} the beginning of phase \(n\), with \(X_{<1}=\emptyset\) for \(n=1\). Then, we can write
\[
\supp{\hat{h}} \coloneqq X_{<n} \cup \bc{z-n} \cup \bc{x\in\bZ : x>J_{n-1}} \cup \bc{*^k : 1\le k\le z-1}.
\]
Notice that \(z-1\) belongs to the support of \(\hat{h}\) for any \(n\in\bN\): for \(n=1\), it appears directly as \(z-n\); for all other \(n\), it already appeared during a previous phase and is contained in \(X_{<n}\).
Consequently, \(\hat{h}\) is a valid hypothesis from \(\widetilde{\cH}_1^{z-1}\).
By construction, the only string in the adversary's sequence that does not belong to the support of \(\hat{h}\) is \(*^z\), which nevertheless appears in the sequence as a replay of the earlier output \(o_\tau=*^z\).
Thus, the adversary's sequence is a valid enumeration with replay for \(\hat{h}\) and \(\cG\).
Therefore, since \(\cG\) generates \(\cH\) in the limit with replay, \(\cG\) must eventually output an unseen element from the support of \(\hat{h}\).
Since all elements of \(X_{<n} \cup \bc{z-n} \cup \bc{*^k : 1\le k\le z-1}\) have already appeared, any such fresh element must belong to the tail \(\bc{x\in\bZ : x>J_{n-1}}\).
Consequently, \(\cG\) outputs an unseen integer larger than \(J_{n-1}\) at a finite time, contradicting the assumption that phase \(n\) does not terminate. \looseness=-1
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:separation-lim-with-replay}]
    The hypothesis class \(\cH\) is generatable in the limit (Lemma~\ref{lem:H-gen-limit}), but not generatable in the limit with replay (Lemma~\ref{lem:H-not-gen-replay}).
\end{proof}