Abstract geometrical computation 4: Small Turing universal signal machines

作者：Durand Lose Jerome^*

来源：Theoretical Computer Science, 2011, 412(1-2): 57-67.

DOI：10.1016/j.tcs.2010.07.013

• Abstract geometrical computation
• Cyclic tag systems
• Turing universality
• Signal machines
• Small universal 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).

• 出版日期2011-1-2