Warum ist das Halteproblem wirklich so wichtig?

149

Ich verstehe nicht, warum das Problem des Anhaltens so oft verwendet wird, um festzustellen, ob ein Programm anhält. Die Wikipedia [article] [1] erklärt zu Recht, dass eine deterministische Maschine mit endlichem Speicher einen vorherigen Zustand anhält oder wiederholt. Sie können den Algorithmus verwenden, der erkennt, ob eine verknüpfte Liste Schleifen durchläuft, um die Haltefunktion mit der Raumkomplexität von O (1) zu implementieren.

Es scheint mir, dass der Halting-Problem-Beweis nichts anderes als ein sogenanntes "Paradoxon" ist, ein sich auf sich selbst beziehender (zumindest zyklischer) Widerspruch in der gleichen Weise wie das Paradoxon des Lügners. Die einzige Schlussfolgerung ist, dass die Haltefunktion für solche fehlerhaften Fragen anfällig ist.

Ohne paradoxe Programme ist die Haltefunktion also entscheidend. Warum halten wir es also für einen Beweis des Gegenteils?

4 Jahre später : Als ich das schrieb, hatte ich mir gerade dieses Video angesehen . Ein Programmierer erhält einige Programme, muss feststellen, welche beendet werden, und im Video wird erläutert, warum dies nicht möglich ist. Ich war frustriert, weil ich wusste, dass der Protagonist angesichts einiger beliebiger Programme nachweisen konnte, ob sie beendet wurden. Der Begriff der Allgemeinheit ging irgendwie verloren. Es ist der Unterschied zwischen der Aussage "Es kann nicht nachgewiesen werden, dass einige Programme beendet werden" und der Aussage "Es kann nicht nachgewiesen werden, dass kein Programm beendet wird". Viele Algorithmen werden dazu formal demonstriert. Das Versäumnis, diese Unterscheidung durch jede einzelne Referenz zu treffen, die ich online fand, war, wie ich zum Titel für diese Frage kam. Aus diesem Grund schätze ich die Antwort sehr das definiert die Haltefunktion als ternär statt als boolesch neu.

Brent
quelle
16
"eine deterministische Maschine mit endlichem Gedächtnis" ist "langweilig", da es nichts weiter als ein endlicher Automat ist; Diese sind für die Modellierung von Berechnungen im Allgemeinen nicht hilfreich. Was das Problem des Anhaltens betrifft: Es ist ein spezielles Beispiel für eine Funktion, die nicht (Turing) berechenbar ist. Wenn Sie mit einem nicht konstruktiven Beweis zufrieden sind, brauchen Sie ihn nicht. Es hat jedoch immer noch historische Relevanz.
Raphael
16
Trotzdem wirkt Ihre Frage schlecht informiert. Vielleicht möchten Sie auf Ihre Grundlagen der Berechenbarkeit auffrischen Theorie (das wird Ihre Intuition Herausforderung , die von der Realität informiert wird, nicht die dort diskutierten Modelle). Sehen Sie sich zunächst unsere Referenzfragen an. Wenn Sie einen weiteren "Beweis" dafür benötigen, dass Ihre Intuition (was die Theorie betrifft) tödlich ist, lesen Sie diese Frage .
Raphael
12
"Sie können den Algorithmus verwenden, der erkennt, ob eine verknüpfte Liste Schleifen ausführt, um die Haltefunktion mit der Speicherplatzkomplexität von O (1) zu implementieren." 2 ^ 2000000000 Schritte und ein größerer Computer.
user2357112
11
Vor langer Zeit unterhielt ich mich mit einem Freund über das Problem des Anhaltens und jemand, der in der Nähe saß, fragte: "Was ist das Problem des Anhaltens, ist es wichtig?" und mein Freund wandte sich an ihn und sagte: "Wenn wir das Stopp-Problem lösen könnten, könnten wir Städte auf Wolken bauen." Das ist wahr.
Francis Davey
8
@emory Die Behauptung ist vakuumtreu: P => Qgilt für jedes Q, wenn wir wissen, dass dies Pfalsch ist (und wir wissen, dass das Halteproblem nicht lösbar ist). Francis könnte genauso gut sagen: "Wenn wir das Problem des Stillstands lösen könnten, könnten wir selbst ein Heilmittel für den Tod finden." So wird logische Implikation definiert.
Amalloy

Antworten:

217

Denn viele wirklich praktische Probleme sind das haltende Problem in der Tarnung. Eine Lösung für sie löst das Halteproblem.

Sie möchten einen Compiler, der den schnellstmöglichen Maschinencode für ein bestimmtes Programm findet? Eigentlich das haltende Problem.

Sie haben JavaScript, wobei einige Variablen eine hohe und andere eine niedrige Sicherheitsstufe aufweisen. Sie möchten sicherstellen, dass ein Angreifer nicht auf die hohen Sicherheitsinformationen zugreifen kann. Dies ist auch nur das Halteproblem.

