TM Definition and Examples

Formal Definition of Turing Machine

Turing Machine is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, qaccept, qreject)

Where:

Q: Finite set of states
Σ: Input alphabet (does not contain blank B)
Γ: Tape alphabet (Σ ⊂ Γ and B ∈ Γ)
δ: Transition function δ: Q × Γ → Q × Γ × {L, R}
q₀: Start state (q₀ ∈ Q)
qaccept: Accept state (qaccept ∈ Q)
qreject: Reject state (qreject ∈ Q, qreject ≠ qaccept)

Component Details

Q - States

Finite set of control states

Must include:

Start state q₀
Accept state qaccept
Reject state qreject

Can include: Any number of intermediate states

Example: Q = {q₀, q₁, q₂, qaccept, qreject}

Σ - Input Alphabet

Symbols that can appear in input string

Does NOT contain: Blank symbol B

Example: Σ = {0, 1} or Σ = {a, b, c}

Γ - Tape Alphabet

All symbols that can appear on tape

Must contain: Σ ∪ {B}

Can contain: Work symbols (X, Y, Z, etc.)

Example: Γ = {0, 1, X, Y, B}

Relationship: Σ ⊂ Γ

δ - Transition Function

Signature: δ: Q × Γ → Q × Γ × {L, R}

Interpretation: δ(current_state, current_symbol) = (new_state, write_symbol, direction)

Partial function: Need not be defined for all inputs

If undefined, TM “crashes” (rejects)

Halting states: δ not defined for qaccept and qreject

Example:

δ(q₀, 0) = (q₁, X, R)  "Read 0, write X, move right, go to q₁"
δ(q₁, 1) = (q₂, Y, L)  "Read 1, write Y, move left, go to q₂"

Configuration

Configuration describes complete state of TM at any point

Notation: uqv

u: Tape contents to left of head
q: Current state
v: Tape contents from head rightward

Example: abc q₁ xyz

Tape: …abcxyz…
State: q₁
Head: At ‘x’

Start Configuration

For input w: q₀w

State: q₀ (start state)
Tape: w (input string)
Head: At first symbol of w

Example: Input “101” → Start: q₀101

Halting Configuration

Accept: uqacceptv (reached accept state)

Reject: uqrejectv (reached reject state)

No further moves possible from halting states

Computation Step (⊢)

Yields in one step: C₁ ⊢ C₂

Move Right

If: δ(q, a) = (p, b, R)

Then: uqav ⊢ ubpv

Meaning:

Replace ‘a’ with ‘b’
Move head right
State q → p

Example:

δ(q₀, a) = (q₁, X, R)
Input: q₀abc
Step: q₀abc ⊢ Xq₁bc

Move Left

If: δ(q, a) = (p, b, L)

Then: cuqav ⊢ cpubv

Meaning:

Replace ‘a’ with ‘b’
Move head left
State q → p

Example:

δ(q₁, b) = (q₀, Y, L)
Input: aXq₁bc
Step: aXq₁bc ⊢ aq₀Yc

Multiple Steps

⊢*: Yields in zero or more steps

⊢⁺: Yields in one or more steps

Example: q₀abc ⊢* Xq₂YZ means can reach Xq₂YZ from q₀abc

Acceptance and Rejection

Acceptance

M accepts w if:

q₀w ⊢* uqacceptv

for some u, v

Meaning: Starting from q₀w, eventually reach qaccept

Rejection

M rejects w if:

q₀w ⊢* uqrejectv (explicit rejection), OR
No valid transition exists (crashes)

Looping

M loops on w if:

Never reaches qaccept or qreject
Runs forever

Language of Turing Machine

L(M) = {w ∈ Σ* | M accepts w}

Set of all strings that M accepts

Note: Does not include strings M rejects or loops on

Example 1: {0ⁿ1ⁿ | n ≥ 0}

Language: Equal number of 0’s and 1’s, 0’s first

Strategy

1. Mark leftmost 0 with X
2. Find matching 1, mark with Y
3. Go back to start
4. Repeat until all matched
5. Check all marked (accept) or mismatch (reject)

TM Definition

Q = {q₀, q₁, q₂, q₃, q₄, qaccept, qreject}
Σ = {0, 1}
Γ = {0, 1, X, Y, B}
Start: q₀

Transitions

// Phase 1: Mark leftmost 0
δ(q₀, 0) = (q₁, X, R)    // Mark first 0 with X, move right
δ(q₀, Y) = (q₀, Y, R)    // Skip already marked Y's
δ(q₀, B) = (qaccept, B, R) // All matched, accept

// Phase 2: Find matching 1
δ(q₁, 0) = (q₁, 0, R)    // Skip 0's
δ(q₁, Y) = (q₁, Y, R)    // Skip Y's
δ(q₁, 1) = (q₂, Y, L)    // Found 1, mark with Y, go back

// Phase 3: Return to start
δ(q₂, 0) = (q₂, 0, L)    // Move left over 0's
δ(q₂, Y) = (q₂, Y, L)    // Move left over Y's
δ(q₂, X) = (q₀, X, R)    // Found X, start next iteration

// Edge cases
δ(q₀, 1) = (qreject, 1, R)  // 1 before all 0's matched
δ(q₁, B) = (qreject, B, R)   // No 1 to match

Trace for “0011”

q₀0011      // Start
⊢ Xq₁011    // Mark first 0
⊢ X0q₁11    // Skip second 0
⊢ X0Yq₂1    // Mark first 1
⊢ Xq₂0Y1    // Move left
⊢ q₂X0Y1    // At X
⊢ Xq₀0Y1    // Start next iteration
⊢ XXq₁Y1    // Mark second 0
⊢ XXYq₁1    // Skip Y
⊢ XXYYq₂    // Mark second 1
⊢ XXYq₂Y    // Move left
⊢ XXq₂YY    // Move left
⊢ Xq₂XYY    // Move left
⊢ q₂XXYY    // At start
⊢ Xq₀XYY    // Start next iteration
⊢ XXq₀YY    // Skip X
⊢ XXYq₀Y    // Skip Y
⊢ XXYYq₀    // At blank
⊢ XXYYqaccept // Accept! ✓

Example 2: {aⁿbⁿcⁿ | n ≥ 1}

Language: Equal a’s, b’s, and c’s (not context-free!)

Strategy

1. Mark leftmost 'a' with X
2. Mark leftmost 'b' with Y
3. Mark leftmost 'c' with Z
4. Go back to start
5. Repeat until all matched
6. Accept if all marked correctly

TM Definition

Q = {q₀, q₁, q₂, q₃, q₄, qaccept, qreject}
Σ = {a, b, c}
Γ = {a, b, c, X, Y, Z, B}

Key Transitions

// Mark 'a'
δ(q₀, a) = (q₁, X, R)    // Mark a with X

// Find 'b'
δ(q₁, a) = (q₁, a, R)    // Skip a's
δ(q₁, Y) = (q₁, Y, R)    // Skip Y's
δ(q₁, b) = (q₂, Y, R)    // Mark b with Y

// Find 'c'
δ(q₂, b) = (q₂, b, R)    // Skip b's
δ(q₂, Z) = (q₂, Z, R)    // Skip Z's
δ(q₂, c) = (q₃, Z, L)    // Mark c with Z

// Return to start
δ(q₃, ...) = (q₃, ..., L) // Move left
δ(q₃, X) = (q₀, X, R)     // At marked position, restart

// Accept when all marked
δ(q₀, Y) = (q₄, Y, R)     // Check all marked
δ(q₄, Y) = (q₄, Y, R)     // Skip Y's
δ(q₄, Z) = (q₄, Z, R)     // Skip Z's
δ(q₄, B) = (qaccept, B, R) // All matched!

Trace for “aabbcc”

q₀aabbcc
⊢ Xq₁abbcc     // Mark first a
⊢ Xaq₁bbcc     // Skip second a
⊢ XaYq₂bcc     // Mark first b
⊢ XaYbq₂cc     // Skip second b
⊢ XaYbZq₃c     // Mark first c
⊢ ... (return to start)
⊢ Xq₀aYbZc     // Next iteration
⊢ XXq₁YbZc     // Mark second a
⊢ ... (match second b and c)
⊢ XXYYZZq₀     // All matched
⊢ XXYYZZqaccept // Accept! ✓

