Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site umcp-cs.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!gatech!seismo!lll-crg!gymble!umcp-cs!dsn
From: dsn@umcp-cs.UUCP (Dana S. Nau)
Newsgroups: net.ai,net.philosophy
Subject: Re: A halting problem
Message-ID: <2750@umcp-cs.UUCP>
Date: Tue, 14-Jan-86 15:36:36 EST
Article-I.D.: umcp-cs.2750
Posted: Tue Jan 14 15:36:36 1986
Date-Received: Fri, 17-Jan-86 05:58:53 EST
References: <2175@aecom.UUCP> <1084@bunker.UUCP>
Reply-To: dsn@maryland.UUCP (Dana S. Nau)
Distribution: net
Organization: U of Maryland, Computer Science Dept., College Park, MD
Lines: 55
Xref: watmath net.ai:3175 net.philosophy:3786

In article <1084@bunker.UUCP> ricker@bunker.UUCP (James A. Ricker) writes:
>> 	The human mind, on the other hand, given enough time an
>> practice, can find an endless loop in any procedure. (You doubt this?)
>
>I don't doubt this. I think it's important that the "time and practice" clause
>be accented.

Well, I *do* doubt it!  I think you're assuming humans are *much* less
fallible than they actually are.

Suppose you think you've found an endless loop in some program.  How can you
really be sure it's an endless loop?  In really complicated cases, you might
end up incorrectly believing that a loop is endless.(*) You can't really be
sure it won't terminate unless you can prove it won't terminate.(**) But if
you try to write a formal proof, you will run into the same halting-problem
difficulties as a Turing machine would.

The point is that problems like the halting problem and the incompleteness
theorem arose from examining the procedures humans use to prove things--and
thus they say just as much about the limitations of how humans ascertain
truth as they do about the limitations of computing machines.

>> 	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.
> 
>Hold it right there! (Now hold it over here.) If you are going to restrict
>the machine to a sequential processing architecture, of course the machine
>will not be able to perform the task as well as a human mind. However, what
>evidence is there that a machine with real-time multiprocessing and/or
>parallel processing capabilities is incapable of detecting an endless loop?

That's not a problem.  It's straightforward to prove that anything that can
be computed on a parallel machine can be computed on a non-parallel
machine--it just takes more time to do the computation.

----------FOOTNOTES----------

(*) Try programming Ackermann's function and waiting for it to terminate.  It
will--but neither you nor the rest of the human race will be around by the
time it does!

(**) Actually, you can't be sure even then--because how do you know your
proof doesn't contain an error of reasoning somewhere?  There are several
well-known cases where published proofs were found to have flaws.  Problems
like this have led some people to argue that mathematical proofs are subject
to some of the same processes of social verification and consensus as is
knowledge in other fields.  I think there was an article in CACM about this
a few years ago.
-- 

Dana S. Nau,  Comp Sci Dept,  U of Maryland,  College Park,  MD 20742
dsn@maryland		seismo!umcp-cs!dsn		(301) 454-7932