Science Forums 2

[Kriminal99]

Ok time to summarize this thread:

1) For the vast majority of programs that anyone is actually going to write (especially if they are not number theorists), the halting problem is decidable.

2) The so called proof of undecidability (by contradiction) makes use of a very convaluted setup that is not representitive of a program that anyone would actually write.

The halting proof diagnolization argument implies an algorithm that simulates an input machine on it's own encoding. This is the realization of "diagonolization". This algorithm takes one input, copies it, and then gives the original input code the copy as input. It must do so in order to ensure that the program runs only on itself. Call this machine G.

Because of the fact that the halting algorithm needs algorithm "code" and input to that code, it is necessary that the halting algorithm traces the input machine to some degree. It must be traced a certain amount in order for it to gain meaningful information. I claim that the amount required ensures it would trace it through the action of copying the input and running H in the case of Machine G.

So, G recieves (G) as input. (G) is the code of G. G copies the (G) and gives (G)(G) to the halting algorithm. The halting algorithm traces G on (G). And we are back where we started - an infinite loop.


This infinite trace loop that causes the halting machine to break down is completely unique to this kind of unrealistic setup. It would not even occur if a halting machine ran on itself without the copying preprocessor, because then the trace loop would stop when the input of what to trace ran out.

Because undecidability is technically defined such that it is something that is true or not true for ALL machines, theorists maintain that the proof is valid. However, all this proof shows is that the problem is undecidable for the single machine B. For every other machine it says nothing at all.

So Undecidable contains one nonsense element, and decidable contains infinite pratical elements. And then there are some more impratical elements to undecidable, which involve things like using a computer program to answer unanswered questions in number theory.