Example 3: {ww | w ∈ {a,b}*}

Language: String repeated twice (not context-free!)

Strategy

1. Mark middle point (non-deterministically guess)
2. Compare first half with second half
3. Accept if match

Alternative (deterministic):

1. Try each possible middle point
2. For each, check if first half = second half
3. Accept if any middle point works

Simplified Approach

1. Mark first symbol, remember it
2. Count to middle (guess)
3. Check if same symbol at middle+1
4. Repeat for all symbols

Complex! But computable by TM.

Example 4: {aⁿ² | n ≥ 0}

Language: Strings of length n² (1, 4, 9, 16, 25, …)

Strategy

1. Mark groups of increasing size
2. Group 1: 1 symbol
3. Group 2: 3 symbols (cumulative: 4 = 2²)
4. Group 3: 5 symbols (cumulative: 9 = 3²)
5. Pattern: Mark 2n-1 symbols for group n
6. Accept if all marked exactly

Insight: n² = 1 + 3 + 5 + … + (2n-1)

Transitions (Conceptual)

1. Count first 1 symbol, mark
2. Count next 3 symbols, mark
3. Count next 5 symbols, mark
4. Continue pattern
5. Accept if reached end exactly

Example 5: Prime Numbers {aᵖ | p prime}

Language: Strings whose length is prime

Strategy

1. Count length n
2. Try dividing n by 2, 3, 4, ..., n-1
3. Accept if no divisor found (prime)
4. Reject if divisor found (composite)

Division Check

To check if n divisible by k:

1. Mark off k symbols repeatedly
2. If end reached exactly, divisible
3. If symbols remain, not divisible

TM can do this!

Example 6: Accepting All Strings {a,b}*

Simplest TM: Accept everything

Q = {q₀, qaccept}
Σ = {a, b}
Γ = {a, b, B}

δ(q₀, a) = (q₀, a, R)     // Skip a's
δ(q₀, b) = (q₀, b, R)     // Skip b's
δ(q₀, B) = (qaccept, B, R) // Accept at end

Always accepts: Every input reaches qaccept

Example 7: Rejecting All Strings ∅

TM that accepts nothing:

Q = {q₀, qreject}
Σ = {a, b}
Γ = {a, b, B}

δ(q₀, a) = (qreject, a, R)   // Immediate reject
δ(q₀, b) = (qreject, b, R)   // Immediate reject
δ(q₀, B) = (qreject, B, R)   // Even empty rejects

Always rejects: Every input reaches qreject immediately

State Diagram Notation

Nodes: States (circles)

Edges: Transitions

Label: a → b, D

Read ‘a’
Write ‘b’
Direction D (L or R)

Example:

    0→X,R
(q₀) ────→ (q₁)

Reads 0, writes X, moves right, goes to q₁

Common TM Patterns

Pattern 1: Marking Symbols

Use: Replace input symbols with markers

Example: a → X, b → Y

Pattern 2: Shuttling

Use: Move back and forth across tape

Example: Match first half with second half

Pattern 3: Counting

Use: Count symbols by marking groups

Example: Check equal a’s and b’s

Pattern 4: Searching

Use: Find specific pattern

Example: Locate matching symbol

Pattern 5: Comparing

Use: Compare two parts of input

Example: Check ww pattern

Decidable vs Recognizable

Decidable (Recursive):

TM halts on ALL inputs
Always answers yes or no
L and L̄ both recognizable

Examples:

{0ⁿ1ⁿ}
{aⁿbⁿcⁿ}
{aⁿ²}

Recognizable but not Decidable:

TM may loop on some inputs
Only L recognizable (not L̄)

Examples:

Halting problem
Acceptance problem

Important Exam Points

