Turing Machines

Definition:

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 × Γ → Q × Γ × {L, R}
• q₀ = Initial state
• B = Blank symbol
• F = Set of final states

Working:

1. Input is written on an infinite tape
2. Read/write head starts at leftmost input symbol
3. TM starts in initial state q₀
4. At each step, based on current state and symbol under head:
   • Change to new state
   • Write a symbol (possibly same)
   • Move head Left or Right
5. TM halts when reaching a final state or no transition defined

Statement:

The Halting Problem asks: Given a TM M and input w, does M halt on w?

This problem is undecidable - no algorithm exists that can solve it for all cases.

Proof by Contradiction:

1. Assume TM H exists that decides halting:
   • H(M,w) = "yes" if M halts on w
   • H(M,w) = "no" if M loops forever
2. Construct D using H:
   • D(M): If H(M,M) = "yes" then loop forever, else halt
3. Run D(D):
   • If D(D) halts → H said "no" → D should loop (contradiction!)
   • If D(D) loops → H said "yes" → D should halt (contradiction!)
4. Contradiction proves H cannot exist.

Significance: Shows computational limits - some problems cannot be solved by any computer.

Definition:

A Universal Turing Machine (UTM) is a TM that can simulate any other TM.

Input:

• Encoded description of TM M
• Input string w

Working:

1. UTM reads the encoding of M
2. UTM simulates M's behavior on w
3. UTM produces same result as M would on w

Significance:

• One machine can do everything any TM can do
• Foundation of stored-program computers
• Programs are data (can be manipulated)
• Proves TMs are programmable

Analogy: A general-purpose computer that runs any program.

Input Format: 1ⁿ 0 1ᵐ (two unary numbers separated by 0)

Output: 1ⁿ⁺ᵐ

Strategy:

1. Find the separator 0
2. Replace 0 with 1 (merging the two numbers)
3. Erase one 1 from the end (to compensate for added 1)

TM Definition:

• Q = {q₀, q₁, q₂, q₃, qf}
• Σ = {1, 0}
• Γ = {1, 0, B}
• F = {qf}

Transitions:

Trace for 11+111 (2+3=5):

Strategy:

1. Mark leftmost unmarked 0 with X
2. Move right to find leftmost unmarked 1
3. Mark it with Y
4. Return left to find next unmarked 0
5. Repeat until all 0s marked
6. Accept if all 1s also marked

TM Definition:

• Q = {q₀, q₁, q₂, q₃, q₄}
• Σ = {0, 1}
• Γ = {0, 1, X, Y, B}
• F = {q₄}

Transitions:

Trace for "0011":

q₀0011 ⊢ Xq₁011 ⊢ X0q₁11 ⊢ Xq₂0Y1 ⊢ q₂X0Y1 ⊢ Xq₀0Y1 ⊢ XXq₁Y1 ⊢ XXYq₁1 ⊢ XXq₂YY ⊢ Xq₂XYY ⊢ XXq₀YY ⊢ XXYq₃Y ⊢ XXYYq₃B ⊢ XXYYBq₄ ✓

Input Format: 1ⁿ 0 1ᵐ 0 (n × m)

Output: 1ⁿˣᵐ

Strategy:

Multiplication = repeated copying. For each 1 in first number, copy entire second number to result area.

1. Mark one 1 in first number (as X)
2. Go to second number
3. For each 1 in second number:
   • Mark it (as Y)
   • Go to result area, write 1
   • Return to second number
4. Restore second number (Y → 1)
5. Return to first number, find next unmarked 1
6. Repeat until first number exhausted

States:

• q₀: Start, mark 1 in first number
• q₁: Move to second number
• q₂: Mark 1 in second number
• q₃: Go to result area
• q₄: Write 1 in result, return
• q₅: Return to second number
• q₆: Restore second number
• q₇: Return to first number
• qf: Accept

Key Transitions (simplified):

Note: Full implementation has many more transitions for navigation and restoration.