Theoretical Computer Science

TitleOn the complex behavior of simple tag systems — An experimental approach
Publication TypeJournal Article
Year of Publication2011
AuthorsDe Mol, L
JournalTheoretical Computer Science
Volume412
Number1
Pagination97–112
Abstract

It is a well-know 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 more theoretical approach or start from a more experimental study of the behavior of such systems with the help of the computer. In this paper, the experimental approach will be applied to very small tag systems. 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 will be analyzed. Special attention will be given to the well-known example Post provided and studied with only 2 symbols and a deletion number v = 3. These results will be combined with some theoretical results on tag systems in order to gain more insight into the computational power of simple tag systems.

Citation Keyde2011complex
Download PDF (Author PDF)
PDF author (public):