Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MTH108:  HOMEWORK 6 – CELLULAR AUTOMATA

Please attempt sections A and B before the tutorials.

Section A – Warm-up questions

A1.  Given n, k ∈ N, what is the total number of configurations for cellular automaton on a universe of n cells and an alphabet of k elements?

A2.  Draw the set of T-shaped dominoes that define the elementary cellular automaton Rule 158.

Section B – Main questions

B1.  Iterate the elementary cellular automaton  Rule 22 for 5 generations, taking an  initial condition with exactly one black cell .

B2.  In Conway’s Game of Life, a configuration of only four live cells arranged adjacently in a square is an equilibrium:  it does not change from one generation to the next .  Find equilibrium configurations consisting of exactly n live cells, for n = 5, 6, 7, 8 cells .

B3.  (Forest Fire) Suppose that we model the spread of a forest fire over the first few hours using a cellular automaton on a 2-dimensional grid z2 .  Suppose that each cell has two states 1 (fire) and 0 (no fire) .  We assume that if a cell is on fire, then if will still be on fire one hour later .   Because of the prevailing wind direction in the region, a cell with no fire will have fire one hour later if the cell to the west or north-west is

on fire, otherwise a cell without fire will still have no fire one hour later . Suppose that the fire begins in two adjacent cells .  How will the number of cells on fire change over the subsequent hours?  Is there a formula for the number of cells on fire after n hours?

B4.  (Algal dispersion) Suppose that a species of algae is introduced to the bank of a lake . Suppose that the algae begin to spread around the edge of the lake from one month to the next . Let us model the situation with elementary cellular automoton Rule 126 implemented on a finite cyclic universe consisting of n cells arranged in a loop .  Investigate the behaviour of the solution for n = 9, 10, 11.

B5.  (Yeast growth) Suppose that we model the growth of a species of yeast across a surface on a lattice  of regular hexagonal cells .  Suppose that each cell has two states 1 (yeast) and 0 (no yeast) .  A cell with no yeast will gain yeast one hour later if two or more of its six neighbours have yeast, otherwise the state of a cell does not change . Suppose that the initial state only has yeast in two adjacent cells .  How many cells will have yeast over the next 5 hours?

Section C – Investigations

C1.  (Surjectivity) Consider the elementary cellular automaton Rule 90.  Show that every configuration has four predecessors .  Find the four predecessors for the configuration with one black cell .

C2.  (Garden of Eden) A garden of Eden is a configuration that can only occur as an initial condition:  it has no predecessor .  Find an elementary cellular automaton with a garden of Eden .