Theoretisch fehlerfreie Programme

Ich habe viele Artikel gelesen, die besagen, dass Code nicht fehlerfrei sein kann, und sie sprechen über diese Theoreme:

• Halteproblem
• Gödels Unvollständigkeitssatz
• Reis-Theorem

Tatsächlich scheint der Satz von Rice eine Implikation des Halteproblems zu sein, und das Halteproblem steht in enger Beziehung zu Gödels Unvollständigkeitssatz.

Bedeutet dies, dass jedes Programm mindestens ein unbeabsichtigtes Verhalten aufweist? Oder heißt das, dass es nicht möglich ist, Code zur Verifizierung zu schreiben? Was ist mit rekursiver Prüfung? Nehmen wir an, ich habe zwei Programme. Beide haben Fehler, aber sie teilen nicht den gleichen Fehler. Was passiert, wenn ich sie gleichzeitig ausführe?

In den meisten Diskussionen ging es natürlich um Turing-Maschinen. Was ist mit linearer Automatisierung (echte Computer)?

Es ist nicht so sehr, dass Programme nicht fehlerfrei sein können. Es ist sehr schwer zu beweisen, dass dies der Fall ist, wenn das Programm, das Sie beweisen möchten, nicht trivial ist.

Nicht aus Mangel an Versuchen, wohlgemerkt. Typsysteme sollen eine gewisse Sicherheit bieten; Haskell verfügt über ein hochentwickeltes Typensystem, das dies bis zu einem gewissen Grad ermöglicht. Sie können jedoch niemals alle Unsicherheiten beseitigen.

Betrachten Sie die folgende Funktion:

int add(int a, int b) { return a + b; }

Was könnte mit dieser Funktion schief gehen? Ich weiß schon was du denkst. Angenommen, wir haben alle Grundlagen abgedeckt, z. B. die Überprüfung auf Überlauf usw. Was passiert, wenn ein kosmischer Strahl auf den Prozessor trifft und ihn zur Ausführung bringt?

LaunchMissiles();

stattdessen?

OK, vielleicht ist das ein bisschen erfunden. Aber auch einfache Funktionen wie die addoben beschriebene müssen in Umgebungen ausgeführt werden, in denen der Prozessor ständig die Kontexte wechselt und zwischen mehreren Threads und Kernen wechselt. In einer solchen Umgebung kann alles passieren. Wenn Sie dies bezweifeln, gehen Sie davon aus, dass der Arbeitsspeicher zuverlässig ist, nicht weil er fehlerfrei ist, sondern weil er über ein integriertes System zur Korrektur der unvermeidlichen Bitfehler verfügt.

Ich weiß was du denkst. "Aber ich spreche von Software, nicht von Hardware."

Es gibt viele Techniken, die Ihr Selbstvertrauen verbessern können, dass die Software so funktioniert, wie sie soll. Funktionale Programmierung ist eine davon. Durch funktionale Programmierung können Sie die Parallelität besser beurteilen. Aber funktionale Programmierung ist kein Beweis, genauso wenig wie Unit-Tests.

Warum? Weil Sie diese Dinge Randfälle genannt haben.

Und wenn Sie nur ein wenig über die Einfachheit von hinausgehen return a + b, wird es bemerkenswert schwierig, die Richtigkeit eines Programms zu beweisen .

Lesen
Sie weiter Sie schreiben das Richtige
Die Ariane 5 Explosion

Lassen Sie uns zunächst festlegen, in welchem ​​Kontext Sie dies diskutieren möchten. Die Fragen und Antworten der Programmierer bei Stack Exchange legen nahe, dass Sie eher an der realen Existenz von Werkzeugen / Sprachen als an theoretischen Ergebnissen und Theoremen der Informatik interessiert sind .

Ich habe viele Artikel gelesen, die besagen, dass Code nicht fehlerfrei sein kann

Ich hoffe nicht, denn eine solche Aussage ist falsch. Obwohl allgemein anerkannt ist, dass die meisten großen Anwendungen nach meinem Wissen und meiner Erfahrung nicht fehlerfrei sind.

