Beispiel eines Algorithmus, dem ein Korrektheitsnachweis fehlt

Wir haben Hoare-Logik. Warum ist es immer noch möglich, dass ein Algorithmus richtig ist, aber es gibt keinen Beweis dafür, dass er richtig ist? Angenommen, der Algorithmus wird in C ausgedrückt. Dann können wir Schritt für Schritt argumentieren, dass er das tut, was er tun soll.

Meine Frage lautet also:

Geben Sie mir ein Beispiel für einen Algorithmus, der richtig ist, aber keinen Beweis für die Richtigkeit hat.

EDIT: Ich denke, ein kleiner Hintergrund kann helfen zu klären, wohin ich gehe. Lassen Sie mich Scott Aaronson zitieren:

Seit den 1970er Jahren wird spekuliert, dass P NP unabhängig von den Standard-Axiomsystemen für Mathematik wie der Zermelo-Fraenkel-Mengen-Theorie sein könnte (dh weder nachweisbar noch widerlegbar). Klar wäre das auch$\ne$

1. Es gibt keinen Polynom-Zeit-Algorithmus für NP-vollständige Probleme, aber wir können ihn niemals beweisen (zumindest nicht in unseren üblichen formalen Systemen)

2. ein Polynom-Algorithmus für NP-vollständige Probleme tut existieren, aber entweder wir können nie beweisen , dass es funktioniert, oder wir können nie beweisen , dass es in polynomialer Zeit anhält.

Ich beziehe mich auf die zweite Möglichkeit. Da Aaronson es so sicher als eine Möglichkeit auflisten kann, denke ich, dass es ein existierendes Beispiel vom Typ 2 geben muss. Deshalb stelle ich diese Frage. Aber eine schnelle und klare Antwort scheint nicht in Sicht.

Hier ist ein Algorithmus für die Identitätsfunktion:

• Eingabe: $n$
• Überprüfen Sie, ob die te Binärzeichenfolge in ZFC einen Beweis von 0 > 1 codiert , und geben Sie in diesem Fall n + $n$$0 > 1$$n+1$
• Andernfalls geben Sie $n$

Die meisten Leute vermuten, dass dieser Algorithmus die Identitätsfunktion berechnet, aber wir wissen es nicht und wir können es im allgemein akzeptierten Rahmen für Mathematik, ZFC, nicht beweisen .

Die meisten Algorithmen haben sich in der Hoare-Logik nicht als richtig erwiesen. Der Hauptgrund dafür ist, dass solche Korrektheitsnachweise ab Januar 2017 extrem teuer sind, wahrscheinlich um mehrere Größenordnungen im Vergleich zur reinen Programmierung. Es wird viel gearbeitet, um diese Kosten durch Automatisierung zu senken, aber es ist ein harter Kampf.

Ein weiterer Grund, warum ein Algorithmus möglicherweise keinen Korrektheitsnachweis hat und der in der Praxis relevanter ist als die von Yuval und Chi erwähnten Unvollständigkeitsphänomene, besteht darin, dass wir möglicherweise nicht wissen, was diese Spezifikation ist. Dieses Problem hat zwei Dimensionen.

• Die Kunden wissen nicht, was sie wollen. Dies ist ein bekanntes Problem in der Softwareentwicklung, und Softwareentwickler haben viele Ansätze entwickelt, um damit umzugehen.

• Die Spezifikation ist schwierig. Ein gutes Beispiel ist die Korrektheit kryptografischer Algorithmen. Erst kürzlich wurde Micali & Goldwasser mit dem Turing-Preis für die Angabe der Bedeutung der kryptografischen Sicherheit ausgezeichnet. Beachten Sie jedoch, dass diese Definition (soweit mir bekannt ist) für "theoretische Kryptographie" gilt, bei der Sie einen Sicherheitsparameter $n$Über natürliche Zahlen reichend, und Gegner sind polynomielle zeitprobabilistische Turing-Maschinen. Nach meinem besten Wissen (bitte korrigieren Sie mich, wenn ich mich irre) besteht eine Diskrepanz zwischen Theorie und Praxis, und konkrete Algorithmen wie AES und SHA256 liegen nicht ganz im Geltungsbereich dieser theoretischen Spezifikationen. Ich glaube nicht, dass es eine vollständige Spezifikation für solche Algorithmen gibt, daher können wir sie im Prinzip nicht im Sinne von z. B. Hoare-Logik verifizieren.

$P(n)$$P(0)$$P(1)$$P(2)$$\forall n\in \mathbb{N}.\ P(n)$

$M$$n$$P(n)$$M$$\forall n.\ P(n)$$M$$\forall n.\ P(n)$

Problem: Geben Sie "Ja" aus, wenn jede gerade Zahl ≥ 4 die Summe zweier Primzahlen ist, und "Nein", wenn es eine gerade Zahl ≥ 4 gibt, die nicht die Summe zweier Primzahlen ist.

Algorithmus: "Ja" drucken

Die meisten Leute denken, dass der Algorithmus korrekt ist. Es gibt keinen bekannten Beweis, und es ist durchaus möglich , dass es ist kein Beweis.

Jeder Algorithmus, der korrekt ist, von dem wir jedoch nicht wissen, wie lange die Ausführung dauert, kann in einen Algorithmus umgewandelt werden, der in einer garantierten Zeitspanne anhält, bei dem wir uns jedoch nicht sicher sind, ob er korrekt ist.

$n$$n+1$$0$$\log(n)^2$$0$$\sqrt{n}$

$P=NP$