Jason Cawley
Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Posts: 712 
Post Tag Systems  Complexity Threshold Lowered
In his live experiment at the start of the NKS 2007 summer school, Wolfram revisited a type of system first examined by Emil Post in the 1920s. A note on page 894 of the NKS book describes this system and what Post already discovered about them.
These rules involve a string of characters, with a fixed number of characters from the front of the string dropped at each step, and a block added to the tail of the string. Which block is added depends on the first character of the string on the current step (before the drop).
The note in the book makes the claim that all the systems of this type that have only 0 or 1 values in the string, and only two rules depending on only the first bit in the manner described above, and that only drop 2 characters per step, have simple behavior. Post had already noticed nontrivial behavior when the block dropped is 3 long, and Wolfram (for the book) found cases of complex behavior when the block to apply is allowed to depend on more than one bit.
In his live experiment, Wolfram revisited the subject, and decided to look for more complicated behavior in the region previously dismissed as simple  2 items dropped, 2 strings to add, only 0 or 1. And he found a case that showed apparently random fluctuations in the length of the resulting string, around a trend that seemed to depend on the square root of two.
Later at the conference following the summer school, we got mail from an attendee who saw another such case. I give code for it below. The replacement rules are {1,0,0} and {0,1}  meaning add the former if the initial cell is 0 and the latter if it is 1, while dropping the first 2 either way  starting from an initial string of {1,0}. This grows with a trend rate of stepnumber / GoldenRatio, with apparently random (but always small) fluctuations around that trend.
In Mathematica terms, let 
init = {1,0}; myrules = {{1,0,0},{0,1}};
onestep[rules_, state_]:= If[First[state]==0, Flatten[{Drop[state,2], rules[[1]]}], Flatten[{Drop[state,2],rules[[2]]}]]
evolve[rules_, start_, steps_]:= NestList[onestep[rules, #]&, start, steps]
GRtrend[steps_]:= Table[N[t/GoldenRatio], {t,1,steps+1}]
then you can see the deviation of the length after 5000 steps from the GoldenRatio trend with 
ListLinePlot[(Length/@evolve[myrules, init, 5000])  GRtrend[5000]]
If you ArrayPlot the evolution of the string itself, it is shiftmap trivial, but the growth rate deviates slightly from the trend, in a complex way, leaving bands of slightly different separation in the shiftmap lines. Out to 25000 steps at least, the deviation from the trend looks completely random.
We got email about this one from Jon Palin. A very nice find.
Report this post to a moderator  IP: Logged
