COMS W3261: Computer Science Theory, Fall 2020

This course is an introduction to models of computation, computability, and complexity. We will ask questions like: How do we define the abstract notion of "computation" or a "computer"? What problems can be computed? What problems can be computed efficiently? Can we prove that some problems can never be computed, no matter how fast our computers become? The course is highly mathematical and abstract; in particular, there will be minimal programming assignments (if any) and homework problems will frequently involve proving or disproving various assertions. Students are expected to be comfortable with the material covered in Discrete Math (W3203) or the equivalent.

Topics (not exhaustive): automata and the languages they define, context-free grammars and the languages they define, Turing machines, basic complexity theory (such as P vs. NP).

• Lecture 1 (9/8): Introduction to class, motivation and overview. Definitions of alphabet, strings, and languages.
  Readings: Chapter 0 (we didn't go over most of it in class, but this is background material you're supposed to know from discrete math). Optional reading ahead: Chapter 1.1
• Lecture 2 (9/10): Defined a DFA and the language recognized by it. A language is regular if there exists a DFA recognizing it. We saw some examples of regular languages, and discussed the intuition of when a language is regular (the DFA corresponds to computation with a fixed constant amount of memory).
  Readings: 1.1 (most of it). Optional reading ahead: finish 1.1, read 1.2.
• Lecture 3 (9/15): All finite lanugages are regular (but the converse is not true). Non-deterministic finite automata (NFA): definition and examples of NFA, when a string is accepted, and the language recognized by an NFA. Intuition of how to interpret NFA computation (via tokens or computation trees, "trying all options in parallel" or "guessing" interpretations).
  Reading: 1.2 (first part).
