The Well-known MU Puzzle

We first observe that letting $I=1$ and $U=0$ , while $M=1$ , then all binary numbers, with the first digit being $M=1$ , represents all possible strings starting with $M$ and containing any number of $I$ s and $U$ s following. Hence, we can assign a natural number $B$ , starting at $2$ , to any given string.

Next, we can assign digits $0,1,2,3$ to the four "Formal Rules", so, again, with the first digit arbitrarily being $1$ , all possible sequences of applications of such rules can be represented by all natural numbers in base $4$ , convertible to natural numbers $A$ in base $10$ , thus starting at $4$ .

A "proof" is simply the function $P\left(A \right) = B$ , which assigns the number representing a sequence of rules applied to the number representing a sequence. We can create a table starting with $A=4$ , and increment successively to any number of arbitrary size. Assuming that for a table of finite length $B$ is present, we can say that eventually determine that $B$ "is a theorem", but this is assuming that $B$ is listed in such a table of any finite length. It may not.

In order to determine whether or not $B$ necessarily exists in such a table of some finite size, we cannot resort to a simple successive application of the formal rules, for reasons given above. As an analogy, suppose given positive integers $a, b$ defining points in a lattice, is there any $a, b$ such that the distance to the origin is some integer multiple of $\sqrt{3}$ ? We can do a successive search of all possible such pairs of integers, and regardless of how long the search takes, it never seems like any such $a, b$ can be found. Proof of non-existence of such a pair $a, b$ sometimes (or often!) has to appeal to reasoning that is outside the limited set of "Formal Rules". "Is there a computer program to decide if a given string is a theorem?" Go see AA's answer, but the salient point being made here is that the "Formal Rules" clearly wasn't sufficient to settle the issue. This is the reason why "definitions and axioms" in mathematics keeps expanding, which was the point of Godel's Theorem.

Supposing that MU isn't an already given theorem , and this supposition should be made because otherwise it wouldn't make sense to verify it on the account of the operations presented , it's impossible to obtain by such operations MU starting with MI.

To prove this proposition consider , formally , the way the index of the operations provided works in it's innate structure starting by the string MI anyway. To obtain MU starting from MI you should get rid of all the Is in the string of MI and all the U's such that you get MU which is only possible by using the operation of replacing III with an U and by the operation of removing 2 U's. This means therefore that the configuration anterior to the application of this operations should contain an odd number of Is and an odd number of repeating U's such that any excess even U's can be eliminated until there remains only one U. Observe further that it order to obtain such a sequence this should be done by working in some way with the operations. This is a principal or understanding by principles which helps reply to the harder questions put later in the problem. Looking therefore at the problem from the point of view of how the operations lead to outputs when are combined deepens elementary understanding.

It sufficient to prove just one of this necessary conditions is not met by the use of the available operations , namely that the number of I's can't be taken away by the use of the operations , in the conceiving of that principal understanding.

Observe that there are 2 possible available operations to use starting from the string MI at first , namely the first 2 listed operations. Observe that you can't obtain an odd number of Is by the operation of doubling the string after M alone as doubling will always get you strings of an even number of Is nor by using a combination of the 2 initially available operations as using the first operation listed you would get from the string by the following reasoning. Using a combination of the first 2 operations firstly to get a sequence which will be good implies , since the first operation has the characteristic that once applied can't be applied a second time without using some intermediate operation because after it's application the sequence will have the terminal element and U and not an I , as required for this operation in order to work , that the resulting output depends on the second listed operation. This because after using the first 2 operations a number of times you will get a sequence like IUIU with I repeating an even number of times before each U where each of the I * n times U sequence repeats for an even number of times remaining therefore to prove that any such resulting sequence can't be transformed in a sequence with an even number of Is and this can be proved because no matter the sequence of IU in each there are an odd nubmers of I's which can't be taken away just by the use of removing 3 I's as the nubmer of removing I's is , because it will be as a result of the doubling operation a power of 2 not divisible with 3 anyway making it impossible for the number to get 0 Is.

Observe that it is sufficient to consider just this characteristic related to the number of Is being divisible with 3 or not to decide anyway if some given string is reducible to the state MU or if it is not , being therefore decidable.

Nonetheless , for cases in which this characteristic related to the divisibility of I is not important , which can be conceived for some variations of the prolbm it can be that , until the moment in which a general understanding is obtained is not decidable. Another interesting problem would be to consider for what specific use of operations proposed , out from some set of operations a problem can be decidable or not which will be a good exercise towards that meta-logical udnerstanding intended anyway.