A turing machine looks like the following:

<aside> ➿ $\vdash$ signifies the beggining of the tape, $\sqcup$ denotes a blank character (end) of the tape.

</aside>

We can both read and write to cells in the infinite tape, and move the head left or right.

Notation

Formally, we have a 7 tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

Corresponding to:

• Set of states $Q$
• The input alphabet $\Sigma$ (does not contain $\sqcup$)
• The tape alphabet $\Gamma$, $\sqcup \in \Gamma, \Sigma \subseteq \Gamma$
• $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is the transition function
• $q_0 \in Q$ is the start state
• $q_{accept} \in Q$ is the accept state
• $q_{reject} \in Q$ is the reject state

<aside> ✋🏽 The turing machine halts when it enters the accept or reject state.

</aside>

Configurations

A configuration is a 3 tuple $X = (u,q,v)$ where:

• the current state is $q$
• $uv$ together make up the entire string contained in the tape
• the reading head is at the first symbol of $v$