%u <[email protected]> wrote:
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 :)
Of course. However, for non-trivial programs it is hard enough that we
may consider it impossible.
--
Simen
