Turing Machine Representations

 

What Is a Representation?

A Turing Machine (TM) can be described in many equivalent ways because it’s an abstract mathematical model.

The most common representations are:

1. Instantaneous Description (ID) — a snapshot of the machine’s current configuration.

2. State Transition Table — a tabular representation of the transition function δ.

3. State Diagram — a graphical representation of δ.

All three describe the same machine behavior — they just present it in different formats.

⚙️ 1. Instantaneous Description (ID)

🔹 Definition

An instantaneous description (ID) gives a complete snapshot of the machine’s current situation — that is, what the TM looks like at any instant during computation.

An ID includes:

• The current state of the control unit

• The current contents of the tape

• The current position of the read–write head

---

🔹 Representation Format

If the tape content is divided as:

$$x a y$$

where:

• x is the part of the tape to the left of the head,

• a is the symbol currently being scanned, and

• y is the part of the tape to the right of the head,

then the instantaneous description is written as:

$$x q a y$$

Here, q is the current state of the Turing machine.

---

🔹 Example

Suppose a Turing machine is in state q₁, scanning the first b in the string:

a b b a

Then the ID is:

$$a q₁ b b a$$

If δ(q₁, b) = (q₂, X, R),
the next ID is:

$$a X q₂ b a$$

This means:

• The scanned b is replaced by X.

• The head moves one cell to the right.

• The machine enters state q₂.

---

🔹 Transition Notation

We write one computational step as:

$$\vdash$$

So if configuration C₁ changes to C₂ in one move, we write:

$$C₁ \vdash C₂$$

And if it changes in several moves:

$$C₁ \vdash^* C₂$$

⚙️ Transition Function (δ)

The transition function is formally defined as:

$$\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$$

Meaning:

Given the current state and scanned symbol,
the TM writes a new symbol, moves the head left or right, and enters a new state.

So,

$$\delta(p, a) = (q, b, D)$$

means:

• In state p, reading a,

• write b,

• move Left (L) or Right (R),

• go to state q.

---

🔄 Relating δ to Instantaneous Descriptions

Let the current ID be:

$$x p a y$$
$$\delta(p, a) = (q, b, R)$$

Then, after one move, the new ID becomes:

$$x b q y$$

(because we wrote b, moved head one step right, and entered state q).

🧾 2. State Transition Table

The state transition table is a tabular representation of the transition function:

$$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$$

Each row corresponds to a state and each column corresponds to a symbol on the tape.

🔁 3. State Diagram (Transition Graph)

A state diagram (or transition graph) is a visual representation of δ.

Each state is drawn as a circle, and arrows (labeled transitions) show how the machine moves from one state to another.

Transition Diagram and Transition Table

🧩 Summary of Representations

Representation	What It Shows	Advantage
Instantaneous Description (ID)	Snapshot of the entire configuration (tape + head + state)	Step-by-step trace of computation
Transition Table	List of all transitions (δ-function)	Precise, compact, and easy for formal definition
State Diagram	Graphical picture of transitions	Intuitive and easy to visualize machine behavior