Morsefolge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Folgenglieder der Morsefolge (auch Morse-Thue-Sequenz, Thue-Morse-Sequenz oder Prouhet-Thue-Morse-Folge genannt) bestehen aus Wörtern, welche 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 w w' gegeben, wobei w' aus 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, …

Bildung der ersten Glieder

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 Morsefolge 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[Bearbeiten]

Die Morsefolge 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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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.