Skip to Main content Skip to Navigation
Journal articles

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.
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
Document(s) archivé(s) le : 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