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 ([email protected])'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 ([email protected])'s article > >> %u<[email protected]> 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? > > > > > > > > > >
