Turing Machine – Formal Definition and Observations


A Turing machine is a 7-tuple

    \begin{equation*} (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) \end{equation*}

where each element is defined as follows

Q – A finite set of states

q_0 – The start state

q_{accept} \in Q – Single accepting state

q_{reject} \in Q – Single rejecting state

Note that, q_{accept} and q_{reject} are two distinct states.

\Sigma – Finite input alphabet not containing the blank symbol \textvisiblespace. The blank symbol \textvisiblespace is a special symbol to indicate that the tape cell is empty.

The input string starts at the beginning of the tape followed by an infinite number of blanks.

\Gamma – Finite tape alphabet with \textvisiblespace \in \Gamma and \Sigma \in \Gamma.

\delta – Transition function (a total function) mapped as follows

    \begin{equation*} Q \setminus \{q_{accept}, q_{reject}\} \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\} \end{equation*}

Given a state and the current tape symbol (pointed by the tape-head) the transition writes a new symbol, changes state and moves the tape-head one cell either to the left or to the right.


  • The above definition makes the Turing Machine a deterministic machine.
  • The input string is initially populated from the left-most end of the tape. Each cell is populated with a single symbol.
  • The input string cells are followed by an infinite number of blank cells. The tape extends infinitely to the right.
  • The tape-head initially starts at the left-most cell (start of the tape). During each transition the tape-head has an option to either go right or left.
  • A computation of a Turing Machine is free to modify the tape-cells (even the input string cells).

Accept/Reject/Run forever

There is only one final state – q_{accept}. There are no outgoing transitions from q_{accept}.

There is only one reject state – q_{reject}. There are no outgoing transitions from q_{reject}.

Once a computation enters q_{accept} state, the Turing Machine accepts that computation. It need not read the entire input.

Once a computation enters q_{reject} state, the Turing Machine rejects that computation. It need not read the entire input.

If q_{accept} is q_0, the machine accepts every string. If q_{reject} is q_0, the machine rejects every string.

It is quite possible that a computation never ends up in either q_{accept} or q_{reject}. This is the case when the machine runs forever.

Leave a Reply

Your email address will not be published. Required fields are marked *