3
$\begingroup$

This is a sub-puzzle of the MIU-system, as described by Douglas Hofstadter in his book Gödel, Escher, Bach. (One can also find a description of this system here.)

My question is: is MUUI a MIU-string (assuming, as usual, that the sole axiom is the string MI)?

If yes, I'd like to see a derivation, starting from MI. If no, I'd like to see a proof.


NB: As a reminder, the MIU-system rules may not be "run backwards". In particular, even though rule IV allows one to drop UU from any MIU-string, it does not allow one to add UU to any MIU string. In other words, rule IV may not be invoked to obtain MUUI from the axiom string MI.


EDIT

The following is excerpted from p. 260 of the latest American edition of GEB:

SYMBOLS: M, I, U

AXIOM: MI

RULES:
I. If xI is a theorem, so is xIU.
II. If Mx is a theorem, so is Mxx.
III. In any theorem, III can be replaced by U.
IV. UU can be dropped from any theorem.

NB:

In the rules,

  1. the word "theorem" is synonym for what I call "MIU-string" earlier in the post;
  2. the variable x stands for any MIU-substring.

See here for examples, and for additional details.

$\endgroup$
  • $\begingroup$ Please don't use the abbreviation "IOW" in a post full of strings like "MIU" and rules identified in roman numerals "II". In fact, please don't use text message abbreviations here at all. We old folks will thank you. $\endgroup$ – Ethan Bolker Apr 27 '18 at 18:21
  • $\begingroup$ I looked it up: IOW stands for "in other words". $\endgroup$ – Peter Kagey Apr 27 '18 at 18:27
  • 2
    $\begingroup$ I would heartily encourage editing this post to include the rules of the system directly; it would help this post substantially and won't make it much longer. $\endgroup$ – Steven Stadnicki Apr 27 '18 at 18:27
  • $\begingroup$ @PeterKagey I guessed IOW from context, and knew FWIW. My comment was a wish for a stylistic convention for SE posts. $\endgroup$ – Ethan Bolker Apr 27 '18 at 21:21
3
$\begingroup$

It is in fact possible to obtain any string $Mx$ where $x$ consists of $I$s and $U$s and its number of $I$s is not a multiple of $3$ (conversely, it is easy to see you cannot obtain any string not of this form). First, I claim it is possible to make $MI^n$ for any $n$ that is not a multiple of $3$. To do this, let $2^m>n$ be such that $2^m-n$ is a multiple of $3$ (this is possible since $n$ is not a multiple of $3$). Using rule II $m$ times gives $MI^{2^m}$. If $2^m-n$ is a multiple of $6$, it is now easy to reach $MI^n$, since you can delete copies of $I^6$ using rules III and IV. If $2^m-n$ is not a multiple of $6$, note that you can first use rule I to get $MI^{2^m}U$, then use rules III and IV to get $MI^{2^m-3}$. From there you can remove copies of $I^6$ to get $MI^n$.

Now, given any string $Mx$ where $x$ consists of $I$s and $U$s and its number of $I$s is not a multiple of $3$, let $a$ be the number of $I$s in $x$ and let $b$ be the number of $U$s in $x$. Then $n=a+3b$ is not a multiple of $3$, so we can make $MI^n$. Replacing copies of $I^3$ with $U$, we can then obtain $Mx$.

For an explicit derivation in the case of $MUUI$, we start by using rule II four times to get to $MI^{16}$. Then rule I gives $MI^{16}U$, rule III gives $MI^{13}UU$, and rule IV gives $MI^{13}$. Using rule III and rule IV we delete an $I^6$ to get $MI^7$. Finally, we use rule III twice to get $MUUI$.

$\endgroup$
1
$\begingroup$

One possible solution:

$$MI \overset{2}{\rightarrow} MII \overset{2}{\rightarrow} MIIII \overset{2}{\rightarrow} MIIIIIIII \overset{1}{\rightarrow} MIIIIIIIIU \overset{3}{\rightarrow} MIIIIIUU \overset{4}{\rightarrow} MIIIII \overset{2}{\rightarrow} $$

$$MIIIIIIIIII \overset{1}{\rightarrow} MIIIIIIIIIIU \overset{3}{\rightarrow} MIIIIIIIUU \overset{4}{\rightarrow} MIIIIIII \overset{3}{\rightarrow} MUIIII \overset{3}{\rightarrow} MUUI$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.