7 ms·

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

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.

jandrese 7y ago
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.
- cyphar 7y ago
  > 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.
- xamuel 7y ago
  >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.
  - jandrese 7y ago
    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.
    - 7y ago
- neilparikh 7y ago
  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 https://eklitzke.org/the-halting-problem
  - jandrese 7y ago
    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.

jandrese 7y ago

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.

cyphar 7y ago
> 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.
xamuel 7y ago
>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.
- jandrese 7y ago
  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.
  - 7y ago
neilparikh 7y ago
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 https://eklitzke.org/the-halting-problem
- jandrese 7y ago
  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.