IIm18-Kreativaufgabe6

Aus ProgrammingWiki

Inhaltsverzeichnis 1 MIU-System (Douglas R. Hofstadter) 1.1 Symbole 1.2 Axiom 1.3 Regeln 1.4 Typografische Regeln: 1.5 Anwendung der typografischen Regeln 1.6 MU ist kein Satz im MIU-System 1.7 Überführung in die Zahlentheorie 1.8 Abbilden der Symbole auf die natürlichen Zahlen 1.8.1 Zuordnung von natürlichen Zahlen zu den Symbolen 1.8.2 Anpassung der Regeln 1.8.2.1 Allgemeine Form 1.8.2.2 Zahlentheoretische Form 1.8.3 Ziel

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

• 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

$M \hspace{2.5mm}\Leftrightarrow \hspace{2.5mm} 3$

$I \hspace{5mm}\Leftrightarrow \hspace{2.5mm} 1$

$U \hspace{4mm}\Leftrightarrow \hspace{2.5mm} 0$

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

$MU \Leftrightarrow 30$

$MIU \Leftrightarrow 310$

$MIIU \Leftrightarrow 3110$

...

Diese Umwandlung kann sich durch folgende Rechnung ergeben

Bsp.: $MIIU$

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

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

$MU = 30$