IIm18-Kreativaufgabe6

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. 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

• Man startet mit MI
• Das Ziel ist es, dass das I verschwindet
• Man erhält mehr I's nur durch Regel (2)
• Dabei werden diese aber immer verdoppelt. Anzahl der I's ist also 2^n
• Man kann durch Regel (3) immer 3 I's entfernen. Dadurch verringert sich die Anzahl der I's um 3k, wenn man diese Regel k-mal anwendet
• Die anderen Regeln sind irrelevant, da sie die Anzahl der I's nicht verändern
• Man will alle I's eliminieren (Anzahl auf 0 bringen. Also: 2^n-3k=0)
• Umgeformt: \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)

1. 10*x+1 \rightarrow 10^2*x + 10
   1. 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
   1. 4*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
   1. 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
   1. y*10^{m+2}+ 0*10^{m+1} + 0*10^m +n*10^0 \rightarrow y*10^m + n*10^0

Ziel: MU = 30