Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!cme!kohout
From: kohout@cme.nist.gov (Robert Kohout)
Newsgroups: comp.ai
Subject: Re: Searle and Radical Translation
Message-ID: <5734@puggsly.cme.nist.gov>
Date: 10 Aug 90 14:33:43 GMT
References: <612@ntpdvp1.UUCP> <5362@puggsly.cme.nist.gov> <614@ntpdvp1.UUCP> <5644@puggsly.cme.nist.gov> <620@ntpdvp1.UUCP>
Reply-To: kohout@cme.nist.gov (Robert Kohout)
Organization: National Institute of Standards & Technology, Gaithersburg, MD
Lines: 92

In article <620@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes:
>
>> Interesting, Ken, but what's the point? Do you intend to imply that this
>> relation represents something that computers "do" and Turing Machines don't?
>
>If you will recall the assertion that I set out to formalize, you will perhaps
>recognize that I have just made my point:  when there is something on the
>tape besides "input", then the "output" is not a function of the "input".
>I hope that you can now agree that this is both obvious and trivial.
>
Imagine I have a non-deterministic TM that begins its computation by
writing a random string of data on its tape. It then uses this data ,
along with its input to compute whatever its output will be. Since the
TM is non-deterministic, we can assume that this "random" number is,
in fact, whatever happens to be on the tape of your machine at the "start".
This TM will then compute whatever your machine computes. 

A TM that prints out occassional values is no more powerful than one
which prints out only one. A 2-tape TM is no more powerful than one with
1 tape. Why can't a TM keep a database of its history on, say, a second tape?
If you're trying to say that the "power" of a real computer comes from
its ability to accept arbitrary inputs, can't a non-deterministic TM just
"guess" these inputs up front and proceed from there?

>> }       1.  A computer is used repeatedly to compute different values.
>> }       2.  The number of times a computer is used is unlimited in
>> }           principle.
>> }       3.  The device may modify its future operation in the course
>> }           of performing the current task.  (by updating the database)
>> }       4.  The sequence of values input to the computer cannot be
>> }           specified in advance.
>> } 
>> None of these are beyond the capacity of a Turing Machine.
>
>It might help to avoid further confusion if you would take the trouble to
>explain this claim.
>
1. Perhaps technically a TM computes only one value, but it is possible
to 'output' several values of the course of a single 'computation'. Perhaps
the TM implements an operating system and technically maps zero to zero.
We don't have to care about the 'function' being computed, and it is
certainly within the capabilities of a TM to perform what may seem like
'several' computations in the course of only a single calculation.

2. Again, while the number of times a TM may be used is technically 1,
this does not prevent us from implementing a TM which, in the course of
its one computation actually performs infinitely many sub-computations.

3. In the context described in 1 and 2 , a TM can certainly keep a database. 
Moreover, since a non-deterministic TM can effectively "guess" its database
at start-up, it generally may not need one.

4. What the sequence of input value is, I do not know, and I do not care.
If you are saying that a real machine can accept its inputs in little
chunks, while a TM requires its input up front I maintain that this adds
nothing to the computing ability of the machine. Obviously, one could take
the entire input over the life of a real machine and encode it in some
fashion that could suffice to be the single, "initial" input of a TM.
Also, what is to prevent a non-deterministic TM from "guessing" user
input whenever it is required?

>> Do you mean to imply by this that a computer is more powerful than a TM?
>> Do you REALLY think you are refuting Church's Thesis?
>
>You must have been very excited to think that you found a "Pro-Searlite"
>(which I am not) who believes he can refute Church's Thesis (which I do
>not).  Sorry to disappoint you, but you have only your reading skills to
>blame.
>
>> . . . You
>> certainly haven't shown anything that computers "do" that TM's don't. For
>> that matter, you haven't made a single assertion about this |= relation
>> insofar as it applies to computers and not Turing Machines.
>
>No.  You have asserted without argument that my (1-4) are not "beyond the
>capacity of a Turing Machine."  That is pure bluff.  Or perhaps you are
>unfamiliar with the concept of "non-denumerable set".
>
I don't see how you can have it both ways. Either Church's thesis is incorrect,
or a RAM machine cannot do anything that a TM cannot do. Which is it?
Perhaps it IS my reading, but you seem to be saying that no, you do not
dispute Church's Thesis, and here is a list of things that a computer can
do and a TM cannot. I have once claimed that nothing in your list is
beyond the capacity of a TM, and now you ask for me to substantiate this
claim. Is this not questioning my statement? And in questioning my assertion,
are you not also implying that you believe that a RAM machine has certain
capabilities which a TM does not? And does that not violate Church's Thesis?

>
>Ken Presting   ("Punchcards on the table")

Bob Kohout