KA MU-Puzzle

Aus ProgrammingWiki

Inhaltsverzeichnis 1 MU-Puzzle 1.1 MIU-System 1.2 Typografische Regeln 1.3 Anwendung der Regeln 2 Überführung in die Welt der Zahlentheorie 2.1 Simultane Ableitung in MIU und 310 Notation 2.2 Aufstellen arithmetischer Regeln 2.3 Zentrale Aussage 3 Lösung des MU-Rätsels 4 Weiterführendes 4.1 Grafische Repräsentation des MIU-Systems 4.2 Weiterführende Literatur

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.

$M \Longleftrightarrow 3$

$I \Longleftrightarrow 1$

$U \Longleftrightarrow 0$

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$

Zentrale Aussage

Douglas R. Hofstadter beschreibt in seinem Buch, dass es, wenn es typografische Regeln gibt, die beschreiben, wie sich Zahlen im Dezimalsystem manipulieren lassen, dass es auch eine Entsprechung mit arithmetischen Regeln dafür gibt inklusive der Operationen mit Zehnerpotenzen, der Addition, Subtraktion etc.

Kurz: "Typographische Regeln für die Manipulation von Zahlzeichen sind in Wirklichkeit arithmetische Regeln für das Operieren mit Zahlen." (D.R.Hofstadter)

Lösung des MU-Rätsels

Nach der mehrfachen Ableitung von Sätzen im MIU-System, wird bald deutlich, dass das Ziel, das Wort MU abzuleiten, scheinbar nicht möglich ist, egal wie oft die einzelnen Regeln angewandt werden. Außerdem wird deutlich, dass die Anzahl der Is im Wort relevant ist, da zur Erlangung des Wortes MU eine durch 3 teilbare Anzahl an Is vorhanden sein muss, um sie mit der Regel 3 ersetzen zu können. Es wäre also wünschenswert eine durch 3 teilbare Anzahl an Is zu erzeugen.

Die Ausgangssituation sieht vor, dass es genau ein I gibt - eine nicht durch 3 teilbare Anzahl. Die Betrachtung der Regeln 1 und 4 zeigt, dass sie die Anzahl der Is nicht verändert. Sie können für die weitere Betrachtung also ignoriert werden.

Regel 2 verdoppelt die Zeichenkette nach dem M. Das heißt, dass sie also die Anzahl der vorhandenen Is verdoppelt. Damit nun aber eine durch 3 teilbare Anzahl an Is durch Regel 2 erzeugt werden kann, muss vorher schon eine durch 3 teilbare Anzahl vorhanden sein.

Ähnlich verhält es sich bei Regel 3. Um eine durch 3 teilbare Anzahl von Is durch Anwendung dieser Regel zu erhalten, also auch 0, muss es vorher eine durch 3 teilbare Anzahl vorhanden sein.

Es wird also deutlich, dass keine durch 3 teilbare Anzahl von I erzeugt werden kann, was auch die Begründung zur Lösung des MU-Rätsels liefert:

MU ist kein Satz des MIU-Systems.

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