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!rochester!pt.cs.cmu.edu!k.cs.cmu.edu!gjs
From: gjs@k.cs.cmu.edu (Gregory Stein)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <720@k.cs.cmu.edu>
Date: Thu, 16-Jan-86 03:10:06 EST
Article-I.D.: k.720
Posted: Thu Jan 16 03:10:06 1986
Date-Received: Sun, 19-Jan-86 04:18:32 EST
References: <2175@aecom.UUCP>
Organization: Carnegie-Mellon University, CS/RI
Lines: 22
Xref: watmath net.ai:3188 net.philosophy:3821

I would tend to agree that there is no algorithm to determine
if some procedure terminated.  This has been proven, so why
doubt it unless you can show that the proof is invalid?  The
humans' ability to determine whether a procedure terminates
or not is based upon a large number of rules about general
program flow.  These rules can catch a majority of the cases of
infinite loops/recursions, but for those cases that the rules
do not apply, I think humans resort to comparing the algorithm,
or portions of it, to a large database of known non-terminating
algorithms.  This would be the case with the Fermat procedure.
No rules can quickly determine that it does not terminate.
Instead, we have just learned that it doesn't.  Therefore, it
would seem that a program could check a large number of cases
given a large enough rule base and database of non-terminating
algorithms.  There would be some that it could not be sure of,
but those would be very rare and extreme algorithms that you
probably wouldn't be worrying about in the first place.

			Greg Stein
			gjs@k.cs.cmu.edu

Is it instinctual for people to have to put in something here?