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 , and input string
Question: Do and have the same behaviour on ?

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

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 of the co-halting problem, construct an instance of the same output problem, where and are defined as follows:

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

Completeness

If does not halt on input , then both and do not terminate on input . Hence is a positive instance of the same output problem.

Soundness

If is a positive instance of the same output problem, then does not terminate on input . By construction, does not terminate only if does not halt on input . Hence is a positive instance of the co-halting problem.

Undecidability

Undecidability of Same Output Problem

The same output problem is undecidable.

Given an instance of the halting problem, construct an instance of the same output problem, where and are defined as follows:

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

Completeness

If halts on input , then both and terminate on input and output . Hence is a positive instance of the same output problem.

Soundness

If is a positive instance of the same output problem, then terminates on input . By construction, can only terminate after has halted on input . Hence is a positive instance of the halting problem.