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

* 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 \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$

====Anpassung der Regeln====
=====Allgemeine Form=====
# $x1 \rightarrow x10$
# $3x \rightarrow 3xx$
# $y111x \rightarrow y0x$
# $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$

* $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$

* $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$====