Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site nvuxf.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!pyuxww!pyuxv!nvuxa!nvuxf!markg
From: markg@nvuxf.UUCP (M. Guzdial)
Newsgroups: net.ai
Subject: AI and Turing's Thesis
Message-ID: <113@nvuxf.UUCP>
Date: Sat, 18-May-85 12:50:04 EDT
Article-I.D.: nvuxf.113
Posted: Sat May 18 12:50:04 1985
Date-Received: Sun, 19-May-85 00:45:51 EDT
Organization: Bell Communications Research, Red Bank, NJ
Lines: 45

The discussion on the Net recently concerning Hofstadter's comments about
machines composing music has brought to mind a puzzle that occurred to me
in reading GEB and in studying theoretical computer science.  I imagine
that the question is not original with me (perhaps not even new to this
newsgroup, as I'm yet a rookie around here), and I'm confident that
someone in AI has puzzled this one out.  Perhaps someone can enlighten
me with a solution.

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.

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.

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.

Human beings can "debug" programs, and are capable of determining if
a program goes into "infinite loop."  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.  Second, perhaps the machines we are
developing today are more powerful than Turing machines, which begs the
question of what is truly "computable."  Third, perhaps humans cannot
always "debug" programs.  Douglas Lenat has stated that "AM" did things
that he did not suspect.  Perhaps computable process Lenat was finding that
it could not determine the "halting function" for Turing machine "AM."

-- 
Mark Guzdial
{ihnp4, houxm}!nvuxf!markg
(201) 949-5471