Reference

• randomized algorithms. motwani and raghavan

Models of Computation

Deterministic Turing Machine(TM)

• $M=(S,\Sigma,\delta,s)$
• s is the initial state in S
• halting state HALT, YES(accept) and NO(reject) are states, but formally not in S
• $\text{BLANK}, \text{FIRST} \in \Sigma$, the first symbol of input x is FIRST, and the left-most BLANK is regarded as the end
• The third halting state, HALT, is for the computation of functions whose range is not Boolean
• $\delta: S \times \Sigma \to (S \cup \{ \text{HALT, YES, NO} \}) \times \Sigma \times \{ \leftarrow, \rightarrow, \text{STAY} \}$
• The transition function is designed to ensure that the cursor never falls off the left end of the input, identified by FIRST. The machine may of course overwrite the BLANK symbol.

non-deterministic Turing Machine(NTM)

deterministic TM computation: unique successive configuration, until reach accept/reject configuration

non-deterministic TM computation: may explore multiple successive configurations at once. Reject, loop, accept. A NTM accepts if there’s any valid sequence of configuration resulting in an accepting state.

running time=maximum path

Random Access Machine(RAM)

• RAM, O(1) can load/compute/store O(1) words, O(1) registers
• Each register or memory location may hold an integer that can be accessed as a unit, but an algorithm has no access to the representation of the number.