Cellular Automata

Cellular automata (CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. - plato.stanford.edu .

1. CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, following state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance).
2. CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.

1. wolfram
2. plato.stanford.edu

The following python code will output to a command-line console.

Here are the conditions and the rules:

1. Each line of the program's output represents a row of 64 boolean values. True should be printed as an asterisk (*) and False should be printed as a hyphen (-). So each line of output should be 64 characters of asterisks or hyphens, followed by a newline.
2. We'll use the following rules to determine the values in the rows:
   1. The initial row of booleans should be all False, except for one True roughly in the middle (in the 32nd position; so it should be 31 Falses, followed by one True, followed by 32 Falses).
   2. Each subsequent row of booleans will depend on the one immediately before it. Each new row should be calculated using this rule.
   3. The value for a given position in the new row should be True if in the previous row, either the position immediately to the left or immediately to the right was True, but not both. Otherwise it is False.
3. We'll print out 32 lines worth of output total using these rules. Email back the output as well as the code.

Here is the code:

def ca():
   ''' Celluar automata with Python - K. Hong'''
   # 64 Boolean - True(1) : '*'
   #            - False(0): '-'
   # Rule - the status of current cell value is True
   # if only one of the two neighbors at the previous step is True('*')
   # otherwise, the current cell status is False('-')

   # list representing the current status of 64 cells
   ca = [
         0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,  0,0,0,0]

   # new Cellular values
   ca_new = ca[:]

   # dictionary maps the cell value to a symbol
   dic = {0:'-', 1:'*'}

   # initial draw - step 0
   print  ''.join( [dic[e] for e in ca_new])
   # additional 31 steps
   step = 1
   while(step < 32):
      ca_new = []
      # loop through 0 to 63 and store the current cell status in ca_new list
      for i in range(0,64):
         # inside cells - check the neighbor cell state
         if i > 0 and i < 63:
            if ca[i-1] == ca[i+1]:
               ca_new.append(0)
            else:
               ca_new.append(1)

         # left-most cell : check the second cell
         elif(i == 0):
            if ca[1] == 1:
               ca_new.append(1)
            else:
               ca_new.append(0)

         # right-most cell : check the second to the last cell
         elif(i == 63):
            if ca[62] == 1:
               ca_new.append(1)
            else:
               ca_new.append(0)

      # draw current cell state
      print  ''.join( [dic[e] for e in ca_new])

      # update cell list
      ca = ca_new[:]

      # step count
      step += 1

if __name__ == '__main__':
   ca()

Here is the output: