The "neighborhood" in a cellular automata model defines the geometry of the space. In class, we discussed 4 different kinds of neighborhoods for 2-dimensional cellular automata - the 8-neighbor Moore, the 6-neighbor triangular, the 4-neighbor von Neumann, and the 3-neighbor hexagon. (a) Let N_k (x, y) be the set of neighbors of site (x, y) where z and y are integers. If k = 3, then N_3 (x, y) = {{(x + 1, y), (x, y + 1), (x, y - 1)} lf x + y is even, {(x - 1, y), (x, y + 1), (x, y - 1}) if x + y is odd. Find similar formulas for N_4 (x, y), N_6(x, y), and N_8(x, y). (b) In a regular lattice, the atomic loop length is the smallest number of neighboring edges in loop from (0, 0) back to itself where the same edge between two neighbors is never traversed more than once. Each such loop with this minimal loop length is called an atomic loop". For each k elementof {3, 4, 6, 8}, find the atomic loop length and the number of atomic loops containing (0, 0) for lattices with neighborhoods N_k (x, y). (c) Given a neighborhood N_k (x, y), we can define a metric d_k((x, y), (u, v)) to measure the distance between points (x, y) and (u, v) recursively as follows: d_k((x, y), (u, v) = {0 if (x, y) = (u, v), 1 + min {d_k((w, z), (u, v)): (w, z) elementof N_k ((x, y))} otherwise. For each k elementof {3, 4, 6, 8}, draw the set of points {(u, v): d_k ((0, 0), (u, v)) lessthanorequalto 2} on the appropriate lattice. (d) For each k elementof {3, 4, 6, 8), find d_k((0, 0), (3, 3)). The "neighborhood" in a cellular automata model defines the geometry of the space. In class, we discussed 4 different kinds of neighborhoods for 2-dimensional cellular automata - the 8-neighbor Moore, the 6-neighbor triangular, the 4-neighbor von Neumann, and the 3-neighbor hexagon. (a) Let N_k (x, y) be the set of neighbors of site (x, y) where z and y are integers. If k = 3, then N_3 (x, y) = {{(x + 1, y), (x, y + 1), (x, y - 1)} lf x + y is even, {(x - 1, y), (x, y + 1), (x, y - 1}) if x + y is odd. Find similar formulas for N_4 (x, y), N_6(x, y), and N_8(x, y). (b) In a regular lattice, the atomic loop length is the smallest number of neighboring edges in loop from (0, 0) back to itself where the same edge between two neighbors is never traversed more than once. Each such loop with this minimal loop length is called an atomic loop". For each k elementof {3, 4, 6, 8}, find the atomic loop length and the number of atomic loops containing (0, 0) for lattices with neighborhoods N_k (x, y). (c) Given a neighborhood N_k (x, y), we can define a metric d_k((x, y), (u, v)) to measure the distance between points (x, y) and (u, v) recursively as follows: d_k((x, y), (u, v) = {0 if (x, y) = (u, v), 1 + min {d_k((w, z), (u, v)): (w, z) elementof N_k ((x, y))} otherwise. For each k elementof {3, 4, 6, 8}, draw the set of points {(u, v): d_k ((0, 0), (u, v)) lessthanorequalto 2} on the appropriate lattice. (d) For each k elementof {3, 4, 6, 8), find d_k((0, 0), (3, 3))
