[Theory] Halting problem

[Norbert Nemec]

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.