Multiway Storage Modification Machines
This work provides a new parallel machine model for theoretical computer science, addressing computational complexity and parallelism, but it appears incremental as it builds on existing models like the Storage Modification Machine.
The paper introduces the Multiway Storage Modification Machine (MWSMM), a parallel version of Schönhage's model, which recognizes in polynomial time what Turing Machines recognize in polynomial space, placing it in the Second Machine Class and conforming to the Parallel Computation Thesis.
We present a parallel version of Schönhage's Storage Modification Machine, the Multiway Storage Modification Machine (MWSMM). Like the alternative Association Storage Modification Machine of Tromp and van Emde Boas, MWSMMs recognize in polynomial time what Turing Machines recognize in polynomial space. Falling thus into the Second Machine Class, the MWSMM is a parallel machine model conforming to the Parallel Computation Thesis. We illustrate MWSMMs by a simple implementation of Wolfram's String Substitution System.