Sie haben einen Parser für Ihre Programmiersprache. Sie ändern es, aber Sie möchten sicherstellen, dass es weiterhin alle Programme analysiert, die es früher verwendet hat. Eigentlich das haltende Problem.

Sie haben ein Antivirenprogramm und möchten feststellen, ob es jemals eine böswillige Anweisung ausführt. Eigentlich nur das Halteproblem.

Was das Wikipedia-Beispiel betrifft, können Sie einen modernen Computer als endliche Zustandsmaschine modellieren. Damit sind jedoch zwei Probleme verbunden.

  1. Jeder Computer wäre ein anderer Automat, abhängig von der genauen Anzahl der RAM-Bits. Dies ist also nicht hilfreich, um einen bestimmten Code zu untersuchen, da der Automat von der Maschine abhängig ist, auf der er ausgeführt werden kann.

  2. 2n2320000000002109300000000

Das Problem des Anhaltens lässt uns über die relative Schwierigkeit von Algorithmen nachdenken. Es lässt uns wissen, dass es einige Algorithmen gibt, die nicht existieren. Manchmal können wir nur ein Problem erraten und nie wissen, ob wir es gelöst haben.

Wenn wir nicht das Stopp-Problem hätten, würden wir immer noch nach Hilberts magischem Algorithmus suchen, der Theoreme eingibt und ausgibt, ob sie wahr sind oder nicht. Jetzt wissen wir, dass wir aufhören können zu suchen, und wir können uns bemühen, Heuristiken und zweitbeste Methoden zur Lösung dieser Probleme zu finden.

UPDATE: Nur um ein paar Probleme anzusprechen, die in den Kommentaren angesprochen wurden.

@Tyler Fleming Cloutier: Das "unsinnige" Problem ergibt sich aus dem Beweis, dass das Stopp-Problem unentscheidbar ist, aber was den Kern der Unentscheidbarkeit ausmacht, ist ein unendlicher Suchraum. Sie suchen nach einem Objekt mit einer bestimmten Eigenschaft. Wenn eines nicht vorhanden ist, können Sie nicht feststellen, wann Sie fertig sind.

Σ00=Π00

Es ist auch möglich zu zeigen, dass es unentscheidbare Probleme gibt, ohne ein unsinniges Paradox wie das Halting-Problem oder das Lügner-Paradox zu verwenden. Eine Turing-Maschine kann mit einer Folge von Bits, dh einer ganzen Zahl, codiert werden. Ein Problem kann jedoch als Sprache kodiert werden, dh als Teilmenge der ganzen Zahlen. Es ist bekannt, dass es keinen Unterschied zwischen der Menge der ganzen Zahlen und der Menge aller Teilmengen der ganzen Zahlen gibt. Es muss also einige Probleme (Sprachen) geben, denen keine Turing-Maschine (Algorithmus) zugeordnet ist.

@Brent: Ja, das gibt zu, dass dies für moderne Computer entscheidend ist. Aber es ist für eine bestimmte Maschine entscheidend. Wenn Sie ein USB-Laufwerk mit Festplattenspeicher oder die Möglichkeit zum Speichern in einem Netzwerk oder etwas anderem hinzufügen, hat sich das Gerät geändert und das Ergebnis wird immer noch nicht angezeigt.

Es muss auch gesagt werden, dass es viele Male geben wird, in denen der Algorithmus sagt, dass "dieser Code anhält", weil der Code ausfällt und der Speicher knapp wird, und dass das Hinzufügen eines einzelnen zusätzlichen Speicherbits dazu führen würde, dass der Code angehalten wird Erfolg haben und ein anderes Ergebnis liefern.

Die Sache ist, dass Turing-Maschinen nicht unendlich viel Speicher haben. Es gibt nie eine Zeit, in der unendlich viele Symbole auf das Band geschrieben werden. Stattdessen verfügt eine Turing-Maschine über "unbegrenzten" Speicher, sodass Sie bei Bedarf immer mehr Speicherquellen zur Verfügung haben. Computer sind so. Sie können RAM, USB-Sticks, Festplatten oder Netzwerkspeicher hinzufügen. Ja, Ihnen geht das Gedächtnis aus, wenn Ihnen die Atome im Universum ausgehen. Unbegrenzter Speicher ist jedoch ein viel nützlicheres Modell.

