Morse-Folge

Die Folgenglieder der Morse-Folge (auch Morse-Thue-Sequenz, Thue-Morse-Sequenz oder Prouhet-Thue-Morse-Folge genannt) sind Wörter, die aus 0 und 1 gebildet werden und wie folgt definiert sind: Das erste Folgenglied ist 0. Wenn ${\displaystyle w}$ das ${\displaystyle n}$-te Folgenglied ist, so ist das ${\displaystyle (n+1)}$-Folgenglied durch ${\displaystyle ww'}$ gegeben, wobei ${\displaystyle w'}$ aus ${\displaystyle 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, …

Die Länge des Wortes verdoppelt sich von Folgenglied zu Folgenglied, weil jede Ziffer durch zwei Ziffern ersetzt wird.

Als alternative Schreibweise der Folge wird auch die zugehörige Folge aus 0 und 1 verwendet:

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, … (Folge A010060 in OEIS)

Diese Folge hat, wenn man mit 0 zu zählen beginnt, an der 0., der 3., der 5., der 6., der 9., der 10. usw. Stelle eine Null. Die bösen Zahlen geben die Stellen an, an denen die Morse-Folge eine Null hat. Die abscheulichen Zahlen geben die Stellen an, an denen diese Morse-Folge eine Eins hat.

Diese Folge lässt sich auch mit einem Semi-Thue-System definieren. Sie hat enge Beziehungen zum Gray-Code.

Die Morse-Folge ist eine kubikfreie Sprache: sie enthält nirgends drei aufeinanderfolgende identische Teile wie 000 oder 010101. Schreibt man die Folge als Nachkommastellen einer Binärzahl mit 0 vor dem Komma, erhält man die Prouhet-Thue-Morse-Konstante (0,01101001…₂ = 0,412454… – Folge A014571 in OEIS).