4 ms·
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;}"
by xamuel 7y ago
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;}"
- jandrese 7y agoA 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.