X-Message-Number: 15326
Date: Thu, 11 Jan 2001 23:25:26 -0700
From: Mike Perry <>
Subject: Re: Turing Rides Again

From Thomas Donaldson's posting, #15300, cited by Joseph Kehoe (#15312):

>Hi everyone!
>
>Someone other than Mike Perry also seems hypnotized by Turing machines.
>He claims that a human brain could be imitated (if I read him right)
>by a single fast processor. While a very small brain could probably
>be imitated, it doesn't follow from that that much larger brains
>could be so imitated. The problem becomes exponentially harder the
>more neurons used. I would like to see his explicit calculations on
>this issue.
>...

Actually, the problem does not become "exponentially harder". A
3-dimensional cellular space (CS), with small cell size and rapid
propagation of signals, could probably simulate a brain in realtime,
including growth and/or atrophy of tissue as well as propagation of nerve
signals and other brain processes. Suppose we have an n-dimensional CS and
we start with active cells confined to a sphere of radius R, where our unit
of distance, say, is the radius of sphere enclosing a cell. (All cells in a
cellular space are assumed to be of uniform size and shape.) Then over time
t the number of cells that can become active is at most order of (R +ct)^n,
i.e. the volume of a sphere of radius R + ct, where c is a constant (c works
like the the speed of light in this case). The number of active cells, then,
is polynomial in time t, and it can be seen that the number of state
transitions must also be polynomially bounded, since each cell can only
undergo qt transitions in time t, where again q is some constant. This
means, of course, that a sequential processor could imitate the whole thing
in a polynomial time bound.

It's true that this whole argument might be challenged on grounds of quantum
computing, where more-than-polynomial-time computing seems possible, but
there you have an analogue of a universal Turing machine that keeps up with
any other device within a polynomial time bound. (See, for example, Seth
Lloyd's paper, "Universal Quantum Simulators," *Science* v. 273 pp. 1073-79
[23 Aug. 1996]). 

You could also argue that *even if* the time-requirement for the TM did
increase exponentially (as when it is imitating the so-called
"nondeterministic" TM that is able to manufacture self-replicating copies of
itself as it goes along) it can still carry out the simulation. Doing so, in
this case, would still be of philosophical interest though not necessarily
practical. So the upshot is that, *considered as a thought experiment, at
least*, the brain should be imitatable by a single, fast enough sequential
processor. I'm not sure why that point has been so hard to get across.

Mike Perry

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