BuK/IIm13/Studenten/simaknoc/KA MU-Puzzle

Wiki-Quelltext dieser Seite.

==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'''

# Regel: Wenn xI ein Satz ist, dann auch xIU.
# Regel: Wenn Mx ein Satz ist, dann auch Mxx.
# Regel: In jedem Satz kann III durch U ersetzt werden.
# 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.

# Regel: Wenn ein Satz mit I endet, so kann ihm ein U dahinter angefügt werden.
# Regel: Wenn ein Satz mit M beginnt, so kann der Teilsatz nach dem M kopiert und dahinter am rechten Ende angefügt werden.
# Regel: Drei aufeinanderfolgende I können durch ein U ersetzt werden.
# 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. 

# Axiom: $MI \Longleftrightarrow 31$
# Regel 2: $MII \Longleftrightarrow 311$
# Regel 2: $MIIII \Longleftrightarrow 31111$
# Regel 3: $MUI \Longleftrightarrow 301$
# Regel 1: $MUIU \Longleftrightarrow 3010$
# Regel 2: $MUIUUIU \Longleftrightarrow 3010010$
# Regel 4: $MUIIU \Longleftrightarrow 30110$
# $\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.

# Regel: Wenn $10m +1$ erzeugbar, dann auch $10 * (10m + 1)$
# Regel: Wenn $3 * 10^m + n$ erzeugbar, dann auch $10^m * (3 * 10^m + n) + n$
# Regel: Wenn $k * 10^{m+3} + 111 * 10^m + n$ erzeugbar, dann auch $k * 10^{m+1} + n$
# 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:

# Axiom: $31$
# Regel 2: $311$ $(m=1, n=1)$
# Regel 2: $31111$ $(m=2, n=11)$
# Regel 3: $301$ $(m=1, n=1, k=3)$
# Regel 1: $3010$ $(m=30)$
# Regel 2: $3010010$ $(m=3, n=10)$
# Regel 4: $30110$ $(m=2, n=10, k=301)$ 
# $\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