A New Kind of Science: The NKS Forum > Pure NKS > Post Tag Systems - Complexity Threshold Lowered
Author
 Thread
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 non-trivial 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 shift-map trivial, but the growth rate deviates slightly from the trend, in a complex way, leaving bands of slightly different separation in the shift-map 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

07-23-2007 10:12 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Attaching a Mathematica 6 notebook to examine and evolve these...

Attachment: postsystem.nb
This has been downloaded 2045 time(s).

Report this post to a moderator | IP: Logged

07-23-2007 10:19 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-15 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives