11.1 Machine Definitions
11.1 Machine Definitions A Turing machine is a formal model of an algorithm. It describes computation using a finite set of rules and an unbounded tape. The machine has three main parts: Part Role Tape stores symbols Head reads and writes one cell at a time Finite control stores the current state The tape is divided into cells: $$ \cdots,\ c_{-2},\ c_{-1},\ c_0,\ c_1,\ c_2,\ \cdots $$ Each cell contains...