Notation New Concepts Church-Turing Thesis turing machine multi-tape TM theorem Time Complexity P NP: verifier formulation of NP non-determinism Important Results / Claims Turing Machine as a universal algorithm properties of turing machines Church-Turing thesis as local steps time hierarchy theorem Why stuff is great why TM is awesome why NP is awesome Questions Scratch Let L \in P, and M be the polytime TM that decides L. Define M’ to be M with q_{\text{accept}} and q_{\text{reject}} swapped. Fact: M’ decides \neg L.