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.
I still think most CS courses teach the Halting Problem in just about the worst way possible.
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.
>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."
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.
You only need to blacklist the possibility that the program under review has access to the output of the Halting Detection program for itself.
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.
Oh I see what you're getting at. I think what you're trying to get at is, "If you had a halting-solver, you could use that like an oracle to answer arbitrary mathematical questions." Unfortunately, this isn't true, you couldn't use it to answer arbitrary mathematical questions, just certain questions.
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.]
Finding any finite number of repeating digits does not prove that there's an infinite number to follow. You might find 1000 3s in a row, followed by not a 3.
If you know the entire state of your algorithm then it's possible to compare the state vs. it's state in a previous step to determine if you are in a repeating loop. If all of the parameters and internal are identical, then the algorithm can not produce a different result.
A machine can print the same thing over and over, and yet never repeat its own internal state. For example, "let x=0; while(true) { print("0"); x=x+1;}"
A halting problem solver would necessarily have to be smart enough to detect state that is relevant to the completion of the program vs. not. Plus, even in this case on a real world machine x can only store as much state at the underlying type. So if it's a 32 bit int then you can absolutely prove the algorithm does not halt after only 4 billion iterations, but even before that you can simply note the lack of exit conditions from the loop to show that it never terminates.
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.
This isn't exactly what you're talking about, but I found this blog post to be an interesting exploration of some related ideas: https://eklitzke.org/the-halting-problem
That is exactly what I'm talking about. The Halting Problem has to be able to solve every problem in mathematics (and by extension everything else in the world) even ones that we don't know the solutions to. Even ones that we have not yet discovered.
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.
> 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.
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.
