Problem stoppen - ein Problem, das mich stört

Meines Wissens fragt das Problem beim Anhalten, ob es ein Programm gibt, das entscheidet, ob ein getestetes Programm unter Berücksichtigung einiger Eingabedaten (unabhängig davon, um welches Programm es sich handelt oder welche Eingabedaten wir geben) beendet wird oder nicht. Die Antwort auf dieses Problem lautet "Nein". Mit anderen Worten, es gibt kein "einzelnes" Programm, das es für alle möglichen Paare überprüfen kann (einige Algorithmen, einige Eingabedaten).

Dies bedeutet jedoch nicht, dass wir nicht entscheiden können, ob ein bestimmtes Programm X beendet wird oder nicht.

Ich kann noch keine anderen Antworten kommentieren, aber eine davon hat meine Aufmerksamkeit erregt:

In der Praxis ist dies wichtig, da Sie Ihren unwissenden Vorgesetzten sagen können, "was Sie fragen, ist mathematisch unmöglich".

Vielleicht kannst du mir sagen, was diese Person gemeint hat? In meinem Szenario kann mein ignoranter Chef mich bitten, zu überprüfen (tatsächlich zu beweisen oder zu widerlegen), ob mein Programm (das ein bestimmtes Programm ist) beendet wird oder nicht. Und natürlich gibt es Paare (Algorithmus, Eingabedaten), von denen nachgewiesen werden kann, dass sie enden (oder niemals enden).

Die Frage ist - kann ich es für jedes solche Paar (Programm, Eingabedaten) separat beweisen? Selbst wenn die Antwort ja lautet, gibt es ein Problem - es kann unendlich viele 'Eingabedaten' geben. Es ist also ganz natürlich zu fragen: Kann ich für jeden Algorithmus beweisen, dass dieser Algorithmus beendet wird (oder umgekehrt), unabhängig davon, welche Eingabedaten ich bereitstelle?

computability halting-problem user4205580
quelle

Ob wir all diese Beweise finden können , ist eine Frage der Logik, denke ich, aber es gibt sicherlich viele, die wir noch nicht gefunden haben .

Raphael

Das Stoppproblem ist als ein spezifischer Algorithmus definiert, der bestimmen kann, ob ein Programm angehalten wird oder nicht. Es ist möglich, ein bestimmtes Programm (oder sogar mehrere bestimmte Programme) mit verschiedenen Algorithmen zu überprüfen, ob sie angehalten werden können oder nicht (der allgemeine Fall ist dies nicht)

Nikos M.

Antworten:

Nein, Sie können dies nicht für jeden Algorithmus (Turing-Maschine) beweisen. Dies wird eher zu einer Frage nach der Art der Beweise als zu einer Frage der Berechnung.

Betrachten Sie die folgende Turingmaschine : Überprüfen Sie, ob ein Beweis für die Anweisung Halts der Länge(Zur Erklärung der Selbstreferenz siehe Klenees Rekursionssatz). Wenn ein solcher Beweis gefunden wird, geraten Sie in eine Endlosschleife (andernfalls halten Sie an). $M(x)$ $\forall x \hspace{1mm} M(x)$ $\le |x|$

