Turing Machine & Undecidability – Complete Notes (Plain Text)

PART 1: Turing Machines (TM) – Basics and Language Acceptance

1. Turing Machine – Basic Model

A Turing Machine is a 7-tuple:

M = (Q, Σ, Γ, δ, q0, B, F)
Where:

 Q: Finite set of states

 Σ (Sigma): Input alphabet (no blank symbol)

 Γ (Gamma): Tape alphabet (includes Σ and blank symbol)

 δ (delta): Transition function: Q × Γ → Q × Γ × {L, R}

 q0: Start state (q0 ∈ Q)

 B: Blank symbol (B ∈ Γ and not in Σ)

 F: Set of accepting/final states (F ⊆ Q)

2. Formal Definition and Representation

Example:
δ(q0, a) = (q1, X, R)
Meaning: If in state q0 and reading symbol a, the TM:

 Writes symbol X

 Moves tape head right (R)

 Transitions to state q1

3. Instantaneous Description (ID)

Represents the current configuration of the TM.

Format: α q β
Where:

 α: Left part of the tape

 q: Current state

 β: Current symbol under the head and everything to the right

4. Language Acceptance by TM

A Turing Machine accepts a string if it halts in an accepting state after

reading the input.
L(M) = { w ∈ Σ | M accepts w }*
The language accepted by TM M:

PART 2: Variants and Computability

5. Variants of Turing Machines

 Multi-tape TM: Uses multiple tapes; each tape has its own head

 Non-deterministic TM (NTM): Can have multiple possible

transitions; accepts if any branch accepts

 Multi-track TM: A single tape with multiple tracks per cell

 Semi-infinite tape: Tape is infinite in only one direction

All are equivalent in power to a standard TM.

6. TM as Computer of Integer Functions

A TM can compute integer functions like f(x, y) = x + y, where numbers

are represented in unary or binary.
It accepts a string representing input and transforms it into an output on
the tape.

7. Universal Turing Machine (UTM)

A UTM is a special TM that simulates any other TM.

Input: an encoding of machine M and its input w, written as ⟨M, w⟩.

 It interprets the encoded machine’s transitions and simulates them

step-by-step.

 This is the theoretical foundation of modern general-purpose

computers.

8. Church’s Thesis (Church-Turing Thesis)

Church's Thesis states that:

Any function that can be effectively computed (i.e., by a mechanical

procedure or algorithm) can be computed by a Turing Machine.

Alternate Formulations:

 A function is effectively computable ⇔ Turing computable

 Equivalence:

o Turing Machines
 o Lambda Calculus (by Alonzo Church)

o Recursive Functions (by Gödel, Kleene, etc.)

Key Points:

 Not a formal theorem, but a foundational hypothesis accepted in

theoretical CS.

 All known models of computation (like RAM machines, register

machines, etc.) have been shown to be no more powerful than TMs.

 Supports the idea of universality in computation—that TMs

capture all mechanical/algorithmic computation.

Implications:

 Sets the boundary of what can be computed by any algorithm.

 Suggests that undecidability and uncomputability are real and

unavoidable limitations of computation.

PART 3: Recursive Languages, RE Languages, and Undecidability

9. Recursive and Recursively Enumerable (RE) Languages

 Recursive (Decidable): There exists a TM that always halts

(accepts or rejects) for every input.

 RE (Semi-decidable): There exists a TM that halts for strings in the

language (accepts) but may loop forever for strings not in the
language.

Recursive ⊂ RE
All Recursive languages are RE, but not all RE languages are Recursive.

10. Halting Problem

The Halting Problem asks:

Given ⟨M, w⟩, will Turing Machine M halt on input w?

This problem is undecidable:

 No general algorithm (TM) exists to solve this for all possible inputs.

11. Introduction to Undecidability

A problem is undecidable if there is no TM that can decide it (i.e., halt

with a correct yes/no answer) for every possible input.
Examples include:
  Halting problem

 Language emptiness

 Language equivalence

PART 4: PCP and Recursive Function Theory

12. Undecidable Problems About TMs

Examples of undecidable problems:

 Emptiness: Is L(M) = ∅?

 Finiteness: Is L(M) finite?

 Equivalence: Do two TMs accept the same language?

