The problem is that even real live humans can't always tell if something will halt. For instance, you tell me if this loop ends:

    n = 4;
    goldbach = true;
    while(goldbach) {
        goldbach = isSumOfTwoPrimes(n);
        n += 2;

You just have to prove the Goldbach Conjecture. :-)