GATE CS - THEORY OF COMPUTATION:Turing Machines and Computability
Mastering turing machines and computability concepts and implementation.
Turing Machines and Computability for GATE CS
GATE TM questions are vocabulary-heavy: decidable vs recognizable, undecidable examples, and simple TM variants (multi-tape ≡ one-tape in power).
TM model
7-tuple sketch: states, tape alphabet, transition, start/accept/reject. Infinite tape; halt or loop.
Language classes
| Class | Meaning |
|---|---|
| Recursive / decidable | TM always halts; accepts iff in (L) |
| RE / recognizable | TM accepts iff in (L); may loop outside |
| Non-RE | Not even recognizable |
(A_{TM}) recognizable but undecidable. Complement of (A_{TM}) not recognizable (standard exam fact).
Reductions
To show (L) undecidable: reduce a known undecidable problem to (L). Direction matters — map known-hard instance into your language's instance.
Variants
Multi-tape, nondeterministic TMs: same recognizability power as deterministic TM (complexity differs — see next chapter).
Next: Complexity. Hub: GATE.