In the previous unit, we mentioned the idea that a Turing Machine can be used to prove theories about the capabilities of a computer. We will formalize this concept and study examples of such proofs.
The Halting Problem is a classic example of a computational question: given a program and input, can a computer determine whether that program will halt or run forever without running the program? We will prove the answer using a Turing Machine.
Another example of a major problem in computer science is the P vs NP problem. We will use Turing Machines to examine the idea of polynomial and nondeterministic polynomial, which is necessary to understand the problem: can algorithms that can be verified in polynomial time also be solved in polynomial time? This problem is still unsolved!
We will study several examples of NP problems, and prove that they are in fact NP.