KA MU-Puzzle

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 Zahl zugeordnet. Welche Zahlen dabei verwendet werden, ist egal.

Entsprechend dieser Zuordnung ergibt sich für das Axiom MI nun die Abbildung 31. Jede Zuordnung ist sogleich Gödelnummer der entsprechenden Zahl.

Simultane Ableitung in MIU und 310 Notation

Zudem ist es möglich die Ableitungen in beiden Notationen (MIU und 310) simultan abzubilden, was im folgenden veranschaulicht werden soll.

1. Axiom: MI \Longleftrightarrow 31
2. Regel 2: MII \Longleftrightarrow 311
3. Regel 2: MIIII \Longleftrightarrow 31111
4. Regel 3: MUI \Longleftrightarrow 301
5. Regel 1: MUIU \Longleftrightarrow 3010
6. Regel 2: MUIUUIU \Longleftrightarrow 3010010
7. Regel 4: MUIIU \Longleftrightarrow 30110
8. \ldots

Aufstellen arithmetischer Regeln

Mit der Überführung in die Zahlentheorie sollen die Ableitungsregeln nun auch in arithmetische überführt werden. Wobei für die nachfolgenden Regeln gilt, dass m und k beliebige natürliche Zahlen und n eine beliebige natürliche Zahl kleiner 10^m sind.

1. Regel: Wenn 10m +1 erzeugbar, dann auch 10 * (10m + 1)
2. Regel: Wenn 3 * 10^m + n erzeugbar, dann auch 10^m * (3 * 10^m + n) + n
3. Regel: Wenn k * 10^{m+3} + 111 * 10^m + n erzeugbar, dann auch k * 10^{m+1} + n
4. Regel: Wenn k * 10^{m+2} + n erzeugbar, dann auch k * 10^m + n

Angewandt auf das obenstehende Beispiel ergibt sich folgende Belegung für k,m,n während der Ableitungsschritte:

1. Axiom: 31
2. Regel 2: 311 (m=1, n=1)
3. Regel 2: 31111 (m=2, n=11)
4. Regel 3: 301 (m=1, n=1, k=3)
5. Regel 1: 3010 (m=30)
6. Regel 2: 3010010 (m=3, n=10)
7. Regel 4: 30110 (m=2, n=10, k=301)
8. \ldots

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