Die Folge (auch Morse-Thue-Sequenz oder Thue-Morse-Sequenz genannt) besteht aus Wörtern gebildet aus 0 und 1 und wird wie folgt definiert: Das 1. Element ist: 0
Wenn $w$ das $n$-te Folgenglied ist, so ist das $(n+1)$-Folgenglied durch $ww\text{'}$, wobei in $w\text{'}$ aus $w$ gebildet wird, indem jede 0 durch 1 und jede 1 durch 0 ersetzt wird.

Sie beginnt mit: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, ...

Sie kann durch einen Substitutionsalgorithmus erzeugt werden, indem man mit 0 beginnt und in jedem Schritt eine 0 durch 01 und eine 1 durch 10 ersetzt.

Die führt zu der Folge 0,01,0110,01101001,... (oder dezimal 0,1,6,105,..).

Die Länge des Wortes verdoppelt sich von Folgenglied zu Folgenglied, weil jede Ziffer durch zwei Ziffern ersetzt wird. Alternativ kann man diese Folge auch mit einem Semi-Thue-System definieren. Sie hat enge Beziehungen zum Gray-Code.

Die Morsefolge wurde von Marston Morse in den Dreißiger Jahren gefunden als Beispiel für eine kubikfreie Sprache. Die Lösung von Axel Thue aus dem Jahre 1914 war ihm nicht bekannt.

Formale Sprachen

Thue-Morse sequence | Sucesión de Thue-Morse | Suite de Prouhet-Thue-Morse | Последовательность Морса | Thue-Morsejevo zaporedje