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: 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 zu entscheiden, ob sie äquivalent sind. Dies folgt aus dem Satz von Rice.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.