Compiling Turing Machines into Storage Modification Machines
arXiv:2110.01415v11 citations
Originality Synthesis-oriented
AI Analysis
This work is incremental, providing a simplified approach for researchers and practitioners in theoretical computer science interested in automata and compiler design.
The authors tackled the problem of transforming Turing Machines into Storage Modification Machines by proposing a simple transformation method, which serves as the foundation for a straightforward TM-to-SMM compiler.
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.