Introduced by Alan Turing. A model that can deal with arbitrary length of input, and is as powerful as there can be.
For DFA, we can only do a single pass and use only up to a constant memory.
So if we want to have more computation powers for DFA, what should we do to extend it?
→ Multiple passes
→ Allow the “head” to move both ways (to left and right)
→ Variable memory (Give storage capacity that is not bounded and is writable)
→ Read/Write to memory
→ “Out of order” (random access machines)
Algorithm is a finite answer to an infinite number of questions!
Turing Machines $\equiv$ DFAs + left/right movement on input + read/write memory
We can assume that for Turing Machines, we load all the input inside a memory tape and we can have a fixed number of states k
In each step of computation:
“You are in state i and read a bit a (0 or 1) at the “head“ of the tape”
→ Actions that we can do:
Let’s have a more formal definition
<aside> <img src="/icons/light-bulb_green.svg" alt="/icons/light-bulb_green.svg" width="40px" /> Definition: Turing Machine → K states → Have an alphabet $\Sigma$ that contains $\{0,1,\empty,\triangleright \}$ (”$\triangleright$”: notation for start of the tape, “$\empty$”: notation for nothing is written)
</aside>
Transition $S(state_i, a) = (state_j, b, \text { "Move head certain way"})$ where a, b are symbol from alphabet and “Move head” could be Left, Right, Stay or Halt
Given a input loaded in memory, the Turing Machine can calculate it by