# Turing Machine A **Turing Machine** is an abstract device that operates on an infinitely long tape made up of 1s and 0s. The machine has an internal state. It then reads a cell. Depending on it's state and what it reads, it then writes a 1 or 0, and then shifts left or right. In order to represent the machines entire behavior. Below, because there are four states, $A, B, C, D$, we say this is a $4$ state machine.  For every combination of the state and the value it reads, we have three actions to determine: 1. The value to write 2. How shift 3. What state to transition into For instance, according to the above table, if the system state is $A$ and it reads a value of $0$, we would write a value of $1$, move to the left, and change the system state to $D$. --- Date: 20241117 Links to: Tags: References: * [The Boundary of Computation - YouTube](https://www.youtube.com/watch?v=kmAc1nDizu0&t=1s)