Relativistic automata continued

Previously I covered some ideas about fractal automata and extending it to a kind of relativistic version. I'll summarise this then describe some thoughts on extending the system to be more relativistic.

translation

Starting with simple cellular automata, like conway's game of life, we generalise it by saying that the function acting on each cell (which chooses whether to turn the cell on or off) can be any function of n nearest neighbours. Typically we pick some small set, like the 9 neighbours in a 2d grid (including the centre one). Giving 2^n possible neighbour patterns and 2^2^n possible functions. The choice of function isn't too important here, what is interesting is the type of results you get by searching through the set of functions as applied to initially random data.

scale

We can expand this system to fractal cellular automata by using a grid tree rather than a single grid, the nearest neighbours for each cell include those on the parent and child grids as shown here:

The coloured cells being example nearest neighbours of the red cell. Typically you watch the highest detail grid evolve. This system effectively gives you a continuous euclidean space, which is more physically real than a discrete grid.

non-uniform scale

These grids can be 3d too, or even 4d. But to deal with time properly we need to use a Minkowski 4d space rather than a euclidean grid. It can be approximated by making the time axis the long diagonal of the 4d grid and allowing non-uniform scales, i.e. cuboid grids. So just as scale becomes like an extra degree of freedom in fractal automata, we let scale in x, y and z separately become three extra degrees of freedom. As discussed in my previous post. The non-uniform scale allows the same rules to apply at different velocities, which are represented by the different non-uniform scales.

At this point there are actually two ways that you can work with time here, you can make the cellular automata only depend on cells that are further back in time, which means that the automata spreads forwards along the time direction:

Or you can keep the cells dependent on all the neighbours (both forwards and backwards in the time direction). This means that a whole span of time evolves as you iterate the automata. This second method has three possible outcomes:
1. The evolving automata converges on a fixed result. This can then be 'played' as a single time line.
2. The automata ends up in a cycle, so no single time line exists, but you could consider each result as being parallel time lines.
3. The automata doesn't settle into a cycle (so is a strange attractor). This has some similarities with the many-universe interpretation of quantum theory, since there are infinite time lines, describable by a probability density function. So any of the time lines is a valid result, after it has converged.

symmetric sheer

The next step is to allow a diagonal stretch of the grid. This corresponds to information which changes more or less slowly with time:

This feature is part of general relativity, time is more dense close to high mass objects. This change in the 'speed of the physics' is what causes objects to fall under gravity. It hasn't been tested, but the idea is that moving points will deflect into the higher density areas, causing something vaguely like gravitation.
This extension has some problems which require a further addition to solve; the stretched grids have a different apparent maximum velocity, inconsistent with the real world.

I have headed the sections in this post to show the different symmetric transforms that each algorithm adds to the system. Continuing this theme and generalising, a square cell can be transformed by any transformation matrix. So there are a few remaining degrees of freedom that can be added as extra symmetries:

rotation

If the path of massive objects is allowed to rotate with time (as opposed to a boost, which is the non-uniform scale above) then the object will be able to attain just as high speed as a light object, which is physically real. However it doesn't appear to obey special relativity since the rotation could make any object go faster than some maximum (light) speed. 

I think the way this is avoided is that the frame that we visualise is the square (not uniformly scaled) frame, and the frame of heavier objects is 'ghosted' onto this square frame, just as low resolution objects 'ghost' onto the high resolution mesh that we view. The ghosting process prevents the object going faster than light since it can't ghost beyond this speed.

This is again a bit speculative, but it seems that the movement of a high mass (stretched) grid can only change direction over a longer period of time, in other words its acceleration should be less in general, and would be symmetric to higher acceleration in a lower mass object.

non-symmetric sheer

The final degrees of freedom are non-symmetric sheering of the cell. This relates to symmetric sheer much as pressure relates to mass or energy in general relativity I think. So for a 4d space-time, the general transform would be a 4x5 matrix, giving 20 dimensions to the cellular automata.

dealing with scale problems

The problem with using symmetric scale for mass is that the stretch only jumps by some fixed factor, like two.

