**Unit 4: Computation in Cellular Automata: Selected Review**
*In the first part of this unit, we provide the description of one
dimensional cellular automaton and study some rules by which cellular
automaton evolved. Then, we will discuss some properties of the regular
language sets generated by a finite number of steps of cellular
automaton evolution. Also, we show Stephen Wolfram's classes of
cellular automaton behavior. Next, we show the standard cellular neural
network model and its potential applications. In the end of the unit,
we will study complex systems, such as living organisms, the brain,
society, the economy, etc. Complex systems are part of computer science
and a computer scientist invents algorithmic processes and formulates
suitable abstractions to model complex systems to predict its behavior.
Complex systems depend on a huge number of details making them nearly
irreducible, so that they cannot be described in terms of a small number
of variables. *

**Unit 4 Time Advisory**

This unit will take approximately 29 hours to complete.

☐ Subunit 4.1: 15 hours

☐ Subunit 4.1.1: 3 hours

☐ Subunit 4.1.2: 3 hours

☐ Subunit 4.1.3: 3 hours

☐ Subunit 4.1.4: 3 hours

☐ Subunit 4.1.5: 3 hours

☐ Subunit 4.2: 7 hours

☐ Subunit 4.3: 3 hours

☐ Subunit 4.4: 3 hours

☐ Unit 4 Assessment: 1 hour

**Unit4 Learning Outcomes**

Upon successful completion of this unit, the student will be able to:

- Define the one dimensional cellular automaton.
- List and describe the four classes of cellular automaton behavior.
- Explain the construction and properties of finite time sets.
- Define the cellular neural network.
- Describe the architecture and workings of cellular neural network-universal machine.

**4.1 Computation Theory of Cellular Automata**
**4.1.1 Introduction**
- **Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory
of Cellular Automata: “Introduction”**
Link: Stephenwolfram.com: Stephen Wolfram's *Computation Theory of
Cellular Automata:*
“Introduction”
(HTML)

Instructions: Read the description of one dimensional cellular
automaton. Please make sure to carefully review the examples and
figures given.

Terms of Use: Please respect the copyright and terms of use
displayed on the webpage above.

**4.1.2 Construction of Finite Time Sets**
- **Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory
of Cellular Automata: “Construction of Finite Time Sets”**
Link: Stephenwolfram.com: Stephen Wolfram's *Computation Theory of
Cellular Automata:* “Construction of Finite Time
Sets”
(HTML)

Instructions: Read the webpage in its entirety to learn how
cellular automaton evolved. Be sure that you understand the
examples and figures provided before moving on to other readings.

Terms of Use: Please respect the copyright and terms of use
displayed on the webpage above.

**4.1.3 Properties of Finite Time Sets**
- **Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory
of Cellular Automata: “Properties of Finite Time Sets”**
Link: Stephenwolfram.com: Stephen Wolfram's *Computation Theory of
Cellular Automata:* “Properties of Finite Time
Sets”
(HTML)

Instructions: Read the webpage in its entirety for a discussion
about some properties of regular language sets generated by a finite
number of steps of cellular automaton evolution. Please pay careful
attention to the examples and figures provided.

Terms of Use: Please respect the copyright and terms of use
displayed on the webpage above.

**4.1.4 Evolution of Finite Time Sets**
- **Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory
of Cellular Automata: “Evolution of Finite Time Sets”**
Link: Stephenwolfram.com: Stephen Wolfram's *Computation Theory of
Cellular Automata:* “Evolution of Finite Time
Sets”
(HTML)

Instructions: Read the webpage about several types of cellular
automaton behavior. Pay attention to classes of cellular automaton
behavior defined by dynamical systems theory.

Terms of Use: Please respect the copyright and terms of use
displayed on the webpage above.

**4.1.5 Some Invariant Sets**
- **Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory
of Cellular Automata: “Some Invariant Sets”**
Link: Stephenwolfram.com: Stephen Wolfram's *Computation Theory of
Cellular Automata:* “Some Invariant
Sets”
(HTML)

Instructions: Read the webpage in its entirety for information on
limiting sets of configurations generated by many steps of cellular
automaton evolution.

Terms of Use: Please respect the copyright and terms of use
displayed on the webpage above.

**4.2 Cellular Neural Network**
- **Reading: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's
“Cellular Neural Network”**
Link: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's
“Cellular Neural
Network”
(HTML)

Instructions: Read the website to learn about standard CNN model,
the potential applications of a Cellular Neural/Nonlinear Network,
and biological and technological motivations for computational
models. This reading covers subunits 4.2.1 through 4.2.3.

Terms
of Use: The linked material above has been reposted by the kind
permission of Tamás
Roska and Giovanni E. Pazienza, and can be viewed in its original
from
here. Please
note that this material is under copyright and cannot be reproduced
in any capacity without explicit permission from the copyright
holder.

**4.2.1 Standard CNN Model**
**4.2.2 CNN - Universal Machine and Cellular Wave Computing**
**4.2.3 Biological and Technological Motivations**
**4.3 Strong Random Correlations in Complex Systems**
- **Web Media: Videolectures.net: Imre Kondor’s "Strong Random
Correlations in Complex Systems”**
Link: Videolectures.net: Imre Kondor’s "Strong Random Correlations
in Complex Systems"
(YouTube)

Instructions: Watch this video about the complex systems (living
organisms, the brain, society, the economy, etc.), which depend on a
large number of details making them nearly irreducible, so that they
cannot be described in terms of a small number of variables. Repeat
watching any sections of the video that are hard to follow. When
necessary, pause the video to take the notes. This should take
about 3 hours of study time.

Terms of Use: This
video is licensed under a Creative Commons
Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is
attributed to videolectures.net and the original version can be
found
here.

**4.4 Similarity and Differences by Finite Automata**
- **Web Media: Videolectures.net: Tamás Gaál’s "Similarity and
Differences by Finite Automata”**
Link: Videolectures.net: Tamás Gaál’s "Similarity and Differences
by Finite Automata"
(YouTube)

Instructions: Watch this video about the similarity and differences
between finite automata, kernels, morphological analyzers,
compilers, and image processors. You may benefit from viewing
certain sections of this video more than once; repeat watching the
sections of the video that are hard to follow. It may also help to
take notes as you watch the video. This should take approximately 3
hours of study time.

Terms of Use: This
video is licensed under a Creative Commons
Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is
attributed to videolectures.net and the original version can be
found here.

**Assessment: The Saylor Foundation's "CS411: Unit 4 Quiz"**The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.