Ist die Entscheidung über die Entscheidbarkeit entscheidend?

Ich frage mich, ob es ein entscheidbares Problem ist, über die Entscheidbarkeit eines Problems zu entscheiden. Ich vermute nicht, aber nach ersten Recherchen kann ich keine Literatur zu diesem Problem finden.

computability undecidability decision-problem synchronisieren
quelle

Oh, ich habe gehört, Sie mögen die Entscheidbarkeit, also ...

David Richerby

Ihre Frage ist in der aktuellen Form nicht beantwortbar, wie die beiden Antworten zeigen, die im Wesentlichen "Trivial, nein" und "Trivial, ja" sagen (mit einem Bonuskommentar, der "nein" zu "nein" sagt). Sie haben gefragt, ob ein Problem entscheidbar ist, aber Sie haben nicht definiert, um welches Problem es sich handelt. Was ist insbesondere der Input? Wenn Sie eine Turing-Maschine

entwerfen möchten, die Ihnen sagt, ob ein Problem entscheidbar ist, müssen Sie dieses Problem als Eingabe an

. Aber wie machst du das?

M

$M$

M

$M$

David Richerby

Angesichts der aktuellen Antworten gibt es die Frage "Entscheidet Entscheidet Entscheidbar Entscheidbar?", Aber ich werde es nicht fragen :-)

Mark Hurd

Antworten:

Hauptbearbeitung meines Originals:

Eine naive Lektüre Ihrer Frage scheint zu sein, sei das Problem $P$

Ist eine gegebene Sprache entscheidbar? $P=$ $L$

Dann fragst du

Ist entscheidbar? $P$

Wie DW und David bemerkt haben, lautet die Antwort "Ja, das ist es", obwohl wir nicht wissen, welcher der beiden trivialen Entscheider der richtige ist. Um Ihr Problem so zu gestalten, dass es nicht ganz so trivial ist, würde ich dies vorschlagen. Lassen Sie uns zunächst die Dinge einschränken, indem wir nur die Sprachen die von einigen TM akzeptiert werden . Der Grund dafür ist, dass eine Sprache, die von keinem TM akzeptiert wird, nicht wieder (erkennbar) und daher nicht rekursiv (entscheidbar) sein kann. Dann können wir als neu fassen $L(M)$ $M$ $P$

Bei einer Beschreibung, eines TM, ist entscheidbar? $P'=$ $\langle M\rangle$ $M$ $L(M)$

Nun ist eine Sprache der TM-Beschreibungen und keine Sprache der Sprachen, wie es schien (bei einer großzügigen Interpretation), und es ist jetzt völlig vernünftig zu fragen, ob die Sprache entscheidbar ist. Unter dieser Lesart die Sprache bestehend aus TM Beschreibungen ist nicht entscheidbar. Dies ist eine einfache Konsequenz des Satzes von Rice . Jetzt haben wir also zwei Antworten: Mein "Nein" und das "Ja" der DW, abhängig von der Interpretation. $P'$ $P$ $P'$

{⟨ M ⟩ ∣ M is a TM and L (M) is decidable}

$\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}$

Rick Decker
quelle

Vielen Dank! Wenn ich zumindest oberflächlich verstehe, haben mir beide Antworten die Informationen geliefert, nach denen ich gesucht habe: "Können wir eine Maschine erstellen, die entscheiden kann, was sie kann und was nicht?" (Keine gute Phrasierung, ich weiß, aber ich kann mir keine bessere Phrasierung vorstellen.) Sehr hilfreich, insbesondere, dass Sie beide Interpretationen anerkennen.

synchronisieren

Ich dachte zu zeigen, dass für jedes entscheidbare Problem ein Zertifikat (Algorithmus mit Beweis) und für jedes unentscheidbare Problem auch ein Zertifikat (Reduktion von unentscheidbarem Problem) ausreicht.

Rus9384

Wie wir in den verschiedenen Antworten gesehen haben, besteht ein Teil der Antwort darin, das richtige Problem zu formulieren.

Im Jahr 1985 schrieb Joost Engelfriet "Die Nicht-Berechenbarkeit der Berechenbarkeit" (Bulletin des EATCS Nr. 26, Juni 1985, Seiten 36-39) als Antwort auf eine Frage eines klugen Schülers. Leider war das BEATCS zu dieser Zeit nur auf Papier und der Artikel hinterließ keine elektronischen Spuren.

