Orchid XP v7 <voi### [at] devnull> wrote:
> The HP does *not* say that it's impossible to tell whether a program 
> halts. It is quite possible to tell that certain programs do in fact 
> halt. And it is also quite possible to tell that others are never going 
> to halt. The HP says that it is impossible to tell FOR EVERY POSSIBLE 
> PROGRAM. Big difference.

  All complexity class definitions talk about the generic case, not if
there exists at least one case for which the complexity bound does not hold.

  For example, sorting elements using only comparisons between pairs of
elements cannot be done faster than in n*log n steps.
  Of course that means that it's not possible to create an algorithm
which sorts, using comparison only, all possible inputs faster than that.
It doesn't mean there doesn't exist any input which could not be sorted
faster than that using comparisons (an already sorted input is the simplest
case, which can be "sorted" with a linear amount of steps).

  The halting problem belongs to the worst possible complexity class: The
one of unsolvable problems. Of course that doesn't mean there exist no
inputs for which it is solvable. It means that there exist inputs for
which it's not.

-- 
                                                          - Warp

Post a reply to this message