Cellular Automata
Cellular automata are very important mathematical objects. They are capable of universal computation and are fundamental to the modern theory of computation.
Rule Input and Validation
The most basic kind of cellular automata exists in two states 1/0 and sums the three cells above the current new position. The cells generate a binary sum between 0 and 111 (7). There are 256 possible responses to these 8 possible sum states.
Firstly however, a valid rule has to be given to the machine. This must take the form of an 8 bit binary number.
|
The first task is to measure the length of the rule string.
to length :string
if emptyp :string [output 0]
output 1+length butfirst :string
end
This uses a recursive call to length to find the length of the string.
|
Output generated on testing at the command line
show length "diamond
7
show length "whjhjwhjhj0000
14
|
|
This code uses a recursive call to pad rules out upto a length of 8 binary bits added at the front.
to checkRule :string
if (length :string )<8
[
make "string word "0 :string
make "string checkRule :string
]
output :string
end
|
Output generated on testing at the command line
show checkRule "hello
000hello
|
|
Binary to Decimal Conversion
A recursive procedure could be used to do this too.
to binToDec :string
make :string checkRule :string
make "twoPower 128
make "decValue 0
repeat 8 [
if (first :string)=1 [
make "decValue :twoPower + :decValue ]
make "string butfirst :string
make "twoPower :twoPower/2 ]
output :decValue
end
Output generated on testing at the command line
show binToDec 11001100
204
show binToDec 11001101
205
|
Decimal to Binary Conversion
Could be done recusively
to decToBin :number
make "string "
repeat 8 [
make "twoPower power 2 repcount
ifelse (modulo :number :twoPower)=0 [
make "string word "0 :string
][
make "string word "1 :string
make "number :number - modulo :number :twoPower]
]
output checkRule :string
end
Output generated on testing at the command line
show decToBin 204
11001100
show decToBin 199
11000111
|
|
This program constructs a very basic cellular automata.
to cellaut
setpencolor (list 254 254 254)
cs
make "a (array 40 0)
make "b (array 40 0)
for [c 0 39 1][
setitem :c :a random 2
]
for [x 0 150 1] [
pu home rt 90 fd -400+:x*5
lt 90 pd
ifelse ( (item 0 :a)+(item 1 :a)+(item 39 :a)= 1) [ setitem 0 :b 1] [ setitem 0 :b 0]
ifelse ( (item 38 :a)+(item 39 :a)+(item 0 :a)= 1) [ setitem 39 :b 1] [ setitem 39 :b 0]
for [c 1 38 1][
ifelse ( (item :c+1 :a)+(item :c :a)+(item :c-1 :a)= 1) [ setitem :c :b 1] [ setitem :c :b 0]
]
for [c 0 39 1][
setitem :c :a item :c :b
ifelse ( (item :c :b)= 0) [ setfc [ 0 0 0]] [ setfc [ 255 255 255]]
repeat 4 [ fd 5 rt 90]
pu rt 45 fd 2 fill bk 2 lt 45 pd
fd 5
]]
end
| 
This is a fairly complex program.
It uses arrays to store values. Arrays are read using the item command. Values are put into arrays by using the setitem command.
The array is read from array :a constructed in array :b and drawn to the screen. The array :b is then written into array :a and the process repeats.
This cellular automata uses a transition rule which fills the child cell to the left iff (if and only if) one of its three parent cells is full. The parent cells are the cells that are level with, one above and one below the child cell in the column to the right.
|