Given a program and an input, determine whether that program, given that input, will ever halt, or if it will loop infinitely.
One of the fundamentals of academic computer science is learning that it is mathematically impossible to solve the halting problem - which is why the grandparent comment simply notes "the halting problem" with no further explanation; it's a famous problem. (Don't feel bad, everyone has to learn something the first time!)
The poem linked elsewhere in this comment tree is a simple and pithy description of the mathematical proof.
For (many) more details, Wikipedia has plenty of information.
Thanks for the explanation! No shame here (I didn't study CS in undergrad) but I find it intuitive that a program can't detect an input that would loop indefinitely.
If that's intuitive for you already (great!) consider one step further: Rice's Theorem. Rice's Theorem in layman's term is "all nontrivial properties of a program are undecidable in the general case". "Undecidable" is the difficulty class of the halting problem (there are actually harder problems!).
A couple accessible examples:
1. Constant Propagation - we know that we'll never detect all compile-time constants because of Rice.
2. Exception frequency - I can write a function that has "raise new FooException()" in the code, but the function never raises, and you won't be able to prove it never raises.
Well, you won't always be able to prove that it never raises. In many cases, you can, which is why compilers can eliminate dead code. Sometimes the compiler can prove the code is dead, sometimes it can prove the code is live, and sometimes it just doesn't know. For any prover, there will be code that defeats it.
Given a program and an input, determine whether that program, given that input, will ever halt, or if it will loop infinitely.
One of the fundamentals of academic computer science is learning that it is mathematically impossible to solve the halting problem - which is why the grandparent comment simply notes "the halting problem" with no further explanation; it's a famous problem. (Don't feel bad, everyone has to learn something the first time!)
The poem linked elsewhere in this comment tree is a simple and pithy description of the mathematical proof.
For (many) more details, Wikipedia has plenty of information.