init stuff

Off[General::spell1];  Off[General::spell]

<< NKSExplorer`

$MinT = -1.5; $MaxT = 
      9.5; $AbsMinT = -5; $PointStyle = {AbsolutePointSize[8]}; $MaxX = 
      8;
$RightLineStyle = {AbsoluteThickness[1], 
          RGBColor[0, 0, 1]};
$LeftLineStyle = {AbsoluteThickness[1], 
          RGBColor[1, 0, 0]};
$SpaceSliceStyle = {AbsoluteDashing[{2, 8}]};
$DefaultFont = {"Helvetica", 14};
$Lines = 4;

points = 
        Flatten[Table[{2  n, 2  m}, {n, 
              0, $Lines}, {m, -($Lines - n), $Lines - n, 2}], 
          1];

PointLine[{t_, x_}] := {Sequence @@ $RightLineStyle, 
        Line[{{x - t + $MinT, -$MinT}, {x + $MaxT - t, -$MaxT}}], 
        Line[{{x - t + $MinT, -$MinT}, {x - t + $MinT, -$AbsMinT}}], 
        Sequence @@ $LeftLineStyle, 
        Line[{{x + t - $MinT, -$MinT}, {x - $MaxT + t, -$MaxT}}], 
        Line[{{x + t - $MinT, -$MinT}, {x + 
                t - $MinT, -$AbsMinT}}]}

MyPoint[{t_, x_}] := {Sequence @@ $PointStyle, 
        Point[{x, -t}]}

PointLabel[{t_, x_}] := 
      Text["(" <> ToString[t] <> "," <> 
          ToString[x] <> ")", {x +  .4, -t}, {-1, 0}]

SpaceSlice[t_, label_] := {Sequence @@ $SpaceSliceStyle, 
        Line[{{-$MaxX - $MaxT, -t}, {$MaxX + $MaxT, -t}}], 
        Text[label, {$MaxX + $MaxT - 
              6, -t +  .02}, {-1, -1}]}

ColorState[s_String] := 
      StringReplace[
        s, {"A" -> "\!\(\* StyleBox[\"A\",FontColor->RGBColor[0,0,1]]\)\
", "B" -> "\!\(\* \
StyleBox[\"B\",FontColor->RGBColor[1,0,0]]\)"}]

TransformedSpaceSlice[tp_, v_] := 
      With[{γ = 1/Sqrt[1 - v^2]}, {Sequence @@ $SpaceSliceStyle, 
          Line[{{-$MaxX - $MaxT, -(tp/γ + 
                      v*(-$MaxX - $MaxT))}, {$MaxX + $MaxT, -(tp/γ + v*($MaxX + $MaxT))}}]}]

SlicedNetwork[v_] := 
      Graphics[{PointLine /@ points, 
          MyPoint /@ points, TransformedSpaceSlice[#, v] & /@ 
            Range[-1, 9, 2]}, 
        PlotRange -> {{-$MaxX - $MaxT, $MaxX + $MaxT}, {-$MaxT, -$AbsMinT}}, AspectRatio -> Automatic]

\(FindState[tp_, v_] := 
      With[{initx = Table[i, {i, \(-$MaxX\), $MaxX, 4}], γ = 
            1/Sqrt[1 - v^2]}, 
        StringJoin[
          Last /@ Sort[
              N@Flatten[\({{Max[# -  .1, \((tp/γ + #)\)/\((1 - 
                                  v)\)], "A"}, {Min[# +  .1, \(-\((tp/γ - #)\)\)/\((1 + v)\)], "B"}} &\) /@ initx, 1]]]]\)

\(LTEvolHistory[v_, opts___] := 
      Module[{sortedevents, histx}, 
        sortedevents = 
          Split[Sort[
              Flatten[Table[{\(LorentzTransform[{2  n, 2  m}, 
                        v]\)[\([1]\)], \((m + $Lines)\) + 1}, {n, 
                    0, $Lines}, {m, \(-\(($Lines - n)\)\), $Lines - n, 2}], 
                1]], #1[\([1]\)] == #2[\([1]\)] &]; 
hist = 
          FoldList[
            Function[{x, 
                y}, {Fold[
                  StringReplacePart[#1, \ "BA", \ #2[\([2]\)] + {0, 
                          1}] &, x[\([1]\)], 
                  y], \(\((#[\([2]\)] + {0, 1} -> #[\([2]\)] + {0, 
                            1})\) &\) /@ y}], {"ABABABABAB"}, 
            sortedevents]; 
NKSExplorer`TimeNetworks`SMWXGraphicsStreamed[hist, 
          NKSExplorer`TimeNetworks`Private`YFactor -> 2, 
          NKSExplorer`TimeNetworks`ColorTable -> {{0, 0, 1}, {1, 0, 
                0}, {0.5`, 0, 0}, {0, 0.5`, 0}, {0, 0, 0.5`}, {0.5`, 0.5`, 
                0}, {0.5`, 0, 0.5`}, {0, 0.5`, 0.5`}, {0.25`, 0.75`, 0}}, 
          opts]]\)

Øyvind Tafjord, Wolfram Research

Outline of talk:

NKS and fundamental physics

Causal networks from underlying evolution histories

Quick review of special relativity

Causal networks and special relativity

NKS and fundamental physics

The approach to fundamental physics taken in A New Kind of Science involves features such as:

Simple programs can do complicated things

Traditional fundamental physics is based on PDEs and continuous systems. A New Kind of Science makes real the possibility that a simple, discrete system could do the job.

No rigid notion of space and time

In a cellular automaton, say, there is a well-defined global notion of space (the cells across the page) and time (the steps going down the page). This is probably too rigid, and we seek a way in which space and time instead emerge from more basic concepts.

Causal networks provide structure

Rather than starting with rigid cells with synchronized updates, we instead focus on the network of causal events built from an asynchronous underlying evolution. We look for systems generating "casually invariant" evolutions - we'll see that this in itself has interesting consequences such as special relativity.

Exhaustive rule searches

In a simple enough framework we can do exhaustive searches over all possible rules, without any preconceived notions of what we're looking for (caveat: must chose an appropriate framework!).

Causal Networks

In a causal network, each node corresponds to an event in the underlying system. An event is something that happens at a given place and a given time.

Here is the causal network for a particular substitution system (NKS p. 516):

In this system, the order in which the rules are applied affects the eventual outcome of the system - and the causal network is not unique.

Causal invariance

We are more interested in causal invariant systems, for which the causal network will be unique. As we'll see, this will give us a notion of special relativity.

One way to ensure causal invariance in a substitution system is to make sure that the replacement rules can never overlap. A simple example is the sorting rule "AB" -> "BA" applied to a string of A's and B's:

Causal invariance

If we take the "AB"->"BA" rule and apply it to a starting string "ABABABABAB...", we get a very regular causal network:

In this picture, we've applied the rule as early as possible, but note that the same causal network structure arises no matter when the various substitutions are made.

We will see how this results in a close connection with special relativity, but first a quick review of the latter.

Special Relativity

Einstein's theory of special relativity tells us that our common sense notion of space and time is only valid at low velocities (compared to the speed of light). More generally, space and time are not absolute notions - they depend on your point of view! (this would be hard to reconcile with the rigid space structure in an ordinary CA, e.g.).

Einstein's principle of relativity: Velocity is only relative, not absolute - if you're moving at constant velocity, you cannot tell by doing any physical experiment. In particular, the speed of light will always be measured as 299 792 458 m/s.

To make this work, time must run slower for someone who is moving faster. Consider a set of events, say the light blinks from a lighthouse, as seen by the lighthouse keeper and by a boat zipping past. Each blink has a time and a space location, denoted (t,  x). From the lighthouse keeper's perspective the blinks always happen at x = 0 and t  =  0,  1,  2,   ... . But what about the boat?

The theory of special relativity, tells us that the time and space locations of the blinks as seen from the boat, (t',  x'), can be calculated using the Lorentz transformation (v is the speed of the boat, and c is the speed of light):

\(TraditionalForm\`t' = \(t - v\ x/c\^2\)\/\@\(1 - v\^2/c\^2\); \ \(\(x'\)\(=\)\(\(x - v\ t\)\/\@\(1 - v\^2/c\^2\)\)\(\ \)\)\)

So for instance, if v = (3/5) c, then (t, x)  =  (1, 0) corresponds to (t', x') = (1.25,  -0.75) (where time is measured in seconds and distance in light seconds). So according to the boat, the lighthouse blinks every 1.25 seconds, not every second!

Special Relativity

Let's make a plot of the events corresponding to blinks from the lighthouse:

LorentzTransform[{t_, x_}, v_] := 
      With[{γ = 1/Sqrt[1 - v^2]}, γ {t - x v, 
            x - v t}]

events = N[Table[{t, 0}, {t, 0, 6}]]; 
    LTevents = N[LorentzTransform[#, 3/5] & /@ events];
Show[
        GraphicsArray[{{Graphics[{MyPoint /@ events, PointLabel /@ events}, 
                PlotRange -> {{-8, 4}, {-8, 1}}, 
                AspectRatio -> Automatic, Frame -> True, 
                FrameTicks -> False, 
                PlotLabel -> "v = 0 (lighthouse keeper)"], 
              Graphics[{MyPoint /@ LTevents, PointLabel /@ LTevents}, 
                PlotRange -> {{-8, 4}, {-8, 1}}, 
                AspectRatio -> Automatic, Frame -> True, 
                FrameTicks -> False, 
                PlotLabel -> "v = 3c/5 (superfast boat)"]}}]];

Causal Networks and Special Relativity

Claim: In a causal network, corresponding to a causally invariant evolution, motion at different speeds corresponds to slicing the network at different "angles".

Let's see how this works explicitly for the simple "AB"->"BA" rule which looked like this:

Causal Networks and Special Relativity

To make things a little clearer, let's use the colors blue and red for A and B respectively, and redraw the causal network like this:

Show[
        Graphics[{PointLine /@ points, MyPoint /@ points}, 
          PlotRange -> All, 
          AspectRatio -> Automatic]];

This corresponds to starting with the string "ABABABABAB" and ending up with "BBBBBAAAAA".

Each node in this network corresponds to an event, let's associate the events with coordinates corresponding to the actual positions in the above network. The links are always at 45 degrees, corresponding to the speed of light.

Show[
        Graphics[{PointLine /@ points, MyPoint /@ points, 
            PointLabel /@ points}, PlotRange -> All, 
          AspectRatio -> Automatic]];

Causal Networks and Special Relativity

We can now consider space slices in the system - the state of the system at given times, in this particular reference frame:

Show[
        Graphics[{PointLine /@ points, MyPoint /@ points, 
            PointLabel /@ 
              points, SpaceSlice[#, "t=" <> ToString[#] <> ":  " <> 
                    ColorState[FindState[#, 0.001]]] & /@ 
              Range[-1, 9, 2]}, PlotRange -> All, 
          AspectRatio -> Automatic]];

The succession of states on the right, corresponds to a particular evolution in the microscopic system - a particular ordering of the replacements.

Show[LTEvolHistory[0]];

Let's now try to view this system from a reference frame that is moving.

Causal Networks and Special Relativity

To consider a moving reference frame, we apply the Lorentz transformation to all the events in the system.

v = 5/13; 
    newpoints = LorentzTransform[#, v] & /@ points;

This takes us from

Show[
        Graphics[{MyPoint /@ points, PointLabel /@ points}, 
          PlotRange -> All, 
          AspectRatio -> Automatic]];

to

Show[
        Graphics[{MyPoint /@ newpoints, PointLabel[Round[10  #]/10. ] & /@ 
              newpoints}, PlotRange -> All, 
          AspectRatio -> Automatic]];

Causal Networks and Special Relativity

Let's put the links back in:

Show[
        Graphics[{Block[{$MinT = #[[1]] - 1}, PointLine[#]] & /@ 
              Take[newpoints, $Lines + 1], 
            MyPoint /@ 
              newpoints, SpaceSlice[#, "t'=" <> 
                    ToString[#] <> ":  " <> 
                    ColorState[FindState[#, v]]] & /@ Range[-1, 9, 2]}, 
          PlotRange -> All, 
          AspectRatio -> Automatic]];

We see that the events have all been shifted around, but all the links are still at 45 degrees as required (the speed of light is the same in all reference frames). We can now consider space slices in this reference frame, keeping t' constant, rather than t. We see that a different evolution history now appears, but also one that is consistent with the underlying rules, namely

Show[LTEvolHistory[5/13]];

Causal Networks and Special Relativity

Alternatively, we can keep showing the events in the original reference frame, but plot the space slices according to the equations for t'  =  constant, rather than t  = constant:

Show[
        Graphics[{PointLine /@ points, 
            MyPoint /@ points, TransformedSpaceSlice[#, v] & /@ 
              Range[-1, 9, 2]}, PlotRange -> All, 
          AspectRatio -> Automatic]];

Reading the colors left to right as they cross each slice, we find the exact same result as in the previous diagram:

Show[
        Graphics[{Block[{$MinT = #[[1]] - 1}, PointLine[#]] & /@ 
              Take[newpoints, $Lines + 1], 
            MyPoint /@ 
              newpoints, SpaceSlice[#, "t'=" <> 
                    ToString[#] <> ":  " <> 
                    ColorState[FindState[#, v]]] & /@ Range[-1, 9, 2]}, 
          PlotRange -> All, 
          AspectRatio -> Automatic]];

Causal Networks and Special Relativity

So we see that motion at different speeds simply corresponds to slicing the causal network at different angles:

Show[
        GraphicsArray[
          Partition[SlicedNetwork /@ { .05,  .25,  .5,  .8}, 
            2]]];

And this corresponds to different order in which the various update rules are applied:

Show[
        GraphicsArray[
          Partition[
            LTEvolHistory /@ {0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 
                0.85, 0.95}, 5]]];

Note that these diagrams only show the order in which the rules are applied, not the absolute timing of the updates in the various frames.

Summary

We have seen how special relativity arises naturally in a causal network with causally invariant update rules.

The causal invariance is important because it ensures that all different slices corresponds to an actual evolution.

We see that in such a universe, the order in which the rules are applied depends on your point of view!

These considerations are indendent of the details of the underlying system. We looked at a simple substitution system, but the same applies to other systems, such as the network rewrite systems discussed in A New Kind of Science.