Xref: utzoo comp.ai:5548 talk.philosophy.misc:3442 sci.philosophy.tech:1922
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!purdue!bls
From: bls@cs.purdue.EDU (Brian L. Stuart)
Newsgroups: comp.ai,talk.philosophy.misc,sci.philosophy.tech
Subject: Re: Algorithms, Turing, Semantics
Message-ID: <9261@medusa.cs.purdue.edu>
Date: 15 Jan 90 19:31:42 GMT
References: <12883@phoenix.Princeton.EDU> <91Eq02wy7eX=01@amdahl.uts.amdahl.com>
Reply-To: bls@cs.purdue.edu (Brian L. Stuart)
Followup-To: comp.ai
Organization: Department of Computer Science, Purdue University
Lines: 47

In article <91Eq02wy7eX=01@amdahl.uts.amdahl.com> kp@amdahl.uts.amdahl.com (Ken Presting) writes:
>In article <12883@phoenix.Princeton.EDU> kadickey@phoenix.Princeton.EDU (Kent Andrew Dickey) writes:
>>
>>2) Others have named that current computers are not Turing machines--is
>>this not false?  Aren't all digital computer simulatable on a Turing
>>machine?  Or again, am I missing something obvious?  What's the simplest
>>problem a digital computer can solve that a Turing machine cannot?
>
>A guiding principle behind most of computer science is the "Church-Turing
>Thesis" - that all possible types of computation can be performed by
>Turing machines.  Many formal systems for defining computations have been
>devised, and all can be reduced to Turing machine programs.
>
>The only difference between computers and Turing machines is:
>(1) Computers don't have an infinitely long tape
>(2) Computers are real physical objects, whereas Turing machines are
>    abstract objects (like numbers or functions)

If you'll indulge me one last waste of bandwidth, I'd like to elaborate
on this point briefly.  Yes, all computers (except those with physical
noise sources) are simulatable on a TM.  The converse is not true because
they don't have the infinite tape as mentioned in (1).  To be precise,
here is the relationship among computer programs running on finite computers,
algorithms and TMs.
a)  Since a finite computer has a finite (albeit large) number of states
    it is a finite automaton, and finite automata recognize only regular
    languages.
b)  Algorithms by definition can recognize recursive languages which are
    a proper super-set of regular languages.
c)  TMs recognize recursively enumerable languages which are in turn a
    proper super-set of recursive languages.
So the question is not "what can a computer do that a TM can't?"  It is
"what can a TM do that a computer can't?"  And the answer is a non-empty
set of things.  There are no things that a computer can do that a TM
can't (except for certain computers that have quantum noise sources to
generate "true" random numbers).

The issue for AI is whether or not the brain's operation fits into one
of these catagories.  If it fits into the first, then strong AI is assured.
If it fits into the other two, then we want to know if a finite approximation
will suffice.  If it will, then again strong AI is assured.  If not, well
then we still can have fun in showing it.  Besides there are still some
practical problems that we can solve without achieving a full intelligence.

Brian L. Stuart
Department of Computer Science
Purdue University