[Theory] Halting problem

[%u]

== Quote from Stewart Gordon (smjg_1998 at 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