Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!ncar!mephisto!mcnc!rti!ntpdvp1!kenp
From: kenp@ntpdvp1.UUCP (Ken Presting)
Newsgroups: comp.ai
Subject: TM's (Was: Re: Searle and Radical Translation)
Summary: Read my lips: Computers are not functions
Message-ID: <628@ntpdvp1.UUCP>
Date: 30 Aug 90 18:08:53 GMT
Organization: SNA Solutions Inc., Contract Programming Group
Lines: 113

(This article is in reply to a posting received while I was on vacation)

> kohout@cme.nist.gov (Robert Kohout) writes:
>In article <620@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes:
>>. . .  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.

This is true, but notice that no deterministic TM can simulate the
operation of writing a string of arbitrary length on a blank tape.
The familiar equivalence between D and ND machines is stated in terms
of the *functions* they can compute.  If you wish, you may think of
my claim as referring to non-deterministic TM's which do not compute
functions.

I defined "|=" as a relation between deterministic computations, but that
does not imply that an equally useful concept cannot be defined in other
terms.  Recall that my intention was to define a formal concept with
which to model systems whose output is not a function of their input.  Non-
deterministic TM's can have this property, so your suggestion is at least
in the ball park.  I would argue that my relational concept has a technical
advantage, because it makes the weaker assumption that the content of the
database is *arbitrary*, while you are assuming that the database is
*random*.  (This is perhaps a mere quibble)

The important point is the non-equivalence of DTM's and NTM's, IN THIS
CONTEXT.  In the more familiar context of computing a function, there are
no advantages in the use of non-determinism.  But we are discussing a
different context.  We are concerned with devices which can generate
new outputs for the same inputs (perhaps as a result of learning from
experience).

Finally, don't overlook the issue of cardinality.  The set of paths defined
for Determinstic machines by "|-", the state-change relation, is countable.
For Non-deterministic machines, the set of paths is UNcountable.  Similarly
for the set of "chains" defined by "|=".  There can be no isomorphism
between sets of differing cardinality, so the concept of "|=" cannot be
reduced to any deterministically definable relation.


>4. What the sequence of input value is, I do not know, and I do not care.

This is our main source of difficulty.  The output of real computers is
dependent on the past sequence of inputs, and this is exactly the
phenomenon which concerns me.  If it does not interest you, then we have
no disagreement.

One reason that change in output over time is important is simply, learning.
I do not see any hope of defining "learning" in terms of machines which
always produce the same output from a given input.

So we have now two reasons for believing the "|=" relation to represent
a useful concept, distinct from Turing computability: (1) it defines a
set of non-denumerable cardinality, and (2) it can be used to represent
a sequence of inputs (and thereby represent learning).

>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.

I agree that this is obvious, but it is relevant only in the context of
machines which are used to compute functions.


>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?

Let me immediately quash the idea that I am talking about RAM machines vs.
TM's.  I defined the "|=" relation entirely in terms of TM's.  RAM machines
are strictly irrelevant.

>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?

If by "Church's Thesis" we mean:

   Every effective procedure is representable as the operation of a
   deterministic TM

then my proposal has no relationship to Church's thesis at all, because
the |= relation does not represent an "effective procedure".  For that
matter, neither does your (isomorphic) suggestion of allowing an NTM to
"guess" an arbitrarily long input string.  "Waiting for input" and "guessing"
are not finitary, effective, or reliable operations.

Let me recal how we got into this issue.  I said that Searle's main premise
is a consequence of Tarski's theorem on the undefinability of truth.  This
theorem entails (via Church's thesis) that no effective procedure can be
interpreted unambiguously as understanding the symbols it uses.  "No problem"
I say.  Real computers are not always instances of effective procedures.

So far, that is the whole story - a very short story.  Searle's argument
is sound if by computation we mean "effective procedure", and unsound
otherwise.  All that I am saying is that we each have, at our fingertips,
a counter-example to Searle's assumption that all computation is reducible
to effective procedures.


Ken Presting  ("Are we acquiring information yet?")