Notation
New Concepts
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
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\).