A vivid example that the halting problem is hard... :)
Is there some n for which the following algorithm does not halt?
int n;Of course, this is the famous 3n+1 problem, or the Collatz problem. It dates back to 1937, and many people are betting that it's "the next Fermat", if it is lucky enough to stay unsolved for a few more centuries. Erdős said "Mathematics is not yet ready for such problems."
while(n > 1)
n = (n % 2) ? 3*n+1 : n/2;
Like many people I know, I too spent some time in high school trying to tackle it. Other people, who presumably spent quite a bit of time on the problem after high school, showed various interesting things. For example, if a cycle exists, it has size at least 275000 [Lagarias 85].
While this may look like a CS problem, I suggest we do not claim it, and let the mathematicians worry about it for a while.