Xref: utzoo comp.ai:2584 talk.philosophy.misc:1558
Newsgroups: comp.ai,talk.philosophy.misc
Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!bradb
From: bradb@ai.toronto.edu (Brad Brown)
Subject: Re: Artificial Intelligence and Intelligence
Message-ID: <88Nov15.170837est.707@neat.ai.toronto.edu>
Organization: Department of Computer Science, University of Toronto
References: <484@soleil.UUCP>
Date: Tue, 15 Nov 88 17:08:22 EST


Claiming that the existence of Turning-unsolvable problems precludes AI
is just plain wrong.  That old chestnut has been around for a long time
and has been debunked many times, so here's my attempt to debunk it 
(again :-)

Assumption 1:

	Turning machines are capable of computing any function that 
	any imaginable computer (or what we know of as a computer)
	can compute.  Therefore the limits of Turing machines apply
	to any computer that we can construct.

Assumption 2:

	There are problems that Turing machines cannot compute.
	The canonical example is the halting problem -- there is
	a simple proof that it is impossible to write a program 
	that will take as input another program and the input to
	the other program and decide whether the program will
	halt.  There are other examples which can be proved to 
	be non-computable because they can be related to
	(technically, "reduced to,") the halting problem.

False assumption 3:

	Since Turing machines cannot compute everything imaginable,
	they can't compute (ie simulate) human intelligence.


Assumption 3 is implicitly based on an assumption that 
artificial intelligence requires a solution to the halting
problem.  It's not at all clear that this is neccessarily
the case.

To show that a solution to the halting problem is required,
you would have to show that intelligent beings could perform
some task which was reducable to the halting problem.
For instance, you would have to show me that you were able
to determine whether a program would halt given the program
and the input -- for any program, not just a specific one.
Bet you can't think of *any* task humans perform that 
is *provably* halting-reducable.

People have known for some time that there are limits to 
what can be computed by *any* mathematically-based system.
The halting problem for Turing machines is only one example --
Godel's Incompleteness Theorem is a more general result
stating that any axiomatic system of sufficient power will
be fundimentally incomplete.  (NB  Systems that are not of
'sufficient power' are also not of sufficient interest to
consider for the purpose of AI)

Unfortunately, Godel's result is another example of a limitation
of formal systems that is misunderstood to mean that formal 
systems cannot exhibit intelligence.  In this case, Godel
shows that there will exist theorems which are true within
a system that the system will not be able to prove true.

Again, the fallacy of the popular opinion is that intelligent
systems will require that such truths be provably true.  This
is an even more tenuous claim than the requirement for solutions
to the halting problem -- given the number of mistakes that
humans make all the time, why should we expect that humans
will have to know the truths of these pathalogical cases?
Indeed, most of the "errors" that formal system will make
in determining the truth of a theorem will occur only for
pathological cases that are probably not important anyway.


So, I regard claims that AI requires some form of unachievably
"perfect" reasoning with great schepticism.  I feel strongly
that if you are a person who looks at the brain from the 
point of view of a scientist who examines causes and effects,
then the possibility (though certainly not the achievability)
of AI is very credible.  IMHO, beliefs to the contrary imply
a belief in a "magic" component to the brain that defies
rational explanation.  Sorry, but I just don't buy that.

					(-:  Brad Brown  :-)
					bradb@ai.toronto.edu

					+:   O
					+:  -+-
	Flame-retardant shielding -->   +:   |
					+:  / \