Turing Machines Tm Notes & Formulas

1. Definition

A Turing Machine is a mathematical model of computation consisting of an infinite tape, a read/write head, a finite set of states, and a transition function. It defines the limits of what is algorithmically computable.

2. Formal Definition

TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) where:

• Q = finite set of states
• Σ = input alphabet (not containing blank ␣)
• Γ = tape alphabet (Σ ⊆ Γ, blank ␣ ∈ Γ)
• δ: Q × Γ → Q × Γ × {L, R} = transition function
• q₀ = start state
• q_accept = accept state
• q_reject = reject state (q_accept ≠ q_reject)

3. How TM Works

1. Input written on tape, rest is blank
2. Head starts at leftmost input symbol
3. At each step: read symbol → write symbol → move L or R → change state
4. Halt in q_accept → accept; halt in q_reject → reject; loop forever → neither

4. TM vs Other Models (Very Important)

| Model | Memory | Accepts |
|---|---|---|
| DFA | States only | Regular |
| PDA | Stack (LIFO) | CFL |
| LBA | Tape bounded by input | CSL |
| TM | Infinite tape | RE |
| Multi-tape TM | Multiple tapes | RE (same power) |
| Non-deterministic TM | Infinite tape, nondeterministic | RE (same power) |

Key equivalences: Multi-tape TM = single-tape TM = Non-deterministic TM in power (all recognize RE languages). However NTM can be exponentially faster.

5. TM Variants (Same Computational Power)

• Multi-tape TM: k tapes, k heads. Simulated by single-tape TM with O(t²) time overhead
• Non-deterministic TM: Multiple possible transitions. Simulated by deterministic TM
• Enumerator: Prints (enumerates) all strings in language. L is RE iff some enumerator enumerates it
• Oracle TM: TM with access to oracle for some problem - used in complexity theory

6. Language Classes and TM

• Recursive (Decidable): TM that always halts (accepts or rejects)
• Recursively Enumerable (RE): TM that accepts all strings in L (may loop on non-members)
• Not RE: No TM accepts this language

Complement:

• If L is decidable → L̄ is decidable
• If L is RE but not decidable → L̄ is NOT RE
• If L is RE and L̄ is RE → L is decidable

7. Universal Turing Machine (UTM)

A single TM U that simulates any TM M on input w, given ⟨M,w⟩ (encoding of M and w).

• Basis for stored-program computers
• UTM exists → computation is universal

8. Encoding of TMs

TMs can be encoded as strings over {0,1} → countably many TMs. Languages over {0,1} are uncountably infinite (2^(Σ*) is uncountable). Therefore most languages have no TM → most problems are undecidable.

9. Configuration and Computation

Configuration: (q, tape_contents, head_position) - represents complete snapshot

• Start configuration: (q₀, input, 0)
• Accepting configuration: state = q_accept
• TM accepts w if start config leads to accepting config via finite computation steps

10. GATE Trick

NTM and DTM have same computational power - both recognize exactly RE. NTM is not more powerful than DTM, just potentially faster. Multi-tape TM does not increase power but can reduce time complexity. UTM proves general-purpose computers are possible. L is decidable iff both L and L̄ are RE - key theorem directly tested.