Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : Liesbeth de Mol <>
Soumis le : lundi 14 novembre 2016 - 15:24:45
Dernière modification le : vendredi 8 janvier 2021 - 11:22:05
Archivage à long terme le : : lundi 20 mars 2017 - 21:39:19


Fichiers produits par l'(les) auteur(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⟩



Consultations de la notice


Téléchargements de fichiers