[Theory] Halting problem

Stewart Gordon smjg_1998 at yahoo.com
Tue Oct 12 15:29:12 PDT 2010


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.


More information about the Digitalmars-d mailing list