Programmäquivalenz

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: P₁(E)=A genau dann, wenn P₂(E)=A

als Sprache: E ∈ L(P₁) genau dann, wenn E ∈ L(P₂) also L(P₁) = L(P₂)

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.