Re: Can you find anything wrong with this solution to the Halting Problem?

From: Jón Fairbairn (jon.fairbairn_at_cl.cam.ac.uk)
Date: 07/13/04 

Date: 13 Jul 2004 18:48:48 +0100

"Peter Olcott" <olcott@worldnet.att.net> writes:

> > He may or may not be, but his argument is correct. The whole
> > point and effect of mathematical proofs is that once they
> > have been done there's no need to worry about the question
> > any more. It's faintly possible that there may be an error
> > in Turing's proof (but how come none of us computer
> > scientists and mathematicians has spotted it?), or an
>
> http://home.att.net/~olcott/halts.html
> Maybe because you quit looking, and assumed that it
> was fruitless.

Look. Whenever someone produces a groundbreaking proof like
Turing's, lots of mathematicians look it over to see if they
can find mistakes. For something like Wiles's proof of
Fermat's last theorem, it takes a long time because the
mathematics involved is really difficult. For proofs of the
halting theorem the maths is relatively easy, so checking it
isn't terribly hard. In fact it's much simpler than the
stuff on your web page, because the model of computation is
completely specified, whereas yours involves talk about
"functions" and "screen data", and I don't know what you
mean by that. Note that the description to which you link
from your page is only a sketch of the proof, not a proper
proof -- he doesn't show how to convert the functions to
Turing machines, for example.

If you want to talk about computations in terms of
functions, learn the lambda calculus or combinatory
logic. Then the halting problem becomes a normalisation
problem, but it might be easier for you to understand.

> In any case since this does not address any of the points
> that I made it is not any form of valid refutation.

Of course it is! If a well understood theorem says P, and
someone comes along and says ¬P, the theorem is already a
refutation of ¬P, so there's no work to do.

Other people have already pointed out flaws in your
argument. The easiest one to grasp should be that it doesn't
matter if WillHalt is in protected memory, because if
WillHalt exists, it has a representation that can be fed
back into LoopIfHalts whether or not we know which value it
is, because it's supposed to work on /all/ values. You are
playing a game that's like this one:

Player A thinks of a positive whole number but keeps it secret.
Player B has to name that number.

Player B: 1, 2, 3, 4, ...

and you, as player A, are claiming that because player B
can't read your mind (and you are right in that: he can't!),
he'll never name your number. He might never know that he
has, but that's only because you don't have the grace to
admit defeat. 

-- 
Jón Fairbairn                                 Jon.Fairbairn@cl.cam.ac.uk

Relevant Pages

  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... lots of mathematicians look it over to see if they ... > that I made it is not any form of valid refutation. ... WillHalt exists, it has a representation that can be fed ... Player A thinks of a positive whole number but keeps it secret. ...
    (comp.theory)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... lots of mathematicians look it over to see if they ... > refutation of ¬P, so there's no work to do. ... people that never make any mistakes, ... > Player A thinks of a positive whole number but keeps it secret. ...
    (comp.theory)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... lots of mathematicians look it over to see if they ... > refutation of ¬P, so there's no work to do. ... people that never make any mistakes, ... > Player A thinks of a positive whole number but keeps it secret. ...
    (sci.math)
  • Re: Myth about mathematicians and mental arithmetic
    ... The great majority of novelists are excellent ... majority of mathematicians are excellent at mental ... To play darts at top level you have to be able to very quickly calculate the ... Each player starts with a score of 501 and takes turns to throw 3 darts. ...
    (sci.math)
  • Craps were Borned
    ... > When do the dice know that it's time to give the player the win so that ... "When do the dice know that it's time to give the player the win?" ... these sincere mathematicians were myopic and lacked the required ... I have personal knowledge that the dice know when it's time to give the player ...
    (rec.gambling.craps)
Quantcast