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.

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…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]

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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.