Similarly, the problem with using rotation with time to give a mass a velocity is that grid-based cellular automata can only rotate by 90 degrees. 

The solution to such problems might be to treat the scales (which are the rows of the 4x4 matrix) the same way as position is treated (the 5th row), i.e. use the overall scale to allow each row to be continuous. 

I'm not sure how well this idea works, so this problem leads to a completely different formulation that I will discuss in the next post.

Summary

Space-time is usually thought of as a 4d continuum of points, something which could be naively modelled as a 4d grid cellular automata. 

Instead, if we think of space-time as built of 4d volumes then the description of such volumes which is independent of any reference frame is one which is symmetric to any 4x5 transform. This is quite similar to the principles of special and general relativity. Such a 20 dimensional automata could potentially have the following extra realisms over basic cellular automata:

1. It is continuous

2. parts can have velocity

3. nothing goes faster than light, time dilation etc of special relativity
4. many-world timelines, consistent with some quantum effects

5. mass affecting how fast something accelerates
6. gravitational wells (general relativity)

7. attraction based on pressure (also part of general relativity)

Quaternions aren't rotations

Recently I discussed the difference between unit intervals and integers. Unit intervals are kind of the complement or the opposite of integers, they represent the whole space between each integer, and you could say that they represent the full transition between each consecutive integer.

This is relevant because I was recently reading about the spin group Spin(n) and the special orthogonal group SO(n). The special orthogonal group can be thought of as an n dimensional rotation matrix and the spin groups are spinors which kind of represent rotations as well, but have the confusing feature that you need to travel 720 degrees to return to the same spot. The 3d spinor is the same as the quaternion.

Spinors are confusing, as illustrated by Michael Atiya (from the Wikipedia article on spinors):
"No one fully understands spinors. Their algebra is formally understood but their general significance is mysterious. In some sense they describe the “square root” of geometry and, just as understanding the square root of -1 took centuries, the same might be true of spinors."

It dawned on me that spinors are to the rotation matrices what intervals are to the integers. Spinors are the full set of configurations between two rotation matrices. So they do not represent attitudes (orientations) themselves.

Looking at the 3d example, the attitude of an object is its 3x3 rotation matrix. If you attach that object by many elastic strings to a reference frame (like to the walls of the room that it is in) then the 3d spinor (which is a quaternion) represents the configuration of the strings (which do only repeat after a rotation of 720 degrees of the object). 
So in this example the rotation matrices are the object and the room, and the quaternion is the strings. It is a full path (or interval) between two rotations, which is quite different to a relative rotation matrix.

To rotate a vector v by a spinnor s, you do: s' * v * s. Same for rotating a rotation matrix by s.
The reason for the double operation (which also explains the double cover) is easier to see if you convert back to the integer and interval analogy:


Integers are just points, which really convey no size. In order to add 1 to an integer, first you must append a unit interval from the integer (think of laying down a metre rule from that point), then you must append the point to the other end of the unit interval, so you are doing the first operation kind of in reverse. 
In fact, for any vector you can move to a different vector position by laying down a straight line (an interval) from the first point, then placing the new vector at the other end of the line.
This two-stage symmetric operation can be defined as s' * v * s.


So in fact, basic arithmetic and vector operations can actually be done using these two complementary objects (the point and the interval), we just don't usually think of it that way as we have a simpler system of adding only vectors. But this two object system is exactly what is required for operations acting on orientations.

Adding some relativity to fractal automata

A previous post described fractal automata, which are just like other cellular automata but they also include scale as effectively an extra dimension.
Here's how to add the main component of special relativity to these fractal automata.

Consider the case with one space dimension and one time dimension. Classically we could uses a 2d grid to discretise in time and space. For special relativity (Minkowski space) we rotate this grid 45 degrees...
Now consider the black square in the centre of the diagram above. An equivalent square directly below it would just touch the axis origin so be visible at time zero. This below square has the black square as its neighbour, and so if its update rule turns the square on when its neighbour is on then this piece of space will continue to propagate through time.

