Morse-Folge

Bildung der ersten Glieder

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.

Erzeugung der Folge durch Substitution

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 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).

Geschichte

Die Morse-Folge wurde von Marston Morse 1921 für eine Anwendung in der Differentialgeometrie konstruiert.^[1] Die Lösung von Axel Thue aus den Jahren 1906^[2] bzw. 1912^[3] war ihm nicht bekannt. Die früheste Erwähnung dieser Folge findet sich in einem kurzen Artikel von Eugène Prouhet zum Prouhet-Tarry-Escott-Problem, der 1851 erschienen ist.^[4] 1929 gab es eine weitere unabhängige Entdeckung der Folge durch Max Euwe, der die Kubikfreiheit benutzte, um die Möglichkeit von nicht abbrechenden Schachspielen unter bestimmten Regelwerken zu beweisen.^[5]

Weblinks

• Thue-Morse Sequence Artikel zur Prouhet-Thue-Morse-Folge auf MathWorld (engl.).
• Thue-Morse Constant Artikel zur Prouhet-Thue-Morse-Konstante auf MathWorld (engl.).
• Jean-Paul Allouche, Jeffrey Outlaw Shallit: The Ubiquitous Prouhet-Thue-Morse Sequence (engl.). In: Cunsheng Ding, Tor Helleseth, Harald Niederreiter (Hrsg.): Sequences and Their Applications. Proceedings of SETA '98. Springer 1999, S. 1–16.

Einzelnachweise

1. ↑ Marston Morse: Recurrent Geodesics on a Surface of Negative Curvature. Trans. Amer. Math. Soc. Vol. 22 (1921), S. 84–100.
2. ↑ Axel Thue: Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), S. 1–22.
3. ↑ Axel Thue: Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), S. 1–67.
4. ↑ Eugène Prouhet: Mémoir sur quelques relations entre les puissances des nombres. C. R. Adad. Sci. Paris. Sér. 1, Vol. 33 (1851), S. 225.
5. ↑ Max Euwe: Mengentheoretische Betrachtungen über das Schachspiel. Proc. Konin. Akad. Wetenschappen. Vol. 32(5) (1929), S. 633–642.