3 ms·

The halting problem hegemony. I can tell if a program would exit eventually or not. At some point there must be a subset of all possible programs we can tell, c

by gxt 5y ago

The halting problem hegemony. I can tell if a program would exit eventually or not. At some point there must be a subset of all possible programs we can tell, can stop, and can tell would stop under x,y,z conditions. So the whole problem thing always felt like a strawman.

JohnDeHope 5y ago
I run into this problem a lot on my day job. A lot of things are easy for people to do. A person can look at one example and categorize it A or B. No problem. But trying to get a computer to do it, en masse, at scale, algorithmically, in a reasonable amount of time, can be impossible. Some things just require a fuzzy neural network, I guess. One thing about the halting problem too... the computer can't run the program to determine if it halts or not, it has to be able to tell through essentially static analysis, without running it. I'd say for a human looking at a program, if they did the classic "run the program in my head" which many of us learn to do, then you aren't really abiding by the halting problem's strictures. It may not be as easy to "tell" as you think!
- Tainnor 5y ago
  > the computer can't run the program to determine if it halts or not, it has to be able to tell through essentially static analysis, without running it. Not really, as a turing machine is fully able to simulate any other turing machine. The problem is not that the "termination checker" may not run the program it's checking (it is allowed to do that). The problem is that if that program runs forever then the "termination checker" program will also run forever and thus never return "yes" or "no". (You could say, well just output "no" if the program runs for longer than x days / weeks / months / years, but it's quite easy to write programs that run for a very long time but do eventually terminate. At best, you'll manage to write a checker that can output "yes" or "I don't know").
twistier 5y ago
Can you? Try proving the Collatz conjecture. It's a very simple program.
Tainnor 5y ago
Of course, such subsets exist. You can either define such subsets informally yourself, or you can find a total programming language (such as Coq), in which you may only write programs that provably terminate. Even without identifying specific subsets, it's quite possible to predict whether specific programs terminate. For example, it's trivial to write a program that loops forever. Some people misrepresent the halting problem and its corollaries as "we can under no circumstance predict any aspect of the behaviour of any program", which is in fact wrong. What is true is that, for every property we may want to assert about a program, there exists a program (on a Turing machine or in a Turing-complete language, so excluding any of the total programming languages) for which you will fail to tell if it has that property.

by gxt 5y ago

JohnDeHope 5y ago

I run into this problem a lot on my day job. A lot of things are easy for people to do. A person can look at one example and categorize it A or B. No problem. But trying to get a computer to do it, en masse, at scale, algorithmically, in a reasonable amount of time, can be impossible. Some things just require a fuzzy neural network, I guess. One thing about the halting problem too... the computer can't run the program to determine if it halts or not, it has to be able to tell through essentially static analysis, without running it. I'd say for a human looking at a program, if they did the classic "run the program in my head" which many of us learn to do, then you aren't really abiding by the halting problem's strictures. It may not be as easy to "tell" as you think!

Tainnor 5y ago
> the computer can't run the program to determine if it halts or not, it has to be able to tell through essentially static analysis, without running it. Not really, as a turing machine is fully able to simulate any other turing machine. The problem is not that the "termination checker" may not run the program it's checking (it is allowed to do that). The problem is that if that program runs forever then the "termination checker" program will also run forever and thus never return "yes" or "no". (You could say, well just output "no" if the program runs for longer than x days / weeks / months / years, but it's quite easy to write programs that run for a very long time but do eventually terminate. At best, you'll manage to write a checker that can output "yes" or "I don't know").

twistier 5y ago

Can you? Try proving the Collatz conjecture. It's a very simple program.

Tainnor 5y ago

Of course, such subsets exist. You can either define such subsets informally yourself, or you can find a total programming language (such as Coq), in which you may only write programs that provably terminate. Even without identifying specific subsets, it's quite possible to predict whether specific programs terminate. For example, it's trivial to write a program that loops forever. Some people misrepresent the halting problem and its corollaries as "we can under no circumstance predict any aspect of the behaviour of any program", which is in fact wrong. What is true is that, for every property we may want to assert about a program, there exists a program (on a Turing machine or in a Turing-complete language, so excluding any of the total programming languages) for which you will fail to tell if it has that property.