Bio

Daniel Napierski studied economics at Duke University before getting his master’s in computer science from Harvard University. Since then, he and his wife have lived in the Boston area where he works as an independent software consultant. His work has included agent-based simulations and online retail recommendation-engines. Currently he spends much of his time advising clients on software engineering best practices. He is interested in intelligent agents, software design, complex systems, and game theory, among other pursuits.

Project: Programming Sequential Substitution Systems By Example

The goal of this project was to investigate the ability of sequential substitution systems (SSS) to perform specified functions.

The approach taken was inspired by the process of test-driven development (TDD). Within the field of software engineering, TDD is done by formally specifying how a software component should perform before attempting to engineer the code. The desired functionality is described by a suite of unit tests, each asserting that given a particular input the component will produce the correct predetermined output. When the suite of tests is initially created, all of the tests should fail, but as the developer builds the software component, the tests should begin to pass. Once the component passes all of the tests, the developer may have some confidence that the component is acting as intended.

In this project, string substitution examples are acting as software tests. Instead of engineering the desired code, the universe of simple string replacement rules (or programs) is searched in order to find those that produce output matching the examples. Of all the simple programs composed of string replacement rules, only those that can match the output of the examples can be thought of as passing the tests. By this effort, we may begin to understand how simple programs, such as SSS, can be used within a commercial software engineering environment. One may foresee a future where standard software engineering processes make greater use of simple programs harvested for their ability to perform recognizable computations.

Even when searching only the space of very small programs, many sequential substitution systems were found to be carrying out well defined mathematical functions. Of the programs that were analyzed, there also existed a variety of mechanisms, or algorithms, by which they arrived at their end result. The ability of sequential substitution systems to execute identifiable computations has been clearly demonstrated. However, this ability is heavily dependent on how the inputs and outputs to these systems are encoded and decoded. With more experience, it may be possible to develop an intuition into how best to encode and decode the data so that program searches may be done more effectively.

Favorite Outer Totalistic Three-Color Rule

Rule chosen: 8681

I chose rule 8681 because of all the different behavior it displays, including different sized triangles and more complex patterns in the middle.