Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!topaz.rutgers.edu!brandx.rutgers.edu!webber
From: webber@brandx.rutgers.edu (Webber)
Newsgroups: sci.philosophy.tech
Subject: Re: Complexity and Philosophy
Message-ID: <245@brandx.rutgers.edu>
Date: Sun, 31-May-87 03:02:20 EDT
Article-I.D.: brandx.245
Posted: Sun May 31 03:02:20 1987
Date-Received: Tue, 2-Jun-87 01:19:42 EDT
References: <19071@ucbvax.BERKELEY.EDU> <8705291501.AA12310@brahms.Berkeley.EDU> <634@uwm-cs.UUCP>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 121
Summary: The quest for a pocket-sized universe
To: webber


[Two replies, the first is to the following from Matthew P Wiener 
(ucbvax!brahms!weemba)]

>  An example: even though physics might be
> boiled down to automata theory some day, I fail to see how "time" would
> mean anything to such low-level calculations.  If wave-function collapse
> or what have you is an exponentially hard, or even non-recursive computa-
> tion--that seems perfectly reasonable to me.  We need never notice, be-
> cause of renormalization.

If one thinks of the universe as a state description, then the
automata that models it would be defined:

    Let S be the set of all state descriptions.
    Introduce a directed graph that has elements of S as vertices and
     each vertex s1 has one outward pointing arc indicating the state s2
     description that follows s1 after one time unit.
    Distinquish a start state, s0, as the `beginning of the universe'.
    Introduce an `interpretation rule' that a computation consists of
     moving from one state to the next.

Such a model gives us a perfectly reasonable infinite automata
representation of the universe.  Given that we have a way of
determining what `state' the universe is in and how many time units
have passed, it even gives us a predication as to what `state' the
universe should change to.

However, such a description of the behavior of the universe is a bit
large to keep in one's pocket, so we impose some structure and hope
things will work out.  Let p(n,s) denote the nth piece of the state
descriptor s.  We then make a locality assumption and claim that for
each n, there exists a set N' such that p(n,s1) is a function of
p(N',s0).  From this, we introduce the notion of a parallel automata
computing the universe.  At each step, each part of the state vector
is computed simultaneously.  Someone in a universe that could be
represented this way would probably not directly percieve this
structure.  However, someone who lived in a universe that could not be
represented this way might conceivably notice that predictions based
in this model never worked out.  How much along these lines they could
observe would depend on the universe in question.

However, this description of the universe is still too large to fit in
one's pocket.  Next we introduce a finiteness constraint, i.e., for
each n, the associated N' is finite.  Now we can carry around in our
pocket the description of one small piece of the universe, however,
the whole universe could still allude us.  However, we have gained the
ability to observe a finite portion of the universe and then predict
what state some other finite portion of the universe will assume.

What we need is a way of determining N' for any given n.  Also, you
might have already noticed that once we have N', we will need a way of
determining p(N',s0).  To have a `way of determing' something
formalizes into the notion that there is a computable function that
calculates that something.  Loosely, the function connecting n with N'
defines what we think of as the geometry of a universe and the
function that simulates p corresponds the the physical laws of that
universe.

One aspect of computability is that the person doing the computation
will exist in the universe being simulated.  Thus these functions must
define a system within which they themselves can be defined (under
suitable mappings).  From this we observe that in order to understand
the universe, it will be useful to figure out what functions can be
implemented within the universe.

A second observation is that it really doesn't matter if a description
of the universe can fit in one's pocket unless one can `understand' it in time
to make some use of it (such as verifying a prediction).  This
introduces the question of the complexity of the relevant computable
functions.  Complexity is not a direct measure of the rules of a
universe, but rather an investigation of how the rules could be
evaluated by an observer within a system that follows those rules.

> Or are you proposing a computational complexity implementation of Occam's
> razor?

Well, given that whatever set of rules you choose to use, you will
have to evaluate them in order to check them, one might as well begin
with the easy ones.  Of course, there is no guarentee that one of the
easy ones will work, just as there is no guarentee that the universe
has any of this structure.  However, it would appear even less
productive to assume that the universe is not totally understandable.

[and then to reply to the the reply to the above discussed message
from Matthew Wiener sent by B. Litow (litow@uwm-cs.UUCP)]

> I doubt very much that physics is reducible to automaton theory because I
> do not believe that automaton theory is reducible to itself. By that I 
> only mean that we cannot understand automata behaviors in a purely
> combinatorial way. 

Here we are moving yet another step further and saying that there are
actually very few automata models that we know how to analyze from a
global point of view.  However, at least these models give us clear
predictions at a local level.  We have not really been working on the
problem of global analysis long enough to know whether or not it is a
`real' difficulty or just a temporary lack of insight.

>The wave function collapsing mentioned in a previous
> posting (included above in part) is apparently widely believed but in
> 'secret'. 

This is a fascinating secret.  It has been revealed and yet I still
don't know what it is.

>Because of the way in which I define computer science this notion
> is disturbing to me. I should say that I 'sort of' believe it. CS is the
> working out,largely mathematically as in physics,of the consequences of
> assuming Church's Thesis. ...

Computer science (perhaps we should call it Computability Science) is
not restricted to studying the ramifications of Church's Thesis.
Church's Thesis is just the currently most productive hypothesis being
investigated.  There are many other possibilities, such as stochastic
automata.  However, it will probably be days before we know the
answers to all the questions of the universe.

---------------------------- BOB (webber@aramis.rutgers.edu)

     I never metaphysics I didn't like.
                                         Anonymous