Turing Machine - Formal Definition and Observations

Definition

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.

Observations

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.

The Beard Sage

Turing Machine – Formal Definition and Observations

Definition

Observations

Accept/Reject/Run forever

Leave a Reply Cancel reply