[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