Program equivalence

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

Program equivalency means that two computer programs (or two algorithms ) calculate the same function . This means that both programs always deliver the same output for the same input or that they accept the same language :

as a function: P ₁ (E) = A if and only if P ₂ (E) = A

as language: E ∈ L (P ₁ ) if and only if E ∈ L (P ₂ ) i.e. L (P ₁ ) = L (P ₂ )

The equivalence of two programs is of central importance in theoretical computer science , especially for formal semantics , complexity theory, and computability theory . However, it is generally not possible to decide for any two programs whether they are equivalent. This follows from Rice's theorem .