Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 07/05/04 

Date: Mon, 05 Jul 2004 20:00:06 GMT

In sci.logic, Peter Olcott
<olcott@worldnet.att.net>
 wrote
on Mon, 05 Jul 2004 04:24:59 GMT
<vK4Gc.60874$OB3.48940@bgtnsc05-news.ops.worldnet.att.net>:
>> > It is merely that asking whether or not the specific counter-example
>> > program will halt forms another question within the incorrect
>> > question category. I am defining the term incorrect question as
>> > synonymous with the term impossible question. I am defining
>> > the term impossible question as any question where the correct
>> > answer can not be provided based on the meaning of the words
>> > in the question. I am calling the conditional expression that
>> > calls the WillHalt() function and tests its value the impossible
>> > question.
>> >
>>
>> So in other words the halting problem is solvable, if it's
>> formulated properly?
>
> Not quite as much as this. Once the proof that the Halting
> Problem is unsolvable is eliminated, the question becomes
> unanswered rather than undecidable. To actually fully answer
> this question (to fully solve the Halting Problem) would require
> deriving all of the methodology necessary to determine if any
> arbitrary program will halt.
>
> That it can be solved directly follows from the reasoning
> that I provided, merely eliminate the counter-example
> program (in all of its variations). As soon as one does this
> then one finds that no counter-example exists that shows
> that the determination of whether or not any other program
> will halt can be derived.
>

You might simply be having trouble with the phraseology.
Properly done, the Halting Problem is not a problem --
since one machine emulating another is routinely done, and
even a modern PC is basically interpreting numbers anyway,
namely, code instructions. Those code instructions can
emulate another machine, as well (and it can go as deep as
one wants, given enough space and time -- but after about
two it's probably time for a new implementation :-) ).

I frankly don't see your problem.

As usually phrased: assume a Turing Machine H takes
two parameters on its tape (separated by an agreed-upon
delimiter symbol, which I'll call "comma"). The first
is a machine description m, which is basically a number
encoding a Turing machine. The second is a number encoding
a tape t. The machine writes a "1" in the first cell
of the tape if the machine M halts on input T, and a "0"
if the machine M does not halt on input T.

(And yes, the casing is intended. m is an encoding of M.
t is an encoding of T. The details of the actual encodings
aren't all that important here. The machine description
can be added to, making it a finite state acceptor or
rejector; one might think of this as adding a front panel
to the Turing machine, with a "YES" (green) and "NO"
(red) light or something.)

The usual subterfuge is to take H's construction -- which
is admittedly a little vague since we merely assume it
exists within a certain well-known form -- or its encoding,
h, and construct another machine therefrom, which I've
been calling W (with its encoding, w). Basically, W
overwrites its second parameter with an encoding of its
first one, comma, 0, then goes through H's steps, then
makes a decision.

if it sees a "1" in the first cell of the tape, it loops.
if it sees a "0" in the first cell of the tape, it halts.

Then one feeds the tape "w,encoded_blank" into H.
Either H malfunctions, or one gets a contradiction.
(H malfunctioning would indeed be a contradiction anyway,
as H was assumed to work perfectly on all encodings of
combinations of possible machines and inputs -- including
its twisted half-brother, W.)

I personally prefer infinite-integer-register constructs,
as they're a little easier to work with in some areas.
However, Turing machines are classic, and rather simple:
write something, move the tape, make a decision.

If you want, I can postulate that W is not constructed
from H, but that w(m) is a 1-1 non-onto mapping that
instead maps an arbitrary Turing machine, M, twisting it
as described above. This function should be computable,
although for most machines W(m)'s behavior isn't all
that interesting since W(m) will either fail to find
the second parameter on the tape, mangle the entire tape
after the delimiter if the input is not conformant to H's
specification, do something strange if the first cell
is not "0" or "1", or loop if the first cell is "1" --
at least the last is by design, but for most functions
looping isn't all that useful.

But for the single machine W() is designed to kill, it works. :-) 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages