Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site idacrd.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!idacrd!wiener
From: wiener@idacrd.UUCP (Matthew P Wiener)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <130@idacrd.UUCP>
Date: Sun, 12-Jan-86 15:50:37 EST
Article-I.D.: idacrd.130
Posted: Sun Jan 12 15:50:37 1986
Date-Received: Mon, 13-Jan-86 07:48:35 EST
References: <2175@aecom.UUCP>
Distribution: net
Organization: idacrd, princeton, nj
Lines: 71
Xref: watmath net.ai:3161 net.philosophy:3726

> 
> 	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?)

YES!!

> 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

The human mind can get out of all infinite loops???  "This sentence
is false" will always bug me I fear, no matter how much I hear about
it.  (I realize that this is a tangential example. (?))

Suppose your mind tries the following:
procedure FERMAT:
loop on x,y,z>0 and n>2:
	if x^n+y^n=z^n then HALT;
endloop;

Does your mind detect the infinite(?) loop.

And that is merely a trivial example: one can simulate any
mathematical existence with a solution to the halting problem.
As the mathematical statement under question gets more difficult
(technically, alternation of "for all ..." and "there exists ..."
assertions), one can nest the halting problems within each other.

Even worse (because someone might answer the above question) is
the following:
procedure ZERMELO:
loop on all sequences p of set-theoretic assertions:
	If p is a proof that ZFC is inconsistent then HALT;
endloop;

(ZFC is one particular axiomitization of set theory)
The human mind has generally agreed that this is an
infinite loop.  But is it?
			
As an aside, any *particular* amount of meta-cognizance could be
programmed into a machine, and your PARADOX procedure would be the
first one meta-halted.

Also, try reading Kierkegaard and Sartre.  Now there's an infinite
loop for you!  :-)
-- 
berkeley!brahms!weemba
Matthew P Wiener
Math Dept UCB
Berkeley CA 94720