Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!ut-sally!im4u!rutgers!ucla-cs!zen!ucbvax!CS.UTAH.EDU!shebs
From: shebs@CS.UTAH.EDU (Stanley Shebs)
Newsgroups: comp.ai.digest
Subject: Re: Should AI be scientific?  If yes, how?
Message-ID: <8709031503.AA05856@cs.utah.edu>
Date: Thu, 3-Sep-87 11:03:22 EDT
Article-I.D.: cs.8709031503.AA05856
Posted: Thu Sep  3 11:03:22 1987
Date-Received: Wed, 9-Sep-87 04:46:29 EDT
References: <8708240436.AA19024@ucbvax.Berkeley.EDU> <8708251656.AA14266@cs.utah.edu> <8708281322.AA27689@duke.cs.duke.edu>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: cs.utah.edu!shebs@cs.utah.edu (Stanley Shebs)
Organization: PASS Research Group
Lines: 45
Keywords: Goedel, Turing, computability
Approved: ailist@stripe.sri.com

In article <8708281322.AA27689@duke.cs.duke.edu> duke!mps
(Michael P. Smith) writes:
>In article <8708251656.AA14266@cs.utah.edu> cs.utah.edu!shebs@cs.utah.edu
>(Stanley Shebs) writes:
>>
>>Goedel's and Turing's ghosts are looking over our shoulders.  We can't do
>>conventional science because, unlike the physical universe, the computational
>							     ^^^^^^^^^^^^^^^^^
>>universe is wide open, and anything can compute anything.  Minute examination
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>of a particular program in execution tells one little more than what the
>>programmer was thinking about when writing the program.
>>
>	[emphasis added]
>
>Would you please explain this tantalizing remark?  Surely not every
>formal system can compute every function (what about the ghost of
>Chomsky?).  Are you alluding to the mutual emulatability of Turing
>machines?

This is basic computer science.  Any formalism sufficiently powerful
to compute all the computable things we know of is equivalent to a Turing
machine (Church-Turing Hypothesis), and formalisms of that power are
all incomplete (Goedel's Incompleteness Theorem).  Incompleteness rears
its ugly head when we find that our most sophisticated programs cannot be
tested completely.

Simpler formal systems such as CFGs are too weak to model human intelligence,
although some aspects of human behavior have been asserted to be context-free
(for instance, Presidents that don't learn from their predecessors :-) ).

>Finally, how does the third sentence follow from the second?

This is the empirical consequence of Turing equivalence.  I can write
Eurisko or XCON in Lisp, Forth, or IBM 1401 assembler, and they will all
behave the same.  Assertions about the details about a program are worthless
from a theoretical point of view, details of algorithms are somewhat better,
but the algorithms appearing in AI programs are either too simple (searching
for instance) or too complicated to be analyzable (the abovementioned large
programs).

>Michael P. Smith	ARPA:	mps@duke.cs.duke.edu

							stan shebs
							shebs@cs.utah.edu