Xigxag
Xigxag is a simple string-copying automaton designed by Chris Pressey in 2001, but not released until 2007.
Execution
A Xigxag configuration is a finite string of < and > symbols. On each transition, every symbol in the string is checked; if the symbol is <, everything to the left of that symbol is copied into the next configuration, and if the symbol is >, everything to the right of that symbol is copied into the next configuration. Substrings are copied into the next configuration left to right.
Along with the definition of the automaton and the release of a Perl script that implements it, Chris Pressey has given a proof that Xigxag has exponential growth for all but a finite number of initial configurations.
Although Xigxag is so simple that it is extremely unlikely that it is Turing-complete, it is also difficult to construct a proof showing that it is not.
Periodic patterns
The following are the only periodic patterns, found by searching all strings of length 7 or shorter. Chris Pressey has proved that all longer strings grow exponentially. Periodic patterns are configurations which eventually return to the initial one (in all the below cases, immediately).
- the empty string
<<<>>><><><<<>>>