I'm currently reading "Gödel Escher Bach" by Douglas Hofstadter, which is in general about strange loops.
A strange loop is a cyclic structure that goes through several levels in a hierarchical system. It arises when, by moving only upwards or downwards through the system, one finds oneself back where one started. source
One of the strange loops Hofstadter describes is a formal system. The first formal system the author describes is the MIU System. The MIU System has four rules.
- If you posses a string whose last letter is
I, you can add on a
Uat the end.
- Suppose you have
Mx. Then you may add
Mxxto your collection.
IIIoccurs in one of the string in your collection, you may make a new string with
Uin place of
UUoccurs inside one of your strings, you can drop it.
The Goal of the Book is to get from MI to MU. I wrote an applet, where you can try it out yourself. Part of the blog post is also available there.
So how to get from
I to the
The only rule that can reduce the number of
I the the 3rd rule, so we should focus on that. To remove all
I, we need to fulfill
count(I) mod 3 = 0, which means that the number of
I must be divisible by 3. count represents the number of
I, mod is the mathematical operation modulo.
With the second rule, we can duplicate the starting I. But doubling a number that is not divisible by 3 will never make it divisible by 3.
Suppose you have a number
nthat is not divisible by 3, so
n mod 3 != 0, which means that
n = x * 3 + y, where
xcan be any natural number and
yis 1 or 2. When doubling the number we get
n * 2 = x * 6 + y * 2.
y * 2is now 2 or 4, both numbers are still not divisible by 2.
x * 6is divisible by 3, so adding 2 or 4 will make it not divisible by 3.
Reducing the number of
I by 3 obviously won't help, we can only use this rule in a useful way when we already have a number that is divisible by 3. All other rules don't affect the number of
So the first exercise given by Douglas Hofstadter in "Gödel Escher Bach" is impossible to solve.
When you don't believe this proof, simply try it out and check if you're able to find a solution. You won't.
But why give the reader an exercise that is not solvable?
Because on encounters a lot of loops in the system. Every time you think "I might try this" you'll get to a previous point and you notice that the whole system loops itself. You figure out, that you can't escape and it doesn't matter how often or long you try, you'll always go back to where you started.