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

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

171

Files downloads

457