Programmsynthese, Entscheidbarkeit und das Halteproblem

Ich las eine Antwort auf eine kürzlich gestellte Frage und kam mir ein seltsamer, vergänglicher Gedanke in den Sinn. Meine Bitte könnte verraten, dass meine Theorie ernsthaft fehlt (meistens wahr) oder dass es für mich einfach zu früh ist, diese Seite zu lesen. Nun, mit dem Haftungsausschluss aus dem Weg ...

Es ist ein bekanntes Ergebnis der Berechenbarkeitstheorie, dass das Stoppproblem für TMs nicht entschieden werden kann. Dies schließt jedoch nicht aus, dass es Maschinen gibt, die das Stoppproblem für bestimmte Klassen von Maschinen lösen können (nur nicht alle).

Betrachten Sie die Menge aller entscheidenden Probleme. Für jedes Problem gibt es unendlich viele TMs, die diese Sprache bestimmen. Könnte folgendes möglich sein

Es gibt ein TM, das das Stoppproblem für eine Teilmenge von Turing-Maschinen entscheidet. und $S$
Alle entscheidenden Probleme werden von mindestens einer Turingmaschine in ? $S$

Natürlich kann das Finden der Turing-Maschine in selbst nicht berechenbar sein; aber wir ignorieren dieses Problem. $S$

EDIT: Basierend auf Shaulls Antwort unten scheint es, dass entweder (a) diese Idee zu schlecht spezifiziert ist, um sinnvoll zu sein, oder (b) mein vorheriger Versuch nicht ganz ins Schwarze getroffen hat. Während ich versuche, in den Kommentaren zu Shaulls Antwort näher darauf einzugehen, ist meine Absicht nicht, dass wir garantiert sind, dass die Eingabe TM in . Was ich mit meiner Frage wirklich gemeint habe, ist, ob es ein solches , so dass die Mitgliedschaft in ein entscheidbares Problem ist . Das Programm zur Lösung des Halteproblems für würde vermutlich "ungültige Eingabe" auf das Band oder etwas anderes schreiben, wenn eine Eingabe gegeben wird, die es als nicht in erkennt $S$ $S$ $S$ $S$ $S$ . Wenn ich es so formuliere, bin ich mir nicht sicher, ob dies uns erlaubt, das Stoppproblem zu lösen oder nicht, oder ob der Satz von Rice gilt (ist Entscheidbarkeit eine semantische Eigenschaft einer Sprache nach dem Satz von Rice?)

turing-machines undecidability halting-problem Patrick87
quelle

Ich denke, es gibt eine legitime / signifikante Frage an den Grenzen der Theorie, die hier irgendwo lauert, aber nicht in der aktuellen Form, dennoch +1 für den Versuch [und dieser Haftungsausschluss am Anfang ist überraschend, wenn man Ihren Repräsentanten- / Moderatorstatus berücksichtigt] ... vielleicht ist dies der Fall die Frage, die Sie gelesen haben? Algorithmus zur Lösung von Turings Stopping Problem

vzn

möglicherweise eine andere Möglichkeit, die Frage zu formulieren, weiß nicht, ob dies die Absicht war (was sie sehr fortgeschritten macht). Betrachten Sie alle möglichen "Quasialgorithmen" und ihre zugehörigen erkannten Mengen

. [siehe andere Frage für defns]. Ist die Vereinigung aller dieser erkannten Mengen

gleich der Menge aller rekursiven / entscheidbaren TMs?

S_{n}

$S_n$

S_{n}

$S_n$

vzn

Ich denke, es kann ein Problem mit der Formulierung des Problems geben.

$S=\{M: M$ $\}$ $S$

$S$

$S$ $S$ $S\neq \emptyset$ $S$ $S$ $S$

Shaull
quelle

S = {⟨ A ⟩ ∣ \forall x . A (x) ↓, L (A) \in R}

$S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$

L (A) \in R

$L(A)\in R$ bedeutet dies nicht

A

$A$ ist ein Entscheider. Deshalb entscheiden wir ausdrücklich.

Shaull

Ah richtig. Der Kommentar wurde korrigiert.

Raphael

+1 Ich bin mir nicht sicher, ob ich meine Bedeutung klar kommuniziert habe. Was ich wirklich gemeint war zu fragen , ob es möglich ist , dass eine solche

S

$S$ exists, and we can check an arbitrary TM to see whether it is in

S

$S$ . We don't know a priori that it is in

S

$S$ ; just that

S

$S$ is formulated in such a way that we can check. In other words, is it possible that there exists an

S

$S$ such that membership in

S

$S$ is decidable? Also, your last sentence is somewhat confusing;

S

$S$ is a set of Turing Machines (well, their representations); not of the languages the TMs decide... but I think I know what you mean to say.

Patrick87

(p.s. Sorry about getting your name wrong in my edits. Its being too early for me to do CS.SE is beginning to appear more and more likely)

Patrick87

Programmsynthese, Entscheidbarkeit und das Halteproblem

Antworten: