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

From: Marc Goodman (marc.goodman_at_comcast.net)
Date: 07/13/04 

Date: Tue, 13 Jul 2004 14:21:43 GMT

Peter Olcott wrote:
> http://home.att.net/~olcott/halts.html
> Maybe because you quit looking, and assumed that it
> was fruitless. In any case since this does not address any
> of the points that I made it is not any form of valid refutation.

The Halting Problem restated in your terms:
Q: Is it possible to write a program A that reads another
program B as input and goes into an infinite loop if B exits,
but exits if B infinite loops?

A: No. Let program B be a copy of program A running
with input a copy of program A running on a copy of program
A running on a copy of program A, etc. Clearly, A and B
have exactly the same input (an infinite sequence of program A
running on program A). But, by definition, if one copy of program
A exits, then the next copy of program A must infinite loop.
But that means that you have two copies of program A that
have exactly the same input, but do different things.
That can't be possible if computer programs are determinisitic,
so either your programs behave randomly (which is bad, because
you can never be sure you're getting the right result), or A
cannot exist.

The basis of your proof is that it's possible to construct
situations in which A is not allowed to tell if B will exit
or not. This is 100% true but 0% useful. It's not necessary
for the above proof that _all_ programs A halt on input B
where B is a program that infinite loops, etc., it's only
necessary that it be possible to construct one program A
under one set of circumstances for which the above is true.
Then, under that circumstance, A cannot exist which means
it is impossible to construct A for _ALL_ circumstances.
That's what the proof says: There may well be cases of
A and B where A will halt if B loops and A will loop if
B halts, but it is impossible to construct a program A
where A will _always_ halt if B loops and will _always_
loop if B halts. Youre counterproof does not refute this,
and therefore your counterproof is not a counterproof of
the halting problem.

I've now wasted far more time on this post than it was
worth, thus proving that Kent was 100% right about invincible
ignorance and timewasting morons, since the odds that you will accept
the above as true are virtually 0%.

Relevant Pages

  • Re: Should compilers elide errors when possible?
    ... Well, with an obvious definition, SLEEP has "no side effects". ... I'd be pretty unhappy if the compiler elided that call to SLEEP. ... it should replace it with (error "infinite loop detected"). ... The only piece of code in a system which has a right to halt by means ...
    (comp.lang.lisp)
  • Re: Implausibility continued (in C)
    ... It's all math, Glenn. ... We are predicting what the computer will do when we step though the ... sufficiently large number and seeing if the program is in the halt state. ... still running must be in an infinite loop. ...
    (talk.origins)
  • Re: functions that halt
    ... > It's not a matter of having an infinite loop, it's a matter of having a ... > halts, or even when you can be sure it won't halt, and you have problems. ... I'm not saying ...
    (comp.theory)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... program B as input and goes into an infinite loop if B exits, ... then the next copy of program A must infinite loop. ... for the above proof that _all_ programs A halt on input B ... Youre counterproof does not refute this, ...
    (sci.math)
  • Re: F2008 draft
    ... (snip on BLOCKs and scoping) ... Can they have an intermediate form of SAVE that makes them last until the procedure exits? ... It is confusing and extremely error prone. ... It is confusing because the reader sees the infinite loop and has to look inside to understand that it can never actually loop. ...
    (comp.lang.fortran)