Encoding of Turing Machine

 

🧩 1. Idea of Encoding 

Every Turing machine $M$ is a finite object — it has a finite number of:

• states,

• symbols, and

• transitions.

Therefore, $M$ can be represented as a finite binary string using only 0s and 1s.

The goal of encoding is to assign a unique binary code to each Turing machine $M$, denoted as ⟨M⟩.
This makes it possible for one Turing machine (the universal TM) to read and simulate another TM just from this code.

---

⚙️ 2. Components of the Turing Machine

A Turing machine is:

$$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$$

We must encode:

• States $q_0, q_1, \ldots, q_k$

• Tape symbols (including blank □ and left-end marker ⊳)

• Transition function $\delta$
  

---

🔢 3. Numeric Coding

We assign natural numbers to each element:

Component	Symbol	Code
States	$q_0, q_1, q_2, \ldots$	0, 00, 000, … (unary numbers)
Tape symbols	e.g. ⊳, 0, 1, □	0, 00, 000, 0000
Directions	L = 0, R = 00, N (no move) = 000

Each item is represented as a string of 0’s, and 1’s are used as separators.

---

🧮 4. Encoding a Transition

A transition of the form:

$$\delta(q_i, X_j) = (q_k, Y_l, D_m)$$

is encoded as:

$$0^i \; 1 \; 0^j \; 1 \; 0^k \; 1 \; 0^l \; 1 \; 0^m$$

That is:

• The number of 0’s in each group represents the index of the state/symbol/direction.

• 1’s separate each field.

---

✅ Example

Suppose we have the transition

$$\delta(q_2, 0) = (q_3, 1, R)$$

We first assign numeric codes:

Item	Code
q₂	00
0 (symbol)	0
q₃	000
1 (symbol)	00
R (direction)	00

Then the encoded transition is:

00 1 0 1 000 1 00 1 00

or compactly:

00101000100100

---

🧾 5. Encoding the Whole Turing Machine

Each transition is encoded as shown above.
Then all transitions are concatenated together, separated by “11” (double separators).

For example, if a machine has transitions $t_1, t_2, \ldots, t_n$:

$$⟨M⟩ = \text{code}(t_1) \; 11 \; \text{code}(t_2) \; 11 \; \cdots \; 11 \; \text{code}(t_n)$$

---

🧠 6. Encoding Input Strings

An input $w\in {\mathrm{\Sigma \; is\; also\; encoded\; in\; a\; similar\; manner:}}^{}$ each symbol by a string of 0’s, separated by 1’s.

Example:
If $w = 01$ and 0→0, 1→00,
then

$$⟨w⟩ = 0 1 00$$

---

⚙️ 7. Putting It All Together

The Universal Turing Machine (U) takes input:

$$<br>$$

$$⟨M⟩\mathrm{\#}⟨w⟩<br>$$

Then U:

1. Decodes ⟨M⟩ — reconstructs the transition table δ.

2. Decodes ⟨w⟩ — initializes the simulated tape.

3. Simulates M step by step on input w.

4. Now we can represent the entire computation as a single input string:

where # separates the machine description from the input.

---

🧩 8. Example of Complete Encoding (Small TM)

Let’s take a toy TM $M$ with transitions:

δ(q0, 0) = (q1, 1, R)
δ(q1, 1) = (q0, 0, R)

Using the unary code scheme:

Item	Code
q₀	0
q₁	00
0	0
1	00
R	00

So:

δ(q0, 0) = (q1, 1, R)
  → 0 1 0 1 00 1 00 1 00
δ(q1, 1) = (q0, 0, R)
  → 00 1 00 1 0 1 0 1 00

Then machine code is:

(0 1 0 1 00 1 00 1 00) 11 (00 1 00 1 0 1 0 1 00)

or, compactly:

0101001001001100100100100100

This long binary string encodes the entire TM!

---

💡 9. Universal Turing Machine

A Universal TM U is one that:

On input ⟨M⟩#⟨w⟩, simulates machine M on input w.

Formally:

$$U(⟨M⟩\mathrm{\#}⟨w⟩)=M(w)$$

If M accepts w, then U accepts the combined input.

---

🧮 10. Summary Table

Concept	Symbol	Meaning
Encoding	⟨M⟩	Binary code (0s for info, 1s for separators)
Transition Encoding	0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ	Encodes δ(qᵢ, aⱼ) = (qₖ, bₗ, Dₘ)
Machine + Input	⟨M⟩#⟨w⟩	Input to Universal TM
Universal TM	U	Simulates M(w)
Key Idea	One TM can simulate all others	Foundation of stored-program computers