[directional computation and surfaces] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
directional computation and surfaces
(Click here to view the original thread with full colors/images)
Posted by: Charles Matthews
I am not a mathematician and would appreciate any mathematical comments on these thoughts.
Computation proceeds in a direction. What has been explored in NKS relates to one direction CA computation over a background that is uniform and simply connected.
Computations that are repetitive and reversible can be made to do some interesting things. A simple computation that puts out alternating white and black cells can be arranged in a ring, of any length of a multiple of two cells. This gives you loops.
A lateral computation at each site, following the same rule. would give you an infinite tube, or a torus.
More complicated patterns that repeated could also fold up into loops with overlapping ends.
In general, it seemed to me that CA make contact with string theory very easily.
I can't be the first to have thought of this, so the observation is either incoherent or there's a lot of work on this I don't know about.
Posted by: Charles Matthews
OK, I am going to elaborate on my own post. I was interested in computation on surfaces because, besides just being a more general view of programs, this approach allows a natural emergence of objects. That is, when you generate a loop by wrapping repeating computations onto themselves, you have an "object".
Such objects, such as loops, would then be available to serve as building blocks for larger objects.
This approach seems to promise something which planar computing presently does not- namely, increasing density of forms, scaling, hierarchy. The computations a few levels up are composed of cells which, on a lower level, are composed of smaller objects.
Related to my other post, it might be possible to define the surfaces by collision rules- that is, if two computations are started at separate areas on a plane, the manner in which they continue to compute when they collide (say, related to the angle of impingement) might be essentially the information about a surface- as if the surface were projected onto the plane.
I am hoping someone out there with a mathematical background could offer some criticism of this idea.
Posted by: Jason Cawley
"Computation proceeds in a direction."
A computation is in general a mapping from some system state to another system state. If a rule is to be applied repeatedly, which is what we usually mean by a simple program, then the subsequent system state must be such that the same rule can still be applied to it. But that is all.
You can say that any such repeated mapping defines a direction of the mapping arrows, a -> b -> c, I suppose. The simple case takes any preceding state to a unique subsequent state. But multiway systems ease that property.
To be reversible, a special case, the mapping needs an inverse, which need not be the same rule, but must again take each system state to something the rule can again be applied to.
Without a requirement of reversibility, general mappings can meet the requirement of providing subsequent states to which the rule can still be applied, with many-to-one behaviors. That is, each future state need not have a unique past.
The computational idea is not at all restricted to one D cases like the 256 elementary CAs. See chapter 5 of the NKS book on "2 dimensions and beyond", for example. Nor is the built in structure of cells in a regular grid necessary. Easing each of the elements of built in structure in elementary CAs, one by one, is the theme of chapter 3 "the world of simple programs". A network rather than a CA is suggested in chapter 9 for fundamental physics, precisely because a CA would have too much built in structure, while a network does not.
It is true that anything repeatedly applied can be thought of as involving time-slices, and thus as leaving a trail of previous states. But we display that for our own comprehension, tracing the behavior of the rule over a succession of steps. The rule itself does not in general look back beyond the previous step (though rules of that type can also be examined, e.g. in recursive functions).
Typical 2-D CA displays do not try to show their past behavior, since it would interfer with display of the present system state. Fading grey can be used to mix some of both in the same display, as a convenience. But basically you watch the 2-D display evolve like watching a movie, rather than reading time down the page as with 1-D CAs.
You can also vary the treatment of edges in systems of definite size. You can treat anything beyond the initial edges as empty, you can allow a pattern to expand beyond those edges or not, or you can "wrap" the system to itself with a "cyclic" boundary, where the rightmost cell of a 1-D CA is treated as the left-hand neighbor of the left-most cell e.g. This effectively gives a ring. With 2-D cases you can wrap one boundary to get a cylinder with two edges, or 2 to get a manifold without boundary.
Nothing in a rule itself specifies the geometry of the relation of the elements. The rule says what happens on the next step based on elements at a previous step, including some interrelation of those elements, typically local but in principle any relation. The form of the rule may require some structure to be well defined - an elementary 1-D CA needs "neighbors" to make sense. But that is all.
At the NKS 2003 conference, Seth Chandler presented a display and gave a talk about his implimentation of elementary CA rules on regular graphs rather than an array of cells laid out left to right. (Part of the motivation was that arbitrary graph relations seemed to him more likely to apply to general social science problems than ordered locality on a grid).
A regular graph is one in which each node is connected to the same number of other nodes. Using a regular graph with 3 connections for each node, he could take those connections as the neighborhood for a CA rule. Since there is no notion of "left" vs. "right" on a regular graph, he considered totalistic rules that get the value at the next step by adding values from the previous neighborhood. Which are therefore well defined on a regular graph with 3 connections per node.
Without the "down the page" time structure of 1-D CAs, he displayed his results as a movie of changing values at statically displayed nodes - "blinking lights" over time.
The point is there is nothing restricted to the topology of a linear layout about the idea of computation. It is in principle as general as any well defined mapping.
I hope this helps.
Posted by: Charles Matthews
"Nothing in a rule itself specifies the geometry of the relations".
Networks can model space curvature. Are you saying that general surfaces whose curvature is sufficient to produce a closed geometrical object cannot be modeled in CA that use small neighborhood rules?
Thanks for your reply
Posted by: Jason Cawley
"Networks can model space curvature."
Yes. An arbitrary network can have any sort of geometry, any tangle of self-connectedness. It can, if you like, look like a bad wiring diagram. Or something simpler. That it is a network doesn't specify, one way or the other.
So you can take the geometry involved in ordinary space - or curved space - and mirror those geometric relations in relations among network nodes. This is not because of a particular kind of structure built into all networks, it is because there is a particular structure built in to space, as we typically understand it.
That is, in space, each point is closer to fewer points than the number at some longer distance according to a definite relationship in growth of neighbors with distance. You notice this property in space. You isolate it. You can then deliberately set up a network to have that property. When you do so, you are exploiting the generality of networks, how little they have built in, rather than how much.
"general surfaces whose curvature is sufficient to produce a closed geometrical object cannot be modeled in CA"
In networks, because they are flexible enough it should be straightforward. CAs are much more structured than networks. But there are some closed geometrical objects that are easy to put a CA rule on. An example is a ring (adding the time dimension, a cylinder).
Most of the actual random initial condition experiments in the NKS book were done with "cyclic" boundary for the CAs. Meaning, the right most cell acts as the left hand neighbor of the leftmost cell. This effectively wraps the line of cells onto a ring. The pictures down the page, showing the time dimension, are thus on cylinders. You can often see this e.g. when some structure runs "off the page" on the right, and appears on the left.
The point of my overall comments was that the amount of geometric structure to build into a particular kind of rule is quite up to you. There is nothing about the NKS approach that is "married" to only one geometric layout of elements, in principle.
The most extensive work has certainly been done on 1-D cases, because they are particularly easy to see (including their time evolution), and behind those on 2-D cases. Often on regular grids, though not always. But this is simply a matter of starting simple because one can already see interesting stuff there.
The approach is not tied to it. The simple program idea is in principle as general as any general mapping from a system to itself that you can do repeatedly. Which mathematically speaking means some slight requirements (like not collapsing the number of dimensions at each step), but is very general.
Posted by: Charles Matthews
Jason,
I apologize for not being clear. I understand what you are saying about the generality of local rules and their applications to space curvature.
I am trying to understand in general how to think about objects and surfaceswith NKS. And I think what I a trying to ask is not about local curvature, but about global connectedness. I understand you to be saying that the global topology is extrinsic to the local program and the curvature generated in locl network relations.
I am understanding you to say that the planar printout has no information about the global connection- whether, for example, you decide to do this on a plane or a cylinder. So, for example, if you wanted to show a cylinder, you would have to add some large neighborhood rule about large scale connection which is equivalent to specifying that the printout will be cylindrical.
If one had an ongoing computation of an elementary 1-d CA on a flat plane, and consider the various ways that plane could be globally folded- say, into a cylinder- it seemed to me that the output of those "collisions" areas would encode a pattern that specified the global topology. That is, when looking at the planar display of a 1-d CA, the information specifying (not just the curvature but) the global topology is there.
Perhaps I want to say that given the right intial conditions, the planar output of a 1-d CA encodes information equivalent to a higher dimensional shape. Or- that somewhere in a universal planar CA there is information equivalent to all possible global topologies.
Just thinking about universality, it may not be necessary to hope for progressive density of the appearance of complex features, when a patch of apparently featureless output of a 1-d CA may be equivalent to a very ordered higher dimensional object.
Since my mathematics is limited, I apologize for beating this horse, and I really appreciate your time with this line of questions. When I look around, I see programs impinging on programs- there is too much density of forms around here for NKS to reach this for me yet. Kidneys, brains, skin pigmentation, all these things play out simple programs- but the regularity is too dense, it looks like programs impinging on programs. Biological growth, as you know, is typically limited by some physical constraint. It isn't satisfying to say the human body, and the assembly of humans around us, must be some rare event out somewhere on a universal CA; in a way this explains nothing, like looking for the right shell on an infinite beach. So an account of the ways in which patterns impinge on patterns, or how patterns might reach constraints under some form of packing, seems important to me.
Could you comment?
Posted by: Jason Cawley
Your last is completely unclear.
"the output of those "collisions" areas"
What "collision areas"? What's a collision?
If you specify some folding on the 1-D layout of elements, then of course you get the elements laid out with that global interconnection.
CAs have defined adjacency. It is the only built in geometric relation. There is a primitive concept of "next to". What results from all of the "next to"s linked together, is some overall structure. That overall structure does not depend on the particular CA rule. It is a larger scale relationship among the elements in which the CA acts. It can be anything.
The particular CA rule type tells you how many adjacents an element has, up to some range away, that make a difference for that element at the next step. This is not enough to specify an overall shape to the elements. There are any number of overall shapes of the elements compatible with any give rule type. One set of network connections can give 1-D, another 2-D, etc.
If you specify the overall shape of the elements (ring, cylinder, etc) then you can see what effect it has on the development of the rule, certainly. You can't read a shape out of a rule type (e.g. "trivalent network" or "self plus 2 neighbor CA") - there are too many of them "allowed".
If you mean tracing out the "emergent" interconnection seen in a particular case (not rule type, or even rule, but those plus initials and a number of steps), then maybe I can see what you mean. You do still have to specify the arrangement of underlying elements - line or ring e.g. But you can then ask about regions in the results rather than cell layout. E.g. Rule 254 from a single black cell, on a ring, gives 2 pieces, one white and one black, until the black extends and takes over the whole ring. On a line it instead gives 3 pieces, white black white. This is looking at a structure in the output.
Can you explain what you are after with the simplest possible example(s)? Leave kidneys and curvature aside, and just talk simple 1-0 finite element cases.
Posted by: Charles Matthews
Rule 254 with the same initial condition gives one output on a line and another on a ring.
Suppose you are looking at two outputs, one white-black-white, the other all black.
I'm saying that a white-black-white background is a rule 254 initial condition black expression for a line, and that an all black background is a rule 254 initial condition black expression for a ring.
And I find the observation that there is an equivalent to spatial topological information in these two planar backgrounds interesting.
I'm not sure whether there is something I simply don't understand here, or that you don't find the observation interesting because it yields information only in trivial cases which are so narrowly defined.
Thanks for your reply
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings