> 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 re

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