Infinite sequence of digits without consecutive repeating subsequenes

Question

Problem description:

Suppose we use a set of digits $\{0,1,2\}$ to form a sequence, for example \begin{equation} 120210120102012102010210120212010\cdots \end{equation} The length can be finite or infinite.

The sequence is invalid if there are two finite subsequences appears consecutively. For example, the following sequences are invalid \begin{equation} 0{\bf 11}\cdots, \quad 010{\bf 201\, 201 }\cdots \end{equation} where the consecutive subsequences are highlighted.

Question: Does there exist a valid sequence of infinite length? (a non-constructive proof is also acceptable; but a constructive one would be better.)

One way to think about it:

We can transform the sequence to a (base 3) real number, \begin{equation} 120\cdots \rightarrow 0.120\cdots \end{equation} Then the only possible infinite sequence should be a irrational number. Irrational number has no period, which means the pattern will not repeat infinite many times, but may repeat finite many times. A famous example is the Feynman point,

The Feynman point is a sequence of six 9s that begins at the 762nd decimal place of the decimal representation of $\pi$.

So not all irrational number($\le 1$) are valid sequences.

I use a short program to do enumeration, but it quickly falls in exponential growth of candidates. I failed to come up with a contraction.

Generalization:

Can we take a larger set like $\{0,1,2,3, \cdots, n\}$? Can we relax the constraint to be three consecutive repetition or more?

Motivation

This problem origins from threefold repetition rule in chess,

In chess and some other abstract strategy games, the threefold repetition rule (also known as repetition of position) states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions do not need to occur in succession. The idea behind the rule is that if the position occurs three times, no progress is being made.

It reduces to the proposed problem if we modify the this rule to be "the same position occurs two times with the same sequences of moves".

Thanks for your help.

Edit: I find a related question: Largest binary sequence with no more than two repeated subsequences

Answer 1

Yes, there are "valid" infinite sequences with three digits. They are called square-free words. Quoting the Wikipedia article:

In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row.

Thus a square-free word is one that avoids the pattern $XX.$

One example of an infinite square-free word over an alphabet of size $3$ is the word over the alphabet $\{0,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence. That is, from the Thue–Morse sequence $$0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1,\ 0,\ 0,\ 1,\ 0,\ 1,\ 1,\ 0,\dots$$ one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is $$1,\ 0,\ −1,\ 1,\ −1,\ 0,\ 1,\ 0,\ −1,\ 0,\ 1,\ −1,\ 1,\ 0,\ −1,\dots$$ (sequence A029883 in OEIS).

Another example found by John Leech is defined recursively over the alphabet $\{a,\ b,\ c\}.$ Let $w_1$ be any word starting with the letter $a$. Define the words $\{w_i \mid i \in \mathbb{N} \}$ recursively as follows: the word $w_{i+1}$ is obtained from $w_i$ by replacing each $a$ in $w_i$ with $abcbacbcabcba,$ each $b$ with $bcacbacabcacb,$ and each $c$ with $cabacbabcabac.$ It is possible to check that the sequence converges to the infinite square-free word $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\dots$$