No subject

[David Wolpert]

Mitsu Hadeishi writes:

>>>>>
David Wolpert writes in response to Penio Penev regarding his recently
posted abstract:

>What's quite a bit more difficult is emulating an arbitrary (discrete
>space and time) Turing machine using a neural net with an *uncountably* 
>infinite "memory", and *continuum* dynamics of the signal through
>the net (i.e., signal dynamics governed by differential equations, rather 
>than by discrete time steps).

        I'm interested to know what effect noise or signal degradation
might have on your technique for emulating an arbitrary Turing machine
using your linear field computer.  I would imagine that you would get
some sort of statistical approximation of a Turing machine, for example
you'd have a certain (perhaps quite high) probability of correct
results.  Of course, real physical finite computers have exactly
the same problem, with the potential for memory failures and other
unexpected deviations from theory.  However, I was wondering
to what extent your technique for getting computational universality
was sensitive to noise and whether you addressed this issue in your
paper.
>>>>>

This is a very good question. It opens up the whole area of
error-correcting field computers.

Although we've thought about this issue, we haven't addressed it in
any detail, other than to note a change of basis which might
facilitate robustness against noise. (We didn't want to try to cram
too much into the paper.)

In general though, it would seem that the issue is dependent on a
number of factors.


First, the *kind* of noise process is important.  Our system is one
which evolves continuously in time, and is continuous in space (i.e.,
in neuron index). Accordingly, one might think that something like a
Weiner process for noise would be appropriate. But it's not hard to
think of other possibilities.

In particular, if the noise is multiplicative (or for some other reason
preserves the set of neurons which are non-zero), then it won't
affect our system *at all*, since our system is linear, and its
interpretation only depends on the set of neurons which are 
non-zero, and not their actual values.

More generally, one would expect that for most kinds of noise processes,
the degree of degradation would depend on how long the system runs
(especially given that our system is linear). So the accuracy of
emulation of a particular Turing machine, when noise is involved, is
in general undecidable - if the Turing machine doesn't halt, one would
generically expect that any (non-multiplicative) noise process would 
result in complete degradation eventually.

Second, one of the first things we do in demonstrating computational
universality is show how to transform the original system, which is
continuous-space, continuous-time, with a time-independent weight
matrix, to a new system, which is discrete-space, continuous-time,
with a time-dependent weight matrix. (We then demonstrate
computational universality for this second system.) In essence, we
transform the system into a "cellular automaton" evolving continuously
in time, with time-dependent dynamics. This transformation relies on
choosing the original time-independent weight matrix to lie in a
particular equivalence class of such matrices.

This is important because if the noise doesn't interfere with this
transformation, then it will only affect how accurately our resultant
"cellular automaton" is mimicing a Turing machine. However if the
noise instead interferes w/ the transformation, we will have automatic
"cross-talk" going on *continuously* between all possible Turing
machines. (Only at t = 0 would we be coding for only one particular Turing
machine.)  Generically, this will affect the degradation of our system
differently.

***

Finally, in practice one would (often) want to use our system the
same way neural nets are used - as simple mappings from inputs to
outputs, which reproduce a given training set (up to regularization
issues), rather than as systems which reproduce a given Turing 
machine. (In many senses, proving computational univsersality is
of interest because it establishes the potential power of a system,
not as a practical way to use the system.) And in general, noise 
is much less calamitous if all you're trying to do is reproduce 
a given finite (!) training set - you have much more freedom to set 
things up so that there are "buffers" around the behavior you 
want to get, buffers which can absorb the noise.