CA 1D Rule 30 Turtle

CA 1D Rule 30 Turtle preview image

2 collaborators

Uri_dolphin3 Uri Wilensky (Author)
Eytan Bakshy (Author)

Tags

cellular automata 

Tagged by Reuven M. Lerner about 11 years ago

computer science 

Tagged by Reuven M. Lerner about 11 years ago

Model group CCL | Visible to everyone | Changeable by group members (CCL)
Model was written in NetLogo 5.0.4 • Viewed 407 times • Downloaded 80 times • Run 0 times
Download the 'CA 1D Rule 30 Turtle' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


WHAT IS IT?

This program models one particular one-dimensional cellular automaton -- the one known as 'rule 30'. It is intended to be a companion model to the CA 1D Rule 30 model and to show an alternate way of modeling a cellular automaton --- by using turtles to do the processing instead of patches.

A cellular automaton (aka CA) is a computational machine that performs actions based on certain rules. It can be thought of as a "board" which is divided into cells (such as the square cells of a checkerboard). Each cell can be either on or off. This is called the "state" of the cell. The board is initialized with some cells on and some off. A clock is then started and at each "tick" of the clock the rules are "fired" and this results in some cells turning "on" and some turning "off".

There are many kinds of cellular automata. In this model, we explore a one-dimensional CA --- the simplest type of CA. In this case of one-dimensional cellular automata, each cell checks the state of itself and its neighbors to the left and right, and then sets the cell below itself to either "on" or "off", depending upon the rule. This is done in parallel and continues until the bottom of the board.

This model is one of a collection of 1D CA models. It is meant for the beginning user. If you have experience with CA, we suggest you check out a more sophisticated model such as CA 1D Elementary.

In his book, "A New Kind of Science", Stephen Wolfram argues that simple computational devices such as CA lie at the heart of nature's patterns and that CAs are a better tool than mathematical equations for the purpose of scientifically describing the world.

HOW IT WORKS

As the turtles move forward, each turtle checks the color of its current patch and the patches directly to the left and right of it, and then paints the patch below it according to Rule 30:

Y Y Y     Y Y B     Y B Y     Y B B
  B         B         B         Y

B Y Y     B Y B     B B Y     B B B
  Y         Y         Y         B

For example, if we have a Rule 30 CA, and the current cell is black and its left neighbor is yellow and its right neighbor is yellow, the cell below it is painted black.

HOW TO USE IT

Initialization & Running:

  • SETUP initializes the model with a single cell on in the center.
  • SETUP-CONTINUE copies the last row of the previous run to the top so that you can continue running the model in "wrapped" mode when you click GO.
  • GO begins running the model with the currently set rule. It continues until it reaches the last row of patches.

THINGS TO NOTICE

Although the rules are very simple, extremely complex patterns emerge in Rule 30. These patterns are not highly regular nor are they completely random.

Note that the pictures generated by this model do not exactly match the pictures in Wolfram's book, "A New Kind of Science". That's because Wolfram's book computes the CA as an infinite grid while the NetLogo model "wraps" around the horizontal edges of the world. To get pictures closer to the ones in the book, you may need to increase the size of the NetLogo world. You can increase the size of the world up to the available memory on your computer. However, the larger the world, the longer time it will take NetLogo to compute and display the results.

THINGS TO TRY

Is there any consistent pattern to the way this CA evolves?

If you look at the middle vertical line, are there more yellow or black cells?

Can you predict what the color of the nth cell on that line will be?

EXTENDING THE MODEL

What if you wanted to observe the behavior of a CA over many iterations without having to click continue every time it reaches the bottom of the view? Simply replace the stop with setup-continue in the go procedure:

  if (not any turtles)
    [ stop ]

with

  if (not any turtles)
    [ setup-continue ]

What if a cell's neighborhood was five --- two to the left, itself, and two to the right?

Classical CAs use an "infinite board". The CA shown here "wraps" around the edges of the world (sometimes known as a periodic CA or CA with periodic boundary condition). How would you implement in NetLogo a CA that comes closer to the infinite board?

Try making a two-dimensional cellular automaton. The neighborhood could be the eight cells around it, or just the cardinal cells (the cells to the right, left, above, and below).

NETLOGO FEATURES

The CA in this model uses turtles to process cells. While this is functionally identical to the traditional CA, the turtles can be thought of as processors moving down each row, while the cells are used simply as a data set for the processors. This differs from the patch-baed CA implementation in that the processor and data are decoupled from each other.

RELATED MODELS

Life - an example of a two-dimensional cellular automaton
CA 1D Rule 30 - the basic rule 30 model
CA 1D Rule 90 - the basic rule 90 model
CA 1D Rule 110 - the basic rule 110 model
CA 1D Rule 250 - the basic rule 250 model
CA 1D Elementary - a model that shows all 256 possible simple 1D cellular automata
CA 1D Totalistic - a model that shows all 2,187 possible 1D 3-color totalistic cellular automata.

