Thue-Morse-Folge

Thue-Morse-Folge

Die Folgenglieder der Morsefolge (auch Morse-Thue-Sequenz oder Thue-Morse-Sequenz 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 ww' 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, … (Folge A010060 in OEIS)

Bildung der ersten Glieder

Die Länge des Wortes verdoppelt sich von Folgenglied zu Folgenglied, weil jede Ziffer durch zwei Ziffern ersetzt wird. Alternativ kann man diese Folge auch mit einem Semi-Thue-System definieren. Sie hat enge Beziehungen zum Gray-Code.

Die Morsefolge wurde von Marston Morse in den Dreißiger Jahren gefunden, als Beispiel für eine kubikfreie Sprache. Die Lösung von Axel Thue aus dem Jahre 1914 war ihm nicht bekannt.


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Thue-Morse-Sequenz — Die Folgenglieder der Morsefolge (auch Morse Thue Sequenz oder Thue Morse Sequenz 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 …   Deutsch Wikipedia

  • Morse-Thue-Sequenz — Die Folgenglieder der Morsefolge (auch Morse Thue Sequenz oder Thue Morse Sequenz 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 …   Deutsch Wikipedia

  • Unendlichkeitsreihe — Die Unendlichkeitsreihe ist eine unendliche Folge von ganzen Zahlen, die der dänische Komponist Per Nørgård als mathematische Grundlage für Kompositionen verwendete. Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 In der Musik …   Deutsch Wikipedia

  • Morsefolge — Die Folgenglieder der Morsefolge (auch Morse Thue Sequenz oder Thue Morse Sequenz 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 …   Deutsch Wikipedia

  • Formale Sprache — Eine formale Sprache ist eine bestimmte Menge von Zeichenketten, die aus einem Zeichenvorrat zusammengesetzt werden können. Anwendung finden formale Sprachen in der Linguistik, der Logik und der theoretischen Informatik. Formale Sprachen eignen… …   Deutsch Wikipedia

  • Konkatenation (Formale Sprache) — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Leere Sprache — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Potenz (Formale Sprache) — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Wortmenge — Die Artikel Formale Sprache, Formales System, Formales System (Logik) und Kalkül überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”