Turing machines
Theory of Computation · Engineering
Study notes
A TM adding 1 to binary: start at leftmost, move right to the end; moving left, flip trailing 1s to 0 until a 0, flip it to 1, halt. Input 1011 -> 1100. Each step is a (state, symbol) -> (write, move, next-state) rule. Simple rules, yet TMs compute anything computable: this is the Church-Turing thesis.