6.2Variants and equivalent models
The idea
Many variants of the Turing machine (more tapes, nondeterminism, ...) accept exactly the same languages.
Think of it like this: Giving a mathematician a faster pen does not let them prove new theorems.
Why it exists
It shows the TM is a robust definition of computable.
How it works
- Multi-tape, multi-track, two-way tape: equivalent (slower to simulate).
- Nondeterministic TM: same languages (exponential slow-down).
- Two stacks or two counters can simulate a tape.
- LBA (tape = input length) is weaker: CSL only.
Worked example: Simulation cost
A multi-tape machine running in time t can be simulated on one tape in about t² steps.
Now play with it
- →Go through the table and spot the one model that is NOT equivalent to a TM.
| Model | Same languages as a basic TM? | Note |
|---|---|---|
| Multi-tape TM | ✓ | simulation costs a quadratic slow-down |
| Nondeterministic TM | ✓ | exponential slow-down when simulated deterministically |
| Two-way infinite tape | ✓ | fold the tape in half |
| Multi-track tape | ✓ | one cell holds a tuple |
| TM with a stack-only tape (PDA) | ✗ | strictly weaker |
| Two-stack PDA | ✓ | two stacks simulate the tape |
| Linear bounded automaton | ✗ | context-sensitive languages only |
Anything extra you bolt onto a TM (more tapes, nondeterminism, random access) changes the speed, not what is computable.
Check yourself
Which model is strictly weaker than a Turing machine?
Exam notes (the dense version)
Multi-tape, multi-track, two-way infinite tape, nondeterministic TMs and RAM machines all compute the same languages as the basic TM (only the speed differs: simulating k tapes costs a quadratic factor). A linear bounded automaton (tape = input) accepts exactly the context-sensitive languages.
Previous year questions: Turing Machines (4)
PYQs are grouped by topic, so this is the full set for Turing Machines; try the ones that match this subtopic. Open all 4 on the topic page.