Largest binary sequence with no more than two repeated subsequences

Question

$A$ is an ordered sequence of elements $a_i = 0, 1$ containing no more than two adjacent repeated subsequences $[a_i, a_{i + k})$. What is the longest sequence $A$? Is it even finite?

For example, the subsequence $\{0\}$ is found three times in a row in $\{0, 0, 0\}$, and $\{1, 0\}$ is found in $\{\ldots, 1, 0, 1, 0, 1, 0, \cdots\}$ at least three times in a row. Therefore, both sequences are invalid.

As a simplification, if the number of allowed repeated subsequences is decreased to one, the sequences with the maximum cardinality under this new restriction are simply $\{0, 1, 0\}$ and $\{1, 0, 1\}$, each containing 3 elements.

Answer 1

As Gerry Myerson noted in the comments, you're probably interested in cube-free binary words. There are many cube-free infinite binary words (words of infinite length). In fact, there are an infinite number of them. Furthermore, there are an uncountably infinite number of them.

Answer 2

A simple and unusually interesting example is the Thue-Morse sequence. Let: $$\begin{align} S_0 & = \langle 0\rangle \\ S_1 & = \langle 0, 1\rangle \\ S_2 & = \langle 0, 1, 1, 0\rangle \\ S_3 & = \langle 0, 1, 1, 0, 1, 0, 0, 1\rangle \\ S_4 & = \langle 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0\rangle \\ &\vdots \end{align}$$

Where $S_{i+1}$ is formed by concatenating $S_i$ with its own inverse, which has 1 wherever $S_i$ has 0 and vice-versa. The Thue-Morse sequence is the "limit" of this process: The $i$th element of the Thue-Morse sequence is the same as the $i$th element of the first $S_n$ that is long enough to have an $i$th element.

$TM$ satisfies the following recurrence:

$$ \begin{align} TM(0) & = 0 \\ TM(2n) & = TM(n) \\ TM(2n+1) & = 1-TM(n) \end{align} $$

This sequence $TM$ has the property that for any sequence $X$, $TM$ does not contain $XXX$.