Natürlich können Sie nicht beweisen, dass für alle anhält , da ein Beweis für die Länge nicht für alle Eingaben der Größe . Außerdem können Sie nicht beweisen, dass für einige nicht anhält , da dies bedeuten würde, dass es einen Beweis für das Anhalten von an allen Eingaben gibt (Widerspruch). Die Situation hier ist, dass, wenn unser Axiomensystem konsistent ist, für alle anhält , aber Sie können es nicht beweisen (was bedeutet, dass Sie in Ihrer Theorie beweisen können, dass wenn konsistent ist, $M(x)$ $x$ $p$ $\ge p$ $M(x)$ $x$ $M$ $M(x)$ $x$ $T$ $T$ $\forall x \hspace{1mm} M(x)$ wird angehalten, aber Sie können nicht beweisen, dass es ohne diese Annahme angehalten wird, es sei denn, Ihr System ist inkonsistent.

Ariel
quelle

Dies ist die Antwort auf "Kann ich für jeden Algorithmus beweisen, dass dieser Algorithmus beendet wird (oder umgekehrt), unabhängig davon, welche Eingabedaten ich bereitstelle?" - nur um sicher zugehen.

user4205580

Ja. Benötigen Sie mehr Zeichen

Ariel

Vielleicht interessieren Sie auch die Ergebnisse der Unvollständigkeit von Godel : Grundsätzlich gibt es in jedem logischen System, das leistungsfähig genug ist, um über Arithmetik zu sprechen, Aussagen, die wahr sind und nicht bewiesen werden können.

Jmite

- TuringMaschine,

- seine Eingabe. Dann führen wir es beispielsweise mit

. Das Programm übersetzt: "Überprüfen Sie, ob es einen Beweis für die Aussage gibt: für alle

M (2) Halts mit einer Länge von

..." Es ist nicht ganz sinnvoll, für alle

zu sagen. Oder vielleicht sollte ich es nicht so sehen.

M

$M$

x

$x$

x = 2

$x=2$

2

$2$

\leq 2

$\le 2$

2

$2$

user4205580

\forall y M (y)

$\forall y M(y)$

x

$x$

Für ein bestimmtes Programm kann ich sicher beweisen, dass das Programm bei allen Eingaben angehalten wird: Mein Programm hat "halt" als erste Anweisung.

Ein weiteres Beispiel: Ich kann ein bestimmtes Programm haben, das ein Turing-Maschinensimulator ist (dh eine universelle Turing-Maschine). Es interpretiert seine Eingabe als Beschreibung einer Turing-Maschine, und der Simulator simuliert die Maschine, die auf einem leeren Band läuft. Der Simulator stoppt also, wenn die eingegebene Maschine stoppt, und läuft für immer, wenn die eingegebene Maschine für immer läuft. (Wenn die Eingabe nicht das richtige Format zur Beschreibung einer Turing-Maschine hat, stoppt der Simulator.)

Wir wissen, dass es unmöglich ist zu entscheiden, ob eine beliebige Turing-Maschine beim Starten auf einem leeren Band anhält. Für meine spezielle Simulatormaschine gibt es also keinen Algorithmus, mit dem entschieden werden kann, was bei einer beliebigen Eingabe geschieht.

Ich weiß nicht, ob diese beiden Beispiele helfen.

Sicherlich ist es in vielen Problembereichen vernünftig nachzuweisen, dass bestimmte Programme beendet werden. Wenn mein Programm zwei Matrizen multipliziert, würde ich erwarten können, beweisen zu können, dass es keinen Weg gibt, wie es für immer weitergehen kann.

user42735
quelle

Ich kann zumindest die hypothetische Frage klären, die der imaginäre Chef stellen soll und die zu dieser Antwort führt:

Können Sie ein Programm entwerfen, das dieses andere Programm / Vorlage / Datenbankabfrage / usw. verwendet, das immer bestimmt, ob es eine Ausnahme beendet / auslöst / nicht genügend Speicherplatz hat?

Der Punkt des Unmöglichkeitsbeweises ist, dass eine solche Aufgabe nicht erfüllt werden kann. Natürlich ist es heute allgemein bekannt, dass eine solche Aufgabe ziemlich gut angenähert werden kann , dh es ist möglich, einen Algorithmus anzugeben , der bestimmt, ob ein Programm eine Ausnahme auslösen wird , aber manchmal antwortet "könnte eine Ausnahme auslösen", obwohl das Programm dies nicht tut Mach es nicht in der Praxis .

Einige davon sind auch in der Praxis schwieriger durchzuführen, z. B. ist die Beendigung schwieriger zu beweisen als das Fehlen einer Nullzeigerausnahme für "Programme der realen Welt" (aber theoretisch gleichwertig).

Cody
quelle