IIm18-Kreativaufgabe6

MIU-System (Douglas R. Hofstadter)

Symbole

M, I, U

Axiom

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. Wenn am Ende eines Satzes ein I steht, füge ein U daran
2. Wenn der Satz mit M beginnt, kopiere alle Zeichen nach dem M und füge diese an das Ende an
3. Wenn das I dreimal hintereinander auftritt, ersetze es durch U
4. Wenn das U zweimal hintereinander auftritt, werden beide U's gelöscht

Anwendung der typografischen Regeln

• MI \rightarrow MIU \rightarrow MIUIU \rightarrow MIUIUIUIU ...
• MI \rightarrow MII \rightarrow MIIII \rightarrow MUI \rightarrow MUIUI \rightarrow MUIUIUIUI \rightarrow ...
• \hspace{35mm}\rightarrow MIIIIIIII \rightarrow MUUII \rightarrow MII \rightarrow ...

MU ist kein Satz im MIU-System

• Anfangswort: MI
• Ziel: MU
• das heißt es müssen (unter anderem) alle I's eliminiert werden
• Eliminierung der I's nur durch Regel 3 möglich, die mindestens 3 I's voraussetzt
• nur durch Regel 2 können weitere I's erzeugt werden
• dabei werden diese aber immer verdoppelt \rightarrow d.h. Anzahl der I's ist 2^n
• es muss folglich eine Lösung für folgende allgemeine Gleichung gefunden werden, um die Anzahl der I's auf 0 zu bringen

2^n-3k = 0
2^n=3k
\frac{2^n}{3}=k

• jede natürliche Zahl lässt sich in Primfaktoren zerlegen
  • diese Darstellung ist eindeutig (Reihenfolge der Faktoren nicht betrachtet)
• da 2 und 3 Primzahlen sind und {2^n} bereits nur aus Primfaktoren (2*2*2... ) besteht, kann 3 als Primfaktor darin nicht vorkommen
• folglich ist {2^n} nicht ganzzahlig durch 3 teilbar, weswegen ein solches k hier nicht existiert
• Man kann also keine der Regeln n mal anwenden, damit alle I's beseitigt werden
• MU kann entsprechend kein Satz des MIU-Systems sein

Überführung in die Zahlentheorie

Abbilden der Symbole auf die natürlichen Zahlen

Zuordnung von natürlichen Zahlen zu den Symbolen

Dadurch ergeben sich für die unterschiedlichen Wörter des Systems Gödelnummern

...

Diese Umwandlung kann sich durch folgende Rechnung ergeben

Bsp.: MIIU

Anpassung der Regeln

Allgemeine Form

1. x1 \rightarrow x10
2. 3x \rightarrow 3xx
3. y111x \rightarrow y0x
4. y00x \rightarrow yx

Zahlentheoretische Form

• (m ist hier quasi die Länge/Anzahl der Zeichen von x)
• es wird jeweils noch mit angeführt, wie sich die Regeln aus der ausführlichen Form ergeben

1) 10*x+1 \rightarrow 10^2*x + 10

• x*10^1+1*10^0 \rightarrow x*10^2+1*10^1+0*10^0

2) 3*10^m+x \rightarrow 10^m*(3*10^m*x)+x

• 3*10^m + x*10^0 \rightarrow 3*10^{2*m} + x*10^m + x*10^0

3) y*10^{m+3} + 111 * 10^m + x \rightarrow y*10^{m+1} +x

• y*10^{m+3} + 1 * 10^{m+2} + 1 * 10^{m+1} + 1 * 10^m+ x*10^0 \rightarrow y*10^{m+1} + 0*10^1 + x*10^0

4) y*10^{m+2}+n \rightarrow y*10^m + n

• y*10^{m+2}+ 0*10^{m+1} + 0*10^m +n*10^0 \rightarrow y*10^m + n*10^0

Ziel