IIm18-Kreativaufgabe6

MIU-System (Douglas R. Hofstadter)

Symbole

M, I, U

Axiom

MI

Regeln

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