• Lecture 4 (9/17): Review of NFAs. Examples. Proved that a language is regular if and only if it is recognized by an NFA (one direction of the proof is easy, the other direction involved the subset construction). Example of the subset construction.
  Reading: 1.2 (second part). Optional reading ahead: last part of 1.1 and last part of 1.2 (after that we'll move on to 1.3)
• Lecture 5 (9/22): We argued that any generic way to take any NFA and create an equivalent DFA must incur an exponential blowup in the number of states. This is because for any n, there is a language that has a n+1 state NFA recognizing it, but requires at least 2^n states in any DFA recognizing it (we sketched the proof). Defined operations on languages (ie sets): complement, union, intersection, concatenation, power, Kleene star. We claimed that the class of regular languages is closed under all these operations, and started to prove it (we showed it for complement, using DFAs, and for union, using NFA - we'll continue next time).
  Reading: This lecture did not exactly follow Sipser, but the most relevant parts in Sipser are the last part of 1.1 and the last part of 1.2. Optional reading ahead: 1.3. HW1 out.
• Lecture 6 (9/24): Completed the proofs that the class of regular languages is closed under union (two different proofs, constructing an NFA and constructing a DFA), intersection (two different proofs, constructing a DFA and using previously proven closure properties and De Morgan's law), concatenation, and Kleene star (in both cases, by constructing an NFA). Defined regular expressions and the languages described by them.
  Reading: last part of 1.1, last part of 1.2, beginning of 1.3. Optional reading ahead: 1.3.
• Lecture 7 (9/29): Regular expressions and the langauges they generate. Proved that a language is generated by a regular expression if and only if it is regular: One direction, every regular expression has an NFA, follows from closure properties we already proved. For the other direction we showed that any NFA can be transofrmed to an equivalent regular expression by going through a GNFA).
  Reading: 1.3
• Lecture 8 (10/1): Proved that every regular language satisfies the pumping lemma, intuitively saying that every string in the language that is long enough (above some pumping constant for the langauge) must have a non-empty portion that can be pumped up or down any number of times and still be in the language. Thus, to prove that a language is not regular, it suffices to show that it does not satisfy the pumping lemma. We saw some examples. Also noted that this method works often but not always, as some non-regular languages also satisfy the pumping lemma. We will see more methods to prove that a language is not regular next time.
  Reading: 1.4. Optional reading ahead: 2.1. HW1 due. HW2 out.
• Lecture 9 (10/6): Recap of pumping lemma and more examples. Second way to prove a language is not regular: use closure properties (assume L is regular, combine L with other regulate languages, using operations for which we have proved closure of the class for regular languages, to get a language that you already know, or can more easily prove, is not regular, deriving a contradiction). Defined the equivalence relation with respect to an arbitrary language L (strings x and y are equivalent if there is no distinguishing extension, namely they are indistinguishable by L). We claimed (proof omitted but it is straight forward) that this is indeed an equivalence relation (for any L), and that if L is regular and D is a DFA recognizing it, then if the computation of D on two strings x,y ends in the same state, then x and y are equivalent. This implies that the number of equivalence classes for a regular language L is at most the number of states in any DFA recognizing L. Stated the Myhill-Nerode theorem: a language L is regular if and only if the number of equivalence classes wrt L is finite. Moreover, if L is regular, the number of equivalence classes is exactly the number of states in the minimal DFA recognizing L. This theorem can be used as a third way to prove non-regularity of a language: show infinitely many strings so that any two of them are distinguishable / non-equivalent, implying infinitely many equivalence classes, and therefore the language is not regular. Gave some examples of using the Myhill-Nerode theorem.
  Reading: 1.4. The textbook has the Myhill-Nerode theorem as part of its solved exercise 1.52 (the equivalence relation is defined in problem 1.51).
• Lecture 10 (10/8): Wrapped up discussion on regular languages and where we are in the class. Defined context free languages and the languages they generate, with examples. Defined derivation/parse trees and leftmost derivations (each derivation corresponds to a parse tree; a tree can have many corresponding derivations, but only one leftmost derviation). Defined ambiguous grammars and showed an example ambiguous grammar, for which an equivalent non-ambiguous grammar also exists. Defined an inherently ambiguous context free langauge (one for which every CFG is ambiguous) and gave an example. We did not cover proofs.
  Reading: 2.1
• Lecture 11 (10/13): Gave an example CFG with a detailed proof of correctnes (for the language of strings with an equal number of a's and b's). Proved the language of valid regular expressions is context free but not regular.
• Lecture 12 (10/15): Proved that the class of context free languages is closed under the regular operations (union, concatenation, star). Proved that every regular language is context free. Stated the tandem pumping lemma for context free languages, and how to use it to prove a language is not context free.
• Lecture 13 (10/20): Showed examples of languages that are not context free (proved using the tandem pumping lemma). Proved that the class of context free languages is not closed under under intersection, nor under complement. Quickly mentioned (without formal definitions or theorems) that a language is context free if and only if it can be recognized by a pushdown automata, which intuitively is like an NFA with a stack. Mentioned that an NFA with two (or more) stacks, or an NFA with a queue, is much stronger than a PDA, and is in fact equivalent to Turing Machines (which we will define next time), and as strong as your favote programming language in terms of what it can solve (if we ignore efficiency).
• Lecture 14 (10/22): Defined Turing Machines (TM) and contrasted them with DFAs. Defined the computation of a TM on a given input (can accept, reject, or run forever), configurations of a TM, and the language recognized by a TM. Examples of TMs.
  Reading: 3.1
• Lecture 15 (10/27): Definition of a decider (a TM that halts on every input), definition of a recognizable language and a decidable language. Hierarchy of language classes we've seen so far (regular, context free, decidable, recognizable, all languages -- we will see that each of these is a proper subset of the next). Defined an input-output TM and a computable function. Examples of computable functions that can be used as "subroutines" in the construction of other TMs. Showed two variants of TM models and their equivalence to the standard model: a TM with doubly infinite tape, and a TM with with multiple tapes. Mentioned that our transformation of a multiple-tape TM to an equivalent single-tape one incurs a quadratic overhead in running time, and that this overhead is known to be inherent.
  Reading: 3.1, and some of 3.2, 3.3. Definition 5.17.
• Lecture 16 (10/29): Defined non-deterministic TM (NTM) and proved its equivalence to standard (deterministic) TM. Our transformation of a NTM to an equivalent (deterministic) TM involved performing a breadth-first search of the computation tree, and incurs an exponential overhead in running time. Mentioned that whether or not this overhead is inherent is a big open problem (directly related to the P vs NP problem which we will cover later in the class). We listed many other models equivalent to TMs, and stated the Church-Turing thesis, and our shift to identifying algorithms with TMs and using high-level descriptions of algorithms. Discussed the important idea that every algorithm/TM can be encoded as a string (or an integer), and thus fed as input to another algorithm (which may manipulate it, run it, try to reason about it, etc).
  Reading: 3.2, 3.3.
  If you want to see an explicit specific example of how you might encode a TM as a string, you can check section 2 in this document (written by TA Freddy Kellison-Linn who covered a lecture in 2018).
• Lecture 17 (11/5): Review of quiz 6 common mistakes: recall that a TM recognizing a language may either accept, reject, or loop forever on every input; recall that a language L(M) may be decidable even if M is not a decider (as long as there exists some decider for the language). Proved that the class of decidable languages is closed under complement (this statement is not true for the class of recognizable lanuages). Proved that L is decidable if and only if both L and its complement are recognizable. Showed that the following languages are decidable: A_DFA, A_NFA, E_DFA. Also said (without proof) that the following languages are decidable: EQ_DFA, A_CFG.
  Reading: 4.1, Theorem 4.22
• Lecture 18 (11/10): Mentioned without proof that EQ_CFG and AMB_CFG are not decidable. Showed that A_TM is recognizable, recognized by the universal TM (which encompasses "general purpose computing": it takes as input a description of an arbitrary TM M and a string w, and simulates M on w). Discussed why the universal TM is not a decider, and mentioned that A_TM is not decidable (we will prove soon). Showed that NE_TM is recognizable (the recognizing algorithm uses a "dovetailing" technique to run a TM going through all possible strings in a way that makes sure each execution of the loop takes finite time, but if M accepts any string the algorithm will eventually accept).
  Brief overview of what is coming up: we'll prove that there exist languages that are not recognizable (in fact, most languages are not); then we will show some specific examples, followed by a class of many natural and important examples, of languages that are not decidable, and in some cases not even recognizable.
  Defined when sets have the same cardinality (if there's a bijection between them), and defined when a set is countable (if it's finite or there's a bijection from the natural numbers to the set). If A is a subset of B and B is countable, then A is countable. Examples of countable sets: even positive integers, rationals, the set of all strings over a given alphabet, the set of all TMs, the set of all recognizable languages. Claimed that the set of all languages over a given alphabet (namely the powerset of the alphabet) is not countable (we will prove this next time). Concluded that, since there are uncountably many languages of which only countably many are recognizable, there exist (uncountably many) languages that are not recognizable.
  Reading: 4.1, 4.2.
• Lecture 19 (11/12): Proved the set (0,1) of real numbers is not countable (this is Cantor's proof, via diagonalization). Used the same diagonalization method to prove the set of all languages over a given alphabet is not countable. Concluded (as mentioned last lecture) that there exist (uncountably many) languages that are not recognizable. Proved that A_TM is not decidable (via diagonalization). Concluded that the complement of A_TM is not recognizable. Proved that HALT_TM ("the halting problem") is not decidable (via a reduction from A_TM).
  Reading: 4.2, Theorem 5.1.
  You may also want to check out the following resources: (a) a (8 minute) video on (un)countability and Cantor's proof, (b) Another (7 minute) video using diagonalization to prove the halting problem is not decidable. (c) this poem-proof for undecidability of the halting problem (again via diagonalization). (Note: we used diagonalization to prove A_TM is not decidable, and then showed that if the halting problem HALT_TM was decidable, A_TM would also be. The above resources directly prove the halting problem is not decidable via diagonalization - this proof is very similar to our poof for A_TM.)
• Lecture 20 (11/12): Review of last time. Concluded that the class of recognizable languages is not closed under complement. Defined Turing reductions. If A is Turing-reducible to B and B is decidalbe, then A is decidable. Equivalently, if A is Turing-reducible to B and A is undecidable, then B is undecidable. Noted that we've already implicitly used Turing-reductions to show positive and negative results (decidability and undecidability), including our proofs that HALT_TM is undecidable (by reduction from A_TM). Used Turing reductions to show that E_TM and EQ_TM are not decidable.
  Reading: 5.1 (beginning), 6.3 (note: Sipser's "informal notion of reducibility" in chapter 5 is the same as the formal notion of Turing reducibility which he defines in section 6.3).
• Lecture 21 (11/19): Review of quiz 8 common mistakes. Discussed an alternative reduction of A_TM to E_TM. Proof that REG_TM is not decidable. Stated Rice's theorem. The proof of Rice's theorem (as well as some examples, discussion, and bonus material: refined Rice's theorem) was uploaded as a separate video (and lecture notes) to courseworks. You are not responsible for the proof of Rice's thorem (though it is just another example of a reduction).
  Reading: 5.1 (beginning), and problem 5.28 and its solution.
• Lecture 22 (11/24): Review of Rice's theorem. Reviewed ways we have to prove a language is not decidable: diagonalization, Turing reduction, Rice's theorem. Discussed why a Turing reduction from A to B is not sufficient to show that if B is recognizable then so is A, and thus a Turing reduction is not generally sufficient for proving unrecognizability. But it is sufficient in the special case that the Turing reduction calls the decider for B just once and outputs the same -- this special case will be equivalent to a mapping reduction. We defined a mapping reduction and proved the following. If A is mapping reducible to B then A is also Turing reducible to B. If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B. If A is mapping reducible to B and B is recognizable, then A is recognizable. Equivalently, if A is mapping reducible to B and A is not recognizable, then B is not recognizable. We noted that for Turing reductions, if A is Turing reducible to B then any combination of A / complement of A is Turing reducible to any combination of B / complement of B (while for mapping reductions this is true only when you complement both sides). Showed that the complement of A_TM is mapping reducible to REG_TM. Showed that ALL_TM is neither recognizable nor co-recognizable, by showing that the complement of A_TM is mapping reducible to ALL_TM and to the complement of ALL_TM. In summary, ways to show that a language is not recognizable include: prove the language is not decidable but its complement is recognizable, or prove that some other non-recognizable language is mapping reducible to it. We can sometimes also use diagonalization, or use the refined Rice's theorem (see video from last time, but that is not part of lecture material).
  Reading: 5.1 (without the computation histories), 5.3

• Sat 9/19 5pm: Garrison Grogan
• Fri 9/25, 12:45pm: Matt Lawhon
• Wed 10/7, 9:00am: Monika Francsics
• Fri 10/9, 4:00pm: Sophia Kolak, proof writing and discrete math background
• Sun 10/11, 9:00pm: Diego Prado, review for Exam 1 (same material as Rahul's session)
• Mon 10/12, 12noon: Rahul Kataria, review for Exam 1 (same material as Diego's session)
• Fri 10/23, 12noon: Bryce Monier
• Sat 11/7, 11am: Anushka Murthy (recorded)
• Sat 11/14, 2pm: Alan Du (recorded)
• Sat 11/28, 6pm: Eli Goldin (redcorded)
• Wed 12/2, 6pm: Jonathan Zhang, review for Exam 2 (same material as Yulong's session)
• Wed 12/2, 10pm: Yulong Li, review for Exam 2 (same material as Jonathan's session)

For each quiz that you submit, your score will automatically be increased by 25% of the total point value, up to a 100% ceiling. For example, on a quiz with a maximum of 10 points, a score of 2 will be converted to 4.5, a score of 6.5 will be converted to 9, and scores of 7.5 and above will all be converted to 10. A quiz that is not submitted gets a score of 0. The lowest quiz score will be dropped.

You must take the quiz alone, without discussion with anyone else (although you are welcome to go over lecture material with other students). You don't have to finish the quiz in a single pass - you could submit part of it, and then go back and complete the rest (as long as it's before the deadline, and you do it on your own without any discussion with others). You are allowed to use your class notes/ textbook when taking the quiz, although the intention is that the quiz should be solvable without any materials (after you have gone over the previous lectures and digested them). No late quizzes will be accepted.

The quiz is meant to be easier than homework problems, and meant to be completed quickly - within at most 15 minutes if you've already gone over and understood the class material to date. If you find yourself working much longer, contact us and come to office hours (sooner rather than later).

• Quiz 1 (this quiz covers some discrete math prerequisites, in addition to the first two lectures): due Tue Sep 15, 8am NYC time
• Quiz 2 due Thur Sep 24, 8am
• Quiz 3 due Thur Oct 1, 8am
• Quiz 4 due Mon Oct 5, 11pm
• Quiz 5 due Thur Oct 22, 8am
• Quiz 6 due Thur Nov 5, 9am
• Quiz 7 due Thur Nov 122, 8am
• Quiz 8 due Thur Nov 19, 8am