Programmäquivalenz

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 31. August 2022 um 10:12 Uhr durch imported>WholesaleFreedom(4011177).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Programmäquivalenz besagt, dass zwei Computerprogramme (oder zwei Algorithmen) dieselbe Funktion berechnen. Das bedeutet, dass beide Programme für dieselbe Eingabe auch immer dieselbe Ausgabe liefern, bzw. dass sie dieselbe Sprache akzeptieren:

als Funktion: P1(E)=A genau dann, wenn P2(E)=A
als Sprache: E ∈ L(P1) genau dann, wenn E ∈ L(P2) also L(P1) = L(P2)

Die Äquivalenz zweier Programme ist von zentraler Bedeutung in der Theoretischen Informatik, insbesondere für die Formale Semantik, die Komplexitätstheorie und die Berechenbarkeitstheorie. Allerdings ist es im Allgemeinen nicht möglich, für zwei beliebige Programme in einer Turing-vollständigen Sprache zu entscheiden, ob sie äquivalent sind. Dies folgt aus dem Satz von Rice.