See pumping lemma, Minimizing DFAs, Myhill-Nerode Theorem

Streaming Algorithms, Communication Complexity

turing machine

get hyped: turing machine

• Church-Turing thesis
• decidable predicate and predicate recognizability
• universal turing machine
• there are non-recognizable languages
• L is decidable IFF L and not L are both recognizable
• Mapping Reduction
  • halting problem
• computable function

Rice’s Theorem, Oracle Reduction, Self-Reference and the Recursion Theorem

mathematics

Time Complexity + Non-deterministic Turing Machines

P vs. NP, polynomial time mapping reduction