📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT 5: TURING MACHINES & UNDECIDABILITY (university of allahabad )

 

🔴 UNIT 5: TURING MACHINES & UNDECIDABILITY

---

1️⃣ Turing Machine (TM)

✅ Definition

A Turing Machine is the most powerful abstract machine used to model computation.

It can solve any problem that is algorithmically computable.

---

✅ Components of Turing Machine

A Turing Machine is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, B, F)

Where:

• Q → Finite set of states

• Σ → Input alphabet

• Γ → Tape alphabet

• δ → Transition function

• q₀ → Initial state

• B → Blank symbol

• F → Final (accepting) states

---

✅ Structure of TM

A Turing Machine has:

• Infinite tape

• Read/Write head

• Finite control

• Move Left / Right / Stay

---

2️⃣ Instantaneous Description (ID)

✅ Definition

An Instantaneous Description (ID) represents the current state of the Turing Machine.

Format:

$$α q β$$

Where:

• α → Tape content to left of head

• q → Current state

• β → Tape content under and right of head

---

✅ Example

101q011

Means:

• Head is reading 0

• Current state = q

• Tape contains 101011

---

3️⃣ Language Accepted by Turing Machine

A language L is said to be accepted by a TM if:

• TM halts in accepting state for every string in L

• TM may loop for strings not in L

---

4️⃣ Turing Computability of Functions

A function is Turing computable if:

• There exists a TM that computes it

• TM halts for all valid inputs

---

Important Fact

All recursive functions are Turing computable

---

5️⃣ Equivalence of Turing Machine and Recursive Functions

Theorem:

A function is Turing computable if and only if it is partial recursive.

This proves:

• Turing Machine

• Recursive Functions

• Lambda Calculus

➡ All are equivalent models of computation

---

6️⃣ Recursively Enumerable (RE) Languages

✅ Definition

A language L is recursively enumerable if:

• There exists a Turing Machine that accepts L

• TM may not halt for strings not in L

---

✅ Types of Languages

Language Type	Description
Recursive	TM halts for all inputs
Recursively Enumerable	TM may loop
Non-RE	Not accepted by any TM

---

7️⃣ Recursively Decidable Languages

✅ Definition

A language is recursive (decidable) if:

• TM halts for all inputs

• Gives YES or NO answer

---

Relationship

Recursive ⊂ Recursively Enumerable

---

8️⃣ Undecidability

✅ Definition

A problem is undecidable if:

• No algorithm exists to solve it for all inputs

• TM cannot decide it

---

9️⃣ Undecidability of Type-0 Grammar

Type-0 grammars generate:

• Recursively enumerable languages

Problem:

Whether a given string belongs to a Type-0 grammar?

Result:

❌ Undecidable

Because:

• Equivalent to Halting Problem

• No general algorithm exists

---

🔟 Church–Turing Thesis

✅ Statement

Any function that can be computed by an algorithm can be computed by a Turing Machine.

---

⚠ Important Points

• Not a theorem (cannot be proved)

• Based on strong evidence

• Foundation of computer science

---

1️⃣1️⃣ Halting Problem

✅ Problem Statement

Given a program P and input I, determine:

Will P halt or run forever?

---

✅ Result

🚫 Halting Problem is Undecidable

---

✅ Proof Idea (Simple)

• Assume halting problem is decidable

• Construct a contradictory machine

• Leads to logical contradiction

• Hence undecidable

---

1️⃣2️⃣ Importance of Halting Problem

• Shows limits of computation

• Basis of undecidability theory

• Used in compiler design & verification