jmite
quelle
4
@Mehrdad Für jede vernünftige Definition von "schnellstmöglichem Maschinencode für ein bestimmtes Programm" ist die Frage sinnvoll und die Antwort lautet "Es kann keinen solchen Compiler geben."
David Richerby
13
Es funktioniert auch, um den kürzest möglichen Maschinencode für die Ausgabe zu finden, den mit dem geringsten Speicherzugriff usw. usw. Für allgemeine Programme ist es unentscheidbar, eine optimale Transformation zu finden. Dies ist im Grunde der Satz von Rice.
Jmite
4
Als Konsequenz aus der Suche nach Hilberts magischem Algorithmus ohne das eng verwandte Konzept der Turing-Äquivalenz würden wir uns immer noch darüber streiten, ob Gotos oder selbstmodifizierender Code leistungsfähigere Berechnungen ermöglichen und nach leistungsfähigeren Hardwareformen suchen Und die Argumente, über die die beste Programmiersprache gesprochen wird, wären weitaus subjektiver als jetzt.
Sdenham
3
Es taucht sogar an Orten auf, die Sie nicht erwarten würden. Möchten Sie einen C ++ - Compiler schreiben, der alle ungültigen Programme ablehnt, während alle gültigen kompiliert werden? Lösen Sie zuerst das Halteproblem. Die Metaprogrammierung der C ++ - Vorlagen ist vollständig. Wenn Sie also feststellen möchten, ob Ihre Vorlagen gültig sind oder nicht, müssen Sie sie im Allgemeinen lösen.
Mark
7
@ Merhrdad: Ihr Beispiel für die "Simulation des gesamten Computerprogramms" ist ein hervorragendes Beispiel dafür, warum das Problem des Anhaltens so wichtig ist. Bei einigen Programmen ist das Simulieren des Programms nicht so einfach wie es scheint (siehe zum Beispiel die Wikipedia-Seite zum Anhalten). Wenn das Problem in dieser Form täuschen kann, können Sie sich vorstellen, wie schwer es ist, jemandem eine verstecktere Form (wie das Antiviren-Problem) zu erklären
Cort Ammon
49

In der Praxis ist es wichtig, weil Sie Ihren ignoranten Vorgesetzten sagen können, "was Sie verlangen, ist mathematisch unmöglich".

Das Stopp-Problem und verschiedene NP-vollständige Probleme (z. B. das Problem des Handlungsreisenden) tauchen häufig in der Form auf: "Warum können Sie nicht einfach ein Programm erstellen, das X unterstützt?", Und Sie müssen in der Lage sein, eine Erklärung abzugeben warum es innerhalb der verbleibenden Lebenszeit des Universums unmöglich oder unmöglich ist.

Beachten Sie, dass es möglich ist, eine Sprache zu entwerfen, die nicht vollständig ist und daher analysiert werden kann, indem unbegrenzte Rekursion und Iteration verboten werden.

o11c
quelle
16
Nun, @bishop, außer Flickr hat das praktisch Unmögliche getan .
Francisco Presencia
8
Es ist möglich, eine Sprache zu entwerfen, die nicht vollständig ist : Beispiel für eine nützliche Sprache, die nicht vollständig ist: SQL (eigentlich eine abgespeckte SQL). Turing-Vollständigkeit würde der Sprache automatisch die Nichtbeendigung hinzufügen, was Sie wahrscheinlich nicht möchten, wenn Sie eine Datenbankabfrage ausführen. (Obwohl ich befürchte, dass alle modernen SQL-Implementierungen ohnehin Vollständigkeit bieten)
Bakuriu
8
@FranciscoPresencia: Sie haben ein Forschungsteam eingesetzt, daher gilt der allgemeine Punkt immer noch.
RemcoGerlich
4
@MooingDuck: Das Flickr-Ding wählt nicht zwischen Parks und Vögeln, es (versucht), eines oder beide zu bestätigen. ODER nicht XOR.
Rickster
45

Sie können den Algorithmus verwenden, der erkennt, ob eine verknüpfte Liste Schleifen durchläuft, um die Haltefunktion mit der Raumkomplexität von O (1) zu implementieren.

Dazu müssen Sie mindestens zwei Kopien des Teilzustands des Programms sowie den Overhead des Prüfprogramms im Speicher ablegen. Auf einem bestimmten Computer können Sie also nicht alle Programme testen, die auf diesem Computer ausgeführt werden können, sondern nur die Programme, die auf einem kleineren Computer mit weniger als der Hälfte des Arbeitsspeichers ausgeführt werden.

Das Problem des Anhaltens für einen bestimmten Computer mit begrenzter Größe kann auf diesem Computer mit begrenzter Größe nicht gelöst werden . Es kann nur auf einem größeren Computer gelöst werden. (Dies gilt für jede Methode, nicht nur für die von Ihnen vorgeschlagene. Ich werde keinen formalen Beweis liefern, aber hier ist das Wesentliche. Wenn ein Computer C N verschiedene Programme ausführen kann, von denen mindestens ein P nicht beendet wird Wenn C und V derselbe Computer sind, dann ist P nicht eines der N verschiedenen Programme, die V ausführt Computer muss mindestens N + 1 verschiedene Programme ausführen, was der Annahme widerspricht, dass C N verschiedene Programme ausführt.)

M2M256

Die Zahlen veranschaulichen, dass es selten praktikabel ist, sich einen Computer als eine endliche Maschine vorzustellen. Die Anzahl der Zustände mag endlich sein, aber es ist unglaublich, unpraktisch riesig. Die einzige Möglichkeit, über Nicht-Spielzeug-Programme zu argumentieren, besteht im Abstrakten, nicht durch Aufzählen von Zuständen, sondern durch logisches Denken.

Ohne paradoxe Programme ist das Problem des Anhaltens also entscheidend

