## Definition

A Turing machine is a -tuple

where each element is defined as follows

– A finite set of states

– The start state

– Single accepting state

– Single rejecting state

Note that, and are two distinct states.

– Finite input alphabet not containing the blank symbol . The blank symbol 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.

– Finite tape alphabet with and .

– Transition function (a total function) mapped as follows

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 – . There are no outgoing transitions from .

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

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

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

If is , the machine accepts every string. If is , the machine rejects every string.

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