The Halting Problem

This is a submission for DEV Computer Science Challenge v24.06.12: One Byte Explainer.

Explainer

The halting problem asks whether there can be a machine that determines whether a program will halt or continue indefinitely. It cannot exist; if we add a negation to this machine and evaluate it on itself, it will always fail because of its contradiction.

Additional Context

Solved by Alan Turing. Explaining this concept is complicated, since it requires the use of several compound functions:

1. Extended Explanation:

   • "H" which can determine whether any program 𝑃 stops or continues given an input.
   • We use "H" to create a program "D" that takes as input the code of a program "P".
   • "D(P)" calls "H(P, P)", evaluating "P" with its own code as input.
   • If "H(P, P)" says "yes" (P stops at P), "D(P)" enters an infinite loop.
   • If "H(P, P)" says "no" (P does not stop at P), "D(P)" stops.

2. Paradox:

   • Passing "D" to itself as input: "D(D)":
     • If "H(D, D)" says that "D(D)" stops, "D(D)" enters an infinite loop (contradiction).
     • If "H(D, D)" says that "D(D)" does not stop, "D(D)" stops (another contradiction).