Core Concepts
Turing Machine
An abstract machine with an infinite tape, a read/write head, and a state transition function. Can simulate any computer algorithm.
P vs NP
P = problems solvable in polynomial time. NP = problems verifiable in polynomial time. The question: P = NP? (Unsolved, $1M Millennium Prize).
Halting Problem
There is no algorithm that can determine whether an arbitrary program will halt or run forever. Proved undecidable by Alan Turing (1936).
Church-Turing Thesis
Any function that can be computed by an algorithm can be computed by a Turing machine.
Worked Examples & Applications
Turing Machine Example: TM to check if string has equal 0s and 1s: States: q0 (scan right), q1 (mark 0, scan right), q2 (mark 1, scan left), q_accept. Transitions: q0 reads 0 → write X, move right, go to q1. q1 reads 1 → write Y, move left, go to q2. If all matched, accept.
NP-Complete Example: Boolean Satisfiability (SAT): Given a boolean formula, is there an assignment that makes it true? SAT was the first problem proven NP-complete (Cook-Levin Theorem, 1971). All NP problems can be reduced to SAT.
Practice Questions
Q: What does it mean for a problem to be NP-complete? A: It is in NP, and every problem in NP can be reduced to it in polynomial time. Solving one NP-complete problem efficiently would solve all NP problems efficiently.
Q: What is the Halting Problem? A: The problem of determining whether an arbitrary program will eventually halt or run forever. Proven undecidable — no algorithm can solve it for all possible inputs.