 # CS411: Non-Standard Computing

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.

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.

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.

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.

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.

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.