Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!rutgers!mcnc!rti!ntpdvp1!kenp
From: kenp@ntpdvp1.UUCP (Ken Presting)
Newsgroups: comp.ai
Subject: Re: Searle and Radical Translation (was: Re: Searle and Biology)
Summary: How to Build a Better Mouse - Don't Bob that Tail
Message-ID: <614@ntpdvp1.UUCP>
Date: 31 Jul 90 03:15:27 GMT
References: <612@ntpdvp1.UUCP> <5362@puggsly.cme.nist.gov>
Organization: SNA Solutions Inc., Contract Programming Group
Lines: 144

In article <5362@puggsly.cme.nist.gov>, kohout@cme.nist.gov (Robert Kohout) writes:
> In article <612@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes:
> >
> >. . . Each time a TM is given a particular input, the tape is erased
> >and the internal state is reset.  So the TM computes a *function* - same
> >input => same output.  That is obviously false for real computers, which
> >have updateable databases. . . .
> >
> >Theorems about TM's, which compute functions, do not apply to real machines,
> >for purely formal reasons.  Real machines do not, in the technical sense,
> >compute functions.
>
> Interesting. You mean to say that you find it perfectly obvious that
> Church's Thesis is false. I wish that you could formalize this - ...

Some preliminaries:

Take a Turing machine TM = (Q,S,D,q0,qf), where Q is a finite set of "states",
S is a finite set of "characters", D is a relation on ((Q cross S) cross (Q
cross S cross {Left, Right})), and q0, qf (the "initial" and "final" states)
are elements of Q.  TM is "deterministic" iff whenever (x,y) and (x,z) are
both elements of D, then y=z.  Only the deterministic case will be considered.
(Note that Q and S must be non-empty and disjoint, and one element of S is
called 'B', the "blank" symbol.)

Let S* be the set of all "words" (finite sequences) on the alphabet S. Let SQ*
be the set of all words on combined alphabet (S union Q).  Let SS be the set
of all words ss in SQ* such that ('_' is concatenation):

      ss = w1_qn_w2, where w1, w2, are in S*, and qn is in Q.

That is, SS is the "state space" of TM.  Elements of SS are usually called
"configurations" of TM, because for each step in any computation performed by
TM, there is a word in SS such that:

      1. The content of the tape before the step is w1_w2,
      2. The head is in state qn, and
      3. The head is positioned on the first character of w2.

Let |- be a relation on (SS cross SS) such that:

      w1_q_w2 |- w1'_q'_w2'
            iff
      there are a1,a2,a2' in S, v1,v2 in S*, and m in {Left,Right} such that:
      1. w1 = v1_a1 and w2 = a2_v2,
      2. <(q,a2),(q',a2',m)> is in D,
      3. if m is Right, then w1' = w1_a2' and w2' = v2,
         except that if v2 is null, then w2' = B,
      4. if m is Left, then w1' = v1 and w2' = a1_a2'_v2.
         except that if v1 is null, then w1' = B,

That is, TM "prints the symbol m and moves one square to the left or right",
adding blanks as needed, "converting" one state to the "next".

The relation |- defines a directed graph on the state space SS, by taking
(ss,ss') to be an "edge" iff ss |- ss'.  For a deterministic TM, there is
never more than one edge leaving any node (except as noted below), so a
"path" in SS is defined by any two "connected" points:

      ss |-* ss'  (read "ss leads to ss'") iff there exist ss0,...,ssn
                  such that ss |- ss0 |- ... |- ssn |- ss'.

TM "Halts" in a state ss iff there is no ss' such that ss |- ss'.

In the usual formalization of "computing a function by a TM" we consider
an alphabet S={B,1} and say:

      TM computes y=f(x) iff
         for all states of the form q0_w
            (where w is a string of x+1 "ones")
         there is a state qf_w'
            (where w' is a string of y+1 "ones")
         wherein TM halts.

For functions of n arguments, the starting state is q0_w1_B..._B_wn.  Vector-
valued functions are represented using a similar tactic in the final state.

Bob, this is what I understand a Turing machine to be, and I trust you will
agree that these definitions are formally equivalent to any in the familiar
texts.  If not, I hope you will correct me.


TM's with unerased input tapes:

Not all paths in the state space of a machine begin with a configuration
in standard form.  Let '|=' be a relation between paths in the state graph,
defined as follows:

      <ss1,ss2> |= <ss1',ss2'>
            iff
         1. ss1 |-* ss2, and ss1' |-* ss2',
         2. the TM halts in qf in ss2, and
         3. there exists d, o, and i in S* such that
            ss2 = d_qf_o, and ss1' = d_q0_i.

Thus, the '|=' relata can be compared to successive iterations of a
program whose main loop waits for input (w1') synchronously, and maintains
a "database" of some sort (w2).  The "database" is stored as a "tail" on
the input and output tape configurations.

Since the TM is deterministic, the waiting state (if there is one) is a
function of the initial state.  There is no difference in computing power
due to the new arrangement of the tape - the difference is only notational.
The obvious point is that the TM does not, in this notation, compute 'o'
as a function of 'i'.

True, the arrangement of the data on the tape is only a convenience.  The
important concept here is the relation |=.   It defines a directed graph
in the space of *paths*, just as |- defined a graph in the space of *states*.
Each time the old TM was used to compute a value, it moved along a path in
state space.  Not all machines do so in a well-behaved way, of course.
Some paths never terminate, and some that do terminate end in a non-
standard configuration.

Likewise, each time the new TM halts and is restarted with a new input,
it moves along an edge of the graph in path-space.  But this motion is NOT
deterministic - from any termination, there are many possible inputs which
could be provided to the machine, and an edge will represent each possibility.
Call a sequence (possibly infinite) P(i) of paths a "chain" iff for every i,
P(i) |= P(i+1).  The shape of a chain is determined partly by the machine,
and partly by the sequence of inputs.

The intuitively obvious facts captured by the relation |= include:

      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.

It may take a moment of thought to verify that while the set of paths
for any TM is denumerable, the set of chains is not.

The most important point here is that we should not suppose that by
identifying computers with Universal Turing Machines we have said anything
very specific about what they can and cannot do.  A Turing machine is a
very flexible formalism.  Many familiar theorems about TM's refer only
to a few of the many ways they can be employed.  Real computers implement
the TM model in an especially powerful way.


Ken Presting  ("I only want to see my name in pixels")