KA MU-Puzzle

Aus ProgrammingWiki
< BuK < IIm13 < Studenten < simaknoc
Archivierte Version vom 2014-10-20T15:29:07+00:00. Aktuelle Version

Inhaltsverzeichnis

MU-Puzzle

Das MU-Puzzle ist ein von Douglas R. Hofstadter konzipiertes Rästel, bei dem es festzustellen gilt, ob MU ein Satz des MIU-Systems ist.

MIU-System

Das MIU-System setzt sich aus folgenden Bestandteilen zusammen:

Symbole

M, I, U

Axiom

MI

Regeln

  1. Regel: Wenn xI ein Satz ist, dann auch xIU.
  2. Regel: Wenn Mx ein Satz ist, dann auch Mxx.
  3. Regel: In jedem Satz kann III durch U ersetzt werden.
  4. Regel: UU kann aus jedem Satz weggelassen werden.

Typografische Regeln

Zum erweiternden Verständnis der Regeln des MIU-Systems soll für jede Regel ein typografisches Pendant erstellt werden.

  1. Regel: Wenn ein Satz mit I endet, so kann ihm ein U dahinter angefügt werden.
  2. Regel: Wenn ein Satz mit M beginnt, so kann der Teilsatz nach dem M kopiert und dahinter am rechten Ende angefügt werden.
  3. Regel: Drei aufeinanderfolgende I können durch ein U ersetzt werden.
  4. Regel: Zwei aufeinanderfolgende U können aus einem Satz gestrichen werden.

Anwendung der Regeln

Zunächst sollen zur Veranschaulichung einige Beispiele für die Erzeugung gültiger Sätze aufgeführt werden.

  • MI \underrightarrow{\small{1}} MIU \underrightarrow{\small{2}} MIUIU \underrightarrow{\small{2}} MIUIUIUIU \underrightarrow{} \ldots
  • MI \underrightarrow{\small{2}} MII \underrightarrow{\small{2}} MIIII \underrightarrow{\small{3}} MUI \underrightarrow{\small{1}} MUIU \underrightarrow{\small{2}} MUIUUIU \underrightarrow{\small{4}} MUIIU \underrightarrow{} \ldots
  • MI \underrightarrow{\small{2}} MII \underrightarrow{\small{1}} MIIU \underrightarrow{\small{2}} MIIUIIU \underrightarrow{\small{}} \ldots

Überführung in die Welt der Zahlentheorie

Zum Klären der Fragestellung, ob MU ein Satz des MIU-Systems ist, soll das Problem in die Zahlentheorie überführt werden. Zu diesem Zweck wird jedem Symbol des MIU-Systems eine Ziffer zugeordnet.

M \Longleftrightarrow 3 I \Longleftrightarrow 1 U \Longleftrightarrow 0

Weiterführendes

Grafische Repräsentation des MIU-Systems

Youtube-Video mit verschiedenen Graphen, die das MIU-System abbilden: https://www.youtube.com/watch?v=EhN28Fh22kY

Weiterführende Literatur

Gödel, Escher, Bach: ein endloses geflochtenes Band (Douglas R. Hofstadter) ISBN: 9783608930375