Häufiger ist akzeptiert , dass es sich nicht (dh Existenz, nicht möglich) ist ein Werkzeug , das perfekt zu bestimmen , ob ein Programm in einer schriftlichen Turing-complete Programmiersprache frei vollständig Bug.

Ein Non-Proof ist eine intuitive Erweiterung des Halting-Problems, kombiniert mit den Beobachtungsdaten der Alltagserfahrung.

Es tut exist Software , die „Beweise tun kann , Korrektheit “ , die überprüfen, ob ein Programm die entsprechenden erfüllt formale Spezifikationen für das Programm.

Bedeutet dies, dass jedes Programm mindestens ein unbeabsichtigtes Verhalten aufweist?

Nein. Es wurde jedoch festgestellt, dass die meisten Anwendungen mindestens einen Fehler oder ein ungewolltes Verhalten aufweisen.

Oder heißt das, dass es nicht möglich ist, Code zur Verifizierung zu schreiben?

Nein, Sie können formale Spezifikationen und Proof-Assistenten verwenden, um zu überprüfen, ob die Spezifikation eingehalten wurde. Wie die Erfahrung gezeigt hat, können im Gesamtsystem jedoch noch Fehler vorhanden sein, z. B. Faktoren außerhalb der Spezifikation - Quellcode-Übersetzer und Hardware in den Spezifikationen selbst.

Weitere Informationen finden Sie unter Coq ist ein solches Tool / eine solche Sprache / ein solches System.

Was ist mit rekursiver Prüfung?

Ich weiß es nicht. Ich kenne mich damit nicht aus und bin mir nicht sicher, ob es sich um ein Computing-Problem oder ein Compiler-Optimierungsproblem handelt.

Ich möchte fragen, bedeutet dies, dass jeder Code mindestens ein unbeabsichtigtes Verhalten aufweist?

Richtige Programme können und werden geschrieben. Wohlgemerkt, ein Programm kann korrekt sein, aber seine Ausführung kann z. B. aufgrund physikalischer Umstände fehlschlagen (wie der Benutzer Robert Harvey in seiner Antwort hier schrieb ), aber dies ist eine eindeutige Angelegenheit: Der Code dieses Programms ist immer noch korrekt. Um genauer zu sein, der Ausfall nicht durch einen verursachten Fehler oder Fehler in dem Programm selbst, sondern in der zugrunde liegenden Maschine , die es ausführt (*).

(*) Ich entlehne Definitionen für Fehler , Irrtümer und Ausfälle aus dem Zuverlässigkeitsbereich als einen statischen Fehler, einen inkorrekten internen Zustand und ein inkorrektes externes beobachtetes Verhalten gemäß seiner Spezifikation (siehe <Papier aus diesem Bereich>). .

Oder heißt das, dass ich keinen Code schreiben kann, der ihn überprüft?

Beziehen Sie sich auf den allgemeinen Fall in der obigen Aussage und Sie sind richtig.

Möglicherweise können Sie ein Programm schreiben, das überprüft, ob ein bestimmtes X-Programm korrekt ist. Wenn Sie beispielsweise ein "Hallo Welt" -Programm als ein Programm mit zwei aufeinanderfolgenden Befehlen definieren, nämlich print("hello world")und exit, können Sie ein Programm schreiben, das prüft, ob seine Eingabe ein Programm ist, das aus diesen beiden Befehlen besteht, und auf diese Weise meldet, ob es ein Programm ist richtiges "hallo welt" programm oder nicht.

Was Sie mit aktuellen Formulierungen nicht tun können, ist, ein Programm zu schreiben, um zu prüfen, ob ein beliebiges Programm anhält, was bedeutet, dass es in den allgemeinen Fällen unmöglich ist, die Richtigkeit zu überprüfen.

Das Ausführen von zwei oder mehr Varianten desselben Programms ist eine bekannte Fehlertoleranztechnik, die als N-Varianten- (oder N-Versions-) Programmierung bezeichnet wird. Dies ist eine Bestätigung für das Vorhandensein von Fehlern in der Software.

In der Regel werden diese Varianten von verschiedenen Entwicklungsteams mit unterschiedlichen Compilern codiert und manchmal auf unterschiedlichen CPUs mit unterschiedlichen Betriebssystemen ausgeführt. Die Ergebnisse werden abgestimmt, bevor sie an den Benutzer ausgegeben werden. Boeing und Airbus lieben diese Art von Architektur.

Es verbleiben zwei Schwachstellen, die zu Gleichtaktfehlern führen:

• Es gibt nur eine Spezifikation.
• Das Abstimmungssystem ist entweder einzigartig oder komplex.

Ein Programm hat eine Spezifikation und läuft in einer bestimmten Umgebung.

^{(Das Beispiel der kosmischen Strahlung in anderen Antworten, die sich ändern add, FireMissiles könnte als Teil der "Umwelt" angesehen werden.)}

Angenommen, Sie können das beabsichtigte Verhalten des Programms (dh seine Spezifikation) und seine Umgebung formell spezifizieren, dann könnten Sie manchmal formal nachweisen, dass das Programm in genau diesem Sinne fehlerfrei ist (sodass sein Verhalten oder seine Ausgabe die Formalisierung seiner Spezifikation in der Formalisierung respektiert seiner Umwelt).

Insbesondere können Sie Analysegeräte für statische Schallquellen wie z . B. Frama-C verwenden .

^{(Der aktuelle Stand der Technik solcher Analysegeräte erlaubt jedoch keine vollständige Programmanalyse und keinen Nachweis von umfangreichen Programmen wie dem GCC-Compiler oder dem Firefox-Browser oder dem Linux-Kernel. Ich glaube, dass solche Beweise in meinem Leben nicht vorkommen werden Ich wurde 1959 geboren)}

Was Sie jedoch bewiesen haben, ist das korrekte Verhalten des Programms in Bezug auf eine bestimmte Spezifikation in einer (Klasse von) Umgebung (en).

In der Praxis könnten (und die NASA oder die ESA wollen wahrscheinlich) Sie beweisen, dass einige Raumschiffsoftware "fehlerfrei" ist, in Bezug auf eine präzise - und formalisierte - Spezifikation. Dies bedeutet jedoch nicht, dass sich Ihr System immer so verhält, wie Sie es möchten.

In einfacheren Worten, wenn Ihr Raumfahrzeugroboter auf ein ET trifft und Sie dies nicht spezifiziert haben, gibt es keine Möglichkeit, dass sich Ihr Roboter so verhält, wie Sie es wirklich wollen ...

Lesen Sie auch die Blogeinträge von J.Pitrat .

BTW, Halting Problem oder Gödels Theorem gelten wahrscheinlich auch für das menschliche Gehirn oder sogar die menschliche Spezies.

Bedeutet dies, dass jedes Programm mindestens ein unbeabsichtigtes Verhalten aufweist?

Nein.

Das Problem des Anhaltens besagt, dass es unmöglich ist, ein Programm zu schreiben, das testet, ob jedes Programm in einer begrenzten Zeit anhält. Dies bedeutet nicht, dass es unmöglich ist, ein Programm zu schreiben, das einige Programme als anhalten, andere als nicht anhalten einstuft. Das bedeutet, dass es immer einige Programme gibt, die ein Stopp-Analysator nicht auf die eine oder andere Weise kategorisieren kann.

Gödels Unvollständigkeitssätze haben eine ähnliche Grauzone wie sie. Bei einem mathematischen System mit ausreichender Komplexität gibt es einige Aussagen im Zusammenhang mit diesem System, deren Richtigkeit nicht beurteilt werden kann. Dies bedeutet nicht, dass Mathematiker auf die Idee des Beweises verzichten müssen. Der Beweis bleibt der Eckpfeiler der Mathematik.

