Bedeutung des Halteproblems

Das Halteproblem ist definiert als:

$H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$

Ich bin mir nicht sicher, was es bedeutet. Ist eine Sammlung von Turingmaschinen, so dass alle das Wort akzeptieren / ablehnen ? Ist das ein bestimmtes Wort? Oder bedeutet das ein Wort in ihrem Alphabet?$H_{TM}$$w$

Vielen Dank

Die Menge (oder Sprache, wenn Sie so wollen) ist eine Menge von Paaren wobei eine beliebige Zeichenfolge Ihres Alphabets ist und eine Turing-Maschine ist und mit als Eingabe anhält .$H_{TM}$ $(M,w)$$w$$M$$M$$w$

Dies bedeutet, dass ein Paar genau dann in der Menge ist, wenn .$P = (M,w)$$H_{TM}$$M(w) \downarrow$

Die Entscheidung für diesen Satz ist jedoch nicht möglich. Es gibt keine Turing-Maschine, die diese Sprache akzeptiert, und nichts weiter. Dies ist eine Version des Halteproblems (daher das ).$H$

Wir wählen zuerst ein Alphabet mit Symbolen, die unsere Turing-Maschinen auf den Bändern lesen und schreiben können. Normalerweise haben wir drei Symbole: , und "leer". Ein Wort ist eine endliche Folge von Symbolen.$0$$1$

Wenn und Wörter sind, können wir ein neues Wort das die beiden zusammengesetzten Wörter darstellt (dies erfordert eine gewisse Codierung, damit wir erkennen können, wo ein Wort aufhört und das andere beginnt).$u$$v$$\langle u, v \rangle$

Eine Turingmaschine kann mit einem Wort beschrieben werden.

Wie bei allen Entscheidungsproblemen ist eine Reihe von Wörtern . Genauer gesagt enthält alle Wörter der Form wobei eine Turing-Maschine ist.$H_{TM}$$H_{TM}$$\langle M,w \rangle$$M$$w$ ist ein beliebiges Wort und $M$ wird angehalten, wenn wir es mit Eingabe ausführen $w$.

Hier ist eine einfache / informelle Definition des Halteproblems mit minimaler symbolischer / mathematischer Sprache. Betrachten Sie zunächst die Turing-Maschine . Turingmaschinen lösen verschiedene Probleme basierend auf (Programmierung über) ihre Zustandstabelle.

Jetzt kann die Statustabelle jeder Turing-Maschine selbst wie alle Eingaben in eine Turing-Maschine als Zeichenfolge codiert werden. Betrachten Sie nun eine hypothetische Maschine${TM}_H$ welches ein Codierungspaar einer Statustabelle einer Maschine akzeptiert $M$und eine Eingabezeichenfolge $w$:: $\langle M, w \rangle$. nimm das an$TM_H$ akzeptiert die Eingabe iff (genau dann, wenn) Maschine $M$ hält bei der Eingabe an $w$. von Turings berühmtem Beweis für das Anhalten des Problems (1936),${TM}_H$ kann nicht existieren, dh dieses "Problem" ist nicht berechenbar.

das $H_{TM}$Sie beschreiben die Beschreibung desselben Problems in Bezug auf die Gruppen- / Sprachmitgliedschaft. Eine Zeichenfolge befindet sich im Set$H_{TM}$ iff $M$ hält an $w$.