Ist das Halteproblem für reine Programme auf einem idealen Computer entscheidbar?

25

Es ist ziemlich einfach zu verstehen, warum das Problem des Anhaltens für unreine Programme (dh Programme mit E / A und / oder Zuständen, die vom maschinenglobalen Zustand abhängen) nicht entschieden werden kann. aber intuitiv scheint es, dass das Anhalten eines reinen Programms auf einem idealen Computer z. B. durch statische Analyse entscheidbar wäre.

Ist das tatsächlich der Fall? Wenn nicht, welche Gegenbeispiele oder Papiere widerlegen diese Behauptung?

halting-problem static-analysis Jules
quelle
35
Beachten Sie, dass die Standard-Beweise, dass das Problem des Anhaltens nicht zu entscheiden ist (wie das auf Wikipedia beschriebene: de.wikipedia.org/wiki/Halting_problem#Sketch_of_proof ), alle mit Berechnungsmodellen funktionieren, die nicht einmal versuchen, E / A darzustellen. Und während zB Turingmaschinen zustandsbehaftet sind, ist ihr Verhalten formal über reine Funktionen definiert. In gewissem Sinne ist "reine Programme auf einem idealen Computer" die Einstellung, in der sich das Problem des Anhaltens normalerweise als unentscheidbar herausstellt.
Ben
1
Welche Recherchen haben Sie durchgeführt? Googeln "Halteproblem" hätte diese Frage schon für Sie beantworten sollen.
Jonathan Cast

Antworten:

38

Hier ist ein Beweis der Unentscheidbarkeit durch Reduktion des Halteproblems.

MxHMxMxM

HHMx

Lieuwe Vinkhuijzen
quelle
2
Das Problem mit dem Anhalten
Hendrik Jan,
@HendrikJan Genau!
Lieuwe Vinkhuijzen
16

Nein, das ist es nicht und es hängt auch nicht von der E / A ab.

Einfaches Gegenbeispiel: Schreiben Sie ein Programm, um eine perfekte ungerade Zahl zu finden (dies ist ein offenes Problem: Wir wissen noch nicht, ob es eine gibt). Es nimmt keine Eingaben entgegen und führt keine unreinen Aufgaben aus. es kann anhalten, wenn es eine findet, oder es kann unendlich funktionieren (in dem Fall, dass eine solche Nummer nicht existiert). Wenn nun die statische Analyse leistungsfähig genug wäre, um den Haltefall zu bestimmen, würde sie verwendet, um diesen (und viele weitere) Fragen zu beantworten, bei denen das Halten die positive Existenz einer solchen Zahl bedeuten würde und nicht das Halten die Existenz einer solchen Zahl bedeuten würde, aber leider die statische Analyse ist nicht so mächtig.

Böse
quelle
18
Ich sehe den Punkt in dieser Antwort nicht wirklich. Nur weil wir derzeit nicht wissen, ob eine solche Zahl existiert, heißt das noch lange nicht, dass wir in Zukunft keinen statischen Analysator schreiben können, der dies entscheiden kann. Eine bessere Alternative besteht darin, ein bekanntes, unentscheidbares Problem zu verwenden. Zum Beispiel ist bekannt, dass es kein Programm gibt, das alle diophantinen Gleichungen lösen kann, und das Lösen einer solchen Gleichung ist eine ähnliche Aufgabe wie die in der Antwort gezeigte.
Bakuriu
2
Nun, wenn das Problem des Anhaltens entscheidbar wäre, wäre jedes Problem entscheidbar, wenn wir es in eine Form bringen könnten, in der wir fragen, ob ein Programm anhält oder nicht. Oder eine Frage der Form: Es gibt eine abzählbare Menge, und ich kann entscheiden, ob ein einzelnes potenzielles Element in der Menge enthalten ist oder nicht. Ist das Set leer? Diophantine Gleichungen haben eine Reihe von möglichen Lösungen, und ich kann prüfen, ob jede einzelne mögliche Lösung eine Lösung ist oder nicht. Wenn das Halteproblem entscheidbar wäre, wären diophantinische Gleichungen entscheidbar.
gnasher729
10
@ gnasher729 Ja, und da es sich nicht um das Halting-Problem handelt, ist es nicht zu entscheiden. Das ist mein Punkt. Die Aussage in dieser Antwort hat zwar keine wirkliche Bedeutung: "Betrachten Sie diese mathematische Definition. Derzeit haben wir keine Ahnung, ob ein Programm, das dies entscheidet, aufhört oder nicht, aber morgen könnte ein Typ herausfinden, dass dies der Fall ist oder nicht, und diese Antwort wird 100 % bedeutungslos ".
Bakuriu
6
Ist dies nicht ein ähnlicher Fall wie Wie kann entschieden werden, ob π eine Ziffernfolge hat? Ist das Halteproblem unentscheidbar auf Klassen von Problemen, nicht einzelne Probleme.
Npostavs
2

Der klassische Beweis durch Diagonalisierung ist eine reine Maschine , nicht nur eine reine Turingmaschine, sondern beruht nicht auf "offenen Problemen".

In einem Beispiel hat eine Turing-Maschine, die die Collatz-Vermutung ausführt, einen unbekannten Haltestatus, der sich jedoch auf unsere Unkenntnis der Collatz-Vermutung stützt. Eines Tages könnten wir beweisen, dass Collatz Recht hatte, und dann würden wir in der Lage sein, den Haltestatus der Vermutung zu bestimmen (Entweder für einige Eingaben nicht anhalten, oder immer anhalten).

Die Collatz-Vermutung könnte Ihre Frage also bereits beantworten (zumindest vorübergehend), stützt sich jedoch auf etwas, das wir nicht wissen . Stattdessen ist der klassische Beweis ein gelöstes Problem: Wir wissen bereits, dass dies nicht zu entscheiden ist .

Spielentwickler
quelle
0

Nur zur Veranschaulichung: Der Standardbeweis für die Unentscheidbarkeit des Halteproblems basiert auf der gleichen Idee wie Quines: Es ist möglich, ein Programm zu schreiben, von dem ein Teilbegriff den Quellcode für das gesamte Programm auswertet. Wenn es dann eine Funktion gäbe halts, die im angegebenen Quellcode für ein Programm True zurückgibt, wenn dieses Programm bei allen Eingaben angehalten wird, und andernfalls False, wäre dies ein zulässiges Programm:

prog() = if halts "prog" then prog() else ()

wo "prog"wäre ein Ausdruck, für den der Quellcode ausgewertet wird prog; Sie können jedoch schnell erkennen, dass prog(für alle Eingaben) angehalten wird, wenn es nicht angehalten wird, was ein Widerspruch ist. Nichts in diesem Beweis ist in irgendeiner Weise von I / O abhängig (brauchen Sie I / O, um ein Quine zu schreiben?).

Übrigens möchten Sie vielleicht in "dialogbasierte E / A" nachsehen, um weitere Beweise dafür zu finden, dass E / A für Ihr Problem völlig irrelevant sind (im Grunde können Programme, die E / A ausführen, auf Programme reduziert werden, die Eingaben als annehmen (explizite) funktionale Argumente und Ausgabe als (explizite) zusätzliche Ergebnisse in einer faulen Sprache). Leider kann ich im Moment keine vernünftige, nicht voreingenommene (oder pro-dialogische) Seite im Web finden.

Jonathan Cast
quelle