Halteproblem für Turingmaschinen

Einfache Sprache

Def. Halteproblem für Turingmaschinen

Das Halteproblem für Turingmaschinen $\text{HALT}_\text{TM}$ ist definiert durch

$$\text{HALT}_\text{TM} = \{\langle\mathcal M, w\rangle\mid \mathcal M \text{ ist eine TM und die Berechnung von $\mathcal M$ auf $w$ terminiert}\}.$$

Sätze

• Satz Halteproblem für Turingmaschinen ist unentscheidbar
• Satz Halteproblem für Turingmaschinen ist erkennbar