On the complex behavior of simple tag systems: An experimental approach - Université de Lille Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2011

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

Résumé

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.
Fichier principal
Vignette du fichier
TCS_CSP_minor_revision.pdf (1.1 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01396517 , version 1 (14-11-2016)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More