Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site dg_rtp.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!rti-sel!dg_rtp!throopw
From: throopw@dg_rtp.UUCP
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem :-)
Message-ID: <90@dg_rtp.UUCP>
Date: Mon, 13-Jan-86 19:53:56 EST
Article-I.D.: dg_rtp.90
Posted: Mon Jan 13 19:53:56 1986
Date-Received: Wed, 15-Jan-86 00:25:29 EST
References: <2175@aecom.UUCP>
Lines: 58
Xref: watmath net.ai:3167 net.philosophy:3750

> [A halting problem counterexample:]
>       PROCEDURE PARADOX:
>               IF HALT(PARADOX) THEN PARADOX
> [...]
> 	The human mind, on the other hand, given enough time an
> practice, can find an endless loop in any procedure. (You doubt this?)

Yes.  Silly me.

> After going through any loop several times, it can usually hit me,
> "HEY! There is no time I'm ever get out of this loop!" (Take for
> example the fact that you probably saw the paradox of procedure PARADOX.)

Why not take for example a loop that takes 10 million years for a single
iteration when run on a supercomputer.  Why do you always take the easy
cases and leave the hard ones for the poor automatons?

>         This would mean that there is a set of problems no procedure
> can ever do, yet the human mind does.

Let me get this straight.  Are you saying:

            {E}(h,p): H(h, p)    =>   {E}h:({A}p: H(h,p))

or maybe you mean the weaker claim:

            {E}(h,p): H(h,p)     =>   {A}p:({E}h: H(h,p))

or maybe yet again:

            {E}(h,p): H(h,p)     =>   {E}(h,c,p): ~H(c,p) & H(h,p)

or maybe just the "Proof by Emphatic Assertion":

            {E}h:({A}p: H(h,p))  =>   {E}h:({A}p: H(h,p))

    where:
        {E}     "there exists" (the backwards E)
        {A}     "for all" (the upside-down A)
        :       "such that"
        =>      "implies"
        ~       "not"
        &       "and"
        h       is from the set of all humans
        c       is from the set of all computer programs
        p       is from the set of all procedures
        H(x,y)  means "agent x can tell if procedure y halts"

Most remarkable, whichever way you mean your argument to go.

--
(defun two-matched-dox()
    "Fred must either lie, or admit he can't solve the halting problem"
    (if (progn (print "Hey Fred, will I terminate?") (yes-or-no-p))
        (two-matched-dox) ) )
-- 
Wayne Throop at Data General, RTP, NC
<the-known-world>!mcnc!rti-sel!dg_rtp!throopw