Halting Problem

The halting problem is a problem that asks, for an arbitrary computer program and input, is it possible to determine if the program will run forever or halt. It was proved that the halting problem is undecidable, meaning that it is impossible to create an algorithm that will determine if an arbitrary program will halt.

Proof of undecidability

The halting problem’s undecidability was proved via contradiction. Assume that a program $H(P,I)$ exists, where $H$ is a program that always gives the solution to the halting problem, $P$ is the program to decide the halting program for, and $I$ is the input to $P$. Create a second program $C(X)$, where $X$ is the input program. $C(X)$ does the opposite of $H(X,X)$, i.e. if $H(X,X)$ says $X$ will halt on input $X$, then $C(X)$ will not halt.

$C(C)$ will then either not halt if $H(C,C)$ says it will halt, or halt if $H(C,C)$ says it will not halt. In either case, $H(C,C)$ is incorrect, which contradicts the initial assumption that $H$ is always correct. Therefore, there is no program $H$ that determines the solution to the halting problem for a arbitrary program and input. In this model, any input is allowed, which is why programs can be passed as input.