Compiling Turing Machines into Storage Modification Machines

Chauvet, J. -M.

arXiv.org Artificial Intelligence 

It is well known that Sch\"onhage's Storage Modification Machines (SMM) can simulate Turing Machines (TM) since Sch\"onhage'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.