Theory of Computation: Planar Turing Machines

We prove that every Turing Machine can be converted into an equivalent Turing Machine that is planar, that is a drawing in the plane without edge crossings. The idea is simple: we add a state at any existing edge crossing, and then some more states and transitions that put a unique symbol depending on the incoming transition. Then once the machine enters the first added state, the unique symbol forces the TM to go the original intended direction. ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.