CA 1D Elementary

2 collaborators

Uri Wilensky (Author)

Eytan Bakshy (Author)

WHAT IS IT?

This program models one-dimensional cellular automata. A cellular automaton (CA) is a computational machine that performs actions based on certain rules. The automaton is divided into cells, like the square cells of a checkerboard. Each cell can be either on or off (its "state"). The board is initialized with some cells on and some off. At each time step (or "tick") some rules "fire" and this results in some cells turning "on" and some turning "off".

There are many kinds of cellular automata. In this model, we explore one-dimensional CA -- the simplest types 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 explores all 256 possible CA rules that can be constructed by each cell checking only its immediate left and immediate right neighbor. Cellular automata can be created on any board size and dimension.

This model is one of a collection of 1D CA models. It is meant for the more sophisticated user. If you are seeing CA for the first time, we suggest you check out one of the simpler CA models such as CA 1D Rule 30.

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 TO USE IT

Initialization & Running:

SETUP-SINGLE initializes the model with a single cell on in the center.
SETUP-RANDOM initializes the model with a percentage of the cells "on." The percentage on is determined by the DENSITY slider.
AUTO-CONTINUE? CA automatically wraps top the top once it reaches the last row when the toggle is on
GO begins running the model with the currently set rule. It runs until the end of the screen. If it is pressed again, the CA continues the current run from the top, stopping again at the end of the screen.
FOREGROUND & BACKGROUND set the "on" and "off" cell colors respectively.
SHOW-RULES clears the view and gives a graphical preview of the rules. The 8 cases are displayed across the top of the world. To run the model, you must press either SETUP-SINGLE or SETUP-RANDOM and then click GO.

Rule Setup: There are 8 switches, the names of which correspond to cell states. "O" means off, "I" means on. For example, the top switch is called "OOO". (NOTE: the switch names are composed of the letters "I" and "O", not the numbers zero or one). If this switch is set to "on", then the following rule is created: when a cell is off, its left neighbor cell is off and its right neighbor cell is off, then the cell below it will be set "on" at the next time step. If this switch is set to 0, then the cell below it will be set to "off" at the next time step. So, since each switch has two settings and there are eight switches, there are 256 (2^8) possible rules. The current rule number is shown by the "RULE" slider, and it is calculated by changing a switch's name from binary to decimal and taking the sum of all the switches that are set to one. For example, if "011" and "001" are set to "on" and all the rest are set to "off", then the rule number is 4 (011 = 3, 001 = 1, and 3 + 1 = 4)).

The RULE slider can also be moved to set the current rule. Doing so will change the current state of the switches in the same way the switches set the rule.

THINGS TO NOTICE

What different patterns are formed by using a random setup versus a single setup?

Why do some rules always end up the same, regardless of the initial setup?

Are there rules that repeat a pattern indefinitely?

Are there rules that produce seemingly chaotic, random results?

Can all rules be classified into these above types? Are there more rule types than these?

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 boundaries. To get pictures closer to the ones in the book, you may need to increase the size of the 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

Find some rules that converge to all cells "on" or to all cells "off".

Are there any rules that conditionally converge to all cells "on" or all cells "off", depending upon the initial percentage of on/off cells?

A classic automaton is used to compute various things. Can these cellular automata be used to compute anything? How?

Experiment with the density variable and various types of rules. What are some relationships?

EXTENDING THE MODEL

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

Classical CA use an "infinite board". The CAs shown here "wrap" around the horizontal edges of the world (sometimes known as a periodic CA or CA with periodic boundary condition). How would you implement a CA in NetLogo 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).

Can you develop some tools to analyze the behavior of CAs? Compare different iterations from one continuation to the next of the same CA? Compare different rules?

NETLOGO FEATURES

This model takes advantage of a special optimization in the NetLogo compiler that makes the expression "ask patches with [px/ycor = ]" run much faster than it would otherwise.

RELATED MODELS

Life - an example of a two-dimensional cellular automaton CA 1D Rule 30 - the basic rule 30 model CA 1D Rule 30 Turtle - the basic rule 30 model implemented using turtles 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 Totalistic - a model that shows all 2,187 possible 1D 3-color totalistic cellular automata. CA Stochastic- the probabalistic counterpart to this model

CREDITS AND REFERENCES

Thanks to Eytan Bakshy, Geoff Hulette, and Erich Neuwirth for their 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.

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:

Wilensky, U. (1998). NetLogo CA 1D Elementary model. http://ccl.northwestern.edu/netlogo/models/CA1DElementary. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

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 project: CONNECTED MATHEMATICS: MAKING SENSE OF COMPLEX PHENOMENA THROUGH BUILDING OBJECT-BASED PARALLEL MODELS (OBPML). The project gratefully acknowledges the support of the National Science Foundation (Applications of Advanced Technologies Program) -- grant numbers RED #9552950 and REC #9632612.

This model was converted to NetLogo 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. Converted from StarLogoT to NetLogo, 2001.

Comments and Questions

Click to Run Model

globals
[
  row           ;; current row
  old-rule      ;; previous rule
  rules-shown?  ;; flag to check if rules have been displayed
  gone?         ;; flag to check if go has already been pressed
]

patches-own
[on?]

to startup  ;; initially, nothing has been displayed
  set rules-shown? false
  set gone? false
  set old-rule rule
end 

;;;;;;;;;;;;;;;;;;;;;;;;
;;; Setup Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;

to setup-general  ;; setup general working environment
  cp ct
  set row max-pycor   ;; reset current row
  refresh-rules
  set gone? false
  set rules-shown? false  ;; rules are no longer shown since the view has been cleared
end 

