The halting problem

[VALIS]

Hi, I'm trying to understand the halting probelm; and I really don't. Maybe some computer geeks can explain this to me.

So we have a programme and an input, and the input feeds into the programme telling me whether the programme will halt or not. Then there is the famous contradiction paradox.
If Yes (the programme will halt) then it loops forever instead.
If No (the programme will not halt) it halts immediately.

But why is this, I don't understand, why the contradictions?

[Gaidin]

The halting problem isn't a paradox so much as a proof, at least the interesting part. Turing proved that given a general algorithm and general input, a mathematically well defined definition of a computer and program(Turing Machine), then a solution to the halting problem for all possible program-input pairs cannot exist.

There is a so-called paradox and what I'll call a definitive paradox to this.

The so called paradox comes in with the interpreters that can execute a program's code with given input and determine whether it will halt or not halt. The interpreters can demosntrate the program does halt if this is the case, as the simulation will stop. The *so-called* paradox is that an interpreter will not halt if the input program doesn't halt, so the approach cannot solve the halting problem, and can't successfully answer 'doesn't halt' for these programs.

Now, the *definitive* paradox is that the halting problem is defined for mathematically well defined computers, programs, and input. They are given infinite resources to run. When running these simulations on an actual computer, the computer may not be mathematically well defined(and thus able to finish a program that doesn't halt anyway under the right conditions), and it will certainly not have infinite resources. The operating system will eventually tell the interpreter to frak off and the program will halt, as such.

[VALIS]

The *so-called* paradox is that an interpreter will not halt if the input program doesn't halt

But why is this? If it tells you that it will halt....thats the end of the matter, it has told you it will halt, then it finishes it's task as well. Why does it get stuck in this endless loop? - Will halt (loops forver instead), Won't halt (halts). I don't get that. Why can't the little programme inform you what the other programme will do and then shut itself off...or something.

[Gaidin]

You have your loops backwards. If it'll halt the interpreter can tell you and it'll stop. Eventually. Depending on the program and input data. If it won't halt the interpreter won't stop, and you'll never get an answer. Hence the 'so-called' paradox, as it's not really one, but you never get the answer you need anyway as it'll keep running until it halts, never.

Bear in mind these are for mathematically well defined systems, which most processors aren't.

[VALIS]

Still don't get it. Can you expand your explanation out a little bit.
I'm sure I have read over and over (Ive spent far too long trying to even understand this halting problem), that if it(the interpreter?) tells you that it will halt - it won't halt. And if it tells you that it won't halt - it halts.
What's that about?

[Gaidin]

Simply put, when dealing with the mathematically well defined systems under optimal conditions(infinite time and resources) the interpreter will stop when it has an answer for you. If the program doesn't halt, the interpreter will never have an answer.