4 ms·
Finding any finite number of repeating digits does not prove that there's an infinite number to follow. You might find 1000 3s in a row, followed by not a 3.
by tlb 7y ago
Finding any finite number of repeating digits does not prove that there's an infinite number to follow. You might find 1000 3s in a row, followed by not a 3.
- jandrese 7y agoIf you know the entire state of your algorithm then it's possible to compare the state vs. it's state in a previous step to determine if you are in a repeating loop. If all of the parameters and internal are identical, then the algorithm can not produce a different result.
- xamuel 7y agoA 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.