Wann können wir sagen, dass zwei Programme unterschiedlich sind?

Q1. Wann können wir sagen, dass zwei Programme (geschrieben in einer Programmiersprache wie C ++) unterschiedlich sind?

Das erste Extrem ist zu sagen, dass zwei Programme äquivalent sind, wenn sie identisch sind. Das andere Extrem ist, dass zwei Programme gleichwertig sind, wenn sie dieselbe Funktion berechnen (oder dasselbe beobachtbare Verhalten in ähnlichen Umgebungen zeigen). Aber das ist nicht gut: Nicht alle Programme, die die Primalität prüfen, sind gleich. Wir können eine Codezeile hinzufügen, die sich nicht auf das Ergebnis auswirkt, und betrachten sie trotzdem als dasselbe Programm.

Q2. Sind Programme und Algorithmen die gleichen Objekte? Wenn nicht, wie ist ein Algorithmus definiert und wie unterscheidet er sich von der Definition eines Programms? Wann können wir sagen, dass zwei Algorithmen gleichwertig sind?

Frage 1: Es gibt viele Begriffe von Programmäquivalenz (Traceäquivalenz, Kontextäquivalenz, Beobachtungsäquivalenz, Bisimilarität), die Dinge wie Zeit, Ressourcenverbrauch, Nichtdeterminismus und Terminierung berücksichtigen können oder auch nicht. Es wurde viel Arbeit geleistet, um brauchbare Vorstellungen von Programmäquivalenz zu finden. Zum Beispiel: Operational Based Theories of Program Equivalence von Andy Pitts . Dies kratzt aber kaum an der Oberfläche. Dies sollte nützlich sein, auch wenn Sie daran interessiert sind, wenn zwei Programme nicht gleichwertig sind. Man kann sogar über Programme ohne Unterbrechung nachdenken (mit Bisimulation und Coinduktion).

F2: Eine mögliche Antwort auf einen Teil dieser Frage ist, dass interaktive Programme keine Algorithmen sind (vorausgesetzt, man geht davon aus, dass ein Algorithmus alle Eingaben auf einmal übernimmt, aber diese enge Definition schließt Online-Algorithmen aus). Ein Programm kann eine Sammlung interagierender Prozesse sein, die auch mit ihrer Umgebung interagieren. Dies stimmt sicherlich nicht mit dem Algorithmus der Turing-Maschine / Rekursionstheorie überein.

Das andere Extrem ist, dass zwei Programme gleichwertig sind, wenn sie dieselbe Funktion berechnen (oder dasselbe beobachtbare Verhalten in ähnlichen Umgebungen zeigen). Aber das ist nicht gut: Nicht alle Programme, die die Primalität prüfen, sind gleich. Wir können eine Codezeile hinzufügen, die sich nicht auf das Ergebnis auswirkt, und betrachten sie dennoch als dasselbe Programm.

Dies ist kein Extrem: Die Programmäquivalenz muss in Bezug auf einen Beobachtungsbegriff definiert werden.

Die gebräuchlichste Definition in der PL-Forschung ist die kontextbezogene Äquivalenz. In der kontextuellen Äquivalenz besteht die Idee darin, dass wir Programme beobachten, indem wir sie als Komponenten größerer Programme (den Kontext) verwenden. Wenn also zwei Programme für alle Kontexte den gleichen Endwert berechnen, werden sie als gleich bewertet. Da diese Definition über alle möglichen Programmkontexte quantifiziert, ist es schwierig, direkt damit zu arbeiten. Ein typisches Forschungsprogramm in PL ist es daher, kompositorische Argumentationsprinzipien zu finden, die eine kontextuelle Äquivalenz implizieren.

Dies ist jedoch nicht der einzig mögliche Begriff der Beobachtung. Zum Beispiel können wir leicht sagen, dass das Speicher-, Zeit- oder Leistungsverhalten eines Programms beobachtbar ist. In diesem Fall gelten weniger Programmäquivalenzen, da mehr Programme unterschieden werden können (z. B. Mergesort kann jetzt von Quicksort unterschieden werden). Wenn Sie Sprachen entwickeln möchten, die immun gegen Timing-Channel-Angriffe sind, oder wenn Sie raumbegrenzte Programmiersprachen entwickeln möchten, müssen Sie dies tun.

Wir können auch beschließen, einige der Zwischenzustände einer Berechnung als beobachtbar zu beurteilen. Dies geschieht aufgrund der Möglichkeit von Interferenzen immer für gleichzeitige Sprachen. Sie können diese Ansicht aber auch für sequentielle Sprachen verwenden. Wenn Sie beispielsweise sicherstellen möchten, dass keine Berechnungen unverschlüsselte Daten im Hauptspeicher speichern, müssen Sie das Schreiben in den Hauptspeicher als beobachtbar betrachten.

Grundsätzlich gibt es keinen einheitlichen Begriff der Programmäquivalenz. es ist immer relativ zu dem Begriff der Beobachtung, den Sie auswählen, und das hängt von der Anwendung ab, die Sie im Auge haben.

F2: Ich denke, die üblichen theoretischen Definitionen unterscheiden nicht wirklich zwischen Algorithmen und Programmen, aber "Algorithmus", wie er üblicherweise verwendet wird, ähnelt eher einer Klasse von Programmen. Für mich ist ein Algorithmus wie ein Programm, bei dem einige Unterprogramme nicht vollständig spezifiziert sind (dh ihr gewünschtes Verhalten ist definiert, aber nicht ihre Implementierung). Beispielsweise spezifiziert der Gaußsche Eliminierungsalgorithmus nicht wirklich, wie eine Ganzzahlmultiplikation durchgeführt werden soll.

Es tut mir leid, wenn das naiv ist. Ich mache keine PL-Forschung.