Oh my! this reminds me of a class I took in my masters. Had to learn "Halting Problem". Godel's work in just astonishing and way beyond my caliber. I managed to pass the class but memories are still with me.
They always give you that one highly contrived counterexample where you're feeding the algorithm with the output from itself which doesn't even begin to touch on what the Halting Problem actually is or why it is so important. And if the student asks "well, what if we redefine it so it only works on OTHER algorithms to avoid this one weird edge case" the answer is basically "that's not covered."
But really, the Halting Problem is asking the question if we can solve all of mathematics, and indeed all of philosophy with a fancy enough computer program. Can we build a machine God? And the standard textbook answer is roughly "If we built a machine God it could create a burrito so big that even it could not eat it, therefore machine God can not exist."
IMHO, it would make more sense to get students down the right path to ask them what the halting computer would do when fed a program that calculates all of the digits of Pi. Or one that halts when it computes the answer to life, the universe, and everything. The halting problem may have been mathematically disproven by finding one highly convoluted counter example, but it's more significant failing is that it is infinite and thus can not be implemented on a machine with finite limits.
Only if the teacher doesn't know what they're talking about. If they know what they're talking about, the answer is "Since every function can be implemented by infinitely many different algorithms, in order to blacklist our halting-solver from the list of things we can input into our halting-solver, we would need to blacklist ALL the algorithms that implement it, but in order to do that, we'd need an algorithm for determining whether or not a given algorithm is a halting-solver, and it can be shown that that itself is just as impossible as solving the halting problem."
>digits of Pi
You seem to be deeply mistakenly about something, but it's hard to point out exactly what you're mistaken about because all the terms are so poorly defined. If, for example, you meant, "What the halting computer would do when fed a program P that takes an input n and outputs the nth digit of Pi, if we asked whether or not P halts on a particular input n", then the answer would be "Yes". If you meant "What the halting computer would do when fed a program Q that takes no input and runs forever, listing all the digits of Pi, when asked whether or not Q halts on no input", then the answer would be "No". Either way, there's absolutely nothing deep or profound about the digits of Pi here.
>life, the universe, and everything
Please, don't make things even more complicated for the poor students.
The Digits of Pi example is to illustrate that the Halting Program needs to understand the high level math necessary to prove that Pi is infinite. And then you lead them on to discovering that it needs to be able to solve every problem in mathematics, even ones that have not yet been discovered, and then you realize that it has to be omnipotent and infinite.
The purpose is to pull students away from the kind of empirical solutions that immediately pop into your head when presented with the halting problem. "Well, if we look at the loops and what the exit conditions are and start iterating over all possible inputs..." which is not at all what the Halting Problem is about, despite what it looks like on the surface.
For example, even if Pi happens to be rational, and the algorithm to list its digits eventually starts listing a periodic repetition (possibly the all-0 repetition even), that still doesn't mean it halts. So the halting-solver doesn't directly help you determine whether or not Pi is rational. You would instead need a "determine-if-given-function-eventually-has-periodic-output" solver, which is stronger than a halting solver.
I'm not sure if there are any really slam-dunk examples of what you seem to be looking for, that don't involve proofs in some guise or other. An example which does involve proofs might look like this: "Let x be a program which attempts, by brute force, to find a proof that P<>NP, and immediately halts when it finds such a proof, if ever. If you had a halting detector, you could plug x into it and based on its output, you would know whether or not there is a proof of P<>NP." [Which is subtly different than whether or not P<>NP is true. That would require something stronger than a halting solver to obtain.]
However clever you are, the halting problem program has to be even more clever by definition. But we don't have an upper bound on cleverness, so the halting problem program has to be infinitely clever, hence my previous point about it being able to solve all of mathematics.
The formal counterexample is completely correct, but absolutely useless in enlightening students as to what the halting problem is actually asking. If anything it drives them further down the wrong line of thinking.
I agree that would be a better way to teach it, but Turing machines have infinitely-long tapes -- the really unexpected result is that you couldn't solve the Halting Problem even if you had (countably) infinite tape and infinite time to do it. The same probably holds for uncountably-infinite tapes too (the "burrito" counterexample still breaks it), though you can't really address a tape that long for obvious reasons.