Das Problem des Anhaltens besagt, dass es keinen Algorithmus gibt, der feststellt, ob ein bestimmtes Programm anhält. Infolgedessen sollte es Programme geben, über die wir nicht sagen können, ob sie enden oder nicht. Was sind die einfachsten (kleinsten) bekannten Beispiele für solche Programme?
computability
turing-machines
halting-problem
MaiaVictor
quelle
quelle
Antworten:
Ein ziemlich einfaches Beispiel könnte ein Programm sein, das die Collatz-Vermutung testet :
Es ist bekannt , dass es fürn bis zu mindestens anhält5×260≈5.764×1018 , aber im Allgemeinen ist es ein offenes Problem.
quelle
"Wir" sind kein Algorithmus =) Es gibt keinen allgemeinen Algorithmus, der bestimmen könnte, ob ein bestimmtes Programm für jedes Programm anhält .
Betrachten Sie das folgende Programm:
Die Funktion is_perfect prüft, ob n eine perfekte Zahl ist . Es ist nicht bekannt, ob es ungerade perfekte Zahlen gibt, daher wissen wir nicht, ob dieses Programm anhält oder nicht.
quelle
Du schreibst:
Dies ist in beide Richtungen keine Sequenzierung. Sie erliegen einem allgemeinen Irrtum , der es wert ist, angesprochen zu werden.
Bei jedem festen Programm ist sein Stoppproblem ("Hält P immer an?") Immer entscheidbar, da die Antwort entweder "Ja" oder "Nein" ist. Auch wenn Sie nicht erkennen können, um welchen es sich handelt, wissen Sie, dass einer der beiden einfachen Algorithmen, die immer mit "Ja" bzw. "Ja" antworten, "nein" löst das PP P P Halting-Problem.
Nur wenn Sie verlangen, dass der Algorithmus das Problem des Anhaltens für alle Programme löst, können Sie nachweisen, dass kein solcher Algorithmus existieren kann.
Das Wissen, dass das Problem des Anhaltens nicht entschieden werden kann, bedeutet nicht, dass es Programme gibt, deren Beendigung oder Schleifenbildung niemand beweisen kann. Selbst wenn Sie nicht leistungsfähiger sind als eine Turing-Maschine (dies ist nur eine Hypothese, keine bewiesene Tatsache), wissen wir nur, dass kein einzelner Algorithmus / keine einzelne Person einen solchen Beweis für alle Programme liefern kann . Es kann eine andere Person geben, die für jedes Programm entscheiden kann.
Weitere verwandte Lektüre:
Sie sehen also, dass Ihre eigentliche Frage (wie unten wiederholt) nichts damit zu tun hat, ob das Halteproblem berechenbar ist. Überhaupt.
Zugegeben, diese sind nicht sehr "natürlich".
quelle
Jedes offene Problem in Bezug auf die Existenz einer Nummer mit bestimmten Eigenschaften führt zu einem solchen Programm (demjenigen, das nach einer solchen Nummer sucht). Nehmen Sie zum Beispiel die Collatz-Vermutung; da wir nicht wissen, ob es wahr ist, wissen wir auch nicht, ob das folgende Programm beendet wird:
quelle
Da das Busy Beaver- Problem für eine Turing-Maschine mit 5 Zuständen und 2 Symbolen nicht gelöst ist, muss es eine Turing-Maschine mit nur fünf Zuständen und nur zwei Symbolen geben, die beim Starten für ein leeres Band nicht angehalten oder nicht angezeigt wurde . Das ist ein sehr kurzes, kurzes und geschlossenes Programm.
quelle
Die Frage ist knifflig, da die Entscheidbarkeit (die CS-äquivalente Formalisierung / Verallgemeinerung des Halteproblems) mit Sprachen verbunden ist und daher in diesem Format neu gefasst werden muss. dies scheint nicht besonders hervorgehoben zu werden, aber viele offene Probleme in Mathe / CS können leicht in Probleme (Sprachen) unbekannter Entscheidbarkeit umgewandelt werden. Dies ist auf eine enge Übereinstimmung zwischen Theorembeweis und (Un) Entscheidbarkeitsanalyse zurückzuführen. Nehmen Sie zum Beispiel (ähnlich wie die andere Antwort für ungerade perfekte Zahlen) die Zwillingsprim-Vermutung, die auf die Griechen (vor über 2 Jahrtausenden) zurückgeht und großen jüngsten Forschungsfortschritten unterworfen ist, z. B. von Zhang / Tao. Konvertieren Sie es wie folgt in ein algorithmisches Problem:
Der Algorithmus sucht nach doppelten Primzahlen und hält an, wenn er n von ihnen findet. Es ist nicht bekannt, ob diese Sprache entscheidbar ist. Die Lösung des Problems der Doppelprimzahlen (die fragt, ob es eine endliche oder eine unendliche Zahl gibt) würde auch die Entscheidbarkeit dieser Sprache auflösen (wenn auch bewiesen / entdeckt wird, wie viele es gibt, wenn sie endlich ist).
In einem anderen Beispiel nehmen wir die Riemann-Hypothese und betrachten diese Sprache:
Der Algorithmus sucht nach nichttrivialen Nullen (der Code ist nicht besonders komplex, er ähnelt der Wurzelfindung, und es gibt andere äquivalente Formulierungen, die relativ einfach sind und im Grunde genommen die Summe der "Parität" aller Primzahlen kleiner als x usw. berechnen ) und hält an, wenn es findet n von ihnen und es ist nicht bekannt, ob diese Sprache entscheidbar ist und die Auflösung "fast" der Lösung der Riemann-Vermutung entspricht.
Wie wäre es nun mit einem noch spektakuläreren Beispiel? ( Einschränkung, wahrscheinlich auch kontroverser)
In ähnlicher Weise entspricht die Auflösung der Entscheidbarkeit dieser Sprache fast dem P-gegen-NP-Problem . In diesem Fall gibt es jedoch weniger offensichtliche Gründe für "einfachen" Code für das Problem.
quelle
Schreiben Sie ein einfaches Programm, das prüft, ob für jedes n1≤n≤1050 , the Collatz sequence starting with n will reach the number 1 in less than a billion iterations. When it has the answer, let the program stop if the answer is "Yes", and let it loop forever if the answer is "No".
We cannot tell whether this program terminates or not. (Who is we? Let's say "we" is anyone who could add a comment to my answer). However, someone with an incredibly powerful computer might tell. Some genius mathematician might be able to tell. There might be a rather small n, say n ≈1020 where a billion iterations are needed; that would be in reach of someone with a lot of determination, a lot of time, and a lot of money. But right now, we cannot tell.
quelle