CSCI 460 Theory of Computing

David Keil  (dkeil@framingham.edu)

Framingham State University, Spring 2012

Syllabus (PDF ver.)

Assessment questions (PDF ver.)

Assignments (PDF ver.)

Notation (PDF ver.)

Topics (with links to slides and handouts):

Introduction

      Notation

      Definitions, theorems, proofs

Discrete Math and Data Structures review 

1. Uncountable sets
      Diagonal proofs

      Induction and coinduction

2. Deterministic finite automata, regular languages, and lexical analysis  

3. Pushdown automata, context-free grammars, and parsing  

4. Turing machines and undecidability
       Equivalence of 1-tape and 2-tape TMs 

5. Random-access machines and recursively definable functions

        Macros

6. Models of interactive computation

      Peter Wegner, Why Interaction Is More Powerful Than Algorithms
      Dina Goldin, Persistent Turing Machines as a Model of Interactive Computation

7. Models of concurrent and multistream computation

 

Updated 1/17/12