Was sind die einfachsten Beispiele für Programme, von denen wir nicht wissen, ob sie enden?

27

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?

MaiaVictor
quelle
Sie widersprechen in Ihren Antworten ..... Danke! Das Stopp-Programm setzt jedoch die Kenntnis der Quelle voraus. ... Wenn dies zutrifft, haben Sie Ihre Frage beantwortet. Das Stopp-Programm würde es schon wissen. Stellen Sie sich ein System vor, das ein Schild steuert, das immer leuchtet und blinkt. Wann schaltet es sich aus? Stromausfall, Netzschalter oder während der Blitzsequenz. Oder niemals mit einer Batterieunterstützung und einem Generator.
htm11h
Ich würde hinzufügen, dass das Problem des Anhaltens nur dann ein Problem ist, wenn Sie keine obere Grenze für das Timing festlegen. Sicherlich gibt es in der Praxis keinen Unterschied, ob eine Antwort zu spät kommt, um von Nutzen zu sein, oder nicht. Sie können fragen, ob ein Programm innerhalb weniger Schritte eine Antwort zurückgibt, wie z. B. eine Echtzeitdefinition der Korrektheit. Wenn Sie keine zeitnahe Antwort garantieren können, haben Sie einfach ein Programm, für das keine Richtigkeitsgarantie besteht.
Rob
1
@Rob Das stimmt eigentlich nicht. Wenn Sie nicht wissen, ob eine Maschine anhält, können Sie auf unbestimmte Zeit warten, um festzustellen, ob sie anhält. Nach einem Jahrtausend wissen Sie immer noch nicht, ob es beispielsweise am nächsten Tag aufhört oder nicht.
Kyle Strand
@KyleStrand Ich stimme dir zu. Aber ich sage auch, dass es in der Praxis ein völlig überfrachtetes Problem ist, da für alle realistischen Berechnungen Fristen gelten (Millisekunden bis Monate). Wenn Sie eine Antwort innerhalb von 5 Sekunden benötigen, ist es nur wichtig, ob Sie eine Antwort innerhalb von 5 Sekunden garantieren können. Angenommen, Sie könnten eine Antwort mit einer unbestimmten Rechenzeit garantieren. Das wäre eine unbrauchbare Garantie.
Rob

Antworten:

41

Ein ziemlich einfaches Beispiel könnte ein Programm sein, das die Collatz-Vermutung testet :

f(n)={HALT,if n is 1f(n/2),if n is evenf(3n+1),if n is odd

Es ist bekannt , dass es für n bis zu mindestens anhält5×2605.764×1018 , aber im Allgemeinen ist es ein offenes Problem.

npostavs
quelle
9
Um meinen Standpunkt aus dem Kommentar unter der Frage hervorzuheben: Das Problem "Hält für alle n an ?" ist berechenbar . f(n)n
Raphael
6
@KyleStrand Siehe hier .
Raphael
10
@KyleStrand, Raphael ist zu 100% korrekt. Dies ist ein weit verbreitetes Missverständnis. Sie müssen sorgfältig nachvollziehen, was in der Definition steht, und dann stellen Sie möglicherweise fest, dass Ihre Intuition nicht ganz mit der Definition übereinstimmt. Nach der Definition der Berechenbarkeit genügt es , dass es existiert eine Turing - Maschine , es zu berechnen - es spielt keine Rolle , ob wir wissen , was die Turing - Maschine ist. Auf den ersten Blick denken so viele Schüler, dass es betrügt, aber nicht - das ist nur eine Konsequenz der Definition.
DW
2
@KyleStrand Sie müssen die Idee loswerden, dass das Programm das Problem lösen muss . Es tut nicht. Es muss nur die Antwort ausgegeben werden, was eine triviale Aufgabe ist. Algorithmisch gesehen sind Probleme mit endlichen Mengen von Instanzen alle langweilig, da wir die Antworten fest codieren können. (Und selbst wenn wir die Antworten nicht kennen, wissen wir immer noch, dass es einen korrekten Algorithmus gibt.) Wenn Sie im Allgemeinen zeigen, dass es für etwas keinen Algorithmus gibt, müssen Sie keine Annahmen darüber treffen, wie es ablaufen soll Arbeit. Unser Mangel an Vorstellungskraft liefert keinen Beweis.
Raphael
2
@KyleStrand Afaik, ich verwende die Standarddefinition der Berechenbarkeit, wie sie heute gelehrt wird (und afaik schon seit Jahrzehnten). Ich empfehle, dass Sie die Antworten und das verknüpfte Material aufnehmen und herausfinden, wo Sie einen Fehler gemacht haben. Es macht für mich und andere keinen Sinn, dieselben Dinge immer wieder zu wiederholen. Noch ein Versuch: Die Definition der Berechenbarkeit ist von Natur aus existenziell und nicht konstruktiv. Solange Sie im Bereich der klassischen Logik denken, müssen Sie überhaupt keinen "Lösungs" -Algorithmus übergeben können - wir müssen nur zeigen, dass es einen gibt, der die richtigen Antworten gibt.
Raphael
31

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.

"Wir" sind kein Algorithmus =) Es gibt keinen allgemeinen Algorithmus, der bestimmen könnte, ob ein bestimmtes Programm für jedes Programm anhält .

