Unentschlossenes Problem

Im Computerbarkeitstheorie und Computerkomplexitätstheorie, ein unentschlossenes Problem ist ein Entscheidungsproblem für die es als unmöglich ist, eine zu konstruieren Algorithmus Das führt immer zu einer korrekten Ja-oder-nicht-Antwort.^[1] Das Problem stoppen ist ein Beispiel: Es kann nachgewiesen werden, dass es keinen Algorithmus gibt, der korrekt bestimmt, ob willkürliche Programme beim Ausführen letztendlich stoppen.^[2]

Hintergrund

Ein Entscheidungsproblem ist eine willkürliche Ja-or-Nein-Frage zu einer unendlichen Eingabetaste.^[3] Aus diesem Grund ist es traditionell, das Entscheidungsproblem gleichbedeutend mit den Eingaben zu definieren, für die das Problem zurückgibt Jawohl. Diese Eingaben können natürliche Zahlen sein, aber auch andere Werte einer anderen Art, wie z. Saiten von a formelle Sprache. Verwenden einiger Codierung, wie z. Gödel -NummerierungDie Saiten können als natürliche Zahlen kodiert werden. Ein Entscheidungsproblem in Bezug auf eine formale Sprache ist somit ebenfalls gleichbedeutend mit einem Satz von natürliche Zahlen. Um die formale Definition einfach zu halten, ist sie in Bezug auf Untergruppen der natürlichen Zahlen formuliert.

Formal ist ein Entscheidungsproblem eine Untergruppe der natürlichen Zahlen. Das entsprechende informelle Problem besteht darin, zu entscheiden, ob sich eine bestimmte Zahl im Satz befindet. Ein Entscheidungsproblem A wird bezeichnet, lichtbar oder effektiv lösbar, wenn A ist ein rekursive Set und sonst unentscheidbar. Ein Problem wird als teilweise entschlossen, halbschichtig, lösbar oder nachweisbar, wenn A ist ein rekursiv aufzählbarer Satz.^[4]

Beispiel: Das Störungsproblem in der Computerbarkeitstheorie

Im Computerbarkeitstheorie, das Problem stoppen ist ein Entscheidungsproblem was wie folgt angegeben werden kann:

Angesichts der Beschreibung eines willkürlichen Programm und eine endliche Eingabe, entscheiden Sie, ob das Programm ausgeführt wird oder für immer ausgeführt wird.

Alan Turing 1936 bewiesen, dass ein General Algorithmus auf A laufen Turing Maschine Das löst das Stoppproblem für alle Möglicherweise können mögliche Programm-Input-Paare notwendigerweise existieren. Daher ist das Stoppproblem unentscheidbar Für Turing -Maschinen.

Beziehung zu Gödels Unvollständigkeitstheorem

Die Konzepte, die von erhoben werden von Gödels unvollständige Theoreme sind denjenigen, die durch das Störungsproblem angesprochen werden, sehr ähnlich, und die Beweise sind ziemlich ähnlich. Tatsächlich ist eine schwächere Form des ersten Unvollständigkeitssatzes eine einfache Folge der Unentschlossenheit des Stoppproblems. Diese schwächere Form unterscheidet sich von der Standardaussage des Unvollständigkeitssatzes durch die Behauptung, dass ein Axiomatisierung der natürlichen Zahlen, die sowohl vollständig als auch abgeschlossen sind und Klang ist unmöglich. Der "Schall" -Teil ist die Schwächung: Dies bedeutet, dass wir das betreffende axiomatische System benötigen, um nur nachzuweisen Stimmt Aussagen über natürliche Zahlen. Da impliziert Klang KonsistenzDiese schwächere Form kann als als gesehen werden logische Folge der starken Form. Es ist wichtig zu beachten mathematischer Beweis.

