---
title: "SU-CS254 JAN082025"
source: https://www.jemoka.com/posts/kbhsu_cs254_jan082025/
date: 2025-01-08
---

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&rsquo;\) to be \(M\) with \(q_{\text{accept}}\) and \(q_{\text{reject}}\) swapped. Fact: \(M&rsquo;\) decides \(\neg L\).