No algorithm can decide these for all TMs.

13. Post Correspondence Problem (PCP)

PCP asks:
Given two lists of strings over the same alphabet:

 A = [w1, w2, ..., wn]

 B = [x1, x2, ..., xn]

Is there a sequence of indices i1, i2, ..., ik such that:

w_i1 w_i2 ... w_ik = x_i1 x_i2 ... x_ik?

This problem is undecidable over alphabets of size ≥ 2.

14. Modified PCP (MPCP)

Like PCP, but the solution must start with the first pair (w1, x1).
Formally: Is there a sequence of indices such that:
w1 w_i2 ... w_ik = x1 x_i2 ... x_ik?
MPCP is also undecidable.

15. Introduction to Recursive Function Theory

A. Primitive Recursive Functions:

 Built using basic functions (zero, successor, projection)

 Closed under composition and primitive recursion

 Always terminating

 Examples: addition, multiplication, factorial

B. μ-Recursive (General Recursive) Functions:

 Extends primitive recursive by allowing minimization (μ-operator)

 May not terminate for some inputs

 Equivalent in power to Turing Machines

C. Lambda Calculus:

 Formal system by Church for expressing computation via function

abstraction and application

 Equivalent to TMs in power

Equivalence Summary:
Lambda Calculus ≡ μ-Recursive Functions ≡ Turing Machines

Quick Summary Table

Decidable (TM Semi-Decidable Undecidab

Concept
Halts) (RE) le

Recursive
✅ ✅ ❌
Language

RE Language ❌ ✅ ❌

Halting Problem ❌ ✅ ✅

PCP / MPCP ❌ ✅ (in some cases) ✅

Language
❌ ❌ ✅
Equivalence

SOME IMPORTANT QUESTIONS

✅ Q1. Define a Turing Machine. Explain its components with a
diagram. Also, describe how a TM accepts a language.

Answer:

A Turing Machine (TM) is a theoretical model proposed by Alan Turing

that defines a mathematical representation of computation. It is used to
model the behavior of algorithms and understand the limits of what can
be computed.

Formal Definition:

A TM is a 7-tuple:

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

Where:

 Q = Finite set of states

 Σ = Input alphabet (does not contain blank symbol)

 Γ = Tape alphabet (Σ ⊆ Γ and includes the blank symbol 'B')

 δ = Transition function: Q × Γ → Q × Γ × {L, R}

 q₀ = Initial state (q₀ ∈ Q)

 B = Blank symbol

 F = Set of final or accepting states (F ⊆ Q)

Diagram:

Tape: | a | b | a | _ | _ | ...

Head

Control Unit: δ(q, a) = (q’, b, R)

Instantaneous Description (ID):

 Represents current state, tape contents, and head position.

 Written as u q v, where tape content is uv, q is current state, head

on first symbol of v.

Language Acceptance:

A TM accepts an input string w if starting from the initial state q₀ and the
input placed on the tape, it eventually enters a final state from F.
L(M) = { w ∈ Σ | M accepts w }*

✅ Q2. Explain Church-Turing Thesis. Why is it important in

computability theory?

Answer:

The Church-Turing Thesis states that any function that is effectively

computable by an algorithm can be computed by a Turing
Machine.

It was proposed independently by:

 Alonzo Church using λ-calculus.

 Alan Turing using Turing Machines.

Explanation:

 “Effectively computable” means there exists a step-by-step

mechanical procedure.

 The thesis connects informal notion of algorithm with formal models

like TM, λ-calculus, and recursive functions.

Importance:

1. Foundation of Computability Theory.

2. Defines the limits of computation.

3. Establishes equivalence of various computation models.

4. Helps identify decidable vs. undecidable problems.

5. Supports design of general-purpose computers (Universal TM).

Note: It is a thesis, not a theorem—cannot be formally proved but is

universally accepted.

✅ Q3. What is the Halting Problem? Show that it is undecidable.

Answer:

The Halting Problem asks:

“Given a TM M and an input w, will M halt on w?”

Formal Statement:

 Given ⟨M, w⟩, determine if M halts on input w.

Undecidability Proof (By Contradiction):

1. Suppose there exists a TM H that solves the halting problem:

o H(⟨M, w⟩) returns YES if M halts on w, else NO.

2. Construct a TM D as follows:

o D(⟨M⟩): If H(⟨M, ⟨M⟩⟩) = YES → go into infinite loop.

o Else → halt.

3. Now, ask: Does D halt on input ⟨D⟩?

o If H(⟨D, ⟨D⟩⟩) = YES → D loops → contradiction.

o If H = NO → D halts → contradiction.

Hence, no such TM H exists → Halting problem is undecidable.

✅ Q4. Differentiate between Recursive and Recursively

Enumerable Languages. Give examples.

Answer:

Recursive Recursively Enumerable

Feature
Language (R) Language (RE)

TM Halts on All Inputs? Yes No (only on accepted inputs)

Decidable? Yes No

Complement Also in
Yes Not necessarily
Class?

Closure under Union,

Yes Yes
Intersection

Palindromes over
Example Halting problem language
{a, b}

Definitions:

 Recursive Language (Decidable): A language for which a TM

always halts and gives YES or NO.

 RE Language: TM halts only if the string is accepted; may loop

forever for rejection.

Examples:

 Recursive: { w | w has equal number of a’s and b’s }

  RE but not Recursive: { ⟨M, w⟩ | M halts on w } (Halting problem)

✅ Q5. What is Post Correspondence Problem (PCP)? Show that it is

undecidable.

Answer:

Post Correspondence Problem (PCP):

Given:

 Two lists A = [w₁, w₂, ..., wₙ], B = [x₁, x₂, ..., xₙ] over the same
alphabet.

 Is there a sequence i₁, i₂, ..., iₖ such that:

wᵢ₁ wᵢ₂ ... wᵢₖ = xᵢ₁ xᵢ₂ ... xᵢₖ

Example:

A: [ab, a, ba]
B: [a, aba, b]

Try sequences like i₁ = 2, i₂ = 1, i₃ = 3 to match both sides.

Undecidability Proof Idea:

 Reduce the TM acceptance problem to PCP.

 Encode computation of TM into list of strings.

 If TM accepts input, then corresponding PCP has a solution.

Conclusion: PCP is undecidable.

w ∈ {0,1} }. Justify if it is decidable.*