Die schwächere Form des Satzes kann sich aus der Unentschlossenheit des Stoßproblems wie folgt bewiesen. Angenommen, wir haben einen Ton (und damit konsistent) und vollständig Axiomatisierung von allen wahr Logik erster Ordnung Aussagen über natürliche Zahlen. Dann können wir einen Algorithmus erstellen, der all diese Aussagen auflistet. Dies bedeutet, dass es einen Algorithmus gibt N(n) das, bei einer natürlichen Zahl nberechnet eine echte logische Anweisung erster Ordnung über natürliche Zahlen, und für alle wahren Aussagen gibt es mindestens einen n so dass N(n) ergibt diese Aussage. Nehmen wir nun an, wir möchten entscheiden, ob der Algorithmus mit der Darstellung a Halt bei der Eingabe i. Wir wissen, dass diese Aussage mit einer logischen Erklärung erster Ordnung ausgedrückt werden kann, sagen wir H(a, i). Da die Axiomatisierung abgeschlossen ist, folgt, dass es entweder eine gibt n so dass N(n) = H(a, i) oder es gibt eine n' so dass N(n') = ¬ H(a, i). Also wenn wir iterieren gesamt n Bis wir entweder finden H(a, i) oder seine Negation werden wir immer anhalten, und außerdem wird die Antwort, die es uns gibt, wahr sein (nach soliden). Dies bedeutet, dass dies uns einen Algorithmus gibt, um das Stoppproblem zu entscheiden. Da wir wissen, dass es keinen solchen Algorithmus geben kann, folgt die Annahme, dass eine konsistente und vollständige Axiomatisierung aller echten Logikaussagen erster Ordnung zu natürlichen Zahlen falsch sein muss.

Beispiele für unentscheidbare Probleme

Unentscheidbare Probleme können mit verschiedenen Themen zusammenhängen, wie z. Logik, Abstrakte Maschinen oder Topologie. Weil dort sind unzähliger viele unentscheidbare Probleme,^[5] jede Liste, sogar eine von unendliche Länge, ist notwendigerweise unvollständig.

Beispiele für unentscheidbare Aussagen

Es gibt zwei unterschiedliche Sinne des Wortes "unentscheidbar" im zeitgenössischen Gebrauch. Der erste davon ist der Sinn, der in Bezug auf Gödels Theoreme verwendet wird, der einer Aussage, der weder nachweisbar noch in einem angegebenen deduktives System. Der zweite Sinn wird in Bezug auf Computerbarkeitstheorie und gilt nicht für Aussagen, sondern für Entscheidungsprobleme, die zähe unendliche Fragen sind, die jeweils eine Ja- oder Nein -Antwort erfordern. Ein solches Problem soll unentscheidbar sein, wenn es keine gibt berechnungsbare Funktion Das beantwortet jede Frage im Problem fest. Der Zusammenhang zwischen diesen beiden ist, dass es kein konsistent formelles System was für jede Frage beweist A in dem Problem entweder "die Antwort auf A ist ja "oder" die Antwort auf A ist nein ".

Wegen der beiden Bedeutungen des Wortes unentscheidbar, der Begriff unabhängig wird manchmal anstelle von unentscheidbarem "Weder nachweisbarer noch widersprüchlicher" Sinn verwendet. Die Verwendung von "unabhängig" ist jedoch ebenfalls mehrdeutig. Es kann nur "nicht nachweisbar" bedeuten und offen lassen, ob eine unabhängige Aussage widerlegt werden könnte.

Die Unentschlossenheit einer Aussage in einem bestimmten deduktiven System geht nicht an und für sich an die Frage, ob die Wahrheitswert der Aussage ist gut definiert oder ob sie mit anderen Mitteln bestimmt werden kann. Unentschlossenheit impliziert nur, dass das betrachtete bestimmte deduktive System nicht die Wahrheit oder Falschheit der Aussage beweist. Ob es sogenannte "absolut unentscheidbare" Aussagen gibt, deren Wahrheitswert niemals bekannt oder nicht spezifiziert ist, ist ein kontroverser Punkt unter verschiedenen Philosophische Schulen.

Eines der ersten Probleme, bei denen vermutet wurde, dass sie im zweiten Sinne des Begriffs unentscheidbar sind, war die Wortproblem für Gruppen, zuerst posiert von Max Dehn Im Jahr 1911, was fragt, ob es eine endlich vorgestellte Präsentation gibt Gruppe für den kein Algorithmus existiert, um festzustellen, ob zwei Wörter gleichwertig sind. Es wurde gezeigt, dass dies 1952 der Fall ist.

