-
Department Info
-
-
Admissions
-
-
Academics
-
-
-
Research
-
-
-
Main navigation | Main content
4011 is a required class that CSci majors should take in their junior year. In the class students learn theoretical foundations of computer languages and computability. Students will encounter the finite state machine, pushdown automaton, and Turing machine models of computation, and will also learn about language classes such as the regular and context-free languages classes. The issues of decidability, undecidability, and the limits of computability will be studied, and the techniques of reductions and diagonalization as a means for establishing such properties for given languages will be explored. Further topics include time and space complexity, and the notion of NP-completeness.
Logical and mathematical foundations of computer science. Formal languages and their correspondence to machine models. Relevance to practical issues such as lexical analysis, string matching and parsing. Decidability, undecidability, and the limits of computability. Computational complexity.
| Weeks | Topics |
|---|---|
| 1 - 3 | Finite State Machines and regular languages. |
| 4 - 5 | Context-free languages and pushdown automata. |
| 6 - 7 | Turing machines and the definition of computability. |
| 8 - 10 | Decidability, undecidability, and the limits of computation; using reducibility and diagonalization arguments. |
| 11 - 14 | Time complexity and NP-completeness. |
Optional or additional topics include the Recursion Theorem, the undecidability of number theory, and rudimentary descriptive complexity (Chapter 6); and space complexity (Chapter 8).
For most students this is their only look at computability, which is a fundamental and important concept in computer science. Also, many of the concepts used extensively in 4011, such as Turing machines, finite automata, or context-free grammars, occur heavily in the design and implementation of programming languages, as well as in other areas of computer science.
Most students will take 4011 in their junior year.
CSci 1902 (Structure of computer programming II) and CSci 2011 (Discrete Structures of Computer Science). From 1902 students will need some exposure to structured programming, elementary data structures, and recursion before studying computability and language foundations. From 2011 students need experience with proofs involving mathematical concepts they will use in computability.
4011 is a prerequisite for 5106 (Programming Languages). A good number of topics in 5106 rely on concepts from 4011.
3 hours of lecture + 1 hour of recitation per week.
Michael Sipser “Introduction to the Theory of Computation” 2nd Edition Thomson Publishing, 2006.
Upon successful completion of the class, students should be able to:
