2020 March 25,

CS 254: Computability and Complexity

Carleton College, Winter 2020, Joshua R. Davis, , CMC 324, x4095


This course considers the fundamental questions of computer science: What can computers do, and how much time and space do they require to do it? To address these questions, the course proceeds in three stages:

  1. We begin by studying regular languages and context-free languages. We learn about regular expressions, which are a useful programming tool, and parsing, which is important to the theory of programming languages. But the real purpose of this first stage is to serve as a warm-up to the second stage.
  2. We introduce Turing machines, which are a central concept of theoretical computer science. We study what Turing machines can do and, more suprisingly, what they cannot do.
  3. Focusing on problems that are solvable by Turing machines, we analyze the time and space needed to solve them. Compared to CS 252: Algorithms, we operate at a higher level of abstraction. For example, sometimes we analyze an entire class of problems at once.
Along the way, we encounter some fascinating connections to philosophy, mathematics, and linguistics. Your work is a mixture of writing proofs, executing algorithms by hand, and Python programming. For example, you learn how to determine whether a programming problem is solvable by regular expressions, and solve it with them if it is.

The official prerequisites for this course are Introduction to Computer Science (CS 111) and a proof course (CS 202 or Math 236). If you don't know Python, then study it on your own (using the links below or other tutorials). Talk to me if you are concerned about your background.


Our class meets in CMC 301 during period 5A (MonWed 1:50-3:00, Fri 2:20-3:20). Some course materials are:

The following elements contribute to your course grade.

Course grades are assigned according to an approximate curving process. There are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades (A, B, C, etc.). Rather, I assign grades by comparing the students to each other, to earlier students, and most importantly to the course goals. An advantage of this system is that student grades don't suffer when I write a difficult exam, for example. The disadvantage is that you cannot compute your own grade. Visit me in my office, if you want me to estimate your current grade for you.

If some medical condition affects your performance in this course, then let me know in the first week of class (or as soon as it arises). You may need to make official arrangements with the Disability Services.

Work in the Classroom

You are expected to arrive to class slightly early, so that you are ready to participate as soon as class begins. Do not sit alone. You are often expected to work out problems with your neighbor. My ideal class meeting is more of a discussion than a lecture. Discussions are not just for English and history classes. Communication skills are essential to every academic discipline, and they are highly prized by employers.

You are expected to take notes, even if your learning style is primarily aural. Because the material involves many diagrams, you should take notes on paper or on an electronic device that supports rapid drawing. Typing on a laptop is not adequate.

Photographs and recordings are not permitted without my prior approval. Phones are not permitted, except for the purpose of approved photographs and recordings.

Work Outside the Classroom

Although class meetings may seem like the core of the course, homework assignments are actually where you learn the material. As far as your grade is concerned, homework serves primarily as the first step in studying for exams.

On homework, you are encouraged to figure out the problems with other students. However, you should always write/type your solutions individually, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is a violation of Carleton's Academic Integrity standards.

Writing is not just for English and history majors. Communication skills are essential to every academic discipline, and they are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation.

Although homework is assigned every day, it is collected only once a week. When handing in a week's homework, staple your pages into a single packet, in the correct order. Multi-sheet packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? No.

During the term, you have one free pass to hand in a week's homework packet late. You do not have to justify your lateness. In fact, this policy exists so that I don't have to agonize over the relative merits of varying excuses. When using your late pass, simply hand in your late packet when the next packet is due, writing "Late Pass Used" prominently at the top of the late packet. Once you have used your late pass, no late assignments are accepted, except in extreme circumstances that typically involve interventions by physicians or deans.

You are expected to spend about 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than 15 hours, then talk to me.


To help you decode the schedule, here is an example. On Day 03 we discuss nondeterministic finite automata. Section 1.2 of our textbook covers that material; read it before or after class, to get another treament. You might also want to read my extra notes called "DFA vs. NFA Details". You have homework called "Day 03", which you hand in on Day 06.

M 1/0601introductionDay 0101, 020.1-0.4soSuperSum.py
W 1/0802deterministic finite automataDay 02031.1
F 1/1003nondeterministic finite automataDay 03061.2DFA vs. NFA Details
M 1/1304regular expressionsDay 04061.3Python Regular Expressions
W 1/1505pumping lemmaDay 05091.4
F 1/1706catching upDay 0609Radiolab: Loops (6:40-15:33)
M 1/2007context-free grammarsDay 07092.1
W 1/2208Exam A
F 1/2409pushdown automataDay 09122.2Recursion
M 1/2710pumping lemmaDay 10142.3
W 1/2911catching upWikipedia: Alan Turing
F 1/3112Turing machinesDay 12143.1
M 2/0313variants of Turing machinesDay 13173.2
W 2/0514nondeterministic Turing machinesExam B153.3
F 2/0715decidable examplesDay 15174.1Interpreter
M 2/10Midterm Break
W 2/1216undecidable examplesDay 16204.2
F 2/1417undecidable, unrecognizable examplesDay 17205.1
M 2/1718unrecognizable examples, Rice's theorem5.29, 5.30bc20
W 2/1919time complexityDay 19237.1Complexity of {0m 1m : m ≥ 0}
F 2/2120time complexity7.6, 7.7237.2
M 2/2421deterministic polynomial timeDay 21237.3
W 2/2622Exam C
F 2/2823nondeterministic polynomial timeDay 23267.3
M 3/0224mapping reducibility7.26, 7.27267.4
W 3/0425NP-completenessnone7.4
F 3/0626NPSPACE = PSPACEDay 26288.1-8.2
M 3/0927TQBF is PSPACE-completenone8.3TQBF
W 3/1128conclusionnonethis, this, this, ...
S 3/14Exam D 3:30PM-6:00PM