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

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 08/25/04 

Date: Wed, 25 Aug 2004 11:33:31 -0400

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"? 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.

>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.

>Basis of this Informal Proof

It would be nice if you noted what this is an informal proof of.

>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.

>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.

>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.

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

  • Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... >>halt analyzer that always returns a correct result back to the Turing ... > strictly equivalent to a Turing Machine cannot do so either. ... It should be the case that anyone familiar with the Halting Problem ... >>Independently of any other Turing Machine's execution. ...
    (comp.theory)
  • Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... >>halt analyzer that always returns a correct result back to the Turing ... > strictly equivalent to a Turing Machine cannot do so either. ... It should be the case that anyone familiar with the Halting Problem ... >>Independently of any other Turing Machine's execution. ...
    (sci.logic)
  • Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... >halt analyzer that always returns a correct result back to the Turing ... strictly equivalent to a Turing Machine cannot do so either. ... >every element of the universal set of Turing Machines is impossible. ... >Independently of any other Turing Machine's execution. ...
    (sci.logic)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > and Romans that the Earth was a sphere. ... The universal set of all persons was wrong about the shape ... only way to construct a halt analyzer, his proof did not show that constructing ... The paradox that he constructed to show that a halt analyzer can ...
    (comp.theory)