[Theory] Halting problem

[%u]

== Quote from Norbert Nemec (Norbert at Nemec-online.de)'s article
> 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 memory or not.
This is correct.

> 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.
I don't know people in language design, but I suspect they know their stuff and I
would be surprised to hear that they would think of the theoretical Halting
problem where the practical halting problem as an argument would suffice. Programs
generally can't index an infinite amount of memory.
Why would they use an argument which rests on an abstract system where they could
just as easily use an argument based on an actual system.

Anyway, I made this thread because in uni I got the Halting problem explained in
totally the wrong context and would like other people not to make the same wrong
first step.