{{Belege fehlen}}

'''Programmäquivalenz''' besagt, dass zwei [[Computerprogramm]]e (oder zwei [[Algorithmus|Algorithmen]]) dieselbe [[Funktion (Mathematik)|Funktion]] berechnen. Das bedeutet, dass beide Programme für dieselbe Eingabe auch immer dieselbe Ausgabe liefern, bzw. dass sie dieselbe [[Formale Sprache|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 [[Gleichwertigkeit|Äquivalenz]] zweier Programme ist von zentraler Bedeutung in der [[Theoretische Informatik|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ändigkeit|Turing-vollständigen]] Sprache zu entscheiden, ob sie äquivalent sind. Dies folgt aus dem [[Satz von Rice]].

{{SORTIERUNG:Programmaquivalenz}}

[[Kategorie:Berechenbarkeitstheorie]]