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
Liste complète des métadonnées

Cited literature [30 references]  Display  Hide  Download

https://hal.univ-lille3.fr/hal-01396517
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

File

TCS_CSP_minor_revision.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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〉

Share

Metrics

Record views

93

Files downloads

235