Universal Simulations by Spatial Machines
Bruno Martin
In this paper, we consider the relation between spatial machines, Turing machines and cellular automata. We first recall and correct a mistake in the original simulation of a Turing machine by a spatial machine given in [6]. We also propose a parallel simulation of cellular automata by a uniform family of spatial machines. Then, we deduce from the previous simulations the universality of spatial machines, the undecidability of the occurrence of a state and the P-completeness of the General Machine Simulation Problem for spatial machines.