Complex Systems

Predicting the Large-Scale Evolution of Tag Systems Download PDF

Carlos Martin
School of Engineering and Applied Science
Columbia University
New York, New York

Abstract

We present a method for predicting the large-scale evolution of a tag system from its production rules. The tag system's evolution is divided into stages called "epochs" in which the tag system evolves monotonously. The distribution of strings of symbols in the queue at the beginning of an epoch determines the large-scale behavior of the tag system during that epoch, including its growth rate. To predict the tag system's large-scale properties over multiple epochs, we show how to predict the next epoch's initial queue contents from the current epoch's initial queue contents. We compare the values predicted by this method to simulations and find that great prediction accuracy is retained over several epochs.