Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site linus.UUCP
Path: utzoo!linus!sidney
From: sidney@linus.UUCP (Sidney Markowitz)
Newsgroups: net.ai
Subject: Re: AI and Turing's Thesis
Message-ID: <388@linus.UUCP>
Date: Mon, 20-May-85 01:49:46 EDT
Article-I.D.: linus.388
Posted: Mon May 20 01:49:46 1985
Date-Received: Mon, 20-May-85 04:36:09 EDT
References: <113@nvuxf.UUCP>
Reply-To: sidney@linus.UUCP (Sidney Markowitz)
Organization: The MITRE Corporation, Bedford, MA
Lines: 90
Summary: 

In article <113@nvuxf.UUCP> markg@nvuxf.UUCP (M. Guzdial) writes:
>According to the Turing/Church-Kleene/Post Thesis (and derivatives thereof),
>"Any computation one might naturally regard as possible to carry out can
>be performed by some Turing machine having a suitable set of instructions"
>(All quotes in this posting are from "Machines, Languages, and Computation"
>by Denning, Dennis, and Qualitz), or in other words, anything which is 
>"computable" may be simulated by a Turing machine.

Any function computable by one Turing machine is computable by any
other. This is a corollary of the proof that the halting problem is
unsolvable by a Turing machine, since the proof involves having a
Turing machine simulate another Turing machine.  Since such a
simulation can be constructed, all Turing machines are equivalent.
As I explain further below, however this is not the same as saying
that anything computable by any machine is computable by a Turing
machine, unless you use a strictly formal definition of "computable
function" which is defined in terms of what Turing machines can do,
anyway.

>If we are attempting to "simulate" human intelligent activity on a 
>machine (activity including composing music), we must be assuming 
>that such activity is therefore "computable," if we accept that anything
>our machines do is a computable activity.

We are forced to assume that human intelligent activity can be
supported by the hardware we are using to simulate (or imitate)
it. We don't know for sure that the hardware of the human brain is
Turing-equivalent. A Turing machine is a single processor
sequential machine with finite state control and infinite memory.
It is generally accepted that sequential computers with what is now
the conventional (Von Neumann) architecture are also
Turing-equivalent, given sufficient time and memory. But see the
article by Carl Hewitt (of the MIT AI Lab) in the April, 1985 issue
of _Byte_ for a fascinating discussion of parallel asynchronous
architectures (like that of the brain) and how they cannot be
simulated by Turing machines. Hence the current interest in AI in
parallel archtectures and connection machines.

>But Turing also stated that "The halting problem for Turing machines is
>unsolvable" where the halting problem is defined as "Given a Turing
>machine M and an initial tape T, does M halt when started on tape T?"
>I take all this to mean that one computer, given the inputs of
>another computer's hardware and software specifications and its input,
>cannot determine if the program will halt, or will go into "infinite
>loop."  In other words, one computer cannot "debug" another.

The halting problem states that we cannot program a Turing machine
to *infallibly* predict given the specifications of an arbitrary
Turing machine and its input whether it will halt. This is
philosophically like Goedels theorem. It does not mean that
computers cannot debug one another, only that they may not be able
to be infallible at doing so. If the brain were Turing-equivalent,
it would only mean that there are problems we cannot solve. I think
it is quite reasonable to speculate that we have some limitations.

>Human beings can "debug" programs, and are capable of determining if
>a program goes into "infinite loop."

Not infallibly. Remember that the Turing machine is an abstract
automata with infinite memory. The "infinite loop" may be
arbitrarily long. Could a human *always* determine if a computer is
in an infinite loop that takes a *very* long time to repeat? 

>  If human beings can perform an
>activity that Turing machines cannot, they must not be computable.
>Therefore, human intellectual activity cannot be simulated on a machine.
>
>There are three solutions that I see to this problem.  First, what the Thesis
>defines as "computable" is wrong. 

Not wrong, just a restricted, formal mathematical definition that
should not be confused with the more general English word
"computable".

>Second, perhaps the machines we are
>developing today are more powerful than Turing machines, which begs the
>question of what is truly "computable."

As Hewitt points out, that is true of the newer architectures we
are looking at now for AI work.

>Third, perhaps humans cannot always "debug" programs.

Perhaps also correct. Or at least predict what they will do.

-- 
					Sidney Markowitz

ARPA:	sidney@mitre-bedford
UUCP:	...{allegra,decvax,genrad,ihnp4,philabs,security,utzoo}!linus!sidney