Multiway Storage Modification Machines
We present a parallel version of Sch\"onhage'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.
Code (1)
Similar Papers 제목 키워드 기반
Compiling Turing Machines into Storage Modification Machines
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 trans…
Prof. Schönhage's Mysterious Machines
We give a simple Sch\"onhage Storage Modification Machine that simulates one iteration of the Rule 110 cellular automaton. This provides an alternative construction to Sch\"onhage's original proof of the Turing completen…
Projected Tensor-Tensor Products for Efficient Computation of Optimal Multiway Data Representations
Tensor decompositions have become essential tools for feature extraction and compression of multiway data. Recent advances in tensor operators have enabled desirable properties of standard matrix algebra to be retained f…
Multiway sparse distance weighted discrimination
Modern data often take the form of a multiway array. However, most classification methods are designed for vectors, i.e., 1-way arrays. Distance weighted discrimination (DWD) is a popular high-dimensional classification …
ClassificationAlgorithmic subsampling under multiway clustering
This paper proposes a novel method of algorithmic subsampling (data sketching) for multiway cluster dependent data. We establish a new uniform weak law of large numbers and a new central limit theorem for the multiway al…
Clustering