J. -M. Chauvet

J. -M. Chauvet

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.

J. -M. Chauvet

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.

J. -M. Chauvet

We give a simple Schönhage Storage Modification Machine that simulates one iteration of the Rule 110 cellular automaton. This provides an alternative construction to Schönhage's original proof of the Turing completeness of the eponymous machines.