Re: Refutation of the Halting Problem's Proof (Clarifications Wanted)

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/25/04 

Date: Wed, 25 Aug 2004 23:25:32 GMT

"Will Twentyman" <wtwentyman@read.my.sig> wrote in message news:412cb1a7$1_1@newsfeed.slurp.net...
> Peter Olcott wrote:
>
> > www.halting-proiblem.com
> > I want to make what I am saying as clear as possible. If anyone
> > has any points that are still not clear, this is the thread to ask for
> > clarifications.
>
> It would be easier for a request like this if you quoted the material
> here, so that we don't have to do it for you. The quotes below are from
> the website.
>
> >Refuting the Undecidability of the Halting Problem
> >Quick Summary:
> >Alan Turing conclusively proved is that it is impossible to construct a
> >halt analyzer that always returns a correct result back to the Turing
> >Machine being analyzed.
>
> First observation, it is worth noting that this means anything that is
> strictly equivalent to a Turing Machine cannot do so either. If it
> could, it could be converted into a Turing Machine.
>
> >Since returning the result back to the Turing Machine being analyzed is
> >not the only way to construct a halt analyzer, his proof did not show
> >that constructing a halt analyzer that works correctly for each and
> >every element of the universal set of Turing Machines is impossible.
>
> Issues: 1) Turing Machines don't return results, the have an output.
> 2) What are you talking about when you say "returning the result back to
> the Turing Machine being analyzed"?

When I speak of returning a result I am speaking of the higher level
abstraction that is available in most every higher level programming
languages. If we were speaking completely literally, then the latest
chip from Intel would also be incapable of returning results. The
compilers typically use the calling convention of placing the result
in the EAX register.

> There is nothing about analyzing
> whether a TM halts that says anything about whether or not it is allowed
> to make use of that information. You appear to have something in mind
> to prompt that statement, but the context for it is not provided. It
> might be worthwhile to reproduce his proof as you understand it for
> reference.

It should be the case that anyone familiar with the Halting Problem
would instantly see exactly where I am going with this. I will see how
others respond.

>
> >Definition of the Halting Problem
> >There does not exist a Turing Machine that can correctly determine
> >whether or not each and every element in the universal set of Turing
> >Machines will execute in a finite number of steps for a specific input
> >data.
>
> That's the conclusion of the Halting Problem. It's also very wordy. A
> simpler phrasing would be, "There does not exist a Turing Machine, H,
> that correctly determines in finite time whether an inputted Turing
> Machine, TM, will halt on input, I." Note that this definition assumes
> that H(TM,I) somehow encodes its answer on the tape when it halts. This
> definition also assumes that H is to work for all TMs and all inputs.

I might use a form such as the one that you suggested.

> >Basis of this Informal Proof
>
> It would be nice if you noted what this is an informal proof of.

The title already says this. I will see if others think that I
should repeat it here.

> >The basis for this informal proof is to exploit the differences between
> >the first and second paragraph of the Quick Summary. All we have to do
> >to eliminate the historical prohibition to solving the Halting Problem
> >is to refrain from returning the result of the analysis to the subject
> >of the study. One way to accomplish this would be to simply refrain
> >from returning the results of the Halt analyzer to any other Turing
> >Machine.
>
> At this point, you are not constructing a Halt Analyzer. You can't
> claim that a Halt Analyzer exists by offering something that is not a
> Halt Analyzer as the counter-example.

I am only making the exact same assumptions that every other
proof has made. They assume that a Halt Analyzer exists,
and then provide a mechanism that is supposed to show that it
could not ever work. I have provided a mechanism whereby
their mechanism would always fail.

> >Since the Halt analyzer can be called from two different contexts:
> >(1) As a part of another Turing Machine's execution.
> >(2) Independently of any other Turing Machine's execution.
> >This still leaves a means to report the results of the Halt Analysis
> >for each and every element of the universal set of Turing Machines.
>
> A Halt Analyzer is a TM. It operates only on its input. If you want it
> to behave in a peculiar way, you need an additional input, which gives
> you something other than a Halt Analyzer.

I don't think so. It is merely (conceptually) two TM's that are operating
in conjunction, which could be physically implemented as one TM
operating by itself.

> >When the Halt Analyzer determines that is has been invoked as a part of
> >another Turing Machine's execution, it simply halts. If the Halt
> >Analyzer determines that it was not invoked as a part of another Turing
> >Machine's execution, then it analyzes the subject Turing Machine
> >Description, and writes a ONE to a specific tape location if it halts,
> >otherwise it writes a ZERO to this same location.
> >
> >The last step is the method by which the Halt analyzer can determine
> >its invocation context. This can be a very simple feature that is
> >implemented in the Universal Turing Machine. The Halt analyzer would
> >merely ask the UTM whether or not its specifically indicated final
> >state has any state transition defined. This information is very easy
> >for the UTM to provide, it merely looks up the action associated with
> >the state in its state transition matrix table. If there is no state
> >transition defined out of the Halt analyzer's final states, then the
> >Halt analyzer can know with certainty that it was not invoked as a part
> >of another Turing Machine's execution. It can use this information to
> >determine whether or not it can safely return a result, or that it must
> >refrain from returning a result.
>
> A halt analyzer cannot refrain from returning a result.

Sure it can. It is not required to always write to its tape.
There is a separate write operation, than may never be
invoked.

> You are also now talking about something other than a Turing Machine if
> you are accessing the state transition matrix table.
>
> What you are effectively saying is, "I have found something that is not
> a Turing Machine and does not satisfy the output requirements of a Halt
> Analyzer that I want to offer as a counter-example to the non-existence
> proof for there being no Turing Machine that is a Halt Analyzer, where a
> Halt Analyzer has only to possible results, and it is required to
> produce one of them." At this point, you are on a massive tangent.
>
> >If these steps are taken, then the counter-example Turing Machine that
> >has been used as the basis for contructing the Halting Problem Proof
> >can no longer have any effect of the Halt analyzer or its ability to
> >produce correct results for each element of the universal set of Turing
> >Machines.
>
> Your counter-example is not a Halt Analyzer or a Turing Machine. As a
> result, it has nothing to do with the non-existence of a Halt Analyzer
> which is a Turing Machine.
>
> --
> Will Twentyman
> email: wtwentyman at copper dot net
>

Relevant Pages