Aus ProgrammingWiki

Inhaltsverzeichnis 1 Das MU-Rätsel 1.1 MIU-System (Douglas R. Hofstadter) 1.1.1 Symbole: 1.1.2 Axiom: 1.1.3 Regeln: 1.1.4 Typografische Regeln: 1.1.5 Anwendung der typografischen Regeln für die Lösung des MU-Rätsels: 1.1.6 Lösung des MU-Rätsels 1.2 Überführen der Regeln in die Welt der Zahlentheorie 1.2.1 Jedes Symbol wird auf ein neues abgebildet: 1.2.2 Jede Zahl heißt die Gödel-Nummer des entsprechenden Buchstabens. 1.2.3 Typische Ableitung im MIU-System, simultan in beiden Notationen 1.2.4 Regeln 1.2.5 Regeln (Zahlentheorie) 1.2.6 Wir können 31 erzeugen. 1.2.7 Zentrale Aussage 1.3 Grafische Repräsentation

Das MU-Rätsel

Ist MU ein Satz des MIU-Systems?

MIU-System (Douglas R. Hofstadter)

Symbole:

M, I, U

Axiom:

MI

Regeln:

(1) Wenn xI ein Satz ist, dann auch xIU.

(2) Wenn Mx ein Satz ist, dann auch Mxx.

(3) In jedem Satz kann III durch U ersetzt werden.

(4) UU kann aus jedem Satz weggelassen werden.

Typografische Regeln:

(1) "Füge an den rechten Teil eines Satzes ein U an, wenn dieser mit I endet."

(2) "Kopiere den Teil eines Satzes, der rechts neben M steht und füge ihn am rechten Ende an."

(3) "Ersetze den Teil eines Satzes durch U, welcher drei aufeinanderfolgende I's besitzt."

(4) "Lösche den Teil eines Satzes, welcher aus zwei aufeinanderfolgende U's besteht."

Anwendung der typografischen Regeln für die Lösung des MU-Rätsels:

MI $\rightarrow$ MIU $\rightarrow$ MIUIU $\rightarrow$ MIUIUIUIU ....

MI $\rightarrow$ MII $\rightarrow$ MIIII $\rightarrow$ MUI $\rightarrow$ MUIUI $\rightarrow$ MUIUIUIUI $\rightarrow$ .....

$\hspace{17mm}\rightarrow$ MIU $\rightarrow$ .....

$\hspace{17mm}\rightarrow$ MIIIIIIII $\rightarrow$ MUUII$\rightarrow$ MII$\rightarrow$ .....

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.

Überführen der Regeln in die Welt der Zahlentheorie

Jedes Symbol wird auf ein neues abgebildet:

$M \Longleftrightarrow 3$

$I \Longleftrightarrow 1$

$U \Longleftrightarrow 0$

Jede Zahl heißt die Gödel-Nummer des entsprechenden Buchstabens.

Somit ist die Gödel-Nummer einer Kette mit mehreren Buchstaben:

$MU \Longleftrightarrow 30$

$MIU \Longleftrightarrow 310$

$MIIU \Longleftrightarrow 3110$

etc.

• Die Länge der Wörter in Bezug auf die Größe der Zahl setzen.
• Es lässt sich erkennen, dass pro Zeichen des Wortes die Zahl um das Zehnfache wächst.
• Bsp.: MUUII = 3 * 10000 + 0 * 1000 + 0 * 100 + 1 *10 + 1 * 1 = 30011

Typische Ableitung im MIU-System, simultan in beiden Notationen

1)	MI	-----	Axiom	-----	31
2)	MII	-----	Regel 2	-----	311
3)	MIIII	-----	Regel 2	-----	31111
4)	MUI	-----	Regel 3	-----	301
5)	MUIU	-----	Regel 1	-----	3010
6)	MUIUUIU	-----	Regel 2	-----	3010010
7)	MUIIU	-----	Regel 4	-----	30110

Regeln

(1): xI $\rightarrow$ xIU

(2): Mx $\rightarrow$ Mxx

(3): xIIIy $\rightarrow$ xUy

(4): xUUy $\rightarrow$ xy

x ist der linke Teil eines Satzes.

y ist der rechte Teil eines Satzes.

Regeln (Zahlentheorie)

In diesen Regeln sind m und k beliebige natürliche Zahlen und n ist irgendeine natürliche Zahl, die kleiner als $10^m$ ist.

(1): $10 \cdot m + 1 \rightarrow 10 \cdot (10 \cdot m + 1)$

Beispiel: Übergang von Zeile 4 zu Zeile 5. Hier ist $m=30$.

(2): $3 \cdot 10^m + n \rightarrow 10^m \cdot (3 \cdot 10^m + n) + n$

Beispiel: Übergang von Zeile 1 zu Zeile 2, wobei sowohl m und n gleich 1 sind.

(3): $k \cdot 10^{m+3} + 111 \cdot 10^m + n \rightarrow k \cdot 10^{m+1} + n$

Beispiel: Übergang von Zeile 3 zu Zeile 4. Hier sind m und n gleich 1 und k ist 3.

(4): $k \cdot 10^{m+2} + n \rightarrow k⋅10^m + n$

Beispiel: Übergang von Zeile 6 zu Zeile 7. Hier ist $m=2$, $n=10$ und $k=301$.

Wir können 31 erzeugen.

1)	31	gegeben
2)	311	Regel 2 $(m=1, n=1)$
3)	31111	Regel 2 $(m=1, n=11)$
4)	301	Regel 3 $(m=1, n=1, k=3)$
5)	3010	Regel 1 $(m=30)$
6)	3010010	Regel 2 $(m=3, n=10)$
7)	30110	Regel 4 $(m=2, n=10, k=301)$

Zentrale Aussage

Typografische Regeln für die Manipulation von Zahlzeichen sind in Wirklichkeit arithmetische Regeln für das Operieren mit Zahlen.

Grafische Repräsentation

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