[Theory] Halting problem

[Norbert Nemec]

"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?
>
>
>
>
>