Die kombinierte Arbeit von Gödel und Paul Cohen hat zwei konkrete Beispiele für unentscheidbare Aussagen (im ersten Sinne des Begriffs) gegeben: die Kontinuumshypothese kann weder bewiesen noch widerlegt werden ZFC (die Standard -Axiomatisierung von Mengenlehre), und die Axiom der Wahl kann weder bewiesen noch widerlegt werden Zf (Das sind alle ZFC -Axiome außer das Axiom der Wahl). Diese Ergebnisse erfordern nicht den Unvollständigkeitssatz. Gödel bewies 1940, dass keine dieser Aussagen in der ZF- oder ZFC -SET -Theorie widerlegt werden konnte. In den 1960er Jahren bewies Cohen, dass keiner von ZF nachgewiesen wird und die Kontinuumshypothese nicht von ZFC nachgewiesen werden kann.

1970 russischer Mathematiker Yuri Matiyasevich zeigte, dass Hilberts zehnte Problem, im Jahr 1900 als Herausforderung für das nächste Jahrhundert der Mathematiker, kann nicht gelöst werden. Hilberts Herausforderung suchte einen Algorithmus, der alle Lösungen von a findet Diophantinengleichung. Eine diophantinische Gleichung ist ein allgemeinerer Fall von Fermats letzter Satz; Wir suchen die Ganzzahlwurzeln von a Polynom in einer beliebigen Anzahl von Variablen mit Ganzzahlkoeffizienten. Da haben wir nur eine Gleichung, aber n Variablen, unendlich viele Lösungen existieren (und sind leicht zu finden) in der Komplexe Ebene; Das Problem wird jedoch unmöglich, wenn Lösungen nur auf ganzzahlige Werte eingeschränkt werden. Matiyasevich zeigte, dass dieses Problem unlösbar ist, indem eine diophantinische Gleichung zu a abgebildet wurde rekursiv aufzählbarer Satz und Gödels Unvollständigkeitssatz aufrufen.^[6]

1936, Alan Turing bewies, dass die Problem stoppen- Die Frage, ob a Turing Maschine Halt bei einem bestimmten Programm - ist im zweiten Sinne des Begriffs unentscheidbar. Dieses Ergebnis wurde später durch verallgemeinert durch Reis Satz.

1973,, Saharon Shelah zeigte die Whitehead -Problem in Gruppentheorie ist im ersten Sinne des Begriffs in der Standard -Set -Theorie unentscheidbar.^[7]

Im Jahr 1977 bewiesen Paris und Harrington, dass das die Paris-Harrington-Prinzip, eine Version der Ramsey Theorem, ist bei der Axiomatisierung der Arithmetik, die durch die gegeben wurde Peano -Axiome kann sich aber als wahr im größeren System von erwiesen haben Arithmetik zweiter Ordnung.

Kruskals Baumsatz, die Anwendungen in der Informatik hat, ist auch von den Peano -Axiomen unentscheidbar, aber in der festgelegten Theorie nachweisbar. Tatsächlich ist Kruskals Baumsatz (oder seine endliche Form) in einem viel stärkeren System, das die Prinzipien kodiert, auf der Grundlage einer Philosophie der Mathematik, die als Prädikativismus bezeichnet wird, die Prinzipien kodiert.

Goodsteins Theorem ist eine Aussage über die Ramsey -Theorie von den natürlichen Zahlen, die Kirby und Paris gezeigt haben, ist in der Peano -Arithmetik unentscheidbar.

Gregory Chaitin produzierte unentscheidbare Aussagen in Algorithmische Informationstheorie und bewies in dieser Umgebung einen weiteren Unvollständigkeitssatz. Chaitins Theorem stellt fest, dass es für jede Theorie, die genügend Arithmetik darstellen kann, eine Obergrenze gibt c so dass in dieser Theorie keine spezifische Zahl nachgewiesen werden kann Kolmogorov -Komplexität größer als c. Während Gödels Theorem mit dem zusammenhängt LügnerparadoxChaitins Ergebnis hängt mit Berrys Paradoxon.

Im Jahr 2007 bauen Forscher Kurtz und Simon auf frühere Arbeiten von auf J.H. Conway In den 1970er Jahren bewiesen eine natürliche Verallgemeinerung der Collatz -Problem ist unentscheidbar.^[8]

Siehe auch

• Dekidabilität (Logik)
• Entscheidungsproblem
• Beweis der Unmöglichkeit
• Böses Problem

Verweise