turing machine mit genau 42 Zuständen / Zustand der mindestens 42 mal besucht wird

Ich versuche folgende Probleme zu lösen:

Beweis, ob die folgenden Probleme entscheidbar/unentscheidbar sind:

  1. Gegebene Turingmaschine M: Hat M genau 42 Zustände?
  2. Gegebene Turing-Maschine M: Hat M einen Zustand, der mindestens 42 Mal besucht wird, wenn er auf einem leeren Band gestartet wird?
  3. Gegebene Turing-Maschine M: Hat M einen Zustand, der nicht mehr als 42 Mal besucht wird, wenn er auf einem leeren Band gestartet wird?

Ich bin ziemlich neu im Thema Berechenbarkeitstheorie und meine Intuition ist die folgende:

  1. Entscheidbar, da die Anzahl der Zustände vielleicht irgendwie durch die Kodierung der Turingmaschine bestimmt wird (ich habe online etwas über die Kodierung durch eine Gödelzahl gelesen, aber das haben wir in meiner Vorlesung noch nicht gelernt).

  2. und 3. sind wahrscheinlich unentscheidbar. Ich habe versucht, dies zu beweisen, indem ich das Problem auf das Halteproblem auf einem leeren Band reduzierte, kam aber noch nicht auf die richtige Idee.

Ich würde mich über Ideen freuen, die mich in die richtige Richtung weisen...

Sprachliche Spitzfindigkeit: Es ist "entscheidbar", nicht "entscheidend". Und es ist "Berechenbarkeitstheorie" auf Englisch, nicht "Entscheidungstheorie". Bei letzterem geht es darum, als Mensch mit Präferenzen in Bezug auf Ergebnisse auszuwählen, welche Maßnahmen ergriffen werden sollen.
@HenningMakholm Danke - ich habe meinen Beitrag korrigiert :)

Antworten (2)

Hinweis zu (2): Angenommen M hat N Zustände. Nach 42 N + 1 Schritte steht die Maschine entweder still oder ...

(3) ist tatsächlich unentscheidbar. Hier ist eine Beweisskizze durch Reduktion des Halteproblems:

Vermuten Q ist irgendeine Maschine und wir wollen wissen, ob sie auf dem leeren Band stehen bleibt. Dann können wir systematisch eine Maschine konstruieren M Q das macht folgendes:

  1. Schreiben Sie eine Beschreibung von Q zum Band.

  2. Simulieren Sie die Maschine, deren Beschreibung auf dem Band ist, bis sie anhält. (Dazu gehören Techniken aus der Universalmaschine , die Sie hoffentlich konstruieren können).

  3. Löschen Sie den gesamten Inhalt des Bandes.

  4. Sobald das Band gelöscht ist, gehe zu Schritt 1 (d. h. Anfangszustand von M).

Nun, wenn Q hält dann an M Q wird sich immer wieder wiederholen und alles immer und immer wieder tun, sodass jeder Zustand unendlich oft erfüllt wird , was größer als ist 42 . Andererseits wenn Q nicht anhält, dann werden die Zustände, die Schritt 3 implementieren, null Mal ausgeführt, was weniger als 42 ist.

Wenn wir also einen Algorithmus haben, der Problem (3) entscheidet, wenden Sie diesen an M Q werde uns sagen ob Q stoppt. Und wir können offensichtlich ein Programm schreiben, das konstruiert M Q gegeben Q .

Wo dies schwierig wird, ist sicherzustellen, dass alle Staaten in M Q wird tatsächlich während eines abschließenden Laufs von gesehen Q . Es könnte sein, dass es eine Funktion von Turing-Maschinen gibt Q tatsächlich nicht verwendet -- vielleicht schreibt es nie ein 1auf das Band und bewegt sich nach links, während es in einen Zustand übergeht, dessen Zahl ein Vielfaches von 17 ist. Und wenn unsere universelle Maschine einen Zustand hat, der nur ausgeübt wird, wenn die simulierte Maschine es genau tut das, dann sind wir in Schwierigkeiten.

Ein Ausweg wäre, nachdem wir den Simulator für Schritt 2 programmiert haben M Q , um eine feste Maschine zu finden P wie (a) wenn P auf einem leeren Band gestartet wird, wird es auch auf einem leeren Band anhalten, (b) simulieren P übt jeden Zustand des jeweiligen Simulators aus, den wir geschrieben haben.

Dann entscheiden, ob Q Pausen, Form M P ; Q (Wo P ; Q ist eine Maschine, die zuerst tut P und bewegt sich dann in den ersten Zustand von Q ) und fragen Sie, ob dies einen Zustand hat, der höchstens 42 Mal besucht wird.

Alles in allem fühlt sich dieser Beweis komplizierter an, als er sein sollte. Vielleicht gibt es eine einfachere Konstruktion, die ich gerade übersehe.

