BuK/IIm18/IIm18-Kreativaufgabe6

Wiki-Quelltext dieser Seite.

==MIU-System (Douglas R. Hofstadter)==
===Symbole===
 M, I, U

===Axiom=== 
MI

===Regeln===

# Wenn xI ein Satz ist, dann auch xIU.
# Wenn Mx ein Satz ist, dann auch Mxx.
# In jedem Satz kann III durch U ersetzt werden.
# UU kann aus jedem Satz weggelassen werden.

===Typografische Regeln:===

# Wenn am Ende eines Satzes ein I steht, füge ein U daran
# Wenn der Satz mit M beginnt, kopiere alle Zeichen nach dem M und füge diese an das Ende an
# Wenn das I dreimal hintereinander auftritt, ersetze es durch U
# 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===

$M \Longleftrightarrow 3$

$I \Longleftrightarrow 1$

$U \Longleftrightarrow 0$


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


$MU \Longleftrightarrow 30$

$MIU \Longleftrightarrow 310$

$MIIU \Longleftrightarrow 3110$

...

Diese Umwandlung kann sich durch folgende Rechnung ergeben

Bsp.: MIIU

$3*10^3 + 1*10^2 + 1*10^1 + 0*10^0 = 3110$