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

Erzeugung der Folge durch Substitution

Bildung der ersten Glieder

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

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

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