Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!genrad!mit-eddie!think!harvard!seismo!lll-crg!qantel!hplabs!hao!nbires!boulder!cisden!john
From: john@cisden.UUCP (John Woolley)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <404@cisden.UUCP>
Date: Wed, 15-Jan-86 11:30:20 EST
Article-I.D.: cisden.404
Posted: Wed Jan 15 11:30:20 1986
Date-Received: Sun, 19-Jan-86 04:09:35 EST
References: <2175@aecom.UUCP>
Reply-To: john@cisden.UUCP (John Woolley)
Distribution: net
Organization: ConTel Information Systems, Denver
Lines: 42
Xref: watmath net.ai:3187 net.philosophy:3820

I quote a recent argument in full because it's concisely written.  But it
is badly flawed -- a difference between "all" and "some".

In article <2175@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes:
>	There exists a proof that a computer procedure cannot be written
>such that given a procedure as input, it can tell you if that procedure
>contains an infinite loop. In other words, there does not exist a procedure
>halt that returns TRUE if the input procedure does not contain an
>endless loop, and FALSE otherwise. For, if such a procedure existed, we
>could set up a paradox:
>	PROCEDURE PARADOX:
>		IF HALT(PARADOX) THEN PARADOX
>Or, if the routine doesn't contain an endless loop, it will go
>on in an infinite recursion.
>
>	The human mind, on the other hand, given enough time an
>practice, can find an endless loop in any procedure. (You doubt this?)
>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.)
>
>	This would mean that there is a set of problems no procedure
>can ever do, yet the human mind does.  The root of them is at the fact
>that the human brain has meta-cognizance (I can realize, "Hey! This
>loop is taking me no-where.") Or, that the root of intelligence
>can not be duplicated by machine.

It is true, as you say, that no program can be written that detects *all*
infinite loops; it's easy, though, to write one that detects *some*.  And
the fact that human minds can detect *some* loops (as demonstrated by the
fact that we detected the loop in procedure PARADOX) is no evidence at all
that we can detect *all* loops.

In fact, if we *could* detect all such loops, we'd have no unanswered
questions in arithmetic.  You'd just write a program, for instance, to print
out the first odd perfect number (dead easy to do), and (using your "meta-
cognizance") examine the program for termination.  If it terminates, there
is an odd perfect number; if not, not.  But you'd know.
-- 
				Peace and Good!,
				      Fr. John Woolley
"Compared to what I have seen, all that I have written is straw." -- St. Thomas