Gibt es bestimmte Probleme, von denen bekannt ist, dass sie aus anderen Gründen als der Diagonalisierung, der Selbstreferenz oder der Reduzierbarkeit nicht entschieden werden können?

28

Jedes unentscheidbare Problem, das ich kenne, fällt in eine der folgenden Kategorien:

  1. Unentscheidbare Probleme durch Diagonalisierung (indirekte Selbstreferenz). Diese Probleme, wie das Problem des Anhaltens, sind nicht zu entscheiden, da Sie einen angeblichen Entscheider für die Sprache verwenden könnten, um ein TM zu konstruieren, dessen Verhalten zu einem Widerspruch führt. Sie könnten auch viele unentscheidbare Probleme bezüglich der Komplexität von Kolmogorov in dieses Lager werfen.

  2. Probleme, die aufgrund der direkten Selbstreferenz unentscheidbar sind. Zum Beispiel kann die universelle Sprache aus folgendem Grund als unentscheidbar gezeigt werden: Wenn sie entscheidbar wäre, wäre es möglich, Kleenes Rekursionssatz zu verwenden, um ein TM zu erstellen, das seine eigene Codierung erhält, und zu fragen, ob es seine eigene Eingabe akzeptieren wird macht dann das Gegenteil.

  3. Probleme, die nicht zu entscheiden sind, weil bestehende, nicht zu entscheidende Probleme reduziert wurden. Gute Beispiele hierfür sind das Post-Correspondence-Problem (Reduktion vom Halteproblem) und das Entscheidungsproblem.

Wenn ich meinen Schülern Berechenbarkeitstheorie beibringe, nehmen auch viele Schüler dies zur Kenntnis und fragen mich oft, ob es Probleme gibt, die wir als unentscheidbar erweisen können, ohne letztendlich auf eine Art Selbstreferenztrick zurückzugehen. Ich kann nicht konstruktiv beweisen, dass es unendlich viele unentscheidbare Probleme gibt, indem ich ein einfaches Kardinalitätsargument verwende, das die Anzahl der TMs mit der Anzahl der Sprachen in Beziehung setzt, aber dies gibt kein spezifisches Beispiel für eine unentscheidbare Sprache.

Gibt es Sprachen, von denen bekannt ist, dass sie aus Gründen, die oben nicht aufgeführt sind, unentscheidbar sind? Wenn ja, was sind sie und welche Techniken wurden verwendet, um ihre Unentscheidbarkeit zu beweisen?

templatetypedef
quelle
@EvilJS Mein Verständnis war, dass der Unentscheidbarkeitsbeweis die Fähigkeit beinhaltete, TMs zu simulieren, obwohl ich mich vielleicht irre?
Templatetypedef
Sie können sagen, dass der Satz von Rice möglicherweise nicht in eine dieser Kategorien passt, der Beweis des Satzes jedoch.
Ryan
1
@ EvilJS Das ist ein guter Punkt. Was ich hier wirklich suche, ist, ob es eine grundlegend andere Technik gibt, die wir anwenden können. Es wäre zum Beispiel schön, wenn jemand ein Problem als unentscheidbar in einem Fall identifizieren würde, in dem keine Beziehung zu TM-Selbstreferenz oder einem Argument vom Typ Godeling bekannt ist. Wenn das Beste ist, was wir tun können: "Wir haben es vor langer Zeit herausgefunden und dann festgestellt, dass es einfacher ist, es auf andere Weise zu beweisen." Unentscheidbarkeit, die wir kennen.
Templatetypedef
2
Die Belegt-Biber-Funktion wächst zu schnell, als dass ein Programm sie berechnen könnte. Konkret können Sie eine Funktion als eins plus die größte Zahl definieren, die von einem Programm mit einer Länge von höchstens berechnet wird . Zählt das als Diagonalisierung? nf(n)n
Yuval Filmus
1
@YuvalFilmus Vielleicht bin ich hier zu streng, aber das klingt für mich nach einem diagonalen Argument: Sie konstruieren eine Funktion, die sich von allen von TMs berechneten Funktionen unterscheidet.
Templatetypedef

Antworten:

10

Ja, es gibt solche Beweise. Sie basieren auf dem Low Basis Theorem .

Siehe diese Antwort auf Gibt es Beweise für die Unentscheidbarkeit des Halteproblems, die nicht von der Selbstreferenzierung oder Diagonalisierung abhängen? Frage zur Theorie für mehr.

Kaveh
quelle
Wenn sich jemand für fortgeschrittene Techniken in der Berechenbarkeitstheorie interessiert, lesen Sie die Bücher von Robert I. Soare über rekursiv aufzählbare Mengen und Grade sowie Berechenbarkeitstheorie und -anwendungen .
Kaveh
Korrigieren Sie mich, wenn ich falsch liege, aber besteht der Beweis des Satzes der niedrigen Basis nicht darin, eine Funktion auf sich selbst anzuwenden und zu fragen, ob sie keinen Wert erzeugt? Wenn ja, ist das nicht nur eine Indirektionsebene über einem diagonalen Argument?
Templatetypedef
@templatetypedef, ich bin kein Experte aber soweit ich nein verstehe. Siehe z. B. Seite 109 in Soares Buch.
Kaveh
@templatetypedef, ps1: Die Frage, was wir unter Diagonalisierung verstehen, ist etwas vage. Wenn wir nicht aufpassen, können wir das, was wir als Diagonalisierung betrachten, jedes Mal erweitern, wenn wir etwas sehen, was nicht so war. Nehmen Sie z. B. Prioritätsmethoden oder eine allgemeine Methode, um Objekte Teil für Teil so zu konstruieren, dass sie keinem Objekt einer bestimmten Klasse entsprechen.
Kaveh
2
@David, :) Ich öffne die Seite aus dem Buch, das ich teilen möchte, klicke oben auf die Schaltfläche "Teilen" und entferne die Parameter mit Ausnahme von idund pgaus dem Link.
Kaveh
0

