Compiling Turing Machines into Storage Modification Machines
arXiv:2110.01415
Abstract
It is well known that Schönhage's Storage Modification Machines (SMM) can simulate Turing Machines (TM) since Schönhage's original proof of the Turing completeness of the eponymous machines. We propose a simple transformation of TM into SMM, setting the base for a straightforward TM-to-SMM compiler.
6 pages, 1 figure