Intelligence

Please enter your answers on the document and submit it before the due date. Marked out of 30.

1.    [5 marks] Consider the following 1 D cellular automata.

.    .    .        .
.        .        .        .

Complete the rule table for the above CA (the last row has not been generated yet).
0    0    0
0    0    1
0    1    0
0    1    1
1    0    0
1    0    1
1    1    0
1    1    1
Using the rule set you created above, fill in the last row.

Using Wolfram’s classification of Cellular Automata (CA), is the above an example of a Class 1 (Boring), Class 2 (Stable), Class3 (Chaotic) or Class 4 CA (Complex)?

2.    [8 marks] Consider the following State table for a Turing Machine. Note that L is left, R is right, and N means no movement.

State    Read    Write    Move    Next State
A    0     1    R    B
A    1     1    L    C
B    0     1    L    A
B    1     1    R    B
C    0    1    L    B
C    1    1    NO    HALT
Show the result if we set the Read head in the middle of an infinite tape containing all 0s and we started in State A? Describe the movement of the head.

3.     [5 marks] Show the next two generations of the following 2-D cellular automata assuming that we are using Moore’s neighbourhood and the rules are:
– If the number of ON neighbours is exactly 2, then the cell maintains its current state
–If the number of ON neighbours is exactly 3 or exactly 5, then the cell will be ON in the next period regardless of its current state
–If the number of ON neighbours is any other number then the cell will be OFF in the next period

Current Generation                  Next Generation                  Last Generation

.    .
.    .
.    .
.    .

4.    [6 marks] Consider the following Margolus Rule:

MS, D 15; 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0

Show the next generation of the given pattern. Start with the block in the top left corner.

Current Generation                                                     Next Generation
.            .    .            .
.    .    .    .    .    .    .    .
.            .
.            .
.            .
.            .
.    .    .    .    .    .    .    .
.            .    .            .

Is this rule reversible?

5.    [6 marks] Go to the assignment 2 discussion forum and comment on the uses of cellular automata. Try to come up with some new ideas on what other applications there may be for cellular automata. You should make 2 posts – one in response to my question and one in response to another student’s post. Please end your posts with a question to stimulate discussion. You should make your initial post before Module 2 ends. Then you have a week to respond to another student’s post.

Intelligence

Please enter your answers on the document and submit it before the due date. Marked out of 30.

1.    [5 marks] Consider the following 1 D cellular automata.

.    .    .        .
.        .        .        .

Complete the rule table for the above CA (the last row has not been generated yet).
0    0    0
0    0    1
0    1    0
0    1    1
1    0    0
1    0    1
1    1    0
1    1    1
Using the rule set you created above, fill in the last row.

Using Wolfram’s classification of Cellular Automata (CA), is the above an example of a Class 1 (Boring), Class 2 (Stable), Class3 (Chaotic) or Class 4 CA (Complex)?

2.    [8 marks] Consider the following State table for a Turing Machine. Note that L is left, R is right, and N means no movement.

State    Read    Write    Move    Next State
A    0     1    R    B
A    1     1    L    C
B    0     1    L    A
B    1     1    R    B
C    0    1    L    B
C    1    1    NO    HALT
Show the result if we set the Read head in the middle of an infinite tape containing all 0s and we started in State A? Describe the movement of the head.

3.     [5 marks] Show the next two generations of the following 2-D cellular automata assuming that we are using Moore’s neighbourhood and the rules are:
– If the number of ON neighbours is exactly 2, then the cell maintains its current state
–If the number of ON neighbours is exactly 3 or exactly 5, then the cell will be ON in the next period regardless of its current state
–If the number of ON neighbours is any other number then the cell will be OFF in the next period

Current Generation                  Next Generation                  Last Generation

.    .
.    .
.    .
.    .

4.    [6 marks] Consider the following Margolus Rule:

MS, D 15; 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0

Show the next generation of the given pattern. Start with the block in the top left corner.

Current Generation                                                     Next Generation
.            .    .            .
.    .    .    .    .    .    .    .
.            .
.            .
.            .
.            .
.    .    .    .    .    .    .    .
.            .    .            .

Is this rule reversible?

5.    [6 marks] Go to the assignment 2 discussion forum and comment on the uses of cellular automata. Try to come up with some new ideas on what other applications there may be for cellular automata. You should make 2 posts – one in response to my question and one in response to another student’s post. Please end your posts with a question to stimulate discussion. You should make your initial post before Module 2 ends. Then you have a week to respond to another student’s post.