[Theory] Halting problem
%u
e at ee.com
Sat Oct 9 10:58:59 PDT 2010
Just to be clear about this, the halting problem is only unsolvable for Turing
machines.
That is, a machine with a tape that extends or is indefinitely extensible to
the right.[wikipedia:Turing machine]
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.
Simple in theory that is :)
More information about the Digitalmars-d
mailing list