Was sind die einfachsten (kleinsten) bekannten Beispiele für solche Programme?

Betrachten Sie das folgende Programm:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

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.

avsmal
quelle
7
Wir sind ein Algorithmus.
PyRulez
3
@ PyRulez gibt es keinen Beweis dafür, dass die Rechenleistung des menschlichen Geistes Turing Machine entspricht. Der Beweis funktioniert nicht, z. B. ist nicht bekannt, wie man einen Geist in einem anderen simuliert.
1.
1
@avsmal Okay, aber es ist äußerst unwahrscheinlich, dass wir in der Lage sind, Hypercomputer zu verwenden.
PyRulez
2
@PyRulez John Lucas und Roger Penrose haben vorgeschlagen, dass der menschliche Verstand das Ergebnis einer quantenmechanisch verbesserten, "nicht algorithmischen" Berechnung sein könnte. Das ist eine starke Annahme. Aber zumindest kann unser Verstand eine Quelle der Unsicherheit haben. Und das ist genug, um den Beweis zu brechen: Es ist unmöglich, die "randomisierte" (für eine geeignete Definition des randomisierten Mittelwerts) Turing-Maschine zu negieren, wenn nicht bekannt ist, ob sie anhält.
1.
5
Wird Quantencomputing als Hypercomputing betrachtet? Ich bin davon ausgegangen, dass Quantencomputer durch Turing-Maschinen perfekt simuliert werden können - nur ein bisschen langsamer.
MaiaVictor
10

Du schreibst:

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.

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

Was sind die einfachsten (kleinsten) bekannten Beispiele für [Programme, von denen wir nicht wissen, ob sie angehalten oder wiederholt werden sollen]?

S

G(n)={1,S wahr,G(n+1),sonst.

Zugegeben, diese sind nicht sehr "natürlich".


  1. Nicht unbedingt alle , aber "viele" in gewissem Sinne. Zumindest unendlich viele.
Raphael
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Raphael
Ist es richtig zu sagen, dass es zwar keinen eindeutigen Algorithmus gibt, der bestimmen kann, ob ein beliebiges bestimmtes Programm anhält, es jedoch einen programmspezifischen Algorithmus geben kann, um das Halteproblem jedes möglichen Programms zu lösen?
Asad Saeeduddin
@AsadSaeeduddin Es ist "schlimmer": Für jede gegebene endliche Menge von Programmen ist das Problem des Anhaltens trivial . Jede endliche Menge ist entscheidbar.
Raphael
7

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:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  
Klaus Draeger
quelle
6

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.

kein Benutzer
quelle
0

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:

Eingabe: n . Ausgang: J / N gibt es mindestens n Doppelprimzahlen.

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:

Eingabe: n . Ausgabe: J / N Es existieren mindestens n nichttriviale Nullen der Riemannschen Zetafunktion.

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)

Eingabe: c: Ausgabe: J / N Es gibt einen O (n c ) -Algorithmus für SAT.

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.

vzn
quelle
1
Würde der Downvoter erklären, was mit dieser Antwort falsch ist?
MaiaVictor
2
Ihre "Twin Prime" Sprache ist entscheidend. Wenn es nur eine endliche Zahl gibtN von ihnen lautet die Antwort "Ja" für nNund "Nein" sonst immer "Ja". Klar, wir wissen es nichtN, aber das ist irrelevant, antwortet eine (sehr einfache) Turingmaschine. Genau wie in der Sprache "Fermats letzter Satz" gibt es ganze Zahlenein,b,c so dass einn+bn=cn zum n? ", kürzlich haben" wir "das herausgefunden N=2, Wiles 'Beweis änderte die Sprache nicht .
Vonbrand
3
I'm not the downvoter, but all of the claims in this answer are wrong. All three of those problems are provably decidable (without needing to make any unproven assumptions). For why, study Raphael's answer closely.
D.W.
ok maybe the input needs to have the TM specified and the algorithm decides if the TM calculates the problem. have to think about it more... think there is some simple recipe for these types of problems basically connecting open problems to undecidable languages... but agreed this is rarely documented/ formulated in CS refs... have only found a few scattered refs... or maybe the input is a proof and the language verifies if the proof is correct... the other high voted answers mention odd perfect numbers, collatz problem etc... the programs are unknown to halt or not for specific constants.
vzn
Entschuldigung für die Verwirrung! Bei einigen weiteren Überlegungen stimmen die Behauptungen dahingehend, dass sie einfache Programme beschreiben , von denen nicht bekannt ist, dass sie (für alle Eingaben) enden ( dh die ursprüngliche Frage), und dass das Scheitern der von DW skizzierten / angedeuteten Gesamtidee versucht, sie in jeweils umzuwandeln unentscheidbare Sprachen. Ich werde weiterhin über diese letztere Bauidee nachdenken, um eine zu finden, die Erfolg hat. Eine andere Sichtweise ist, dass die Probleme als einzelne Instanzen / Eingaben für einen Stopp-Problemlöser betrachtet werden können, aber nicht wirklich dem Stopp-Problem selbst äquivalent sind.
VZN
0

Schreiben Sie ein einfaches Programm, das prüft, ob für jedes n 1n1050, 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.

gnasher729
quelle