CREDITS AND REFERENCES

Thanks to Eytan Bakshy for his help with this model.

The first cellular automaton was conceived by John Von Neumann in the late 1940's for his analysis of machine reproduction under the suggestion of Stanislaw M. Ulam. It was later completed and documented by Arthur W. Burks in the 1960's. Other two-dimensional cellular automata, and particularly the game of "Life," were explored by John Conway in the 1970's. Many others have since researched CA's. In the late 1970's and 1980's Chris Langton, Tom Toffoli and Stephen Wolfram did some notable research. Wolfram classified all 256 one-dimensional two-state single-neighbor cellular automata. In his recent book, "A New Kind of Science," Wolfram presents many examples of cellular automata and argues for their fundamental importance in doing science.

See also:

Von Neumann, J. and Burks, A. W., Eds, 1966. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, IL.

Toffoli, T. 1977. Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15, 213-231.

Langton, C. 1984. Self-reproduction in cellular automata. Physica D 10, 134-144

Wolfram, S. 1986. Theory and Applications of Cellular Automata: Including Selected Papers 1983-1986. World Scientific Publishing Co., Inc., River Edge, NJ.

Bar-Yam, Y. 1997. Dynamics of Complex Systems. Perseus Press. reading, Ma.

Wolfram, S. 2002. A New Kind of Science. Wolfram Media Inc. Champaign, IL.
See chapters 2 and 3 for more information on 1 Dimensional CA
See index for more information specifically about Rule 30.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

COPYRIGHT AND LICENSE

Copyright 2002 Uri Wilensky.

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or INTEGRATED SIMULATION AND MODELING ENVIRONMENT. The project gratefully acknowledges the support of the National Science Foundation (REPP & ROLE programs) -- grant numbers REC #9814682 and REC-0126227.

Comments and Questions

Click to Run Model

;; the following turtle variables refer to the colors of the 3 focal patches in a neighborhood
turtles-own [left-pcolor center-pcolor right-pcolor]

to setup
  clear-all
  make-turtles
  ask patch 0 max-pycor [ set pcolor yellow ]  ;; create initial yellow cell in the top center of the world
  reset-ticks
end 

to make-turtles
  ask patches with [pycor = max-pycor]  ;; create turtles along the top of the world
  [
    sprout 1 ;; each patch sprouts a turtle
    [
      set heading 180 ;; face the turtle downwards
      ht              ;; make the turtle invisible
    ]
  ]
end 

;; run the CA one view

to go
  if (not any? turtles)
    [ stop ]  ;; stop at the last row
  ask turtles
  [
    do-rule      ;; evaluate rule 30 for each turtle
    fd 1         ;; move down to the next row
    if pycor = min-pycor
      [ die ]    ;; if you've reached bottom, die
  ]
  tick
end 

;; set the state of the patch below the turtle by applying rule 30

to do-rule  ;; turtle procedure
  set left-pcolor [pcolor] of patch-at -1 0
  set center-pcolor pcolor
  set right-pcolor [pcolor] of patch-at 1 0
  ifelse ((left-pcolor = yellow and center-pcolor = black and right-pcolor = black) or  ;; evaluate rule 30
          (left-pcolor = black and center-pcolor = yellow and right-pcolor = yellow) or
          (left-pcolor = black and center-pcolor = yellow and right-pcolor = black) or
          (left-pcolor = black and center-pcolor = black and right-pcolor = yellow))
    [ ask patch-at 0 -1 [ set pcolor yellow ] ]
    [ ask patch-at 0 -1 [ set pcolor black ] ]
end 

;; setup to run the next view

to setup-continue
  ;; copy cells from the bottom to the top
  ask patches with [pycor = max-pycor]
    [ set pcolor ([pcolor] of patch pxcor min-pycor) ]
  ask patches with [pycor != max-pycor]  ;; clear the rest of the patches
    [ set pcolor black ]
  make-turtles  ;; sprout new turtles at the top of the world
end 


; Copyright 2002 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by When Description Download
Uri Wilensky over 11 years ago Updated to NetLogo 5.0.4 Download this version
Uri Wilensky almost 12 years ago Updated version tag Download this version
Uri Wilensky almost 12 years ago Updated to version from NetLogo 5.0.3 distribution Download this version
Uri Wilensky over 12 years ago Updated to NetLogo 5.0 Download this version
Uri Wilensky over 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 14 years ago Model from NetLogo distribution Download this version
Uri Wilensky over 14 years ago CA 1D Rule 30 Turtle Download this version

Attached files

File Type Description Last updated
CA 1D Rule 30 Turtle.png preview Preview for 'CA 1D Rule 30 Turtle' over 11 years ago, by Uri Wilensky Download

This model does not have any ancestors.

This model does not have any descendants.