On 10/10/10 17:06, %u wrote:
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.
I think, the essence here is the "limited memory" issue. A turing
machine has infinite memory available, but a program that finished in
finite time will always have used only a finite amount of memory. The
halting problem is to determine if a program written down as a finite
piece of code will finish in finite time and finite memory or not.
In language design, the theoretical halting problem actually is often an
argument because the compiler does not know the memory limitation at run
time. The finite memory of the machine can therefore not be used to
reason about a piece of code. For the purpose of the compiler, the
machine has to be assumed to have arbitrarily much (i.e. infinite) memory.
