String rewriting

A string rewriting system is a simple model of computation. A program is defined by a list of rules of the form s → t, indicating that the substring s should be replaced by the string t.

Here is a program that uses 3 rules to sort a string of a’s and b’s and c’s:

Note that the program always applies the first applicable rule in the first position possible.

Try running the program on different inputs! If you want to try modifying the rules as well, click “Open in editor”.

Example programs

Bouncer

This program is stuck in an infinite loop. It doesn’t do anything useful, but it looks pretty.

Squarer

This program takes as input a string of length $n$, and outputs a string of length $n^2$. It uses the fact that sorting the string bbbbbaaaaa takes 25 applications of the rule ba → ab.

Binary counter

This program counts up in binary.

Collatz

This program computes the Collatz sequence starting from $n$ and keeps track of how many iterations it takes to reach 1. (oeis.org/A006577)

Maximum

This program computes the maximum of a list of numbers such as [3, 7, 5, 2, 6].

Turing Machines

It is relatively straightforward to translate any given Turing Machine into a string rewriting system. Here is a simulation of a 3-state Busy Beaver:

The state and position of the head is represented by a letter, which is always reading the tape symbol to its immediate right. The replacement A0 → 1B corresponds to the state transition “If in state A and reading a 0 on the tape, write a 1 then move right”. Transitions that require moving to the left are slightly more cumbersome: we need two rules for the two possible tape symbols to the left of the head.

The final 6 rules take care of extending the tape if the head ever reaches the edge.

Here is the same translation applied to a 4-state Busy Beaver:

This runs for 120 steps: the initial string has length 8 and the final string has length 21. From this we can deduce that there were 13 steps which extended the tape, and the actual number of Turing Machine transitions is $120-13=107=\text{BB}(4)$ as expected.

Finally, here is a 5-state Busy Beaver:

I do not recommend running this one all the way through: it halts after $47\,189\,158$ steps (out of which $47\,176\,870$ are TM steps and $12\,288$ are tape extensions).

Challenges

Define the length of an SRS-program to be the total number of characters in all the rules (we will count the rule ab → c as length 3, ignoring the arrow symbol).

The following questions are potentially interesting to play around with:

1. For each $n$, what is the longest-running halting SRS-program of length $n$? (this is an SRS version of the Busy Beaver problem)
2. For each string $s$, what is the shortest SRS-program that outputs $s$ (i. e. halts with $s$ as the final string)?

For both of these questions we will assume that the input is a single character S. Any SRS-program run on empty input either halts immediately or never halts, so we do need some non-empty input to get interesting halting programs. We could also allow the programmer to decide the input as part of the program, and include it when counting the length of the program. However, specifying a fixed input doesn’t significantly affect things, and will simplify some analysis further down the line.

Here are some concrete challenges to get you started:

This program has length 24 and runs for 1013 steps. Can you find a shorter program that runs for longer?

This program has length 31 and outputs exactly 2026 copies of the symbol .. Can you find a shorter program with the same output?

Come share your solutions on Discord!