1. NP problem
decidable problems: P, NP
turing machine: 图灵机：改变状态，在当前位置擦除并写入符号，左、右、或不移动
- Deterministic Turing Machine
executes one instruction at each point in time. Then depending on the instruction, it goes to he next unique instruction.
- Nondeterministic Turing Machine
free to choose its next step from a finite set. And if one of these steps leads to a solution, it will always choose the correct one.