Das Paradox kommt nicht vom Problem, sondern vom Versuch einer Lösung. Für jedes gegebene Programm gibt es einen Algorithmus, der "Ja" sagt, wenn das Programm beendet wird, und "Nein", wenn das Programm nicht beendet wird. Es ist trivial: entweder print "yes"oder print "no"wird es tun. Das Problem besteht darin, festzustellen, welche Sie anrufen möchten. Die Unmöglichkeit, das Halteproblem zu lösen, bedeutet, dass es keinen Algorithmus gibt, der diese Bestimmung vornimmt. Der Grund, warum der Beweis ein Diagonalisierungsargument verwendet, ist, dass er zeigen muss, dass neinLösung funktioniert; Dazu geht es von einer willkürlich vorgegebenen Lösung aus und zeigt, dass einige Programme fehlen müssen, indem ein fehlendes Programm erstellt wird. Die Diagonalisierung (was Sie zu Unrecht als "Paradoxon" bezeichnen) liegt in der Konstruktion, nicht im resultierenden Programm. Die resultierenden Programme sind nicht selbstreferenziell.

Es gibt ein allgemeineres Ergebnis, das als Rice-Theorem bezeichnet wird und besagt, dass es sich um nicht-triviale Eigenschaften handeltvon Programmen ist unentscheidbar - jede Eigenschaft, die nur vom Verhalten des Programms abhängt und nicht von der Art und Weise, in der sie geschrieben wurde (z. B. „besteht der Quellcode aus weniger als 42 Zeichen?“ ist eindeutig entscheidbar, während „gibt es eine Programm, dessen Quellcode aus weniger als 42 Zeichen besteht und das für alle Eingaben das gleiche Ergebnis liefert? “ist nicht, und„ gibt dieses Programm jemals etwas aus? “). Anhalten ist nur ein Beispiel. Dies ist wichtig, da es in der Praxis häufig auftritt (normalerweise möchten wir wissen, ob ein Programm in angemessener Zeit ein Ergebnis zurückgibt, wenn die begrenzten Ressourcen des Computers, auf dem es ausgeführt wird, vorhanden sind. Da dies jedoch in der Praxis nur selten möglich ist, sind wir dafür verantwortlich bereit, sich mit der einfacheren Frage zu begnügen, ob das Programm schließlich beendet wird, wenn genügend Zeit und Speicher vorhanden sind).

Gilles
quelle
2
Ich würde denken, dass die Frage "gibt es ein Programm, das die gleiche Ausgabe wie ein gegebenes in sich geschlossenes Programm produzieren würde (keine Eingabe, aber das Programm selbst), aber in kürzerer Zeit, einschließlich der Zeit zum Laden des Programms ?" wäre entscheidbar, wenn auch nicht umsetzbar, da die maximale Länge der Bewerberprogramme ebenso begrenzt wäre wie die Zeit, um jedes einzelne zu testen.
Supercat
@supercat Ja, diese Eigenschaft ist entscheidend. Für den allgemeinen Fall eines Programms, das Eingaben entgegennimmt, ist dies nicht entscheidend.
Gilles
1
Ich hatte den Eindruck, dass das Problem des Anhaltens normalerweise davon ausgeht, dass alle Eingaben, die ein Programm während seiner Ausführung erhält, mit dem Programm gebündelt werden. Wenn man eine Maschine hätte, die auf magische Weise das Halteproblem für ein Programm lösen könnte, das einer bestimmten Eingabesequenz zugeführt wird , könnte eine solche Maschine dann feststellen, ob ein Programm für alle Eingaben mit begrenzter Länge anhalten würde?
Supercat
3
@supercat Nein, das Orakel für alle Eingaben wäre einen Schritt weiter als das Orakel für alle Eingaben. Das wäre eine gute Frage für diese Site ... in der Tat haben wir es . Übrigens sind mein mentales Standardmodell rekursive Funktionen, wobei "Eingabe" "Argument" bedeutet und ein Programm auszuführen bedeutet, es auf ein Argument anzuwenden. Sie haben Recht, dass meine Aussage in einem Kontext, in dem es um Turing-Maschinen geht, falsch ist. Ich werde sie aktualisieren.
Gilles
28

Es scheint mir, dass das Halteproblem nichts anderes als ein sogenanntes "Paradoxon" ist, ein sich auf sich selbst beziehender (zumindest zyklischer) Widerspruch, genauso wie das Paradoxon des Lügners. Die einzige Schlussfolgerung ist, dass die Haltefunktion für solche fehlerhaften Fragen anfällig ist

Nein, das ist nicht , was das Halteproblem geht. Paradoxe wie das Paradox des Lügners sind nicht wahr oder falsch, sie ergeben einfach keinen Sinn. Ein deterministischer Algorithmus hingegen wird entweder für eine bestimmte Eingabe angehalten oder für immer ausgeführt. Die Funktion halts(program, input)hat für jedes Programm, für jeden Eingang einen genau definierten, deterministischen Wert. Wir können einfach nicht entscheiden , es für jedes Programm. Genauer gesagt: Wir können kein Programm schreiben, das es für jedes Programm / Eingabe-Paar entscheiden kann.

