Correctness Problem

computation

Definition

Correctness Problem

The correctness problem is a decision problem that asks, for a given program $\Pi$ and two strings $I,O$, whether $\Pi$ halts on input $I$ and outputs output $O$.

It is undecidable and semi-decidable.

Undecidable

The correctness problem is undecidable given that the problem statement implicitly asks whether $\Pi$ halts on input $I$ (implicit Halting Problem).