Morse-Thue-Sequenz

Die Folgenglieder der Morsefolge (auch Morse-Thue-Sequenz oder Thue-Morse-Sequenz genannt) bestehen aus Wörtern, welche aus 0 und 1 gebildet werden und wie folgt definiert sind: Das erste Folgenglied ist 0. Wenn w das n-te Folgenglied ist, so ist das (n + 1)-Folgenglied durch ww' gegeben, wobei w' aus w gebildet wird, indem jede 0 durch 1 und jede 1 durch 0 ersetzt wird.

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

Dies führt zu der Folge 0, 01, 0110, 01101001, … (Folge A010060 in OEIS)

Bildung der ersten Glieder

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.