Single-tape Turing machines

Single-tape machines: configurations, steps, halting, composition of machines, tape views, state restriction, and translation of multi-stack machines to one tape (simulation and its halting behaviour, not its time cost).

• Restricting a single-tape machine to a supporting set of states
• Decidable and recognizable predicates on single-tape Turing machines
• Running two single-tape machines one after the other
• Simulating multi-stack machines on a single tape
• Equivalent tape representations

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.