Question

Given the following rule for the evolution of a cellular automation (a - 1'a1') + (a0 a1'). Which of the following is the binary number representation of the rule?

a) 01001010
b) 00101100
c) 00010000
d) 11001110
e) 01000101

Answer 1

Answer on question 37753 – Math- Other

Given the following rule for the evolution of a cellular automaton $(\bar{a}_{-1}\bar{a}_1) + (a_0\bar{a}_1)$. Which of the following is the binary number representation of the rule?

a) 01001010

b) 00101100

c) 00010000

d) 11001110

e) 01000101

Solution

The simplest nontrivial cellular automaton would be one-dimensional, with two possible states per cell, and a cell's neighbors defined to be the adjacent cells on either side of it. A cell and its two neighbors form a neighborhood of 3 cells, so there are $2^3 = 8$ possible patterns for a neighborhood. A rule consists of deciding, for each pattern, whether the cell will be a 1 or a 0 in the next generation. There are then $2^8 = 256$ possible rules.

To begin with, we write all possible triplets combinations of 1 and 0 in the table.

Let us explain the given formula:

$$\bar{a}_i = \begin{cases} 1, & \text{if } a_i = 0 \\ 0, & \text{if } a_i = 1 \end{cases} \qquad \left(a_i a_j\right) = \begin{cases} 1, & \text{if } a_i a_j = 1, \\ 0, & \text{if } a_i a_j = 0; \end{cases} \qquad a_i + a_j = \begin{cases} 1, & \text{if } a_i + a_j > 0 \\ 0, & \text{if } a_i + a_j = 0 \end{cases}$$

Therefore, for the first combination (111), we get

$$(\bar{a}_{-1} \bar{a}_1) + (a_0 \bar{a}_1) = (\bar{1} \bar{1}) + (1 \bar{1}) = (00) + (10) = 0 + 0 = 0$$

For the second combination (110):

$$(\bar{a}_{-1} \bar{a}_1) + (a_0 \bar{a}_1) = (\bar{1} \bar{0}) + (1 \bar{0}) = (01) + (11) = 0 + 1 = 1$$

And so on. Look at the table? The right answer is 01000101.

Answer: e) 01000101