MU
Aus ProgrammingWiki
Inhaltsverzeichnis |
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.
typrografische Regeln:
(1) "Füge an den rechten Teil eines Satzes ein U ein, 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ätseln:
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$ .....
Beweisen Sie das MU kein Satz des MIU-Systems ist, indem Sie die Regeln in die Welt der Zahlentheorie überführen und auf dieser Basis nachweisen, dass MU nicht ableitbar ist.
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.
