Warum ist das Halteproblem wirklich so wichtig?

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.

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. $2^n$$2^{32000000000}$$2^{10^9}$$300000000$

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.

$\exists$$\forall$

$\Sigma^0_0=\Pi^0_0$

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.

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.

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.)

$M$$2^M$$2^{56}$

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).

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.

$\Sigma(n):=$$n$$n$$n$$n$$\Sigma(n)$

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?

$H$$P$$x$$H$$P$$x$

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.

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.

$s$$2^s$

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.

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.

¹ 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.

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.

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üllt$f(0)=1 \;\land\; f(0)=2$$h$$h(M)$$M$$H$$h$$h$

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.

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.