How to prove such program is uncomputable

Question

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, and tests whether the two programs are equivalent.

Answer 1

If such a program $P$ exists, then define a new program $Q$ which takes as input a piece of code $C$ and:

1. builds the program $C; D$ (sequential execution of $C$ and $D$) where $D$ erases the output;
2. uses $P$ to compare $C; D$ with the program that does nothing and produces no output.

$Q$ returns true if $C$ terminates and false otherwise. Thus having $P$ allows us to solve the halting problem, which shows that $P$ does not exist.

---

Even if you restrict the input to terminating programs, equivalence is undecidable. Let $\mathscr{D}$ be the set of programs such that for all programs $M$, $C;M$ terminates iff $D;M$ terminates. Then $C \in \mathscr{D}$, and there is a program $\bar C$ such that $\bar C \notin \mathscr{D}$ (take the program which adds a symbol at the end of $C$'s output on an empty input, and $M$ that terminates iff the length of its input is at most the length of $C(\epsilon)$). By Rice's theorem, since $\mathscr{D}$ is nontrivial, there is no way to decide whether a program $D$ belongs to $\mathscr{D}$. In other words, equivalence to a given terminating program is not decidable.