X-Message-Number: 8639
From: eli+@gs160.sp.cs.cmu.edu
Subject: Re: CryoNet #8632 - #8635
Date: Mon, 29 Sep 97 13:08:02 EDT

>From: Thomas Donaldson <>
>Subject: Re: CryoNet #8631
>Date: Sun, 28 Sep 1997 16:47:44 -0700 (PDT)

>The reference is by HT Siegelmann, ED Sontag, SCIENCE (268(1995) 545-548).

OK, I looked through this -- not in detail, so I may be missing some
fine points.  Nor did I look for followup letters...

>It turns out that a neural net with real-number weights on 
>each connection cannot be imitated by a Turing machine. FULL STOP.

This analog-map model doesn't really involve real (infinite-precision)
numbers, i.e. it's not uncountably infinite.  (They formulate it using
reals, but they note that the infinite precision is superfluous.)  As
a result, it can be emulated with a TM -- at the cost, as usual, of
some time.  (No need to get fancy to make this claim: the brain's
parallelism would also take time to emulate on a serial machine.)

>The implication that our brain's neural nets might do some things
>impossible for a Turing machine bears a lot on the various
>controversies that have been going on in Cryonet.

Wait a minute.  The _Science_ article compares two mathematical
models.  This has no direct bearing on brains and computers.  (Much
less on the "various controversies"...)

The article calls the model "realizable", but I don't think that means
what it seems to mean (i.e. could you build a useful one?).  The model
requires unbounded precision, which is not available.  You may say
that the TM's unbounded tape space doesn't exist either, but there's a
difference: linear space requires roughly linear resources.  If the
world can hold the input for the problem, it can be convinced to yield
linear-sized working space.

Linear precision (which their model requires for a linear-sized job)
generally takes exponential resources.  If you want to place a point
on a line with 20 bits of precision in the presence of 1-mm noise, you
need 2^20 millimeters worth of line.  

If the authors can work around this, their model becomes more
interesting.  Of course, there are standard "digital"[1] unbounded-
precision models too, and guess what?  They're faster than TMs...
[1] the distinction really is meaningless for countably-infinite models.

-- 
     Eli Brandt  |  eli+@cs.cmu.edu  |  http://www.cs.cmu.edu/~eli/

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