...oder muss es doch einen Staat geben, der 42 mal besucht wurde?! Das Problem ist also nur ein spezifischer Fall des Leerbandproblems und daher unentscheidbar?!
@eva: Ja zum ersten Teil deines Kommentars, nein zum zweiten. Der Punkt ist, dass Sie die Eigenschaft einfach durch Simulation bestimmen können 42 N + 1 Schritte der Maschine und zählen Sie, wie oft jeder Zustand gesehen wird. Entweder stoppt die Maschine vorher 42 N + 1 , und zu diesem Zeitpunkt sehen Sie sich nur die Zählungen an, um die Antwort zu finden - oder es läuft immer noch im Schritt 42 N + 1 , in diesem Fall wissen Sie, dass die Antwort "Ja" lauten muss, auch ohne sich die Anzahl anzusehen.
Beachten Sie insbesondere, dass ein bestimmter Fall eines unentscheidbaren Problems nicht selbst unentscheidbar sein muss. Zum Beispiel ist das Halteproblem unentscheidbar, aber wenn wir es auf den speziellen Fall von Maschinen beschränken, die keinen Stoppzustand haben, wird es trivial!
Natürlich! Das macht Sinn - danke ... Ich werde versuchen, die Antworten für 1 und 2 vollständig zu "begreifen", bis ich zu Frage 3 übergehe ;)
Wow - danke für die Erklärung zu 3. Ich bin mir nicht ganz sicher, ob ich mir vorstellen kann, wie die Maschine P aussehen würde, aber ich verstehe definitiv die Idee. So wie Sie die Schritte 1 - 4 konstruiert haben, werden Reduktionen normalerweise so durchgeführt? Es scheint, als könnte dies bei mehreren Problemen mit kleinen Änderungen funktionieren, wie in unserem Fall, um sicherzustellen, dass jeder der MQ-Zustände tatsächlich besucht wird.
@eva: P wäre typischerweise eine lineare Folge von unsinnigen Operationen wie "schreiben 1, nach links bewegen, zurück bewegen, löschen 1, ....". Wir können es iterativ konstruieren: In jedem Schritt gibt es einen Kandidaten P . Überlegen Sie, wie die Universalmaschine dies simuliert. Wenn jeder Zustand der universellen Maschine besucht wurde, sind wir fertig. Wählen Sie andernfalls einen Staat aus, der nicht besucht wird, finden Sie heraus, wozu dieser Staat überhaupt dient, und puzzeln Sie eine Erweiterung für Ihren Kandidaten zusammen P das wird es ausüben. Spülen und wiederholen, bis fertig.
@eva: Was die Reduktionen anbelangt, so werden die einzelnen vier Schritte hier speziell für das spezielle Problem (3) ausgewählt, von dem wir annehmen , dass es (für einen Widerspruch) entschieden werden kann. Hier gibt es ein gemeinsames Thema, da das Problem, das wir als unentscheidbar beweisen wollen, eine Turing-Maschine als Eingabe benötigt , die Reduktion diese Turing-Maschine als Ausgabe erzeugen muss . Und wenn das Problem, von dem wir reduzieren , auch eine Frage von Turing-Maschinen ist, dann muss die Reduzierung eine Turing-Bearbeitung als Eingabe verwenden . Es liegt also in den Randbedingungen, dass der Beweis darin bestehen wird, zu beschreiben, wie man einen Turing transformiert ...
... Maschine Q zu einer anderen Turing-Maschine M Q . Aber es ist keine universelle Tatsache, dass dies durch Einbetten einer universellen Maschine erfolgen muss – es ist eine sehr nützliche allgemeine Idee, mit der man vertraut sein sollte, aber es ist nicht immer das, was funktioniert.
@HenningMakholm, können Sie bitte diesen Absatz ausarbeiten: „Wenn Q anhält, wird MQMQ die Schleife fortsetzen und alles immer wieder wiederholen, sodass jeder Zustand unendlich oft erfüllt wird, was größer als 4242 ist. Andererseits, wenn QQ nicht anhält, dann werden die Zustände, die Schritt 3 implementieren, null Mal ausgeführt, was weniger als 42 ist."

Wenn Sie also denken, dass es unentscheidbar ist , erfolgt die Reduktion vom Halteproblem zu Problem 2/3. Der entscheidende Schritt in diesem Beweis ergibt sich aus der Tatsache, dass Sie, wenn die Probleme 2/3 tatsächlich unentscheidbar sind, jede Instanz des Halteproblems nehmen und in eine Instanz von Problem 2/3 übertragen können. Lösen Sie es dort, was eine Lösung des ursprünglichen Halteproblems impliziert. So kann ich es am besten formulieren, ohne zu viel vom Beweis preiszugeben.

turing machine mit genau 42 Zuständen / Zustand der mindestens 42 mal besucht wird
AntwortenHierDatenschutz-Bestimmungen1y, 0v