r010800: Sketching Computation Theory

Bibliography Readings/Notes
Sketching Computation theory

orcmid.github.io> bib>2001>

visits to **Orcmid on GitHub**

r010800>
0.1.0 2023-10-23 16:30

This is a syllabus that follows the content of Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing (Boston, MA: 1997). ISBN 0-534-94728-X

Michael Sipser is a member of the MIT Theory of Computation Group. His book was being used as the basis for an on-line study program of the Yahoo "Learn-CS-Theory" discussion group (now long gone). The syllabus, below, follows the chapter structure, week by week.

I didn't follow this beyond the first week's introductory material. I am now waiting for the next convenient offering of Ullman's Automatia Theory course on Coursera, instead. I have observations in my note on the first week's material. I will nail some of this down as part of the demonstration of oMiser universality and generalization. I'll do that in appropriate places. This page will remain for reference purposes. I don't foresee developing it further in this form, although some of the later topics are worth visiting further.

-- Dennis E. Hamilton
Seattle, Washington
2014-05-03

Recap: 2023-10-10. I still have this book. I appreciate its outline. I don't know if I will delve in again. The Miser Project is easier, although I might get into the nitty-gritty at some point. Mostly, I think I'll just refer the curious to deeper places, such as the Sipser book.

Week	Topic	Status
2001-08-06	0. Introduction 0.1 Automata, Computability, and Complexity 0.2 Mathematical Notions and Terminology 0.3 Definitions, Theorems, and Proofs 0.4 Types of Proof Exercises and Problems
2001-08-13	1. Regular Languages 1.1 Finite Automata
2001-08-20	1.2 Nondeterminism
2001-08-27	1.3 Regular Expressions
2001-09-03	1.4 Nonregular Languages Exercises and Problems
2001-09-10	2. Context-Free Languages 2.1 Context-Free Grammars
2001-09-17	2.2 Pushdown Automata
2001-09-25	2.3 Non-context-free Languages Exercises and Problems
2001-10-01	3. The Church-Turing Thesis 3.1 Turing Machines
2001-10-08	3.2 Variants of Turing Machines
2001-10-15	3.3 The Definition of Algorithm Exercises and Problems
2001-10-22	4. Decidability 4.1 Decidable Languages
2001-10-29	4.2 The Halting Problem Exercises and Problems
2001-11-05	5. Reducibility 5.1 Undecidable Problems from Language Theory
2001-11-12	5.2 A Simple Undecidable Problem
2001-11-19	5.3 Mapping Reducibility Exercises and Problems
2001-11-26	6. Advanced Topics in Computability Theory 6.1 The Recursion Theorem
2001-12-03	6.2 Decidability of Logical Theories 6.3 Turing Reducibility
2001-12-10	6.4 A Definition of Information Exercises and Problems
2001-12-17	7. Time Complexity 7.1 Measuring Complexity
2001-12-24	7.2 The Class P
2001-12-31	7.3 The Class NP
2002-01-07	7.4 NP-Completeness
2002-01-14	7.5 Additional NP-Complete Problems Exercises and Problems
2002-01-21	8. Space Complexity 8.1 Savitch's Theorem 8.2 The Class PSPACE
2002-01-28	8.3 PSPACE-Completeness
2002-02-04	8.4 The Classes L and NL 8.5 NL-Completeness 8.6 NL Equals coNL Exercises and Problems
2002-02-11	9. Intractability 9.1 Hierarchy Theorems
2002-02-18	9.2 Relativization
2002-02-25	9.3 Circuit Complexity Exercises and Problems
2002-03-04	10. Advanced Topics in Complexity Theory 10.1 Approximation Algorithms 10.2 Probabilistic Algorithms
2002-03-11	10.3 Alternation
2002-03-18	10.4 Interactive Proof Systems
2002-03-25	10.5 Parallel Computation
2002-04-01	10.6 Cryptography Exercises and Problems

0.1.0 2023-10-10T22:03Z Repurpose with a small recap.
0.01 2014-05-03-09:28 Repaved Version: The page is updated to conform to current styles and formats. The material is preserved as a historical matter and to avoid breaking any links that may have existed to it. However, the capitalizations in URLs have changed, and that may break older versions.
0.00 2000-08-09-08:00 Develop Initial Notes (orcmid): Extract notes on how this material is applicable to the Miser Project

You are navigating Orcmid on GitHub

created 2000-08-09T15:00Z by orcmid