[Theory] Halting problem

%u e at ee.com
Sun Oct 10 08:06:26 PDT 2010


I am not sure where exactly the line lies where people tend to use impossible as a
synonym for a hard problem, but I agree that np might well be around that border.
It depends on "trivial", but I wouldn't call integer factorization impossible.

The point I was trying to make was that using "impossible" to denote the practical
halting problem is very confusing as the theoretical Halting problem is truly
impossible.
Confusing, as the proof at first sight seems to hold on memory limited systems as
well.

== Quote from Norbert Nemec (Norbert at Nemec-online.de)'s article
> "Impossible to solve" is often used synonymous to "exponentially hard to
> solve" meaning, as the problem size (e.g. size of finite memory) grows
> as N, the cost for solution grows as exp(N). Of course, the actual cost
> of an actual problem always depends on the pre-factor, but experience
> shows that exponentially hard problems are typically only solvable for
> trivially small problems.
> On 09/10/10 21:59, %u wrote:
> > == 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