Einige Programme können nachweislich korrekt sein. Es ist nicht einfach, aber es kann getan werden. Das ist das Ziel des formalen Theorembeweises (ein Teil der formalen Methoden). Die Unvollständigkeitssätze von Gödel treffen hier zu: Nicht alle Programme sind nachweislich korrekt. Das bedeutet nicht, dass es völlig sinnlos ist, formale Methoden anzuwenden, da einige Programme tatsächlich formal als korrekt nachgewiesen werden können.

Hinweis: Formale Methoden schließen die Möglichkeit aus, dass ein kosmischer Strahl auf den Prozessor trifft und launch_missiles()stattdessen ausgeführt wird a+b. Sie analysieren Programme im Kontext einer abstrakten Maschine und nicht realen Maschinen, die einzelnen Ereignissen wie Robert Harveys kosmischer Strahlung ausgesetzt sind.

Hier gibt es viele gute Antworten, aber sie scheinen alle um den kritischen Punkt herumzugehen, nämlich: Alle diese Theoreme haben eine ähnliche Struktur und sagen ähnliche Dinge, und was sie sagen, ist nicht, dass es unmöglich ist, wahrscheinlich richtig zu schreiben Programme“(aus einem bestimmten Wert von‚richtig‘und‚Programm‘ , das im Fall zu Fall variiert), aber was sie tun sagen‚es unmöglich ist , jemanden zu schreiben ein falsches Programm zu verhindern , dass wir falsch‘sein nicht beweisen kann ( etc).

Betrachtet man das konkrete Beispiel für das Problem des Anhaltens, wird der Unterschied deutlicher: Es gibt offensichtlich Programme, die nachweislich anhalten, und andere Programme, die nachweislich niemals anhalten. Dass es eine dritte Klasse von Programmen gibt, deren Verhalten in keiner Weise bestimmt werden kann, ist kein Problem, wenn wir nur ein nachweislich haltendes Programm schreiben möchten, da wir einfach vermeiden können, ein Programm zu schreiben, das zu dieser Klasse gehört.

Gleiches gilt für den Satz von Rice. Ja, für jede nicht triviale Eigenschaft eines Programms können wir ein Programm schreiben, das diese Eigenschaft weder als wahr noch als falsch erweisen kann. Wir können auch vermeiden, ein solches Programm zu schreiben, weil wir feststellen können, ob ein Programm nachweisbar ist.

Meine Antwort wird aus der Perspektive des realen Geschäfts und der Herausforderungen sein, denen sich jedes Entwicklungsteam gegenübersieht. Was ich in dieser Frage und in vielen Antworten sehe, ist wirklich die Kontrolle von Fehlern.

Code kann fehlerfrei sein. Nehmen Sie eines der "Hello World" -Codebeispiele für eine beliebige Programmiersprache und führen Sie es auf der Plattform aus, die dafür vorgesehen ist, und es wird konsistent funktionieren und die gewünschten Ergebnisse liefern. Es endet jede Theorie über die Unmöglichkeit, dass Code fehlerfrei ist.

Die potenziellen Fehler treten auf, wenn die Logik komplexer wird. Das einfache Hello World-Beispiel hat keine Logik und führt jedes Mal dieselbe statische Operation aus. Sobald Sie logikgesteuertes dynamisches Verhalten hinzufügen, führt dies zu der Komplexität, die zu den Fehlern führt. Die Logik selbst kann fehlerhaft sein, oder die Daten, die in die Logik eingegeben werden, können auf eine Weise variieren, die die Logik nicht handhabt.

Eine moderne Anwendung hängt auch von Laufzeitbibliotheken, CLR-, Middleware-, Datenbank- usw. Schichten ab, die zwar insgesamt Entwicklungszeit sparen, aber auch Fehler in diesen Schichten enthalten können, die durch Entwicklungs- und UAT-Tests und in der Produktion unentdeckt bleiben.

Schließlich ist die Kette von Apps / Systemen, die die Anwendung mit Daten versorgt, die ihre Logik speisen, eine Quelle für potenzielle Fehler, entweder innerhalb ihrer Logik oder innerhalb der Software, auf denen die Logik aufbaut, oder in den vorgelagerten Systemen, auf denen sie Daten verbraucht.

