3 ms·

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. B

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").