Σ(n):=nnnnΣ(n)

Nikie
quelle
2
Es ist erwähnenswert, dass das Paradoxon des Lügners in der üblichen Form explizit auf sich selbst verweist, aber dasselbe Problem kann auftreten, auch wenn dies nicht der Fall ist. Entspricht die Antwort auf die Aussage dem Text? Entspricht die Antwort auf die Aussage dem Text? Fügen Sie nach dem ersten Komma eine in Anführungszeichen gesetzte Kopie ein, nein? und nach dem ersten Komma eine in einfache Anführungszeichen gesetzte Kopie einfügen, nein? Eine solche Aussage bezieht sich nicht ausdrücklich auf sich selbst, sondern auf die Wahrhaftigkeit einer Aussage, die Zeichen für Zeichen identisch ist.
Supercat
2
@supercat: huh, ich glaube nicht, dass ich vorher eine Quine auf Englisch gesehen habe ...
SamB
@SamB: Ich habe ein paar gesehen, aber beschlossen, mich an einer Originalformulierung zu versuchen, die, obwohl sie ausführlicher ist als manche, (vielleicht) natürlicher liest.
Supercat
24

Ich verstehe nicht, warum das Problem des Anhaltens so oft verwendet wird, um festzustellen, ob ein Programm anhält. Der Wikipedia-Artikel erklärt korrekt, dass eine deterministische Maschine mit endlichem Speicher einen vorherigen Zustand anhält oder wiederholt. Sie können den Algorithmus verwenden, der erkennt, ob eine verknüpfte Liste Schleifen durchläuft, um die Haltefunktion mit der Raumkomplexität von O (1) zu implementieren.

Erstens ist es theoretisch sinnvoll, einen realen Computer mit endlichem Speicher als endliche Zustandsmaschine zu betrachten. In der Praxis ist die Anzahl der Zustände eines realen Computers jedoch so groß, dass reale Computer viel besser von Turing-Maschinen oder anderen Berechnungsmodellen für unendliche Zustände modelliert werden können.

Und zweitens ist es sogar theoretisch sinnvoll, einen modernen Computer als eine unendliche Zustandsmaschine anzusehen. Eine Turing-Maschine verfügt nicht über ein unendliches Band, sondern über ein Band, das jederzeit verlängert werden kann, wenn der Arbeitsspeicher der Maschine erschöpft ist. Und ist das nicht genau das, was wir mit echten Computern machen können? (Und wenn der Adressraum der CPU ausgeht, können wir die Cloud usw. verwenden.)

Es scheint mir, dass das Halteproblem nichts anderes als ein sogenanntes "Paradoxon" ist, ein sich auf sich selbst beziehender (zumindest zyklischer) Widerspruch, genauso wie das Paradoxon des Lügners. Die einzige Schlussfolgerung ist, dass die Haltefunktion für solche fehlerhaften Fragen anfällig ist. Ohne paradoxe Programme ist das Problem des Anhaltens also entscheidend. Warum halten wir es also für einen Beweis des Gegenteils?

HPxHPx

Turings Beweis für die Unentscheidbarkeit des Halteproblems verwendet einen Trick, der dem Lügner-Paradoxon ähnelt, ja. Ein Paradox wird oft als offensichtlicher Widerspruch definiert, und manche Leute schließen daraus, dass ein Paradox kein wirklicher Widerspruch ist. Russels Paradoxon (das formale satztheoretische Gegenstück zum Lügnerparadoxon) zeigte jedoch einen wirklichen Widerspruch in der Mathematik, und der Beweis der Unentscheidbarkeit des Halteproblems verwendet einen wirklichen Widerspruch für seinen Widerspruchsbeweis.

Hoopje
quelle
1
+1 zur Erklärung der Beziehung zwischen realen Computern, Finite-State-Maschinen und Turing-Maschinen, die ein wesentlicher Bestandteil des Aufbaus der Frage ist.
David Richerby
1
Sie haben mein Interesse geweckt. Was ist der Unterschied zwischen einem scheinbaren Widerspruch und einem echten Widerspruch?
Brent,
Eine andere Art, dies zu formulieren: Im Allgemeinen beansprucht die Programmierung keine begrenzten Ressourcen. Die meisten Algorithmen, die wir entwerfen oder Programme, die wir schreiben, sind nicht dafür geschrieben, eine begrenzte oder sogar feste Menge an Computerressourcen zu verwenden, es sei denn, wir entwerfen sie speziell dafür Art und Weise (z. B. ist dies häufig bei der Programmierung für eingebettete Systeme erforderlich).
Reinierpost
3
@Brent. Viele Paradoxien sind überhaupt nicht widersprüchlich, sondern nur auf den ersten Blick. Wenn wir genauer hinschauen, stellt sich heraus, dass die Argumentation fehlerhaft ist oder dass sich die Bedeutung geringfügig geändert hat, indem sie in einem anderen Kontext verwendet wurde, oder etwas Ähnliches. Manchmal bringt ein Paradox jedoch einen wirklichen Widerspruch ans Licht.
Hoopje
Ich habe dieses Problem seit meinem OP immer wieder studiert. Bedeutet Gödels Unvollständigkeitssatz, dass es immer möglich ist, ein Paradoxon zu finden, unabhängig vom verwendeten Logiksystem?
Brent
17

