Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines

摘要

In this paper, we prove that a k-tape Minsky machine operating with time T(n) can be modeled by a three-tape Minsky machine in a time not exceeding T(n)(k) x log T(n). It is shown that multitape Turing machines can be modeled by three-tape Minsky machines with optimal word encoding.