Turing-machine variants

Think of the standard Turing machine as a bicycle. You can add a basket, swap one wheel for three, let the pedals also coast, or give it two handlebars. It is still, at heart, a thing that gets you from A to B the same way. Turing-machine variants are these modified bicycles: small or large changes to the basic model that look different on paper but, surprisingly, get you to exactly the same destination, the same class of recognizable and decidable languages.

The common variants change one feature at a time. A two-way infinite tape extends the tape leftward as well as rightward. Multiple tapes give the machine several independent scratch spaces. Multiple tracks pack several symbols into one cell. Multiple heads put several read-write heads on a single tape. A stay-put move lets a head remain on its cell instead of being forced left or right. A nondeterministic transition lets the machine branch into several possible moves. An enumerator drops the input tape entirely and instead prints out, one by one, all the strings of a language. In every case the recipe is the same: prove the variant equivalent to the plain machine by a step-by-step simulation in each direction.

Why bother defining so many? Two reasons. First, convenience: a multitape or stay-put machine is far easier to design and reason about for a given task, so we use the friendly variant and rely on equivalence to know it is legitimate. Second, evidence: the fact that all these structurally different gadgets compute the same functions is precisely the convergence that supports the Church-Turing thesis. The honest caveat is that 'equivalent' here means equal computational power, not equal efficiency; the deterministic simulation of a nondeterministic machine, for instance, can be exponentially slower.