throopw@dg_rtp.UUCP (01/14/86)
> [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