Ist diese Sprache entschieden?

Question

wie der Titel sagt; Ist diese Sprache entschieden und wie beweisen Sie es?

$$ l={\ langle m \ rangle \ mid m \ text {ist eine Turing-Maschine und es gibt einen Eingang, den} m \ text {hält auf} \}$$

Answer 1

Ihre Sprache ist nicht entschieden. Um zu zeigen, dass er genießt, dass das Vorhandensein einer Turing-Maschine $ T $ das entschieden hat $ L $ impliziert die Existenz einer Turing-Maschine, die das Anhalten des Anhaltensproblems löst.

in der Tat angesichts einer Turing-Maschine $ M $ mit input $ x $ Sie können ein Turing erstellen Maschine $ M '$ Das ignoriert seinen Eingang, schreibt $ x $ auf dem Band und simuliert dann < Span-Klasse="Math-Container"> $ M $ . Eindeutig $ M '$ hält (unabhängig von seiner Eingabe), wenn und nur, wenn $ M $ an der Eingabe hält $ x $ . Wir können entscheiden, ob $ M '$ hält, indem Sie prüfen, ob $ M' \ in L $ mit Klasse="Math-Container"> $ T $ mit input $ M '$ .