X-Message-Number: 8596
Date: Mon, 15 Sep 1997 17:07:53 -0400
From: "John P. Pietrzak" <>
Subject: More on Turing Machines & etc.
References: <>

Hi Thomas,

Yes, you're absolutely right, there was never any intention of creating
a real-world "Turing Machine".  The structure of the TM is simply a
combination of several abstract concepts.  It is of value because
(a) it has a clear, concise, and (relatively) simple mathematical
definition, and (b) it can be shown that (IGNORING THE LIMITS OF TIME
AND SPACE) anything which can be performed by a digital processor can
be performed by a Turing Machine.  Just the sort of thing you want when
you'd like to prove general theories about computation.

[On neural nets:]
> Recognition is not a task performable by a PRACTICAL Turing machine.

Let me repeat, there is _no such thing_ as a PRACTICAL Turing Machine.

[On the unique distributed memory system of the brain:]
> Question: the classical Turing machine is given a tape, which it
> moves along marking individual digital spaces. If we allow formation
> of new connections and even new neurons, this tape becomes endless
> not only at both ends but even in the middle.

Ah, but you see, this is the magic of defining the tape as "infinite";
you can always "add" more space in the middle, by moving everything to
the right of it over a few spaces.  Of course, the process of moving
each mark, one by one, over a few spaces, can be incredibly inefficient
and time consuming for a TM; but since it's an imaginary machine anyway,
we don't care.  All we want to do is show that it is *possible*.

> I am certainly aware of all the ideas for mapping, say, a digital
> N-dim infinite set of points to a single 1-dim sequence of points.
> Perhaps that solves the problem of equivalence and perhaps not:
> remember that such a mapping would have to change constantly as the
> Turing machine proceeded.

Indeed, classically, those ideas for mapping multi-dimensional to
single-dimensional spaces are exactly what people use in many TM
proofs.  (In fact, here in Hopcroft & Ullman's book, pp. 164 - 165,
they give an example of just that.)  But then, with the brain, we're
not even talking about infinite sets of points: we have a large but
finite set of neurons (which changes at some rate) with a large but
finite set of interconnections between themselves (which changes at
some rate).

For example, let's say I want to simulate the (changing) inter-
connections between neurons, nothing else.  First, let me assume
that I can give a unique name to each neuron that exists in a person's
brain over their lifespan.  (If we're going to simulate a person's brain
on a computer, we're at least going to have to simulate each individual
neuron that exists at a specific time, and if we want the simulation to
be accurate, the set of neurons is likely to change over time; I assume
such a simulation would have to treat each neuron separately.)  Let me
simply use integers to name them: neuron 1, neuron 2, etc. Second, let
me assume that I can use a single value to simulate the link(s) between
any two neurons at a given time (for simplicity).  Then, given neurons
1,2,3,...,n at a given time, I can use the following table to record
which neurons have connections to which other neurons:

        neuron name
           1  2  3  ...  n
neuron  1  x  x  x       x
name    2  x  x  x       x
        3  x  x  x       x
        .                .
        .                .
        .                .
        n  x  x  x  ...  x

(Where each x is filled in with an appropriate link value.)  This 2-d
structure can be mapped into a single dimension, as you noted, using
various systems.  Therefore, it's not too tough to show that such a
structure could be encoded into a TM.

As the links change, I simply change the link values between the
neurons.  If we should happen to run out of names for each neuron, it's
probably simplest to construct a new, larger table further on down the
tape (we've got as much tape space as you want) and copy the data from
the old table to the new one.

Generally, I suspect that as long as all we're talking about is
simulating a finite number of connections between a finite number of
neurons, there isn't any problem with showing a TM could do it.  Other
problems, for example dealing with the signals sent between neurons,
might be tougher if they turn out to be interpreted in an analog rather
than digital manner; a digital approximation may or may not be
sufficient to encode them.


John

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8596