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
Theoretical Computer Science, Elsevier, 2011, 412 (1-2), pp.97-112. 〈10.1016/j.tcs.2010.08.026〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.univ-lille3.fr/hal-01396517
Contributeur : Liesbeth De Mol <>
Soumis le : lundi 14 novembre 2016 - 15:24:45
Dernière modification le : mardi 3 juillet 2018 - 11:30:05
Document(s) archivé(s) le : lundi 20 mars 2017 - 21:39:19

Fichier

TCS_CSP_minor_revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

181