Loading...

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.
 
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.

    Submit Materials