Der Autor übernimmt wir einen (logischen) Formalismus haben mit den üblichen Booleschen Operatoren und Variablen. Ihre genaue Definition ist nicht wichtig. Eine Formel spezifiziert eine Funktion iff (für alle ) ist wahr, wobei die Zahl ist die Zahl . $\Psi$ $F(m,n)$ $f:\Bbb N \to \Bbb N$ $m,n\in \Bbb N$ $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ $\underline m$ $m$

Ich zitiere:

Satz 1 . Sei ein Formalismus, in dem sowohl eine berechenbare als auch eine nicht berechenbare Funktion angegeben werden kann. Dann gibt es keinen Algorithmus, der für eine beliebig spezifizierbare Funktion (gegeben durch eine Formel, die sie spezifiziert) entscheidet, ob berechenbar ist. $\Phi$ $\Bbb N \to \Bbb N$ $f$ $f$

Der lustige Teil ist in der folgenden Beobachtung in der Zeitung gemacht:

Beachten Sie, dass dieser Satz auf Formalismen insbesondere gilt , in dem alle berechenbaren Funktionen angegeben werden können (eine natürliche Bedingung für einen solchen Formalismus), weil dann auch eine nicht-berechenbare Funktion angegeben werden können. $\Phi$

Hendrik Jan
quelle

Ja. Es ist immer entscheidbar.

Für jedes Problem P sei Q das Problem der Bestimmung, ob P entscheidbar ist oder nicht. Ich behaupte, dass Q entscheidbar ist. Hier ist der Grund. Tautologisch ist entweder P entscheidbar oder nicht. Eines der beiden Programme ist also korrekt: (1) print "yup P is decidable"oder (2) print "nope P is not decidable". Es mag nicht trivial sein, herauszufinden, welches dieser beiden Programme richtig ist, eines davon ist richtig, so dass es mit Sicherheit eine Entscheidung für Q gibt . Daher ist das Problem Q entscheidbar.

Dies erinnert an die folgende klassische Frage: Ist es entscheidend zu sagen, ob Collatz 'Vermutung wahr ist? Die Antwort ist ja. Dies mag seltsam aussehen, da niemand weiß, ob Collatz 'Vermutung wahr ist (das ist ein berühmtes offenes Problem). Was wir jedoch wissen, ist, dass Collatz 'Vermutung entweder wahr ist oder nicht. Im ersten Fall ist das Programm print "yup it's true"ein Entscheider. Im letzteren Fall ist das Programm print "nope it's not true"ein Entscheider. Wir wissen nicht, welcher ein gültiger Entscheider ist, aber dies reicht aus, um zu beweisen, dass ein gültiger Entscheider existiert. Daher ist das Problem entscheidend.

DW
quelle

Ich denke, Ricky Decker interpretiert die Frage überlegen. Entscheiden Sie bei einer bestimmten Kodierung eines Problems, ob das Problem entscheidbar ist.

Yuval Filmus

@YuvalFilmus, OK, das ist vernünftig. Haben Sie eine endliche Kodierung für Probleme (dh Sprachen), die Sie für sinnvoll halten und die das Problem nicht trivial machen? Die natürliche endliche Kodierung für eine Sprache ist eine Turing-Maschine, die diese Sprache erkennt, aber das macht das Problem trivial, wie Ihr Kommentar zu Ricky Deckers Antwort zeigt. Wir brauchen also eine andere vernünftige Kodierung, die nicht unter solchen Problemen leidet. Hast du irgendwelche Vorschläge dafür?

Sie können Logik erster Ordnung in einer geeigneten Sprache verwenden. Oder die Eingabe könnte eine Maschine in 0 'sein (zum Beispiel), dh eine Turing-Maschine mit Zugang zu einem stoppenden Orakel.

Yuval Filmus

Nach dem Satz von Rice wissen wir, dass es nicht zu entscheiden ist, ob R im RE-Universum vorkommt. Ist das nicht ausreichend (Nicht alle TMs sind Entscheider.)

Raphael

Vielen Dank! Dies war zwar nicht die von mir beabsichtigte Interpretation, aber es half mir zu verstehen, warum die Frage, die ich stellte, möglicherweise nicht gut genug formuliert war, um meine Absichten widerzuspiegeln.

synchronisieren