newbie question: why are CAs only always defined on a lattice?
Harald Kirsch
cafaq.com, I find the automaton is defined
on an n-dimensional lattice. I gather the local
update function takes into account the
neighbours of a cell in the lattice which are no more
than r steps away.
Consequently the number of neighbours depends
on the dimensionality of the lattice and the choosen
radius r.
Question: Would it be possible to get rid of the
lattice structure and the dimensionality and just
require a "homogenous" (see below) graph where each
node has a given number of k direct neighbours.
With "homogenous graph" I mean a graph which looks
identical from every node --- and I am not sure if
this really covers what I mean.
Question: Do such infinite graphs exist, or do they
only exist for certain k? Well, for k=4 we take
a 2-dimensional lattice, for k=6 take three dimensions
or a hexagon partition of the plane. What about k=5 or
any other arbitrarily chosen number?
Question: Does the homogeneity requirement perhaps
necessarily lead to a lattice and an associated
dimensionality?
Any hints appreciated,
Harald Kirsch
Disclaimer: If this gets posted twice,
Google tricked me with an internal server
error. Sorry.
Tim Tyler
> Looking up the definition of a cellular automata at
> cafaq.com, I find the automaton is defined
> on an n-dimensional lattice. I gather the local
> update function takes into account the
> neighbours of a cell in the lattice which are no more
> than r steps away.
>
> Consequently the number of neighbours depends
> on the dimensionality of the lattice and the choosen
> radius r.
>
> Question: Would it be possible to get rid of the
> lattice structure and the dimensionality and just
> require a "homogenous" (see below) graph where each
> node has a given number of k direct neighbours.
>
> With "homogenous graph" I mean a graph which looks
> identical from every node --- and I am not sure if
> this really covers what I mean.
>
> Question: Do such infinite graphs exist, or do they
> only exist for certain k? Well, for k=4 we take
> a 2-dimensional lattice, for k=6 take three dimensions
> or a hexagon partition of the plane. What about k=5 or
> any other arbitrarily chosen number?
>
> Question: Does the homogeneity requirement perhaps
> necessarily lead to a lattice and an associated
> dimensionality?
Cellular automata are (by definition) "spatialised".
The historical name for something which *acts* like
a cellular automaton - but has no map onto an
n-dimensional space - is "graph automaton".
Graph automata are the more primitive, fundamental
and important concept (IMO).
I wish the (attractive) term "cellular automata"
*actually* meant what "graph automata" means.
However history currently says that it doesn't :-|
While a CA's map onto an n-dimensional space is
totally irrelevant to the dynamics of the resulting
system, such a map /does/ have some positive aspects.
In particular, it can sometimes help people visualise
what's going on.
However I do think it is mostly irrelevant:
The dynamics are the important thing. The map
onto an n-dimensional space is mostly fluff.
I think it's rather unfortunate that graph automata are
the ones that wound up with the inferior name - and that
cellular automata wound up getting more of the limelight.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
daniel B miller
>>Question: Would it be possible to get rid of the
>>lattice structure and the dimensionality and just
>>require a "homogenous" (see below) graph where each
>>node has a given number of k direct neighbours.
>>
> The historical name for something which *acts* like
> a cellular automaton - but has no map onto an
> n-dimensional space - is "graph automaton".
>
> Graph automata are the more primitive, fundamental
> and important concept (IMO).
>
around, and is interesting (I believe there were some pointers here to
CA's on amorphous lattices recently). The problem I see is that if the
topology is non-trivial, it becomes relevant information that needs to
be dealt with somehow.
Any parallel automata system can be described using these three variables:
(1) the rule that each cell follows
(2) the initial conditions
(3) the connections between cells
In traditional CA's, (3) is always the same, and contains little
information itself. However, in the more general graph case, (3) could
easily contain most of the relevant information that makes the system
behave as it does (ie, the wires between transistors are what makes a
computer what it is). Why stop at the point where the topology is
fixed? We could add the idea that the topology itself is subject to
change, based on the state of affairs at a given time step (Nova Spivak
posted something about this on the old yahoo dp site).
Another problem with generalized graph automata is that you need
something on the order of log(N)*N bits to describe the connections,
where N is the number of cells. Log(N)*N doesn't grow too fast, but if
N is infinite, log(N) is too -- each cell has infinite state! So we're
now limited to describing finite spaces; we can't easily envision an
infinite grid when we need all these address bits to describe the
interconnections.
One can envision tricky things like pseudo-random patterns of
connections that have interesting topologies but don't use up alot of
information (projections from higher dimensional spaces, ala Penrose?),
or connection distributions that favor 'nearby' cells and use some sort
of compressed encoding -- but all of this simply makes the analysis much
more complicated. I think the core appeal of CA's is their simplicity;
adding the complexity of non-standard topologies kind of goes against
that grain.
-dbm
Tim Tyler
> >>Question: Would it be possible to get rid of the
I didn't intend to refer to non-standard topologies (though certainly
graph automata allow this).
What I meant was what might be referred to as a "uniform graph automata" -
where the network topology looks the same from each node's perspective.
This is exactly equivalent to a CA in terms of its behaviour - but no
map onto cells of a particular shape is specified - all that is specified
is the network topology - and there's no map onto an n-dimensional space.
Harald Kirsch (the OP) also made it clear that this is what he intended:
``With "homogenous graph" I mean a graph which looks identical from every
node''.
Harald Kirsch
>
> I think it's rather unfortunate that graph automata are
> the ones that wound up with the inferior name - and that
> cellular automata wound up getting more of the limelight.
I stumbled over the spatialisation when I read that
cellular automata might be fine as a model for
discrete physics. Although I understood from one of
Fredkin's texts that topology of the automaton does not
necessarily reflect the topology of space, a discrete
space immediately seems to force upon us the question
of its neighbourhood topology.
So even if the automaton describing space has a
different topology, I ask: what is the topology of
discrete space. I find myself forced to conclude that
there are discrete cells and that for the benefit of
motion/communication between cells, there are
neighbouring cells --- hence a graph.
Questions:
A) Can discrete space described differently
than as a graph?
B) If it is a graph and we assume sensible
homogeneity, which neighbourhood relations
are possible?
Certainly this was written down already somewhere.
Any hints appreciated,
Harald.
Tom Knight
and arbitrary high dimensional graphs. Regular lattices with
imperfections (dislocations) have many intriguing properties --
specifically a relationship between point, line, and surface defects
and the "curvature" properties of manifolds. Interesting conservation
laws (pair production, e.g.) arise when thinking about growth of
crystals with dislocations.
daniel B miller
...
>
> I didn't intend to refer to non-standard topologies (though certainly
> graph automata allow this).
>
> What I meant was what might be referred to as a "uniform graph automata" -
> where the network topology looks the same from each node's perspective.
>
> This is exactly equivalent to a CA in terms of its behaviour - but no
> map onto cells of a particular shape is specified - all that is specified
> is the network topology - and there's no map onto an n-dimensional space.
>
> Harald Kirsch (the OP) also made it clear that this is what he intended:
>
> ``With "homogenous graph" I mean a graph which looks identical from every
> node''.
m'kay -- I realized after I made my post that I was referring to
something more general -- and I reread the OP and got that the idea is,
the graph looks the same from each cell; not an arbitrary set of
connections between cells (that's one for a future thread.)
This boils down to the question: what kinds of 'homogeneous' graphs are
possible, and how do they differ from N-dimensional lattices (which I
take to be a subset thereof)?
My instinct is that most graphs of this sort, especially if they are
unbounded, would have to be lattice-like, and will tend to map nicely
onto a lattice with integer dimensionality. I visualize them as having
somewhat more complex neighbor relations than a simple lattice, but on a
large scale their topology will tend to have significant extension only
in a specific number of dimensions.
I am very curious to see some counterexamples to this assumption.
Perhaps something of a fractal nature?
BTW IIRC Wolfram touches on something like this in his physics chapter.
-dbm
Tim Tyler
> Questions:
> A) Can discrete space described differently
> than as a graph?
> B) If it is a graph and we assume sensible
> homogeneity, which neighbourhood relations
> are possible?
>
> Certainly this was written down already somewhere.
> Any hints appreciated,
Fredkin has a "wishlist" for his CA at:
http://digitalphilosophy.org/digital_philosophy/29_quarks_and_color.htm
We can specify things like reversibility and computation universaility -
but placing constraints on network topology is harder - besides some
obvious things - such as the abitily to propagate signals in all
directions.
Large-scale spatial isotropy suggests that a structure with a fair degree
of symmetry might be good.
Physicists currently suggest that the universe has at least some eleven
dimensions. I figure any cellular medium supporting it is fairly likely
to have at least that number of dimensions.
Tim Tyler
> Tim Tyler wrote:
> > I didn't intend to refer to non-standard topologies (though certainly
> > graph automata allow this).
> >
> > What I meant was what might be referred to as a "uniform graph automata" -
> > where the network topology looks the same from each node's perspective.
> >
> > This is exactly equivalent to a CA in terms of its behaviour - but no
> > map onto cells of a particular shape is specified - all that is specified
> > is the network topology - and there's no map onto an n-dimensional space.
> >
> > Harald Kirsch (the OP) also made it clear that this is what he intended:
> >
> > ``With "homogenous graph" I mean a graph which looks identical from every
> > node''.
>
> m'kay -- I realized after I made my post that I was referring to
> something more general -- and I reread the OP and got that the idea is,
> the graph looks the same from each cell; not an arbitrary set of
> connections between cells (that's one for a future thread.)
>
> This boils down to the question: what kinds of 'homogeneous' graphs are
> possible, and how do they differ from N-dimensional lattices (which I
> take to be a subset thereof)?
The graph which is equivalent to a hexagonal CA has may maps into
real spaces. You couldl map in onto haxagonal cells in 2D.
Or you could map it to a rectangular lattice - with a neighbourhood like:
. . . . .
. . O O .
. O X O .
. O O . .
. . . . .
You could also map it into a 3D space.
A "regular" graph can also represent a finite torus. In the real world,
cells on the surface of a doughnut are different shapes at different
locations - but in the graph all nodes would be the same.
I think you are right in suggesting that there maybe some "infinite"
fractal graphs with the property in question. I don't have time for an
ASCII diagram - but the "golden ratio" rectingle - there you can cut off a
square and still leave a piece the same shape as before - provides an
example - if you draw lines rather than cut, extend "up" to infinity as
well as "down" - and work in a consistent direction to produce a spiral.
The result is a bit like a nautilus shell with a log spiral. Zoom in and
rotate - and things look much the same.
daniel B miller
> The graph which is equivalent to a hexagonal CA has may maps into
> real spaces. You couldl map in onto haxagonal cells in 2D.
>
> Or you could map it to a rectangular lattice - with a neighbourhood like:
>
> . . . . .
> . . O O .
> . O X O .
> . O O . .
> . . . . .
>
> You could also map it into a 3D space.
>
two-dimensional, period. While a 3D cubic lattice can also be thought
of as a graph with each node connected to six other nodes, the nature of
the connections is totally different.
-dbm
daniel B miller
> Fredkin has a "wishlist" for his CA at:
>
> http://digitalphilosophy.org/digital_philosophy/29_quarks_and_color.htm
>
> We can specify things like reversibility and computation universaility -
> but placing constraints on network topology is harder - besides some
> obvious things - such as the abitily to propagate signals in all
> directions.
>
> Large-scale spatial isotropy suggests that a structure with a fair degree
> of symmetry might be good.
>
> Physicists currently suggest that the universe has at least some eleven
> dimensions. I figure any cellular medium supporting it is fairly likely
> to have at least that number of dimensions.
Perhaps, but those extra dimensions are likely to be 'curled up', ala
String theory. Imagine a glider in a world like that -- it might only
have one 'speed', but depending on the exact direction it moves, its
progress in the macro-observable dimensions will appear to be slower.
It would seem, depending on the topology, you could have gliders with a
wide variety of possible motions.
-dbm
Tim Tyler
> Tim Tyler wrote:
> > daniel B miller <dan...@cmu.edu> wrote or quoted:
> > The graph which is equivalent to a hexagonal CA has may maps into
> > real spaces. You couldl map in onto haxagonal cells in 2D.
> >
> > Or you could map it to a rectangular lattice - with a neighbourhood like:
> >
> > . . . . .
> > . . O O .
> > . O X O .
> > . O O . .
> > . . . . .
> >
> > You could also map it into a 3D space.
>
> no, I don't think so. The topological nature of this lattice is
> two-dimensional, period. While a 3D cubic lattice can also be thought
> of as a graph with each node connected to six other nodes, the nature of
> the connections is totally different.
You can map a 2D lattice into a 3D space. I do it every time I project
a 2D CA onto the surface of a CRT. There are also space-filling maps -
in this example each cell could be the shape of a very long hexagonal
pencil.
The underlying graph is the same in all cases. However while the graph
may /suggest/ a particular map onto an n-dimensional space, it doesn't
/enforce/ any particular one - and typically very many such maps
are possible.
Plamen Petrov
Harald Kirsch <pifp...@gmx.de> wrote in message
news:16990fa4.04082...@posting.google.com...
Harald:
please check out my paper:
"Non-Replicative Fredkin's Rules in Homogeneous Cellular Spaces", In:
T.Toffoli, M.Biafore, J.Leao (ed.), PhysComp96 (Proceedings of the Fourth
Workshop on Physics and Computation), New England Complex Systems Institute
(1996).
You can download the full text + figures (as a single zipped pdf file) from
here:
http://www.digitalphysics.org/Publications/Petrov/Non-Rep/Non-Replicative.pd
f.zip
I am sure you will find a lot of interesting info there that answers your
questions concerning "CAs on homogeneous graphs".
With best wishes,
---
Plamen Petrov
http://www.digitalphysics.org