Das MU-Rätsel

Ist MU ein Satz des MIU-Systems?

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.

typrografische Regeln:

(1) "Füge an den rechten Teil eines Satzes ein U ein, wenn dieser mit I endet."

(2) "Kopiere den Teil eines Satzes, der rechts neben M steht und füge ihn am rechten Ende an."

(3) "Ersetze den Teil eines Satzes durch U, welcher drei aufeinanderfolgende I's besitzt."

(4) "Lösche den Teil eines Satzes, welcher aus zwei aufeinanderfolgende U's besteht."

Anwendung der typografischen Regeln für die Lösung des MU-Rätseln:

MI \rightarrow MIU \rightarrow MIUIU \rightarrow MIUIUIUIU ....

MI \rightarrow MII \rightarrow MIIII \rightarrow MUI \rightarrow MUIUI \rightarrow MUIUIUIUI \rightarrow .....

\hspace{17mm}\rightarrow MIU \rightarrow .....

\hspace{17mm}\rightarrow MIIIIIIII \rightarrow MUUII\rightarrow MII\rightarrow .....

Beweisen Sie das MU kein Satz des MIU-Systems ist, indem Sie die Regeln in die Welt der Zahlentheorie überführen und auf dieser Basis nachweisen, dass MU nicht ableitbar ist.

Jedes Symbol wird auf ein neues abgebildet:

Jede Zahl heißt die Gödel-Nummer des entsprechenden Buchstabens

Somit ist die Gödel-Nummer einer Kette mit mehreren Buchstaben:

• Die Länge der Wörter in Bezug auf die Größe der Zahl setzen.
• Es lässt sich erkennen, dass pro Zeichen des Wortes die Zahl um das zehnfache wächst.
• Bsp.: MUUII = 3 * 10000 + 0 * 1000 + 0 * 100 + 1 *10 + 1 * 1 = 30011

Typische Ableitung im MIU-System, simultan in beiden Notationen

Regeln

(1): xI \rightarrow xIU

(2): Mx \rightarrow Mxx

(3): xIIIy \rightarrow xUy

(4): xUUy \rightarrow xy

x ist der linke Teil eines Satzes.

y ist der rechte Teil eines Satzes.

Regeln (Zahlentheorie)

In diesen Regeln sind m und k beliebige natürliche Zahlen und n ist irgendeine natürliche Zahl, die kleiner als 10^m ist.

(1): k \cdot 10 + 1 \rightarrow 10 \cdot (k \cdot 10 + 1)

Für den linken Teil des Satzes können k-Zeichen auftauchen, also k-Zahlen. Da die Anzahl von Zahlen pro Zeichen des Wortes um eine Zehnerstelle wächst, wird k \cdot 10 gerechnet. Abschließend wird für das I, 1 addiert.

Ersetzung: Da für diese Regel gilt, dass ein U nach einem I hinzugefügt wird, verlängert sich das Wort um ein Zeichen und folglich um eine Zehnerstelle, sodass (k \cdot 10 +1) *10 gerechnet wird.

(2): 3 \cdot 10^m + n \rightarrow (3 \cdot 10^m + n) \cdot 10^m + n

Da ein Satz mit M beginnt und danach ein rechter Satzteil folgt, wird 3 \cdot 10^m gerechnet. Das m ist die Anzahl der Zeichen, welche nach dem M folgen sollen. Dazu werden die einzelnen Zeichen, als Zeichen zum M addiert.

Ersetzung: Da der rechte Satzteil verdoppelt wird, ohne M, ensteht die Formel (3 \cdot 10^m + n) \cdot 10^m + n.

(3): m \cdot 10^{m+3} + 111 \cdot 10^m + n \rightarrow m \cdot 10^m + n

In einem Satz können drei aufeinanderfolgende I's vorkommen, worauf ein rechter Satzteil folgen kann, 111 * 10^m + n. Für den linken Satzteil werden m-Zahlenstellen + 3 Zahlenstellen für die I's berechnet.

Ersetzung: Aus dem Exponent wird die Zahl 3 gestrichen, da aus 3 I's ein U wird.

(4): k \cdot 10^{m+2} + n \rightarrow k⋅10^m + n

Nach einem linke Satzteil mit k-Zahlen können zwei U's vorkommen und ein rechter Satzteil folgen.

Ersetzung: Da zwei aufeinanderfolgende U's gelöscht werden können, entfällt die 2 im Exponent.

Nachweis anhand der Regeln (Zahlentheorie), dass MU nicht ableitbar ist.