[Theory] Halting problem

[Simen kjaeraas]

%u <e at ee.com> 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