Science Forums 2

[CraigD]

Originally Posted by Kriminal99

That is he claims there is a halting machine that can be part of a composite machine that includes an input copying machine that then feeds its output to the (inverted) halting machine. This machine is then fed itself as input and then expected to retain it's normal function in order for the proof to hold.

That is, despite this machine being fed it's own encoding, it is expected to still return a result of whether or not the input machine would halt on it's input which was also given. However in this situatiton a Halting Machine would uniquely be unable to provide a proper result - instead it would always loop. It doesn't always loop, just went given it's own encoding.

This is not at all what Turing’s 1936 proof of the unsolvability of the halting problem claims.

It claims that a Turing machine K can be created in an specific way by slightly modifying any proposed machine H that is a successful solution of the halting problem, and that when H is provided with an program input of K and a input input of K, either of H’s possible outputs (“halts” or “doesn’t halt”) are incorrect. As H is assumed to be a successful solution to the halting problem, which requires that it eventually halt with one of these two outputs, H must always halt. The proof doesn’t claim that for some pair of inputs H does not halt, it claims that for some pairs of inputs, H’s output must be incorrect. No “input copying machine” is explicitly or implicitly stated in the halting problem or Turing’s proof if its unsolvability.

Originally Posted by Kriminal99

At best I can see that if what I claim truly is the source of the contradiction, there probably exists some proof that a Halting machine has to trace the computatitons of the machine encoding it was given as input.

A successful solution H of the halting problem cannot simulate its program input P program’s processing of its input input I input, because if it did, H would not halt if P with input I did not.

One may be tempted to circumvent this problem by extending P to include not only its state diagram (a Turing machine is synonymous with a state diagram that consists only next states, a character to be outputted to the tape, and a zero or one position movement of the tape depending on previous states and the value of the tape at the read head), put every possible state of its entire tape. This is, however, not allowed, because P must have a finite number of states, while its tape may not be limited in length. No finite state machine P is possible for which a tape with more states that P is not possible. Turing machine are infinite-state machines.

If one restricts the halting problem to finite state machines, it’s possible to create a solution to the halting problem using the above technique. (such a solution, while not difficult, is left as an exercise to the reader) In other words, the halting problem is only unvolvable for infinite state machines.

From you simple misunderstandings of the halting problem, Kriminal99, I suspect that you’ve not had much if any experience writing Turing machines, and think you would benefit from it. Try writing one to do something simple, such as add two numbers (in the base of your choice) appearing on the tape, bound and separated with unique characters, writing the result to the tape, then halting. I suspect if you had the familiarity that comes from exercise of this kind, which are typically in introductory computing theory classes, you would not have the objections you do to Turing’s widely accepted proof.