Dies ist nicht gerade eine bejahende Antwort, sondern ein Versuch, etwas in der Nähe dessen zu finden, was über einen kreativen Blickwinkel verlangt wird. Es gibt in der Physik eine ganze Reihe von Problemen, die "weit entfernt" von mathematisch / theoretischen Formulierungen der Unentscheidbarkeit sind, und sie scheinen sich zunehmend von den ursprünglichen Formulierungen zu "entfernen" und "wenig zu ähneln", die das Halteproblem betreffen usw .; Natürlich verwenden sie das Halteproblem an der Wurzel, aber die Argumentationsketten sind zunehmend distanzierter geworden und haben auch einen starken "angewandten" Aspekt / Charakter. Leider scheint es in diesem Bereich noch keine großartigen Umfragen zu geben. Ein aktuelles Problem, das sich in der Physik als "überraschend" unentscheidbar erwiesen hat und viel Aufmerksamkeit auf sich gezogen hat:

Die spektrale Lücke - die Energiedifferenz zwischen dem Grundzustand und dem ersten angeregten Zustand eines Systems - ist für die Quantenvielkörperphysik von zentraler Bedeutung. Viele herausfordernde offene Probleme, wie die Haldane-Vermutung, die Frage nach dem Vorhandensein von topologischen Spin-Flüssig-Phasen mit Lücken und die Yang-Mills-Lücken-Vermutung, betreffen spektrale Lücken. Diese und andere Probleme sind besondere Fälle des allgemeinen Spektrallückenproblems: Ist das Hamilton eines Quanten-Vielkörpersystems lückenhaft oder lückenlos? Hier beweisen wir, dass dies ein unentscheidbares Problem ist. Insbesondere konstruieren wir Familien von Quantenspinsystemen auf einem zweidimensionalen Gitter mit translatorisch invarianten Wechselwirkungen zwischen nächsten Nachbarn, für die das Problem der spektralen Lücke nicht entschieden werden kann. Dieses Ergebnis erstreckt sich auf die Unentscheidbarkeit anderer energiearmer Eigenschaften.

Was Sie anscheinend in der Frage beobachten, ist, dass (informell) Unentscheidbarkeitsbeweise alle eine bestimmte "selbstreferenzielle" Struktur haben, und dies wurde formal in noch weiter fortgeschrittener Mathematik bewiesen, so dass sowohl das Turing-Stopp-Problem als auch der Satz von Godels dies können als Beispiele desselben zugrunde liegenden Phänomens angesehen werden. siehe zB:

Der Stoppsatz, der Satz von Cantor (der Nichtisomorphismus einer Menge und ihres Potenzsatzes) und Goedels Unvollständigkeitssatz sind alle Beispiele des Lawvere-Fixpunktsatzes, der besagt, dass für jede kartesische geschlossene Kategorie, wenn es eine epimorphe Karte gibt, e: A → (A⇒B) dann hat jedes f: B → B einen festen Punkt.

Es gibt auch eine lange Meditation über dieses Thema der (intrinsischen?) Vernetzung von Selbstreferenzialität und Unentscheidbarkeit in den Büchern von Hofstadter. Ein weiterer Bereich, in dem Unentscheidbarkeitsergebnisse häufig vorkommen und anfänglich etwas "überraschend" waren, sind fraktale Phänomene. Das übergreifende Auftreten / die Bedeutung von unentscheidbaren Phänomenen in der Natur ist an dieser Stelle fast ein anerkanntes physikalisches Prinzip, das Wolfram zuerst als "Prinzip der rechnerischen Äquivalenz" beobachtete .

vzn
quelle
andere "überraschende / angewandte" Bereiche der Unentscheidbarkeit: aperiodische Kacheln , eventuelle Stabilisierung im Conway- Spiel des Lebens ( zelluläre Automaten )
vzn
3
Ich verstehe, dass die Beweise dafür, dass all diese Probleme unbestreitbar sind, sich alle auf die Reduzierung des Stillstandsproblems beschränken. Ist das falsch
Templatetypedef
Die Antwort räumt grundsätzlich ein, dass (alle bekannten Unentscheidbarkeitsergebnisse können auf das Stopp-Problem reduziert werden). Ihre Frage ist beinahe als Vermutung formuliert, und ich bin mir keiner widersprüchlichen Erkenntnis darüber bewusst und sehe viele Indizien dafür. aber der nächste zu a formale Beweis, der bekannt ist, ist offenbar den Festkommaformulierungen der Unentscheidbarkeit (es scheint keine anderen formalen Formulierungen der "Selbstreferenzierung" zu geben) von im Wesentlichen dem gleichen Phänomen.
vzn