On the complex behavior of simple tag systems: An experimental approach

Abstract : It is a well-known fact that apparently simple systems can give rise to complex behavior. But why exactly does a given system behave in a complex manner? There are two main approaches to tackle this and other related questions. One can take on a theoretical approach or else start from a more experimental study of the behavior of such systems with the help of a computer. In this paper, the experimental approach is applied to tag systems with a very small program size. After a discussion of some of the main theoretical results on tag systems, several results from a computer-assisted and experimental study on tag systems are analyzed. Special attention is given to the well-known example studied by Post with only 2 symbols and a deletion number v = 3. These results are combined with some theoretical results on tag systems in order to gain more insight into the computational power of simple tag systems.
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

Contributor : Liesbeth de Mol <>
Submitted on : Monday, November 14, 2016 - 3:24:45 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Long-term archiving on: Monday, March 20, 2017 - 9:39:19 PM


Files produced by the author(s)




Liesbeth de Mol. On the complex behavior of simple tag systems: An experimental approach. Theoretical Computer Science, Elsevier, 2011, 412 (1-2), pp.97-112. ⟨10.1016/j.tcs.2010.08.026⟩. ⟨hal-01396517⟩



Record views


Files downloads