✓ 7-tuple: (Q, Σ, Γ, δ, q₀, qaccept, qreject)
✓ Configuration: uqv (state q, head at first of v)
✓ Transition: δ(q,a) = (p,b,D) - read a, write b, move D, go to p
✓ Three outcomes: Accept, reject, or loop
✓ {0ⁿ1ⁿ}: Mark and match strategy
✓ {aⁿbⁿcⁿ}: Shows TM > CFL power
✓ {ww}: Not CFL but TM-recognizable
✓ Trace: Show step-by-step configurations
✓ Decidable: Halts on all inputs
✓ Tape alphabet Γ ⊃ input alphabet Σ

Common Mistakes to Avoid

✗ Mistake 1: Not marking symbols
✓ Correct: Use X, Y, Z to track processed symbols

✗ Mistake 2: Forgetting to return to start
✓ Correct: After marking, shuttle back

✗ Mistake 3: Not handling edge cases
✓ Correct: Check empty string, mismatches

✗ Mistake 4: Wrong direction
✓ Correct: Carefully track L vs R

✗ Mistake 5: Incomplete transition function
✓ Correct: Define for all needed (q, symbol) pairs

✗ Mistake 6: Confusing Σ and Γ
✓ Correct: Γ includes work symbols, Σ doesn’t

Practice Questions

Q1: Design TM for {0ⁿ1²ⁿ | n ≥ 0}

Answer: Mark each 0 with X, mark two 1’s with Y, repeat.

Q2: Trace q₀011 for {0ⁿ1ⁿ} TM

Answer: q₀011 ⊢ Xq₁11 ⊢ XYq₂1 ⊢ Xq₀Y1 ⊢ XXq₁Y ⊢ … ⊢ qaccept

Q3: Why is {aⁿbⁿcⁿ} TM-recognizable but not CFL?

Answer: TM can count three values using marks; PDA has only one stack.

Q4: What does δ(q₀, a) = (q₁, X, L) mean?

Answer: Read a, write X, move left, go to q₁.

Q5: Can TM recognize {ww}?

Answer: Yes! Mark and compare halves (not possible for PDA).

Q6: Difference between decidable and recognizable?

Answer: Decidable always halts; recognizable may loop.

Summary

7-tuple: (Q, Σ, Γ, δ, q₀, qaccept, qreject)
Configuration: uqv (tape, state, head position)
Transition: δ(q,a) = (p,b,D) - read, write, move, new state
Three outcomes: Accept, reject, loop forever
{0ⁿ1ⁿ}: Mark and match pattern
{aⁿbⁿcⁿ}: Proves TM more powerful than PDA
{ww}: Not CFL, but TM-recognizable
Strategies: Marking, shuttling, counting, comparing
Decidable: Halts on all inputs (recursive)
Recognizable: May loop on reject (recursively enumerable)
Tape alphabet Γ includes work symbols and Σ
Key insight: TM can solve problems impossible for FA/PDA

Detailed examples show how to design and trace Turing Machines!

TM Definition and Examples

Formal Definition of Turing Machine

Component Details

Q - States

Σ - Input Alphabet

Γ - Tape Alphabet

δ - Transition Function

Configuration

Start Configuration

Halting Configuration

Computation Step (⊢)

Move Right

Move Left

Multiple Steps

Acceptance and Rejection

Acceptance

Rejection

Looping

Language of Turing Machine

Example 1: {0ⁿ1ⁿ | n ≥ 0}

Strategy

TM Definition

Transitions

Trace for “0011”

Example 2: {aⁿbⁿcⁿ | n ≥ 1}

Strategy

TM Definition

Key Transitions

Trace for “aabbcc”

Example 3: {ww | w ∈ {a,b}*}

Strategy

Simplified Approach

Example 4: {aⁿ² | n ≥ 0}

Strategy

Transitions (Conceptual)

Example 5: Prime Numbers {aᵖ | p prime}

Strategy

Division Check

Example 6: Accepting All Strings {a,b}*

Example 7: Rejecting All Strings ∅

State Diagram Notation

Common TM Patterns

Pattern 1: Marking Symbols

Pattern 2: Shuttling

Pattern 3: Counting

Pattern 4: Searching

Pattern 5: Comparing

Decidable vs Recognizable

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App