"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.kja...@gmail.com)'s article
%u<e...@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?
