[Theory] Halting problem

%u e at ee.com
Sat Oct 9 12:59:54 PDT 2010


== Quote from Simen kjaeraas (simen.kjaras at gmail.com)'s article
> %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]
>
> Of course. However, for non-trivial programs it is hard enough that we
> may consider it impossible.

This may be, but too often I see the theoretical(truly impossible) problem
mentioned when the practical Halting problem is applicable.
Especially people asking about the Halting problem should not be thrown off by
saying that the theoretical Halting problem is why a problem can't be implemented.
Why, for instance, doesn't Stewart Gordon's proof not apply for finite memory
programs?







More information about the Digitalmars-d mailing list