Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site aecom.UUCP
Path: utzoo!linus!philabs!aecom!berger
From: berger@aecom.UUCP (Micha Berger)
Newsgroups: net.ai,net.philosophy
Subject: A halting problem
Message-ID: <2175@aecom.UUCP>
Date: Fri, 10-Jan-86 10:14:08 EST
Article-I.D.: aecom.2175
Posted: Fri Jan 10 10:14:08 1986
Date-Received: Sat, 11-Jan-86 08:02:58 EST
Distribution: net
Organization: Yeshiva University
Lines: 27
Xref: linus net.ai:2935 net.philosophy:3460


	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.

	Okay, thats the arguement. Well.... Where's the flames?

                                        michab