== Quote from Stewart Gordon (smjg_1...@yahoo.com)'s article > 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. Sorry :(
> 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. Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n that is). But those two system could of course be on the same computer. My computer, for instance, can run Halt.exe on 30bit programs :D
