Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site harvard.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!philabs!cmcl2!seismo!harvard!chavez
From: chavez@harvard.ARPA (R. Martin Chavez)
Newsgroups: net.ai
Subject: Re: AI and Turing's Thesis
Message-ID: <137@harvard.ARPA>
Date: Tue, 21-May-85 10:14:47 EDT
Article-I.D.: harvard.137
Posted: Tue May 21 10:14:47 1985
Date-Received: Thu, 23-May-85 03:01:06 EDT
References: <113@nvuxf.UUCP> <388@linus.UUCP>
Organization: Aiken Computation Laboratory, Harvard
Lines: 37


    Let's get some facts straight:

    (1) The Church-Turing Thesis states that "no
computational procedure will be considered an
algorithm unless it can be presented as a Turing
machine" (Lewis and Papadimitriou, \\Elements of
the Theory of Computation//, p. 223).  NO computational
model that carries out finite labor at each step
has yet been shown to accept non-recursive languages.
Any such demonstration would absolutely revolutionize
the field of computational complexity.

    (2) The PRAM is an exceedingly general model
of parallel computation: we are allowed an unbounded
number of processors, and an infinite global memory.
(Each processor can perform arithmetic and load/store operations.)
Probabilistic simulations of PRAMs on fixed-degree
networks are known.  More important for our purposes:
the class of problems solvable in polynomial time
on a PRAM is exactly equivalent to the class of problems
solvable in polynomial space on a sequential Turing
machine.  I very much doubt that Hewitt has discovered
a finite computational model that cannot be simulated
on a Turing machine.

    (3) The notion of a "computable function" has
been defined in terms of various models (e.g., unrestricted
grammars and mu-recursive functions).  The abundance
of alternative characterizations suggest that the
Turing-decidable languages form a stable, natural class.
The notion of computabilitiy, then, is not an artifact
of the Turing-machine model.

			R. Martin Chavez
			Aiken Computation Laboratory, Harvard University
			(chavez@harvard.ARPA)