The diagonal rectangles represent squares that have a velocity. Each one has the same volume and each one's diagonal point the the origin, so they are all objects that will hit distance 0 at time 0. The way to represent these in the cellular automata is to have separate grids for each power of two on each axis. The cellular automata rules can then act on neighbouring velocities as well squares in neighbouring space.
If we draw a grid of the possible scales then we can see that, in addition to its spatial neighbours, each pixel has several scale neighbours:

The mapping applied to each rectangle must be the same at every position on this grid.

The neighbours seen as black arrows are squares that have a velocity, and the neighbours in green are smaller and larger scale versions of the square. In other words, we already use the uniformly scaled neighbours, that is what makes it fractal automata rather than normal cellular automata, we are now just incorporating non-uniform neighbours. 

Amazingly this is all that is needed to allow for special relativity's space-time geometry, time dilation etc, and it allows cellular automata to act on objects with a velocity, without any particular privaleged velocity. The rules are velocity independent. Though I can't show an example as I haven't built any yet.

2D

In 2 dimensions things get trickier. We can't just rotate our grid by 45 degrees. There may be other solutions but my solution is to use a 3d grid and have the time axis as the long diagonal. Squares can then be elongated along three different axes, which equates to different diagonal motions of the object when the axes are different, and it equates to different size objects when they are the same. 

It approximates the light cone by a triangular pyramid.

3D

This is an extension of the 2d approximation, you use a 4d grid and have time as the long diagonal. The expanding light sphere is approximated by an expanding tetrahedron. 

Intervals vs integers and why computers can't count

Counting
It struck me the other day that computers don't count that well and that there is a probably better form of binary.

Above shows the points where each bit flips as we count upwards from zero, giving our well known 0000 0001 0010 0011 0100 etc.

For an arbitrary length number this isn't a great system because many bits have to be flipped on the same clock tick. In fact the number of bit flips is unbounded, so to simply add 1 to 65535 for example we have to flip 16 bits. The worst case comes when going from -1 to 0, where every single bit must be flipped, an infinite task on an unbounded integer.

Instead computers could use a symmetrical system that flips the bits like so:

There are fewer bit flips and to count upwards you only need to flip one bit each time, giving 0000 0001 0011 0010 0110 0111 0101 0100 1100 etc.

Intervals

Counting is a transition each tick, which takes you from one state to another. Therefore the states represent the period between the transitions, they are a set of intervals, just like a year or an age is an interval. If I say I am 25 then I am talking about a year-long interval. The set of intervals are different than the set of integers, unlike integers, intervals don't have a multiply since the result wouldn't be in the set of unit long intervals.

Given that our binary strings represent intervals, we can see how much cleaner it is to represent them this new way:

or as bit strings:

As you can see, the bit string is symmetrical around 0, so the top bit is effectively just a sign bit.