jmite hat die Frage wirklich gut beantwortet. Lassen Sie mich eine kleine Bemerkung zur wahrgenommenen Ähnlichkeit mit dem "Paradoxon des Lügners" hinzufügen, die meiner Meinung nach auf die Verwendung eines Selbstreferenzmechanismus zurückzuführen ist.

Selbstreferenz ist nicht paradox!

Selbstreferenz ist ein sehr nützliches Werkzeug für die Berechnung (ein Algorithmus kann sich auf seinen Code, seine Reflexion beziehen ) und die menschliche Sprache (wir können uns auf uns selbst beziehen, das Selbstbewusstsein ).

Das Problem, das das Paradoxon des Lügners verursacht, besteht nicht in der Selbstreferenz, sondern darin, das Wahrheitsprädikat für eine (formale) Sprache innerhalb der Sprache zu verwenden. Es wird auch ohne Selbstreferenz Probleme verursachen. Wir brauchen keine Selbstreferenz, um ein Paradoxon zu erhalten: Selbstreferenz kann beseitigt werden! . Es würde den Satz nur weniger schön und prägnant machen, aber es ist nicht schwer zu tun. Es ist im Wesentlichen, wie Kleenes Fixpunktsatz bewiesen wird. Was das Paradox des Lügners impliziert, ist, dass die Wahrheit von Aussagen in einer (formalen) Sprache transzendental zu dieser Sprache ist, nicht dass die Selbstreferenz problematisch ist.


Es scheint mir, dass Ihr Unbehagen nicht auf die Unentscheidbarkeit des Halteproblems (für Turing-Maschinen) zurückzuführen ist, sondern auf die Akzeptanz von Turing-Maschinen als theoretisches Modell für Computer. Typischerweise (wenn auch nicht immer) sind Turing-Maschinen (und äquivalente Rechenmodelle wie Random Access Machines ) sehr nützlich für die Diskussion der Berechnung auf tatsächlichen Computern als endliche Automaten, und es gibt gute Gründe dafür (bedenken Sie, dass eine Turing-Maschine keine hat Unbegrenzt viel Speicher, unbegrenzt viel Speicher und das sind verschiedene Dinge: Unbegrenzt bedeutet, dass wir der Maschine mehr Speicher zur Verfügung stellen können, wenn sie benötigt, und nicht, dass sie unendlich viel Speicher benötigt.

Sicher, wenn Sie sich Computer als endliche Automaten vorstellen möchten, und das ist für Ihren Zweck sinnvoll, dann ist das Halteproblem für endliche Automaten entscheidbar (und mit entscheidbar meinen wir entscheidbar durch eine Turing-Maschine, nicht durch endliche Automaten). Das ist jedoch nicht das, was Menschen normalerweise meinen, wenn sie das Stopp-Problem verwenden, sondern das Stopp-Problem für Turing-Maschinen.

s2s

Kaveh
quelle
14

Das Stopp-Problem führte ein neues mathematisches Konzept der "Unentscheidbarkeit" ein, das es in der Mathematik bisher nicht gab. Es war ein ("scheinbar paradoxer") Beweis dafür, dass einige Probleme keine "Beweise" haben. Es ist verbunden mit dem Godelschen Konzept der Unbeweisbarkeit. Der Satz von Gödel ging der Formulierung des Halteproblems durch Turing um einige Jahre voraus. Gödels Ergebnis galt damals als eher abstrakt und war nur Forschern und Fachleuten bekannt. Die Formulierung von Turings hat gezeigt, dass das Prinzip der Unentscheidbarkeit mit sehr praktischen / pragmatischen / angewandten Fragen in der Informatik zusammenhängt, wie zum Beispiel der Feststellung, ob beliebige Programme anhalten, und dass es als weit weniger theoretisches Konzept angesehen wird. Es zeigt sich in modernen Herausforderungen wie " (eine Herausforderung, ob Computer Theoreme entdecken können) und die Programmbeendigung zu beweisen.

Ein weiterer interessanter Aspekt ist, dass es in der (diophantinischen) Zahlentheorie einige sehr alte Probleme gibt, die von den Griechen ausgehen und die seit Jahrtausenden nicht bewiesen sind. Es gibt ein verwandtes Ergebnis, dass allgemeine Fragen zu diophantinischen Gleichungen als Hilberts 10. Problem / Satz unentscheidbar sind . Hilbert lebte um die Jahrhundertwende und schlug als Forschungsprogramm vor, dass die Mathematik systematische Ansätze für mathematische Probleme finden könnte. Diese Herausforderung / dieser Plan wurde durch die Entdeckung der Unentscheidbarkeit einige Jahrzehnte später ernsthaft beeinträchtigt. Unentscheidbarkeit ist weiterhin ein sehr fortgeschrittenes Forschungsgebiet, und die Grenze zwischen unentscheidbaren und entscheidbaren Problemen wird wahrscheinlich immer weiter untersucht und analysiert.

vzn
quelle
14

Sie scheinen den klassischen "selbstreferenziellen" Beweis zu verwechseln, dass das Halting-Problem nicht mit dem Halting-Problem (aka Halt) selbst gelöst werden kann.

Dieses selbstreferenzielle Programm - das Programm, das genau dann anhält, wenn es nicht angehalten wird - wurde erstellt, um zu beweisen, dass Sie Halt nicht lösen können. Die Tatsache, dass wir mit der Technik Y beweisen, dass X unmöglich ist, impliziert nicht, dass Y der einzige Grund ist, warum wir X nicht lösen können.

Anders ausgedrückt, wir können Halt nicht nur nicht lösen, wir können auch nicht feststellen, dass ein Programm die Art von Programm ist, die wir nicht bestimmen können, ob es anhält, abgesehen von einer groben Maßnahme wie "Wenn die Ausführung länger als 1 Minute dauert" es hört nicht auf ".

Wenn Sie vom Problem des Anhaltens ausgehen und andere Probleme darauf reduzieren, erreichen Sie schließlich den Punkt, an dem Sie fast alle Fragen zu Programmen darüber reduziert haben. Wir enden mit dem Satz von Rice:

Sei S eine nicht triviale Eigenschaft von 1, die eine Turing-Maschine akzeptiert. Das heißt, es gibt mindestens eine Turing-Maschine, die Eingaben mit der Eigenschaft S akzeptiert, und eine, die dies nicht tut.

Dann ist es unentscheidbar, ob eine gegebene Turing-Maschine T Eingaben mit der Eigenschaft S akzeptiert.

Sie möchten wissen, ob eine Turing-Maschine auch ganze Zahlen akzeptiert? Unentscheidbar.

Sie möchten wissen, ob eine Turing-Maschine arithmetische Folgen akzeptiert? Unentscheidbar.

Sie können allgemein über die Eingeweide von Turing Machine nachdenken. Sie können über eine bestimmte Turing-Maschine nachdenken und nachweisen, ob sie eine Sequenz anhält / akzeptiert / etc. Sie können jedoch nicht wissen, ob Ihre Technik bei der nächsten Turing-Maschine, die Sie füttern, funktioniert.


1 Durch property ofes enthält nicht den Mechanismus, wie es angenommen wird - nur von was akzeptiert wird. "Es akzeptiert in 100 oder weniger Schritten" ist eine Eigenschaft, wie es akzeptiert, nicht von dem, was akzeptiert wird.

Yakk
quelle
Vielleicht möchten Sie erklären, was eine "Eigenschaft" ist, da die naive Interpretation, die Sie möglicherweise vornehmen, wahrscheinlich falsch ist.
Rick Decker
@rick Ich denke die Fußnote deckt es jetzt ab?
Yakk
7

Sie haben Recht, dass das allgemein eingeführte und festgestellte Problem des Anhaltens nur eine bloße Panne ist. Es beweist nicht, dass es keine dreiwertige Stoppfunktion ('halts', 'loops', 'don't know') geben kann, die in der Praxis immer 'halts' oder 'loops' und nur 'don' zurückgibt. t know 'zum Beispiel für speziell konstruierte Eckschränke.

Zwei Gründe, aus denen das Halteproblem erheblich ist:

1) Dies ist eines der ersten nachweislich unentscheidbaren Probleme. Selbst wenn es hypothetisch nur ein "Weiß nicht" gäbe, wäre es dennoch von großem mathematischen Interesse.

2) Einige Probleme beschränken sich auf das Stopp-Problem, bei dem ein böswilliger Angreifer den zu analysierenden Fall bereitstellen kann. Dies zwingt uns zu akzeptieren, dass es möglicherweise gültige Fälle gibt, die wir noch ablehnen müssen.

Nach dem zweiten Punkt ist die Software-Analyse ein schwieriges Problem, obwohl sowohl bei der Analyse als auch beim Sprachdesign große Fortschritte erzielt wurden, um die Analyse zu vereinfachen. Wenn Sie nachweisen können, dass eine bestimmte Aufgabe der Softwareanalyse ähnelt, ist sie schwer zu bewältigen. "Es ist unmöglich, weil es sich um die Lösung des Halteproblems handelt", obwohl sie in vielen Fällen technisch falsch oder irrelevant ist, wird sie häufig verwendet Abkürzung für diese Beobachtung.

Anonym
quelle
5

In einer Reihe von Beiträgen argumentiert Eric Hehner konträr, dass die Unlösbarkeit des Halteproblems häufig missverstanden wird. Die Artikel "Epimenides, Gödel, Turing: Ein ewiges goldenes Gewirr", "Probleme mit dem Halteproblem", "Rekonstruktion des Halteproblems" und "Halteproblem" finden Sie hier . Damit diese Antwort nicht "nur ein Link" ist, werde ich versuchen, eine seiner Schlussfolgerungen zusammenzufassen, aber nicht das Argument.

