| What you are missing is: 1) Analyzing a function's behavior sometimes (frequently) takes as long as running the function itself, 2) some functions can run forever, and 3) sometimes we can't tell the functions that run forever from those that run a very long time. Example: Write a simple function F to generate prime numbers. (Search the internet for examples if you've never tried it. It can be done in a few lines with two loops.) Your prime-number-generating function F will never halt, because it will never run out of integers to check -- i.e. because there are infinite integers to be tested for being prime. So the halting problem is solvable for F, it is known that F will never halt. Now slightly modify function F to notice whenever it has generated two primes in a row that are only two away from each other, such as 11 and 13. Increment a counter C whenever these Twin Primes are detected. This is as simple as storing the previous prime P1, subtracting it from the newly-generated prime P2, and seeing if P2-P1 is equal to 2. Finally, make one last tiny change to your function: accept a parameter X, and halt when the counter C becomes greater than X. At this point the function F is probably less than ten lines long and not very complicated at all. I get to pick X for you. Can you write an analyzer function A to decide if function F(X) halts or not? The answer is: No, you can't. To write function A you would have to prove or disprove the Twin Prime Conjecture, which mathematicians have been trying to do and failing at for centuries. http://en.wikipedia.org/wiki/Twin_prime_conjecture Lets imagine that the Twin Prime Conjecture is wrong and there are a finite number of Twin Primes, N. We've been searching for N for so long that I'm confident than N is very, very large, whatever it is. Meaning I can pick an X that is less than N, but still so large that function F(X) will take longer than our lifetime to generate that many Twin Primes and halt. Alternately, lets imagine that the Twin Prime Conjecture is correct and there are infinitely many Twin Primes. Again, I can pick an X so large that it will take longer than our lifetime for F(X) to halt. Either way, we would both be dead before knowing the results of the test, and maybe the test will never complete, who can say? Worse, any analyzer function A you could write would have to know N to decide if F(X) will halt or not. But N is not known and has not yet been discovered after hundreds of years of trying. So function A would either have to disprove the Twin Primes Conjecture (unlikely with anything less than artificial intelligence) or it would have to calculate C by generating all the primes that F(X) would generate, meaning that A is equivalent to F, meaning that A is no faster than F. Therefore, neither you nor any currently-conceivable function A can decide if function F(X) will halt or if F(X) will continue searching forever. That's the halting problem and it's unsolvable for this F(X). |