Können wir eine Turing-Maschine finden, so dass es keine Turniermaschine gibt, um zu entscheiden, ob es auf $ \ epsilon $ hält?

Question

Das Halteproblem gibt an, dass es keine Turniermaschine gibt, die bestimmen kann, ob eine beliebige Turierungsmaschine auf $ \ Epsilon $ hält.Aber ich versuche etwas anderes zu fragen, können wir eine bestimmte Turing-Maschine finden $ M $ so, dass $ l_m={0^ n: m $ hält auf $ \ epsilon \} $ ist unentglicht? Oder zumindest können wir es beweisen, dass es solche gibt $ M $ ?

Die Sprache selbst ist nicht das Problem, es ist entweder $ l={0 ^ n: n \ in \ mathbb {n} \ \ in \ mathbb {n} \} $ oder $ l=phi $ und der Weg, um die Fälle zu unterscheiden, ist nur auf der rechten Seite der Definition von $ L $.

Mit anderen Worten, können wir eine Turing-Maschine so definieren, dass wir (oder eine Turing-Maschine) nicht feststellen können, ob es nicht auf $ \ Epsilon $ anhält>

Answer 1

Angenommen, Sie hatten ein solches TM, nämlich eine Maschine $ M $ , für die das Problem "tut $ M $ lautet Halt beim leeren Eingang? "Das Problem wäre sicherlich entschieden: einer von zwei Algorithmen muss korrekt sein, (1) Antwort "Ja" oder (2) Antwort "Nein".Die Tatsache, dass wir vielleicht nicht wissen, welcher der richtige Algorithmus ist, ist hier unerheblich;Das einzige, was zählt, ist, dass wir sicher sind, dass eins der Algorithmen der richtige ist, also wissen wir, dass das Problem entschieden ist.In allgemeinerer Bedingungen ist jegliches Entscheidungsproblem mit einer endlichen Anzahl von Instanzen entgreift.