Turing Machines

Turing-machine design

Designing a Turing machine is like writing a program in the most primitive language imaginable: your only operations are read the current cell, write a symbol, step one cell left or right, and change state. There are no variables, no loops with counters, no memory beyond the tape itself. So the craft is to turn a high-level idea ('check that the as, bs, and cs are equal in number') into a careful dance of the head back and forth, leaving marks as you go. You usually sketch it as a state diagram, the same kind of bubbles-and-arrows picture as for a DFA, but with each arrow labeled read/write/move.

A handful of techniques recur. Marking: overwrite a symbol with a special tape-alphabet symbol (cross an a out as X) so you remember you have already dealt with it. Shuttling: walk the head all the way right, do something, walk all the way back left, repeat, which is how you match far-apart symbols. Tracks: pretend the single tape has several parallel rows by using composite symbols, so you can keep a counter or a copy alongside the data. To recognize a^n b^n c^n you mark one a, one b, one c per left-to-right sweep and accept when every symbol is marked exactly together; to recognize ww you would mark and compare the two halves; to do binary increment you walk to the low end and ripple a carry.

Designing machines builds the intuition that anything an algorithm can do, this tiny instruction set can do too, just tediously. That tedium is the point of two honest caveats. First, real machines for nontrivial tasks have many states and are painful to write out in full, which is why we soon move to higher-level descriptions and trust they could be compiled down. Second, the slowness is inherent: shuttling the head across the tape to compare distant cells can cost time quadratic in the input length or worse, so a Turing machine is a definition of WHAT is computable, never a recipe for computing it fast.

To recognize {a^n b^n : n >= 0}: in each sweep, cross the leftmost a as X, walk right to the leftmost b and cross it as Y, walk back left, and repeat. Accept when no a and no b remain; reject if one runs out before the other. The crossing-out marks are the whole trick.

Mark, shuttle, repeat: the everyday craft of building a Turing machine.

Hand-built Turing machines are correct but slow and verbose; their purpose is to demonstrate computability, not efficiency. Once you trust a task can be done, books describe machines in plain English at a high level rather than spelling out every transition.

Also called
building a TMTM construction圖靈機設計圖靈機構造