to single-cell
  setup-general
  reset-ticks
  ask patches with [pycor = row] [set on? false set pcolor background]  ;; initialize top row
  ask patch 0 row [ set pcolor foreground ]  ;; setup single cell in top center
  ask patch 0 row [ set on? true ]
end 

to setup-random
  setup-general
  reset-ticks
  ask patches with [pycor = row]  ;; randomly place cells across the top of the world
  [
    set on? ((random-float 100) < density)
    color-patch
  ]
end 

to setup-continue
  let on?-list []
  if not gone?  ;; make sure go has already been called
    [ stop ]
  set on?-list map [[on?] of ?] sort patches with [pycor = row]  ;; copy cell states from the
                                                                 ;; current row to a list
  setup-general
  ask patches with [ pycor = row ]
  [
    set on? item (pxcor + max-pxcor) on?-list  ;; copy states from list to top row
    color-patch
  ]
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; GO Procedures      ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;

to go
  if (rules-shown?)  ;; don't do unless we are properly set up
    [ stop ]
  if (row = min-pycor)  ;; if we reach the end, continue from the top or stop
  [
    ifelse auto-continue?
    [
        set gone? true
        display    ;; ensure everything gets drawn before we clear it
        setup-continue
    ]
    [
      ifelse gone?
        [ setup-continue ]       ;; a run has already been completed, so continue with another
        [ set gone? true stop ]  ;; otherwise just stop
    ]
  ]
  ask patches with [ pycor = row ]  ;; apply rule
    [ do-rule ]
  set row (row - 1)
  ask patches with [ pycor = row ]  ;; color in changed cells
    [ color-patch ]
  tick
end 

to do-rule  ;; patch procedure
  let left-on? [on?] of patch-at -1 0  ;; set to true if the patch to the left is on
  let right-on? [on?] of patch-at 1 0  ;; set to true if the patch to the right is on

  ;; each of these lines checks the local area and (possibly)
  ;; sets the lower cell according to the corresponding switch
  let new-value
    (iii and left-on?       and on?       and right-on?)          or
    (iio and left-on?       and on?       and (not right-on?))    or
    (ioi and left-on?       and (not on?) and right-on?)          or
    (ioo and left-on?       and (not on?) and (not right-on?))    or
    (oii and (not left-on?) and on?       and right-on?)          or
    (oio and (not left-on?) and on?       and (not right-on?))    or
    (ooi and (not left-on?) and (not on?) and right-on?)          or
    (ooo and (not left-on?) and (not on?) and (not right-on?))
  ask patch-at 0 -1 [ set on? new-value ]
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Utility Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;

to color-patch  ;;patch procedure
  ifelse on?
    [ set pcolor foreground ]
    [ set pcolor background ]
end 

to-report bindigit [number power-of-two]
  ifelse (power-of-two = 0)
    [ report floor number mod 2 ]
    [ report bindigit (floor number / 2) (power-of-two - 1) ]
end 

to refresh-rules  ;; update either switches or slider depending on which has been changed last
  ifelse (rule = old-rule)
  [
    if (rule != calculate-rule)
      [ set rule calculate-rule ]
  ]
  [ extrapolate-switches ]
  set old-rule rule
end 

to extrapolate-switches
  ;; set the switches based on the slider
  set ooo ((bindigit rule 0) = 1)
  set ooi ((bindigit rule 1) = 1)
  set oio ((bindigit rule 2) = 1)
  set oii ((bindigit rule 3) = 1)
  set ioo ((bindigit rule 4) = 1)
  set ioi ((bindigit rule 5) = 1)
  set iio ((bindigit rule 6) = 1)
  set iii ((bindigit rule 7) = 1)
end 

to-report calculate-rule
  ;; set the slider based on the switches
  let result 0
  if ooo [ set result result +   1 ]
  if ooi [ set result result +   2 ]
  if oio [ set result result +   4 ]
  if oii [ set result result +   8 ]
  if ioo [ set result result +  16 ]
  if ioi [ set result result +  32 ]
  if iio [ set result result +  64 ]
  if iii [ set result result + 128 ]
  report result
end 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; SHOW-RULES RELATED PROCEDURES ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to show-rules  ;; preview cell state transitions
  setup-general
  ask patches with [pycor > max-pycor - 12]
    [ set pcolor gray - 1 ]
  let i 0
  foreach list-rules
  [
    let px (min-pxcor + i * floor (world-width / 8) + floor (world-width / 16)) - 4
    ask patch px (max-pycor - 4)
    [
      sprout 1
      [
        set xcor xcor - 3
        print-block item 0 ?  ;; left cell
        set xcor xcor + 3
        print-block item 1 ?  ;; center cell
        set xcor xcor + 3
        print-block item 2 ?  ;; right cell
        setxy (xcor - 3) (ycor - 3)
        print-block item 3 ?  ;; next cell state
        die
      ]
    ]
    set i (i + 1)
  ]
  set rules-shown? true
end 

;; turtle procedure

to print-block [print-on?]  ;; draw a 3x3 block with the color determined by the state
  ask patches in-radius 1.5  ;; like "neighbors", but includes the patch we're on too
  [
    set on? print-on?
    color-patch
  ]
end 

to-report list-rules  ;; return a list of state-transition 4-tuples corresponding to the switches
  report (list lput ooo [false false false]
               lput ooi [false false true ]
               lput oio [false true  false]
               lput oii [false true  true ]
               lput ioo [true  false false]
               lput ioi [true  false true ]
               lput iio [true  true  false]
               lput iii [true  true  true ])
end 


; Copyright 1998 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	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	about 12 years ago	Updated to version from NetLogo 5.0.3 distribution	Download this version
Uri Wilensky	almost 13 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 Elementary	Download this version

Attached files

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

This model does not have any ancestors.

This model does not have any descendants.

NetLogo