Die Schlussfolgerung lautet wie folgt: Der Grund dafür, dass das Stopp-Problem nicht lösbar ist, liegt nicht darin, dass ein Programm, von dem behauptet wird, es zu lösen, verwendet werden kann, um einen Widerspruch zu erzeugen, sondern darin, dass das Problem selbst in demselben Sinne wie eine Spezifikation einer Funktion, die es ist, nicht implementierbar ist muss sowohl 1 als auch 2 gleichzeitig zurückgeben ist nicht implementierbar. Wir finden es nicht bemerkenswert, dass es kein Programm gibt, das eine Spezifikation erfülltf(0)=1f(0)=2hh(M)MHhh

Theodore Norvell
quelle
3
Ich folge nicht Die Anhaltefunktion ist ein genau definiertes und gültiges Prädikat - für jede gegebene Turing-Maschine und jede gegebene Eingabe hält die Maschine an oder schleift. (Es fehlt Ihnen ein entsprechender Hinweis. Welchen Artikel fassen Sie zusammen?)
Raphael
@Raphael Dass die Funktion gut definiert ist, wird allgemein als Tatsache akzeptiert. Hehners Sichtweise ist anders und wird in seinen Papieren erläutert. Ich bearbeite meine Antwort, um die Namen der Papiere anzugeben.
Theodore Norvell
Sagen wir einfach, was auch immer Hehners Argument ist [ich habe die Zeitungen nicht gelesen], sie haben sich zumindest in ihrer ersten Lesung / Annäherung als kontrovers erwiesen
Fizz
Und es ist angesichts der Art und Anzahl der Zitate, die Hehners Aufsätze (zu diesem Thema) enthalten, nicht klar, dass zusätzliche Lesungen (zu seinen Arbeiten zu diesem Thema) die Mühe wert sind.
Fizz
Seine Beweise scheinen sehr solide zu sein und zeigen, dass es sich nur um eine Wiederholung alberner Dinge handelt, die Sie in der Philosophie tun können, wie den Versuch, die folgende Selbstreferenzaussage auf ihre Wahrhaftigkeit hin zu analysieren: "Dieser Satz ist falsch." Wenn wahr bedeutet, dass es falsch ist, bedeutet dies, dass es tatsächlich wahr ist. Nein, das macht es wieder falsch. en.wikipedia.org/wiki/Liar_paradox Das stoppende Paradox mag ein Fall von Wissenschaftlern sein, die nicht mit Philosophen sprechen.
James Wakefield
3

Ich möchte die Bedeutung des Stillstandsproblems, an dem Menschen und nicht Maschinen beteiligt sind, anders erläutern.

Es ist die letzte Vorlesung des Kurses Struktur und Interpretation des MIT 1986 ; Der Professor fragt: "Gibt es irgendwelche Fragen?" und bereitet sich auf das Ende der Vorlesung vor, als einer der Schüler fragt: "Ist das die letzte Frage?"

Denken Sie einen Moment darüber nach. Wie kann der Lehrer das beantworten? Wenn der Schüler beschließt, dem Lehrer zu widersprechen, gibt es keine gültige Antwort, die der Lehrer geben kann - dies ist genau wie das Problem des Anhaltens.

Wir sind es gewohnt, abstrakt über das Problem des Anhaltens nachzudenken, indem wir Funktionen und Maschinen verwenden, aber es geht viel tiefer. Grundsätzlich bedeutet dies, dass es durchaus berechtigte Fragen gibt, die nicht beantwortet werden können.

PS: Wenn Sie nicht wissen, von welchem ​​Kurs ich spreche, schauen Sie es sich an, es ist großartig.

SlySherZ
quelle
Aber wenn ich ausführen würde, doesHalt(programCode, input);kann das Programm nicht wissen, was die doesHaltFunktion zurückgibt. Es ist nicht möglich, das Programm anzuhalten, nachdem die doesHaltFunktion es ausgewertet hat.
Tvde1
0

Ich kann leicht ein Programm schreiben, das bei einer Eingabe von n entweder die kleinste Primzahl p> n ausgibt, so dass p + 2 auch eine Primzahl ist, oder es läuft für immer, wenn es keine solche gibt. Wenn Sie das Problem lösen können, um vorherzusagen, ob mein Programm für jede Eingabe anhält, haben Sie gerade die Twin Prime Conjecture gelöst.

Es ist durchaus möglich, dass sich diese Vermutung als unentscheidbar herausstellt. In diesem Fall hätten wir ein einfaches Programm, bei dem das Stopp-Programm fehlschlägt.

gnasher729
quelle
Ich denke, Sie mischen "Turing-Undecidable" mit einem ganz anderen Begriff; Möglicherweise sind Sie aus Versehen auf den "gleichen alten" Irrtum gestoßen. Siehe auch hier und hier .
Raphael