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

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 08/26/04 

Date: Thu, 26 Aug 2004 06:49:59 +0000 (UTC)

Peter Olcott wrote:
> "Simon G Best" <s.g.best@btopenworld.com> wrote in message news:412CA1D1.4070003@btopenworld.com...
>
[...]
>>
>>The first thing is the heading on the page, "Refuting the Undecidability
>>of the Halting Problem". It doesn't make sense. It's like, 'refuting
>>the ambiguity of English', or, 'refuting the redness of ripe tomatoes',
>>or, 'refuting the Welshness of Tom Jones', or, 'refuting the invincible
>>ignorance of net.kooks'.
>
> One claims that is gaining acceptance is that I have correctly refuted
> every existing proof of the Undecidability of the Halting Problem.

Nope. That's plainly not true.

> What is a more concise way of saying this?

'A General Refutation of All Existing 'Proofs' of the Undecidability of
the Halting Problem'?

>>The second thing is that you're calling your abstract a "Quick Summary",
>>rather than "Abstract". Of course, an abstract /is/ a quick summary,
>>but I'd suggest labelling it as an abstract. Other than that, your
>>abstract needs to be completely rewritten. Fortunately, that's
>
> I want to eliminate any percieved ambiguity, do you see any?

Your current document is horrendously unclear, ambiguous, and so on.
But here goes:-

In the "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." This is just incorrect; so much so, it isn't
even wrong.

You're stating that "Alan Turing conclusively proved is that it is
impossible...", which means you're agreeing with the proof you're
claiming to refute.

"halt analyzer" is a term you need to define, but the abstract isn't the
place for that. It would therefore be a good idea not to use that term
in the abstract. It's not really a very good term, anyway, as TMs that
implement general solutions to the Halting Problem wouldn't necessarily
be analyzers.

TMs don't return results to other TMs. A TM, A, can be defined in terms
of another TM, B, but that doesn't mean that B returns results to A.
There is a sense in which some TMs contain other TMs as 'components',
but not in a way in which such 'component' TMs get 'called' or 'return'
results.

"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."
Again, that's just terribly incorrect.

The classic proof does not assume that 'halt-analyzing' TMs can only
return results "back to the Turing Machine being analyzed". On the
contrary, they regard such 'halt-analyzing' TMs as 'returning' their
results on their tapes as output - *not* to *any* other TM.

"for each and every element of the universal set of Turing Machines" is
a silly way to word it. You really need to learn how to use universal
and existential quantifiers. Oh, and you keep missing out the stuff
about working for all inputs, too.

Now on to your "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."

As well as all the previous problems with this that have been pointed
out many times, you seem to be limiting it to just "a specific input
data". The Halting Problem is concerned with arbitrary input, /not/ "a
specific input".

I'll stop there for now, as it seems that every single sentence so far
has lots of problems with it. As I said before, that document needs to
be /completely/ rewritten. To do a good job of that, you're actually
going to have to /learn/ the stuff, too.

[...]
>>
>>Next, "Definition of the Halting Problem". It's still wrong. The
>>Halting Problem is the problem of determining whether or not an
>>arbitrary Turing Machine, M, would halt on an arbitrary input, x. More
>>specifically, it is the problem of finding a Turing Machine which
>>carries out such determinations in the general case where M may be any
>>(in the sense of each and every) Turing Machine, and x may be any (again
>>in the sense of each and every) input.
>
> Someone else provided that form. I think that I wil eventually go with
> something like that.

"eventually" is not sufficient. You need to go with the standard,
accepted definition of the Halting Problem /right from the start/. You
should make this one of your first priorities.

[...]
>
> Ernest Hemingway thought that his every rewrite was garbage until
> about the twentieth one.

So what?

>>It'll still be wrong, though.
>
> I do admit that this continues to be the presumption.

It's not a presumption, as has been demonstrated many, many, many times.

> That is why I am going to clean it up for academia.

Cleaning it up is not enough. It needs to be completely rewritten.

> Hopefully if the audience is restricted to PhD computer
> science professors that have an emphasis on automata
> theory I will reach a group of people that will more
> often than not know the burdern of proof of proving
> a negative.

No. You will reach a group who will know and understand that your spiel
about "proving a negative" is a sure sign that you don't know what
you're talking about. In mathematics, it's a matter of universal and
existential quantification.

> In any case If I reach twenty such people,
> and I am right, at least one of them will see it too.

You've already reached lots of sufficiently qualified people who have
repeatedly demonstrated that you are not right.

Simon

Relevant Pages

  • 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 ...
    (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. ... 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: Attempt to Refute the Halting Problems Refutation
    ... providing three different inputs on which any halt analyzer will fail? ... If you can solve the halting problem with such a model, ... it makes no difference at all if it's encoded with a private ... But the way standard TMs are required to present their ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... providing three different inputs on which any halt analyzer will fail? ... If you can solve the halting problem with such a model, ... it makes no difference at all if it's encoded with a private ... But the way standard TMs are required to present their ...
    (sci.logic)
Loading