On 09/10/2010 18:58, %u wrote: <snip>
In the more general limited-memory setup it is actually quite simple to solve the Halting problem: 1. Save every state of the system. 2. If the program ends, the program Halts -> done. 2. For every state, check to if it has been saved before. If so, the program loops -> done. 3. Wait until all states are saved, the program Halts -> done.
I get it now under the assumption that these aren't step-by-step instructions. But can this algorithm run within this limited-memory setup? I think not - by my calculation, to do it for a setup with n bits of memory, the halt analyser would need 2^n bits.
Stewart.
