Universelle Turingmaschine
Einfache Sprache
Eine universelle Turingmaschine kann man sich wie eine TM vorstellen, die als eine Eingabe die Kodierung einer beliebigen TM und ein Eingabe für dies TM bekommt, und die kodierte TM auf der Eingabe simuliert um und das Ergebnis durchreicht.
Def. Universelle Turingmaschine
Sei $\mathcal M$ eine erkennbare oder entscheidbare TM und $w$ ein Wort über dem Eingabealphabet von $\mathcal M$. Eine universelle Turingmaschine $\mathcal U$ ist eine TM mit Eingabealphabet $\{0,1\}$ mit folgenden Eigenschaften:
- $\mathcal U$ akzeptiert $\langle\mathcal M, w\rangle$ genau dann, wenn $\mathcal M$ $w$ akzeptiert.
- $\mathcal U$ verwirft $\langle\mathcal M, w\rangle$ genau dann, wenn $\mathcal M$ $w$ verwirft.
Alternative Definition mit Berechenbare Funktion: Sei $\mathcal M$ eine TM, $f_\mathcal M$ die Berechnete Funktion von $\mathcal M$ und $w$ ein Wort über dem Eingabealphabet von $\mathcal M$. Eine universelle Turingmaschine $\mathcal U$ ist eine TM mit Eingabealphabet $\{0,1\}$ mit folgenden Eigenschaften:
- Falls $f_\mathcal M(w)$ definiert ist, gilt $f_\mathcal M(w) = f_\mathcal U(\langle \mathcal M, w\rangle)$.
- Sonst ist $f_\mathcal U(\langle \mathcal M, w\rangle)$ undefiniert.
Beweisidee: $\mathcal U$ könnte z.B. folgender Maßen konstruiert werden: Eine Mehrband-Turingmaschine speichert auf einem Band die aktuelle Konfiguration von $\mathcal M$ und auf anderen Bändern speichert sie z.B. die Funktionsweise/Transitionsfunktion von $\mathcal M$. Ausgehend von der Anfangskonfiguration werden nach und nach die Folgekonfiguration berechnet. Da wir eine DTM benutzen ist immer klar welche Folgekonfiguration folgt.