Science Forums 2

[Kriminal99]

Originally Posted by CraigD

The halting problem explicitly asks if there exists a program H that can accept as input two data: the enumerated description a program, and that program’s data. The problem places no restriction on the size of value of these data, (other than that they are finite, since obviously we can show that H can’t output its required value of “halts” or “doesn’t halt” if it can never stop reading its input) so both inputs being the description of H is a direct consequence of the lack of a restriction prohibiting it.

Turing’s 1936 proof of the undecidability of the halting problem does not have the input to H be exactly H, but be H with a specific change to the so that H does not always halt (the following link’s illustration labels this program K). Since H by definition must halt with an output of “halts” or “doesn’t halt”, this change is essential to his proof. this textbook excerpt has a terse, illustrated summary of Turing’s proof.

If we change the question to explicitly prohibit inputs to H of description of modified versions of itself, we would have a new problem, as there are an arbitrarily large number of possible K’s. K’s need not be constructed as suggested by the illustrations – they could be entirely different programs, so long as they produced the same output. The problem would now require the answer of another problem, “is it possible for a program R to always halt with the output “like me” when inputted the description of a program that always halts with the same output it would halt with given the same data, and “not like me” when it does not.

If we change the question to explicitly program description and data inputs from being the same, we would again be faced with the “like me” problem, as for this to be effective, not only data inputs identical to program inputs would need to be prohibited, but “like” ones as well. Turing’s halting problem proof is not, upon careful inspection, a proof by contradiction. It does not start with the assumption that a successful H exists, and show that this contradicts some proven or a-priori theorem. Rather, it is a disproof by counterexample. It shows that for any possible candidate H, a K can be built for which it fails. It provides a specific approach for generating K for any H.

Also, I’m unsure that Krim is using the term “proof by contradiction” in a conventional sense. Such a proof must state its assumed-true assertion, or it simply isn’t a this type of proof. The halting problem explicitly requires that all programs can be enumerated, and described in the form of input data. Because it explicitly requires that the programs described in it are Turing-complete, it requires only one actual machine, which is either a universal Turing machine running the program of H, a special purpose Turing machine H, or any machine proven equivalent to one of these Turing machines. No machine actually works on another machine: it works on data describing other machines.

The fact that the H in the proof is "Touring Complete" means the result is extremely weak. There could still be a halting machine that is "Touring - {H} Complete" where H is the halting machine itself.

Encompassing any Universal machine in a larger machine that also contains a machine capable of copying input causes an infinite regress if that Universal machine attempts to trace the computations of the machine encoding it recieves as input. Why? When it traced the computations it would just start the whole process over again, and make a new copy of the input for the next level of recursion. This is done in the proof. It doesn't matter how many K's there are, since it's the entire class that causes the problem.

I don't need to assume that H traces the computations of it's input, because I am not the one proposing a proof. Rather Touring's proof assumes that H can function on itself and still do what it is supposed to, when it is very likely that an H by it's very definition could not operate on itself. You can trivially dodge this by simply defining H to be able to operate on itself, but then you cannot sell the result as a proof that the Halting Problem cannot be decided. The removal of H from the set for which the problem is decidable is not very signifigant, much can still be accomplished by solving the problem for everything else.

The proofs absolutely are done by contradiction and not counterexample. You cannot counter example the possibility of existance of any halting machine. That doesn't make any sense. A counter example is just the opposite - when someone says "This always is the case" or "This cannnot be ever" (ie uses a universal quantifier) you only need one counter example to disprove their claim.

Touring starts by assuming there is a Halting decider H, assumes some other things, and then derives contradictions from the set of assumptions. When you say "possible candidate H", it means assume there is such an H. This is called a proof by contradiction.

And it only proves that a certain assumption is false if you are certain that all other assumptions, both recognized and unrecognized are not false. In this case there is no reason to trust the assumption that a Halting machine is in it's own domain.