Re: Yet another Attempt at Disproving the Halting Problem

From: Acid Pooh (poohonlsd_at_yahoo.com)
Date: 07/26/04 

Date: 26 Jul 2004 00:46:29 -0700

"Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<lo_Mc.136288$OB3.96322@bgtnsc05-news.ops.worldnet.att.net>...
> www.halting-problem.com
>

>
> If the state transition diagram representation of the Halting Problem
> In An Introduction to Formal Languages and Automata, by Peter Lintz
> copyright 1990 pages 317-321 accurately represents the actual
> Halting Problem, then what is taken to be a proof that solving the
> Halting Problem is impossible, can not be correctly concluded
> from the proof.
>

We can't evaluate this claim without a copy of the book. Why don't
you scan the relevant pages and put them on your website?

> What the proof really shows is that there is one way to attempt
> to solve the Halting Problem that is bound to fail. If one takes
> the original unmodified Turing Machine that determines halting,
> and inputs the counter-example program (defined below), the
> result is that this counter-example program does indeed halt.
>

Maybe that's what Linz's "proof" shows, but not what Turing shows.
Turing shows that there is absolutely positively _no_ turing machine
which evaluates the Halting function.

> If this is true (which could be shown with state transition diagrams)
> then the corrupted version of the halt analyzer in no way refutes
> the correctness of the uncorrupted halt analyzer. Because of this
> the original proof (as related in Lintz) does not prove that solving
> the Halting Problem is impossible. All that it really shows is one
> way that is bound to fail at least some of the time.
>
> counter-example program:
> This is the Turing Machine that has been modified from the halt analyzer such
> that the state transition that indicates that this Turing Machine has determined
> that the program being analyzed will halt, is immediately followed by a cyclic
> transition on no input. (Equivalent to the infinite loop)
>
> In order to make this reasonably convincing I will need to learn
> the diagonalization that has been shown to be in the original proof.
> Any help in this would be greatly appreciated.
>

That's easy: Suppose that there is a Turing Machine which evaluates
the halting function. Call it h. So h(x,y) = 1 if the machine with
godel number x halts on input y, = 0 otherwise.

Here comes the diagonalization: Let w(x) =1 -*- h(x,x). (that's a
minus with a dot on top, which is defined by the properties: x -*- y
= x - y if x > y, 0 otherwise. Notice, then, that w(x) = 0 iff h(x,x)
halts.

Notation: If t is a turing machine, then "t" (t in quotation marks)
is it's godel number.

Suppose w("h") halts. Then h("h","h") halts. Which means that
h("h","h") halts. Which means that h("h","h") = 1. So 1 - h("h","h")
= 0, and thus w("h") = 0. Contradiction. (Notice that each of the
implications in this paragraph are in fact "iff" statements, so there
is no need to do the "other direction."

Since the assumption that there exists a turing maching h that
evaluates the halting function leads to a contradiction, we must
conclude that no turing machine solves the halting problem.

> I know that the informal, somewhat imprecise, and probably slightly
> rambling nature of the above is probably not convincing. At this
> stage it is not meant to be convincing. If I can prove that the original
> Halting Problem is incorrect, using the same terms, formality, and
> mechanisms that you all have become accustomed to, then in
> light of this, you will see where this relatively poor quality material
> is still essentially correct.
>

That's a big "if", since the logic used in proving the undecidability
of the halting problem is absolutely solid. Your result wouldn't tear
Turing's result down, but would show that a big part of mathematics is
in fact _inconsistent_.

'cid 'ooh

Relevant Pages