Science Forums 2

[CraigD]

Originally Posted by Kriminal99

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

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.

Originally Posted by Kriminal99

In a proof by contradiction, you don't have to explicitly state that you are making an assumption. Any logical assumption you make, whether you recognize it or not, can be the cause of the contradiction.

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.

Originally Posted by Kriminal99

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

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.