Simulation von Turingmaschine

Question

Aufgabe:

Satz: Jede Turingmaschine kann von einem GOTO-Programm simuliert werden.


Problem/Ansatz:

Hallo zusammen, wie kann man den Satz beweisen?
Danke im Voraus für eure Antwort! :)

Answer 1

Es gibt ein GOTO-Programm, dass die Werte zweier Variablen addieren kann.

Daraus kann man ein GOTO-Programm schreiben, dass die Werte zweier Variablen multiplizieren kann.

Daraus kann man ein GOTO-Programm schreiben, dass prüft ob eine Zahl gerade ist und eines das prüft ob eine Zahl eine Primzahl ist.

Damit kann man den Inhalt eines in beide Richtungen unendlichen Bandes in einer Variable kodieren:

        \(x = \prod_{i=1}^\infty p_i^{x_i}\)

wobei \(p_i\) die \(i\)-te Primzahl ist. Die ungeraden \(i\) codieren die Zellen des Bandes rechts von der ersten Zelle, die Geraden \(i\) codieren die Zellen des Bandes links von der ersten Zelle.

Bis auf das Band sind alle weiteren Komponenten einer Turingmaschine endlich.

Comments

Danke erstmal für deine Antwort :)
Könntest du mir bitte ein Beispiel dazu geben, um besser zu verstehen, was du gemeint hast? Das wäre sehr nett von dir :))

---

Ich frage mich jetzt wie würde x aussehen, wenn wir einen endlichen Automaten statt eine Turingmaschine hätten?

---

wie würde x dass aussehen?

---

Genau so, nur dass es eine andere Bedeutung hätte, da Automaten kein nach beiden Seiten unendliches Band benötigen. \(x_1\) ist das erste Zeichen, \(x_2\) das zweite, etc.

---

Gibt es eine andere Möglichkeit außer das mit Primzahl und so?

---

Ja, es gibt andere injektive Abbildungen von \(\Sigma^*\) nach \(\mathbb{N}\).

---

Danke für deine Antwort! :)

Wie würde x dann aussehen?

---

Die Frage habe ich bereits beantwortet.

---

x=∏i=1∞pixi

Ja aber da haben wir P als Primzahl verwendet haben. Wie würde X dann aussehen, wenn wir mit der anderen Möglichkeiten arbeiten (ohne Primzahl) ?

---

Das Dezimalsystem funktioniert so, dass zum Beispiel

        \(36507 = 7\cdot 10^0 + 0\cdot 10^1 + 5\cdot 10^2 + 6\cdot 10^3 + 3\cdot 10^4\)

ist. Letztendlich werden damit alle endlichen Worter über dem Alphabet \(\Sigma = \{0,1,2,3,4,5,6,7,8,9\}\) umkehrbar eindeutig auf natürliche Zahlen abgebildet (abgesehen von führenden Nullen).

Das funktioniert entsprechend auch mit anderen Alphabeten.

---

Sorry wenn meine Frage jetzt doof ist, aber wieso Dezimalsystem und nicht Binärsystem (wegen kodieren)?

---

Das funktioniert entsprechend auch mit anderen Alphabeten.

---

Weißt du wie ich durch Pumping Lemma beweisen kann, dass es keinen universellen endlichen Automaten gibt?

---

Nein. Ich kenne nur einen Beweis ohne Pumping-Lemma.