Re: Response to Karen and to Willem on recursive proofs

From: Willem (willem_at_stack.nl)
Date: 01/24/04 

Date: Fri, 23 Jan 2004 23:05:05 +0000 (UTC)

)> I think you meant 'while (program_terminates()) { }',

Richard wrote:

) Nope. Sorry for not being clear; I thought it would be self-evident that I
) was describing the Halting Problem:

It was self-evident. But check out the word I underlined in the following
line (my previous reply).

)> otherwise I can simply prove that the loop doesn't terminate.
) ^^^^
) ...
)
) I think you actually said it correctly the first time - after all, you
) included the weasel-word "usually", which made it all okay. I was just
) shooting the moon.

There are real-world programs where it's actually quite difficult to prove
that they terminate. Sometimes you need to prove one or more difficult
mathematical theorems, involving advanced set-theory or something like
that.

SaSW, Willem 

-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Relevant Pages

  • Re: Can the Turing Problem be deflated?
    ... is self-evident. ... IF Turing wants to address a particular problem, THEN it may be the case that the way he tackles it through the 'halting problem' doesn't actually address it. ... So "The Turing Problem MAY be a problem", but IF it is a problem, THEN the problem is not addressed in the form in which it is cast in the halting problem. ... There are grades of nonsense, but I can't find that paper, and its bed-time. ...
    (sci.logic)
  • Re: Can the Turing Problem be deflated?
    ... But I'm a bit unsure how to understand this brilliant new analysis. ... According to the insight you've provided, the Halting problem: ... is self-evident. ... you'll notice a significantly better signal to noise ratio, ...
    (sci.logic)