New Real-Time Simulations of Multihead Tape Units

Abstract

Single-head tapes are used to simulate multihead Turing machine tape units without loss. For one-dimensional tapes, the new simulations are simpler and use far fewer tapes than prevj known simulations. For multidimensional tapes, the results are entirely new.