Fall 2002 Course
22C:135 Introduction to Computation Theory
Instructor: Arthur C. Fleck
Teaching Assistant: Jin Zhou, Office: B20J MLH, Hours: 11-12:20 T-Th, Ph.: 335-3650
Time/place: 10:30 am MWF / 110 MLH
Text: A. C. Fleck, Formal Models of Computation:
The Ultimate Limits of Computing, at IMU bookstore
Course overview
The course develops several formal models of computing systems, and investigates
what computations can be accomplished with various combinations of computing
resources. Properties of both the possible, and the impossible, computations
are studied. The course culminates with results about computations that are
impossible on any computer system regardless of its speed and size.
General background from the formal prerequisite 22C:34 will be assumed.
In particular, it will be assumed that the student has
basic knowledge of sets, functions, relations, and graphs, plus experience
with formal proofs, especially induction proofs.
The course will involve two in-class exams, announced well in advance,
and a final exam, scheduled for Monday December 16 from 2:15-4:15 pm in our
regular classroom. There is also weekly homework. The assignments
in the course do not involve computer programming. The work involves
problem solving, and the careful proof of the conclusions that can be
drawn from rigorous definitions of the computing models.
Anyone who has a disability that requires modification of testing or
other class arrangements should contact me as soon as possible. Please
see me after class or during office hours.
Topic list
- Finite state models
- regular expressions
- deterministic vs. non-deterministic automata
- regularity preserving operations
- pumping lemma and non-regular languages
- transducers and state minimizations
- Grammars and the Chomsky hierarchy
- context-free grammars and languages
- derivations, derivation trees, and ambiguity
- operations preserving context-free languages
- normal form grammars and parsing
- pushdown automata
- pumping lemma and non context-free languages
- context-sensitive grammars and languages
- derivations as computations
- leftmost limitations and loss of the derivation tree concept
- linear bounded automata
- operations preserving context-sensitive languages, and erasing problems
- Turing machines and uncomputability
- relation to general phrase structure grammars
- recursive functions
- random access machine (RAM) simulation
- universal Turing machine
- undecidability (e.g., halting problem, Post's correspondence problem,
context-free ambiguity)
Related Web sources: