There is no algorithm that decides, for every pair (program, input), whether the program halts on that input.
Undecidability of the halting problem
Related concepts
- Natural numbers (ℕ)
- Undiscovered limitative results
- Gödel's first incompleteness theorem
- Church-Turing thesis
- Undiscovered limitative results
- Ω (Chaitin's constant)
- Rice's theorem
- Diophantine equation
- Kolmogorov complexity
- Busy beaver function
- Hilbert's 10th problem (Matiyasevich)
- Arithmetical hierarchy
- Undecidability of the spectral gap in 2D quantum lattice models (Computational Physics)