Loading...

CS411: Non-Standard Computing

Unit 1: Review: Theory of Computation   In the first part of this unit, the student will learn about representing information, the concept of languages, the notion of programs, and the concept of non-determinism. Then, we will get an overview of the mathematical systems of finite-state transducers and grammatical characterizations of the languages that finite-memory programs accept.  The last part of the unit covers the mathematical systems of Turing transducers.  Also, we will discuss the relationship between determinism and non-determinism in Turing transducers.

Unit 1 Time Advisory
This unit will take approximately 27 hours to complete.

☐    Subunit 1.1: 7 hours

☐    Subunit 1.2: 7 hours

☐    Subunit 1.3: 4 hours

☐    Subunit 1.4: 8 hours

☐    Unit 1 Assessment: 1 hour

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

  • Define alphabets and strings.
  • Explain the meaning of string orderings.
  • Define representation.
  • Explain the principles of abstracted finite-memory programs.
  • Define a finite state automaton and regular language.
  • Explain recursion.
  • Define context free language.
  • Describe Turing transducers.
  • Explain the difference between non-determinism and determinism.
  • List the characteristics of universal Turing transducers.

1.1 General Concepts   - Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts” Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation:Chapter 1: General Concepts” (HTML)
 
Instructions: Read the introductory webpage titled “General Concepts."   Then, click on the hyperlinks for each section 1.1-1.5, and read each webpage in its entirety.  From this reading, you will learn about strings and the role that strings have in representing information.  This reading relates the concept of languages to the notion of strings and introduces grammars for characterizing languages.  Also, this text deals with the notion of programs and the concept of non-determinism in programs.  This reading covers subunits 1.1.1 through 1.1.3 of this course.
 
Terms of Use: Please respect the copyright and terms of use displayed here.

1.1.1 Alphabets, Strings, and Representations   1.1.2 Formal Languages and Grammars   1.1.3 Programs   1.2 Finite-Memory Programs   - Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: Finite-Memory Programs” Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation:Chapter 2: Finite-Memory Programs” (HTML)
 
Instructions: Please read the “Finite-Memory Programs” webpage, and then click on each hyperlink for sections 2.1-2.6.  Read each section in its entirety to learn about the mathematical systems of finite-state transducers.  This reading also provides grammatical characterizations for the languages that finite-memory programs accept.  This reading covers subunits 1.2.1 through 1.2.3 of this course.
 
Terms of Use: Please respect the copyright and terms of use displayed here.

1.2.1 Motivation   1.2.2 Finite-State Transducers   1.2.3 Finite-State Automata and Regular Languages   1.3 Recursive Finite-Domain Programs   - Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive Finite-Domain Programs” Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation:Chapter 3: Recursive Finite-Domain Programs” (HTML)
 
Instructions: Please read the introductory webpage titled “Recursive Finite-Domain Programs.”  Then, click on each hyperlink for sections 3.1-3.6, and read each section in its entirety to learn about the notion of recursion in programs and recursive finite-domain programs, which are characterized by finite-state transducers.  A grammatical characterization for recursive finite-domain programs is provided in section 3.3.  This reading covers subunits 1.3.1 through 1.3.3 of this course.
 
Terms of Use: Please respect the copyright and terms of use displayed here.

1.3.1 Recursion   1.3.2 Pushdown Transducers   1.3.3 Context-Free Languages   1.4 General Programs   - Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs” Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation:Chapter 4: General Programs” (HTML)
 
Instructions: Please read the introductory page titled “General Programs.”  Then, click on the hyperlinks for sections 4.1-4.7, and read each webpage in its entirety. Section 4.1 is about the mathematical systems of Turing transducers as a generalization to pushdown transducers.  In section 4.2, you will learn about the relationship between the general class of programs and Turing transducers.  Section 4.3 considers the relationship between determinism and non-determinism in Turing transducers.  Section 4.4 shows the existence of a Turing transducer, called a universal Turing transducer, which can be programmed to compute any computable function.  This reading covers the topics outlined in subunits 1.4.1 through 1.4.4 of this course.
 
Terms of Use: Please respect the copyright and terms of use displayed here.

1.4.1 Turing Transducers   1.4.2 Programs and Turing Transducers   1.4.3 Non-Determinism versus Determinism   1.4.4 Universal Turing Transducers   - Assessment: The Saylor Foundation's "CS411: Unit 1 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](/contribute/)