Ist das Halteproblem für bestimmte Eingaben / Annahmen berechenbar?

Nach meinem Verständnis des Beweises, dass das Problem des Anhaltens nicht berechenbar ist, ist dieses Problem nicht berechenbar, da wir, wenn wir ein Programm P (x) haben, das berechnet, ob das Programm x anhält oder nicht, ein Paradox erhalten, wenn wir P als Eingabe für das Programm geben dasselbe P mit: P (P), wobei versucht wird, zu entscheiden, ob P anhält oder nicht, indem P selbst verwendet wird.

Meine Frage ist also: Kann das Stopp-Problem von Programm P für alle anderen als Eingabe verwendeten Programme außer P selbst berechnet werden? Mit anderen Worten: Ist das Halteproblem nur in diesem speziellen Fall nicht berechenbar oder ist der Beweis allgemeiner und ich vermisse etwas?

Wenn eine berechenbare Funktion ist, dann ist g definiert als$f$$g$

ist auch berechenbar für jede Wahl von .$k,v$

Wenn Sie ein Programm , das g ( n ) für alle n außer n = k berechnet , können Sie diesen Fall "korrigieren" (z. B. mit einem ) und ein anderes Programm P erhalten , das g ( n ) für berechnet alle n .$P'$$g(n)$$n$$n=k$if then else$P$$g(n)$$n$

Wenn Sie also die Anhaltefunktion "außer in einem Fall" berechnen könnten, könnten Sie auch die Anhaltefunktion berechnen (ohne Ausnahmen). Daraus können Sie wie gewohnt einen Widerspruch ableiten.

Fazit: Nein, Sie können das Stopp-Problem nicht "außer in einem Fall" (oder "außer in endlich vielen Fällen") entscheiden.

Kann das Problem des Anhaltens von Programm P für alle anderen als Eingabe verwendeten Programme außer P selbst berechnet werden?

Nein . Betrachten wir die unendliche Folge von Programmen , wobei P i ist „Bewegen Sie den Kopf i  Quadrate nach rechts, dann i  Quadrate nach links, dann tun genau das, was P tun würde.“ Jedes dieser Programme erzeugt für jeden Eingang genau die gleiche Ausgabe wie  P (einschließlich einer  Endlosschleife, wenn P für immer eine Endlosschleife ausführt), aber alle sind unterschiedliche Programme.$P_1, P_2, \dots$$P_i$$i$$i$$P$$P$$P$

Und Sie können dies nicht umgehen, indem Sie nur dazu verpflichten , an Programmen zu arbeiten, die sich funktional nicht entsprechen, da diese Eigenschaft ebenfalls unentscheidbar ist. Vielleicht wäre das Problem entscheidbar, wenn es auf diese Instanzen beschränkt wäre (obwohl ich vermute, dass dies nicht der Fall ist), aber die Menge der Instanzen ist unentscheidbar, sodass Sie die Einschränkung nicht durchführen können.$P$

Es gibt Algorithmen, die zeigen, dass bestimmte Klassen von Programmen anhalten oder nicht. Beispielsweise,

• Es ist möglich, algorithmisch zu bestimmen, ob ein Programm, das eine Maschine mit endlichen Zuständen modelliert, anhält.
• Es kann rechnerisch festgestellt werden, ob eine linear begrenzte Drehmaschine anhält
• Wenn Sie wissen, in welcher Komplexitätsklasse sich ein Programm befindet, wissen Sie, dass das Programm für endliche Eingaben anhält.

Während es keinen Algorithmus gibt, der feststellt, ob ein beliebiges Programm anhält, wurde ein Großteil des Codes entweder zum Anhalten (wie die meisten Subroutinen) oder nicht zum Anhalten (wie eine Endlosschleife zum Behandeln von Ereignissen) entworfen, und es ist möglich, algorithmisch festzustellen, welches Programm welches ist. Mit anderen Worten, Sie können einen Algorithmus haben, der entweder auf "Anhalten", "Nicht Anhalten" oder "Keine Ahnung" antwortet, und ein solcher Algorithmus kann so entworfen werden, dass er genügend Programme abdeckt, die nützlich wären.

Beweise durch Widerspruch müssen nicht erschöpfend sein , ein einziges Gegenbeispiel reicht aus. Der Beweis, dass das Halteproblem unentscheidbar ist, liefert Ihnen ein Beispiel für P, für das die Halteeigenschaft nicht entschieden werden kann. Dieser Beweis besagt nicht, dass P das einzige Programm dieser Art ist. Tatsächlich kann es unabhängige Beweise geben, die völlig unterschiedliche Klassen von P konstruieren.

Der Beweis ist in der Tat allgemeiner: Das Halteproblem ist ein Sonderfall des Satzes von Rice , der besagt

$\Phi$

$A$$B$$\Phi(A)$$\Phi(B)$

$x$$x$

Sie können einige Ergebnisse erzielen, indem Sie den Speicherplatz der Programme einschränken, mit denen Sie arbeiten möchten, obwohl diese Einschränkungen ziemlich drastisch sein müssen. Wenn Sie beispielsweise die Garantie haben, dass das Programm, das Sie erhalten, innerhalb von 100 Schritten angehalten wird oder für immer ausgeführt wird, wird die Entscheidung, ob es angehalten wird, einfach.

$N$$k$$BB(k)$

Sei R eine beliebige rekursiv aufzählbare, aber nicht rekursive Menge. Es gibt unendlich viele solcher Sets. Sei T eine Turing-Maschine, die bei Eingabe von k genau dann anhält, wenn k in R ist. Ein solches T existiert für jede rekursiv aufzählbare Menge. Es ist unmöglich, ein Programm zu schreiben, das das Halteproblem für dieses T lösen kann. Dies liegt daran, dass jeder Algorithmus zur Bestimmung, ob T anhält, einen Algorithmus zur Bestimmung der Zugehörigkeit zu R liefert, der unmöglich ist, wenn R nicht rekursiv ist. Da es unendlich viele solcher R gibt, die jeweils unterschiedliche Turing-Maschinen ergeben, gibt es unendlich viele Turing-Maschinen, bei denen ein Versuch, das Programm P anzuhalten, fehlschlagen würde.