I'm currently reading Gödel Escher Bach. His first formal system he introduces is the MIU system. It follows four rules.
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 fullfill
count(I) mod 3 = 0, which means that the number of
I must be divisible by 3.
count represents the number of
mod is the mathematical operation modulo.
With the second rule, we can duplicate the starting
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 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.
The code for this page can be found at https://github.com/TN1ck/MIU.- Tom Nick