Abstract geometrical computation 4: Small Turing universal signal machines
This paper provides several very small signal machines able to perform any computation in the classical understanding generated from Turing machines, cellular automata and cyclic tag systems. A halting universal signal machine with 13 meta-signals and 21 collision rules is presented (resp. 15 and 24 for a robust version). If infinitely many signals are allowed to be present in the initial configuration, five meta-signals and seven collision rules are enough to achieve non-halting weak universality (resp. six and nine for a robust version). (C) 2010 Elsevier B.V. All rights reserved.
abstract geometrical computation turing universality signal machines cyclic tag systems small universal machines