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.
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.
Evolving Order and Chaos: Comparing Particle Swarm Optimization and Genetic Algorithms for Global Coordination of Cellular Automata Anthony D. Rhodes Portland State University Abstract -- We apply two evolutionary search algorithms: Particle Swarm Optimization (PSO) and Genetic Algorithms (GAs) to the design of Cellular Automata (CA) that can perform computational tasks requiring global coordination. In particular, we compare search efficiency for PSO and GAs applied to both the density classification problem and to the novel generation of "chaotic" CA. Our work furthermore introduces a new variant of PSO, the Binary Global-Local PSO (BGL-PSO). I. INTRODUCTION: CELLULAR AUTOMATA Cellular Automata (CA) are discrete, spatially-extended dynamical systems consisting of cells, each of which contains a finite state machine. Given an initial configuration of cells, CA evolve over time by performing computations according to local rules.
A pseudorandom number generator produces numbers deterministically but they seem aperiodic (random) most of the time for most use-cases. The generator accepts a seed value (ideally a true random number) and starts producing the sequence as a function of this seed and/or a previous number of the sequence. These are Pseudorandom (not truly random) because if seed value is known they can be determined algorithmically. True random numbers are hardware generated or generated from blood volume pulse, atmospheric pressure, thermal noise, quantum phenomenon, etc. There are lots of techniques to generate Pseudorandom numbers, namely: Blum Blum Shub algorithm, Middle-square method, Lagged Fibonacci generator, etc.
This paper studies 3-state, 2-direction Mobile Au- tomata. The results of this study show that although it is more difficult to find complexity in Mobile Automata than Cellular Automata, 3-color Mobile Automata can still be divided into four classes of complexity, thus pro- ducing complex behavior. There are 627 number of 3- color Mobile Automata, which were studied and filtered to prove the complexity of Mobile automata. The results of this study infer that it is possible to observe complex- ity in systems that contain only one active cell, if the system has more then two states.