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 das -te Folgenglied ist, so ist das -Folgenglied durch gegeben, wobei aus 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 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…2 = 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
- ↑ Marston Morse: Recurrent Geodesics on a Surface of Negative Curvature. Trans. Amer. Math. Soc. Vol. 22 (1921), S. 84–100.
- ↑ Axel Thue: Über unendliche Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), S. 1–22.
- ↑ Axel Thue: Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), S. 1–67.
- ↑ 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.
- ↑ Max Euwe: Mengentheoretische Betrachtungen über das Schachspiel. Proc. Konin. Akad. Wetenschappen. Vol. 32(5) (1929), S. 633–642.
