The simplest writing game

Writing games are, unsurprisingly, about writing. They are about putting symbols next to each other following some specified rules, or alternatively, looking at a bunch of symbols next to each other and breaking them down into their ‘constituent parts’ (meaning the symbols that make them up) according to rules.

The simplest writing game is about putting symbols next to each other without any special rule. But what are these symbols? Well, they can be any symbols you want, although each one will result in a different game. Since we are talking about the simplest writing game, let’s start with the simplest of symbol sets – having only one symbol. Let’s say this symbol is: ●.

Once we have our symbol ●, we need our one and only rule about putting the symbol down. Clearly, the first step is to allow one to put down ● by itself. Let’s formulate it:

According to Rule 1, I can now do this:

This rule allows us to write down one, and only one, formula, namely, the symbol ● by itself. ‘Formula’ is the word we will be using to refer to any sequence of symbols of the right sort. The reason for this will become obvious in due time.

But first, notice what happens when we add the following rules:

We can now immediately produce a lot more formulas. Here is a sample:

1. ●●

2. ●●●●●●

3. ●●●●

4. ●●●●●●●●

The answer is: very many! In fact, infinitely many! Here is another thing you can ponder:

Of course, this writing game is not overly interesting, since it can only produce rows of black circles. But we can still ask some interesting questions about it. For example, suppose we do away with Rule 2L and take Rule 2R as our only rule other than Rule 1. Here are two questions you may ask yourself:

Speaking of creating formulas, we can also be very specific about how we created a given formula in either rule systems. In fact, the type of extremely specific representation we will be using can be adapted for many other (and much more interesting!) rule systems.

The main idea behind an explicit representation of the creation of a formula is that anyone can see if you actually followed the appropriate rules. In other words, for every correct formula, you can (at least in principle) show how it can be constructed. Alternatively, there is no incorrect formula for which you can show how it could be constructed (with the given rules).

Let’s say you are considering the correctness of the following formula:

If this formula is indeed a correct one, we should be able to specify how we built it using only the rules that are given to us. Let’s take Rule 1, Rule 2L and Rule 2R first. Here is how we can represent in a compact way how we built the above formula:

Let’s return to Exercise 2.4. There, the question was whether we could tell for a formula like ●●●● how exactly it was created. Now we can show that this is not the case if we have both Rule 2L and Rule 2R since at any step other than the first, we can use either the left or the right hand rule to arrive at the next step.

For example, we could have created our formula as such:

Again, the created formula is the exact same, but the way it was created is completely different. On the other hand, this is not the case if we only have Rule 1 and Rule 2R, for then the only way to arrive at our formula is as follows:

In fact, we can make this fact more precise as follows:

Any formula built with Rule 1 and Rule 2R is built using Rule 1 first, and then using Rule 2R a number of times.

Indeed, we can make this fact even more precise since with any construction of a formula like above, we start with a formula of a lone symbol, which is $1$ character long. Then, at each step, using Rule 2R, we make it $1$ symbol longer. Accordingly, if a formula is made up of $n$ black circles (where $n$ is any natural number you can think of), then we know it was built by one application of Rule 1 and $n-1$ applications of Rule 2R.