Entwickler haben nicht 100% Kontrolle über jedes bewegliche Teil, was die Logik ihrer Anwendung unterstützt. Tatsächlich haben wir nicht viel unter Kontrolle. Aus diesem Grund sind Unit-Tests wichtig, und Konfigurations- und Änderungsmanagement sind wichtige Prozesse, die wir nicht ignorieren dürfen und die nicht träge sind.

Dokumentierte Vereinbarungen zwischen Ihrer Anwendung, in denen Daten aus einer Quelle verwendet werden, die sich Ihrer Kontrolle entziehen, in denen das spezifische Format und die Spezifikationen für die übertragenen Daten festgelegt sind, sowie alle Beschränkungen oder Einschränkungen, von denen Ihr System annimmt, dass das Quellsystem für die Sicherstellung der Ausgabe verantwortlich ist diese Grenzen.

In der realen Welt der Softwareentwicklung werden Sie nicht in der Lage sein, sie zum Fliegen zu bringen, indem Sie dem Unternehmen erklären, warum Anwendungen theoretisch nicht fehlerfrei sein können. Diskussionen dieser Art zwischen Technologie und Unternehmen werden nur nach einer technologischen Störung stattfinden, die die Fähigkeit des Unternehmens, Geld zu verdienen, Geld zu verlieren und / oder Menschen am Leben zu erhalten, beeinträchtigt. Die Antwort auf "Wie kann das passieren?" Lautet nicht "Lassen Sie mich diese Theorie erklären, damit Sie sie verstehen."

In Bezug auf massive Berechnungen, die theoretisch ewig dauern könnten, um die Berechnung durchzuführen und ein Ergebnis zu erhalten, ist eine Anwendung, die nicht beendet werden kann und mit einem Ergebnis zurückkehrt, ein Fehler. Wenn die Art der Berechnung sehr zeitaufwendig und rechenintensiv ist, nehmen Sie diese Anforderung an und geben dem Benutzer eine Rückmeldung, wie / wann er das Ergebnis abrufen kann, und starten Sie die parallelen Threads, um daran zu arbeiten. Wenn dies schneller erfolgen muss als auf einem Server und wenn das Geschäft wichtig genug ist, können Sie es auf so viele Systeme skalieren, wie erforderlich. Aus diesem Grund ist die Cloud sehr attraktiv und bietet die Möglichkeit, Knoten hochzufahren, um die Arbeit aufzunehmen und sie anschließend herunterzufahren.

Wenn die Möglichkeit besteht, eine Anforderung zu erhalten, die nicht vollständig ausgeführt werden kann, sollte sie nicht unbegrenzt mit einem Geschäftsprozess abhängen, der auf die Antwort auf das wartet, was das Unternehmen für ein endliches Problem hält.

Ich glaube nicht, dass Code jemals zu 100% fehlerfrei ist, da Code nie wirklich fertig ist. Sie können immer verbessern, was Sie schreiben.

Programmieren ist ein Gebiet der Wissenschaft und der Mathematik. In diesem Fall sind beide endlos. Das Tolle daran, Entwickler zu sein, ist, dass unsere Arbeit endlos ist.

Es gibt mehr als tausend Möglichkeiten, eine einzelne Codezeile zu schreiben. Die Idee ist, die optimierte Version dieser Codezeile zu schreiben, die jedoch möglicherweise nicht fehlerfrei ist. Fehlerfrei bezieht sich auf die Idee, dass Ihr Code unzerbrechlich ist und der gesamte Code in gewissem Maße oder auf irgendeine Weise beschädigt werden kann.

Kann Code also effizient sein? Ja.
Kann Code endlos optimiert werden? Ja.
Kann Code fehlerfrei sein? Nein, du hast einfach noch keinen Weg gefunden, es zu brechen.
Davon abgesehen wird Ihr Code schwer zu knacken sein, wenn Sie sich und Ihre Code-Schreibpraktiken verbessern möchten.