Same Output Problem

computation

Definition

Same Output Problem

The same output problem is a decision problem that asks whether two programs have the same behaviour on the same input.

Instance: programs ${\Pi }_1$, ${\Pi }_2$ and input string $I$
Question: Do ${\Pi }_1$ and ${\Pi }_2$ have the same behaviour on $I$?

This means that either both programs terminate on $I$ and produce the same output, or both programs do not terminate on $I$.

It is not semi-decidable and undecidable.

Properties

Non-Semi-Decidability

Non-Semi-Decidability of Same Output Problem

The same output problem is not semi-decidable.

Given an instance $(\Pi ,I)$ of the co-halting problem, construct an instance $({\Pi }_1,{\Pi }_2,I)$ of the same output problem, where ${\Pi }_1$ and ${\Pi }_2$ are defined as follows:

procedure Π1:
  Input: input string I
  while (true) do {}
 
procedure Π2:
  Input: input string I
  call Π(I)
  return I

$\Rightarrow$ Completeness If $\Pi$ does not halt on input $I$, then both ${\Pi }_1$ and ${\Pi }_2$ do not terminate on input $I$. Hence $({\Pi }_1,{\Pi }_2,I)$ is a positive instance of the same output problem.

$\Leftarrow$ Soundness If $({\Pi }_1,{\Pi }_2,I)$ is a positive instance of the same output problem, then ${\Pi }_2$ does not terminate on input $I$. By construction, ${\Pi }_2$ does not terminate only if $\Pi$ does not halt on input $I$. Hence $(\Pi ,I)$ is a positive instance of the co-halting problem.

Undecidability

Undecidability of Same Output Problem

The same output problem is undecidable.

Given an instance $(\Pi ,I)$ of the halting problem, construct an instance $({\Pi }_1,{\Pi }_2,I)$ of the same output problem, where ${\Pi }_1$ and ${\Pi }_2$ are defined as follows:

procedure Π1:
  Input: input string I
  return I
 
procedure Π2:
  Input: input string I
  call Π(I)
  return I

$\Rightarrow$ Completeness If $\Pi$ halts on input $I$, then both ${\Pi }_1$ and ${\Pi }_2$ terminate on input $I$ and output $I$. Hence $({\Pi }_1,{\Pi }_2,I)$ is a positive instance of the same output problem.

$\Leftarrow$ Soundness If $({\Pi }_1,{\Pi }_2,I)$ is a positive instance of the same output problem, then ${\Pi }_2$ terminates on input $I$. By construction, ${\Pi }_2$ can only terminate after $\Pi$ has halted on input $I$. Hence $(\Pi ,I)$ is a positive instance of the halting problem.