[Theory] Halting problem

[Justin Johansson]

On 10/10/2010 8:07 PM, Norbert Nemec wrote:
> "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.
>

That's a fair observation.

Cheers
Justin Johansson