Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar

Einfache Sprache

Die Idee ist folgende: Wir nehmen eine TM wie aus dem Halteproblem für Turingmaschinen. Diese TM hat eine $w$ in ihr kodiert, mit dem es immer die Eingabe überschreibt und dann auf dem arbeitet. Es ist also unabhängig von der Eingabe. Dazu definieren wir eine Funktion die eine TM inkl. passende Eingabe in eine, wie oben beschriebene, TM mit kodierter Eingabe überführt. Wäre nun HALT-TM-EPSILON entscheidbar könnte man eine Eingabe für HALT-TM, wie oben beschrieben, in eine Eingabe für HALT-TM-EPSILON überführen. Damit wäre HALT-TM auch entscheidbar, ein Widerspruch, da wir wissen das HALT-TM nicht entscheidbar ist.

Def. Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar

HALT-TM-EPSILON ist nicht entscheidbar.

Beweisidee: Es wird eine Reduktion von HALT-TM-EPSILON auf HALT-TM und Satz Halteproblem für Turingmaschinen ist unentscheidbar.

Beweis: Gegeben eine TM $\mathcal M$ und eine Eingabe $w$ definieren wir die TM $\mathcal M_w$ wie folgt für die Eingabe $x$:

1. Überschreibe die Eingabe $x$ durch $w$.
2. Simuliere $\mathcal M$ auf dem Band ($w$).

$\mathcal M_w$ hält auf $\varepsilon$ gdw. $\mathcal M$ auf $w$ hält. Wir definieren nun $f:\{0,1\}^*\to\{0,1\}^*$ durch

$f$ ist berechenbar, z.B. durch die TM $\mathcal T$, der wie folgt für die Eingabe $x$ arbeitet:

1. Überprüfe, ob $x = \langle\mathcal M,w\rangle$ für ein geeignete TM $\mathcal M$ und geeignetes $w$ gilt. Falls nicht, gibt $\varepsilon$ aus. Geeignet meint hier, das Wort und TM zueinander passen.
2. Konstruiere $\langle\mathcal M_w\rangle$ und gebe es aus.

$f$ ist eine Reduktion von HALT-TM auf HALT-TM-EPSILON. Also gibt $\mathrm{HALT_TM}\leq\mathrm{HALT^\varepsilon_TM}$. Da Satz Halteproblem für Turingmaschinen ist unentscheidbar folgt das $\mathrm{HALT_TM^\varepsilon}$ nicht entscheidbar ist.