✅ Q6. Design a Turing Machine to accept the language L = { ww |

Answer:

L = { ww | w ∈ {0,1} }*

This language contains strings like:

 00, 0101, 110011, etc.

Challenges:

 No fixed delimiter between the two w’s.

 Must compare both halves without knowing midpoint.

TM Strategy (Outline):

1. Mark first symbol (say ‘0’) with X.

2. Move to the right and find the corresponding unmarked symbol from
the second half.

3. Match and mark it with Y.

4. Repeat for all characters.

Use multi-pass scanning to mark and verify.

Is it Decidable?

Yes. Even though hard, a TM can:

 Check all splits of string into two halves.

 Compare both.

 Halt with YES if match found, else NO.

Hence, L is Recursive (Decidable).

✅ Q7. Explain the concept of a Universal Turing Machine with an

example.

Answer:

A Universal Turing Machine (UTM) is a Turing Machine that can

simulate any other TM on any input.

Input to UTM:

 A pair ⟨M, w⟩

o Where M = Encoding of a TM.

o w = Input string.

UTM reads this encoding and mimics M’s transitions.

Example:

Let M accept strings over {a, b} with even number of a’s.

 Encode M into binary (say: ⟨M⟩).

 Give input string w = abaa.

UTM reads ⟨M⟩ and w, simulates M, and decides whether M accepts w.

Importance:
  Forms the basis of general-purpose computers.

 Proves the existence of universal computation.

 Central to Church-Turing Thesis.

✅ Q8. Explain Recursive Function Theory. Differentiate Primitive

Recursive and μ-Recursive Functions.

Answer:

Recursive Function Theory studies functions that can be computed

mechanically.

Three Classes of Functions:

1. Initial Functions: Zero, Successor, Projection

2. Primitive Recursive: Built using composition and primitive

recursion.

3. General (μ-) Recursive: Includes minimization (μ-operator).

Differences:

Primitive General Recursive (μ-

Feature
Recursive Recursive)

Halting
Yes No
Guaranteed

Includes
No Yes
Minimization

Computational
Less powerful Equivalent to TM
Power

Addition, Ackermann function, Halting-

Examples
Factorial check

Relation with TM:

 General recursive functions are equivalent to TM.

 Thus, recursive function theory helps us define decidability

and computability in formal terms.
✅ NUMERICAL-STYLE PRACTICE QUESTIONS (10 Marks Each)

{ w#w | w ∈ {0,1} }*
🔹 Q1. Construct a Turing Machine (TM) to accept the language L =

Language: All strings where the part before and after # is

identical.

📝 Requirements:

 Read first symbol from left.

 Match it with corresponding symbol after #.

 Mark matched symbols (e.g., X, Y).

 Repeat until entire string is processed.

✅ Expected Steps in Answer:

1. Clearly define the TM states.

2. Show transitions (can be a table or verbal).

3. Explain marking and matching logic.

4. Conclude acceptance/rejection mechanism.

🔹 Q2. Simulate the Turing Machine for input string abb

Given TM transitions:

Stat Rea Writ Mov Next

e d e e State

q0 a X R q1

q1 b Y R q2

q2 b Y L q3

q3 Y Y L q3

q3 X X R qf

✅ Expected Steps in Answer:

 Start with q0 abb

 Show all Instantaneous Descriptions (IDs).

  Final state reached: Accept / Reject

🔹 Q3. Construct a TM to accept all strings with equal number of 0s

and 1s

📝 L = { w ∈ {0,1} | #0(w) = #1(w) }*

✅ Expected TM Design Strategy:

 Replace one 0 with X and one 1 with Y each time.

 Loop until all 0s and 1s are marked.

 Accept if no unmarked 0 or 1 remains.

 Reject otherwise.

✅ Expected Components:

 State diagram or transition table.

 Explanation of working.

 Justify correctness and halting.

🔹 Q4. Simulate a Universal Turing Machine (UTM)

Given: A Turing Machine M that accepts strings with even number of a.

Input: w = aa

✅ Expected Steps in Answer:

 Encode TM M as ⟨M⟩

 UTM input = ⟨M⟩, w

 Explain how UTM reads ⟨M⟩ and simulates M step by step.

 Final result: Accept

(No need for actual encoding, focus on explaining simulation process)

🔹 Q5. Given a TM M and input w = aab, show complete sequence

of IDs

Given Transitions:

δ(q0, a) = (q1, X, R)

δ(q1, a) = (q1, a, R)
δ(q1, b) = (q2, Y, L)

δ(q2, a) = (q2, a, L)

δ(q2, X) = (qf, X, R)

✅ Expected Answer:

 Initial: q0 aab

 Show sequence until final state qf

 Each ID must have state and tape contents clearly marked.

🔹 Q6. Construct a TM for palindrome over {0,1}

📝 L = { w ∈ {0,1} | w = w^R }*

✅ Strategy:

 Match first and last symbol (replace with X/Y).

 Move inward.

 Accept if all match, reject if mismatch.

✅ Expected Answer:

 Describe approach.

 State transitions (table or pseudo).

 Example input trace: 0110, show IDs or outline.

🔹 Q7. Given the TM, does it accept input w = 010? Justify using
transitions and configurations

TM Table:

Stat Rea Writ Mov Nex

e d e e t

q0 0 X R q1

q1 1 Y R q2

q2 0 X L q3

q3 Y Y L q3

q3 X X R qf
✅ Answer Format:

 Show sequence: q0 010 → ... → qf

 Final verdict: Accept

🔹 Q8. Convert a μ-recursive function (like factorial) into TM-style

logic

📝 Given Function: f(n) = n!

✅ Expected Answer:

 Explain function via recursion:

f(0) = 1, f(n) = n × f(n-1)

 Write a TM algorithm or simulate its logic.

 Explain use of tape for recursive calls, loop handling.

✨ BONUS: Fill-in or Objective-Style Numericals (2–5 Marks) for

Quick Practice

 What is the ID for the configuration after 2 steps on input 101?

 How many transitions will be made by TM M on input ababa?

 Design a TM that accepts a^n b^n c^n, or justify why it's not TM-
recognizable.