Biological Computation

Cellular Automata    ◾    69

• We will denote by k the number of possible states for each of M

s

’s

cells. Let k = 1 + max(m,n) = m + 1. e state numbered m + 1 is the

quiescent state 0.

• Four cells (h, a, b, s) play a central role in the operation of M

s

(Figure2.10(a)). e cell corresponding to the TM’s read/write head

is denoted as h and is at state P. e cells adjacent to it to the right

and le are denoted as a and b, respectively. e cell currently being

read on the tape is denoted by s and is in state S

0

. We dene the

neighborhood of each cell as the seven cells around them arranged

in the shape shown in Figure2.10(b). Note that ...