Puzzles
Can any program tell you, in advance, if another program will ever finish running?
Imagine a checker program that takes any other program and its input, and reliably answers whether that program will eventually stop, or run forever in an infinite loop. Could such a universal checker ever be built, even in principle, given unlimited time and memory?
Reveal the answer
No, and Alan Turing proved it in 1936. He showed that if such a checker existed, you could build a program that feeds itself into the checker and does the opposite of whatever the checker predicts, halting if predicted to loop, and looping if predicted to halt, which contradicts the checker's answer either way. The result, the undecidability of the Halting Problem, set a hard limit on what computers can ever determine about other computers.