Exploring the Space of Substitution Systems
Richard Southwell*
Chris Cannings
School of Mathematics and Statistics
University of Sheffield, Hicks Building, Hounsfield Road
Sheffield, S37 RH, United Kingdom
*r.southwell@shef.ac.uk
Abstract
Substitution systems, where strings are rewritten according to local rules, have many applications. They are used to model the development of plants, as well as to generate music and architectural designs. Many substitution systems can generate highly complex patterns using only simple rules. This feature can make substitution systems difficult to analyze mathematically. A different approach, pioneered by Stephen Wolfram, is to use computer searches to reveal simple systems with interesting properties. This approach is used to explore a class of systems we call symmetric sequential substitution systems within which a string is repeatedly updated by applying rewrite rules in a non-overlapping way. In this paper several simple examples of these systems are exhibited that produce complex behavior. The dynamics of several of these systems are studied and a system is exhibited that is computationally universal. Applications of symmetric sequential substitution systems are discussed, such as compression and the evaluation of numerical functions.