With the existing form of binary there is a choice of how to represent negative numbers, you can either have a sign bit, or you can use the result of extending the subtraction algorithm beyond zero (called the two's complement method). Whereas with this new binary system you don't have to choose as they are one and the same, negatives are a natural extension.

Integers

As I said, counting is switching between values each tick, so the values naturally represent the interval. If you want to store an integer rather than an interval then that is a trickier problem, currently computers simply consider the integer as the floor of the interval value, and we can do so in this case as well. The + and - will work as it did on the intervals, you just need to be careful in implementing the multiply function.

If we weren't worried about memory it is cleaner to make a new symbol 'c' meaning 'changing between 0 and 1', then you can see the integers are also symmetric:

Summary

Counting naturally operates on the set of intervals ..-2,-1,-0,0,1,2,..

'Symmetric binary' more naturally represents these intervals, and is faster for counting.

The integers (..-2,-1,0,1,2,..) are usually represented as the floor of the interval value, so are a derived representation.

The integer above any interval 1000... occurs at 2^n

Beyond binary

This symmetric system works best in binary since each digit changes at a regular pace, perhaps this is why we haven't used a symmetric system for decimal, and perhaps why we didn't consider this symmetric system when moving from our decimal into a binary form for computers. But we can do a decimal version, in it we can write the years up to and after the year 2000 change over:

1003 1002 1001 1000 2000 2001 2002 2003 2005 2005 2006 2007 2008 2009 2019 2018...

I could also imagine a long lost tribe somewhere using this system base 6 as you can count it on your fingers:

0 1 2 3 4 5 15 14 13 12 11 10 20 21 22 23 24 25 35 34 33 ..

[Update: reading more about non-standard number representations, it looks like the binary numbers are called Gray code (or reflected binary) and the general system is called n-ary Gray code. There is nothing new under the sun or so they say... even to Gray, as Stibitz described it earlier.]

Implementing fractal automata

Assuming you have a knowledge of how Conway's life or other cellular automata are implemented, here is a summary for making fractal automata.

Data structure

Your data structure needs to be a set of grids like so, doubling in their resolution each layer.

so the resolution of layer n is 1 << n by 1 << n. Each square just holds a boolean value. 1 or 0.

The new value at each square is a function f of its neighbours values (including its own present value), for example here are the neighbours of the red square:

You might say that the orange squares are its siblings, the yellows are its children and parent. I also sometimes include the grey squares as neighbours of the red square.

Each square is then updated independently according to function f. Like other cellular automata, you need to have a separate copy of the grid hierarchy so you can 'double buffer' and the change in one cell doesn't affect the others on that frame.

Layer order

The layers must be updated in a specific order, which appears like so:

So on frame 1 you update layer 3 based on its siblings and its parent(s). Since there is no layer below you can treat the layer below as being zeros, just as we do for the neighbours outside of the edges of the grid. On the next frame, update layer 2, then the next frame update layer 3 and so on.

Despite appearances the order is quite easy to calculate. Take the frame number in binary and find the position of the first 1 in it-

In our example we have four layers, so our depth is 4. If p is the position of the first 1, then:

layerToUpdate = depth - 1 - p.

To prevent overflow, add:

if layerToUpdate < 0

{

frame = 1;

layerToUpdate = depth-1;

}

The function f

The function f is the set of rules determining whether the centre square 'lives or dies', or you can call it the mapping from the neighbour values to 0,1. The number of mappings is so large that it helps to try out different simpler rule sets. For example a mapping based on the number of 'on' neighbours without worrying about where they are placed.

Extending convolution

I propose a new operator which is like convolution so I'll call it covolution for the sake of this discussion:

C = B * M where * is the covolution operator.

The base data B is a set of detail levels of single-bit grid trees of some dimension n, so an example in one dimension:

Additionally you have the mask that applies the change to the base data. This is a mapping from each possible permutation of the local neighbourhood to a new bit value for the centre of the mask. For example for the red 1 in the above diagram, an example local neighbourhood is:

The red position takes into account the three nearby higher level bits, the two neighbouring bits on its level, plus itself, and the two lower level bits below it, then maps this to a new bit value for the red position. This same mapping is applied to every bit in the base data B, resulting in the new covolved data C.

In the example above, there are 8 bits in the neighbourhood, therefore 2^8 permutations to map to 0 or 1. i.e. it is a 256 to 2 mapping which can be stored as simply the set of patterns that result in a 1. Neighbourhoods of any size are allowed, since the operator 'covolves' two arbitrary datas of this structure.

For 2d base data, the higher levels can be thought of as coarser resolution images:

A neighbourhood in 2d may choose the 4 nearest parents, the 9 'Moore' neighbours and the 4 immediate children, requiring a mapping of 2^17 to 2.

You may have noticed that this is similar to Conway's life game, which is a convolution of such a 2d grid with a 3x3 neighbourhood mask. With covolution we can do Conway's life, but the extra detail levels mean that it is continuous spatially, rather than a grid:

This example uses a 3x3 parent neighbourhood only, and the mapping acts to smooth corners and remove some cells that are completely enclosed. It is a covolution applied multiple times to base data with initially only the highest level 4 pixels set to 1. Note that the patterns exist at all scales but don't repeat themselves in a simple way, due to the cellular automata nature of the operation.

Covolution can also apply to real values rather than bits, much as convolution usually is applied to real values. You replace the mapping with simply scaling each neighbour value by the mask value and summing, just as with convolution, much like is done with 'soften' and 'sharpen' filters in image packages.

Further, covolution can apply to any data structure rather than bits or reals, and the mapping can be chosen as any function that maps the neighbourhood to a new value of the data structure.

These are not actually different operations, they all are derivable from the bit version, which is ultimately the most general definition.

Continuous Time Covolution

The covolution operator acts instantaneously. It would be tempting to create an animated set by repeated covolutions: B = B*M, but this is not right, since the 1 dimension of time can't be built from multiple 0 dimensional covolutions. Instead we include scale symmetry to time also:

Just like with space, time is also broken into shorter sections for the higher detailed grid levels (like level 1). This leads to an order in which to individually apply the covolution for each level:

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,....

So a covolution applied in this order is called a covolving system. It is continuous in space and time, and means that the fine details change faster than the larger shapes on the coarser levels, producing true dynamic fractals as seen here:

http://vimeo.com/36816056

Various covolving systems, simply by adjusting the mapping.

The only difficulty is finding interesting mappings. Since there are 2^17 neighbourhood patterns, there are 2^(2^17) possible mappings, which is a large search space.

The trick with finding interesting mappings is to use different constraints to search families of mappings. For example, a simple constraint is to map just the total number of neighbours onto the boolean output. Even with this simple constraint there are still 2^16 possible mappings, here is an interesting bacteria-like result:

http://vimeo.com/36867848

Thoughts on the universe's origin

One of the larger questions in physics or philosophy is where the universe came from. Lawrence Krauss's 'a universe from nothing' video got me thinking about it.

If we think of the universe as 4d space-time then it is just a geometry, unmoving, unchanging. We might ask why this geometry, but a starting question is, why is the time axis so different to the space axes?

Well, relativity tends to deal with how the two relate to each other, but why is there this strong dependency in the time direction?

An answer may be that the universe geometry in 4d is radial around a point, in 2d it might look like so:

The radial lines represent information, since there is a strong correlation along the length of the line, you might say that the direction of the lines (which for a small neighbourhood are roughly parallel) represents the time direction, and the other 3 directions are space directions.

Since the correlation is in this direction, it remains to decide which direction is forwards in time, this is simply the direction to higher entropy.

So I am suggesting that the time dimension is simply the one that happens to be the direction of the lines in this radial 4d shape. It explains why the universe appears to be expanding, is consistent with everywhere being equidistant from the 'big bang', and deals with why there is nothing before the big bang (because that is the centre of the volume), it is approximately the same reason that there is nothing north of the north pole, just a geometry issue with our way of parametising time.

Accelerations or decelerations of the expansion could be explained as changes in the density or roughness of these lines, effectively changing how much time is perceived to pass per unit distance along the line.

OK, so if we accept such an explanation of why we perceive a 3d universe changing through time, then the next question is: why is the universe geometry shaped like that and not some other shape?

We can't ask why there is matter in the universe, because matter is just energy (movement) which is just a correlation of information in the time and space direction. All that exists in this universe is just correlated information.

We can't ask what created this correlated information as we have removed the idea of time and cause and effect, so all we can really ask is: why is the information correlated as it is?

Which can be rephrased as: why are there these constraints on this information?

I can only consider this question speculatively... I am fairly certain that the only sensible answer is that there are ultimately no constraints on the information. In other words, each apparent constraint is an emergent constraint from the action of multiple, smaller level, less constrained information.

This idea can be seen right through physics, from Feynman's path-integral descriptions of particles, to entropic forces which explain elastic forces and probably gravity.

So at the highest resolution there are no constraints and therefore there is nothing that needs further explanation.

i.e. we are living by the high level laws that derive from infinite information acting without rules. Even logic and consistency needn't apply at the lowest levels, it is just that logic and consistency is more persistent, an invariant state or attractor of the mass of possible illogic.