OFFSET
0,1
COMMENTS
In the MIU formal system, invented by Douglas R. Hofstadter, we start with the string (axiom) MI and build new strings (theorems) by applying the following rules.
Rule 1: if a string ends with I, we can append U at the end.
Rule 2: if a string is of the form Mx, we can build the string Mxx.
Rule 3: if a string contains III, we can replace it with U.
Rule 4: if a string contains UU, we can remove it.
Hofstadter asks whether the string MU can be obtained by repeatedly applying the above rules and then proves it cannot.
At each recursion level, strings are obtained by applying the rules in order (1 to 4) to each string of the previous level. When the same rule can be applied more than once, it is first applied to the leftmost substring that can be affected.
Following the mapping adopted by Hofstadter himself (see Hofstadter (1979), p. 261), we can encode the characters M, I, and U with 3, 1, and 0, respectively.
See A368953 for a variant where, within a row, duplicates (if present) are removed and encoded strings are lexicographically ordered.
A369173 gives all of the derivable strings within the MIU system.
REFERENCES
Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..3670 (rows 0..7 of the triangle, flattened).
Wikipedia, MU Puzzle.
EXAMPLE
After recursively applying the rules three times, we get the following tree (cf. Hofstadter (1979), page 40, Figure 11).
.
MI
0 ---------------------- 31
/ \
1 2 <--- Rule applied
/ \
MIU MII
1 ---------------- 310 311
/ / \
2 1 2
/ / \
MIUIU MIIU MIIII
2 --------- 31010 3110 31111 Here rule 3 can
/ / / | | \ be applied twice:
2 2 1 2 3 3 <--- it is first applied
/ / / | | \ to the leftmost
MIUIUIUIU MIIUIIU MIIIIU | MUI MIU III substring
3 --- 310101010 3110110 311110 | 301 310
MIIIIIIII
311111111
.
By reading the tree from top to bottom, left to right, the triangle begins:
[0] 31;
[1] 310 311;
[2] 31010 3110 31111;
[3] 310101010 3110110 311110 311111111 301 310;
[4] 31010101010101010 3110110110110 ... 3010 ... 3010 30101 31010;
...
Please note that some strings may be duplicated in different rows and within the same row: within the first four rows, the string MIU (310) is present in rows 1 and 3. In row 4, the string MUIU (3010) is present twice: it can be generated both by applying rule 3 to MIIIIU (311110) and by applying rule 1 to MUI (301). The initial string MI (31) first reappears in row 5.
MATHEMATICA
MIUStepO[s_] := Flatten[Map[{If[StringEndsQ[#, "1"], # <> "0", Nothing], # <> StringDrop[#, 1], StringReplaceList[#, "111" -> "0"], StringReplaceList[#, "00" -> ""]}&, s]];
With[{rowmax = 4}, Map[FromDigits, NestList[MIUStepO, {"31"}, rowmax], {2}]]
PROG
(Python)
from itertools import islice
def occurrence_swaps(w, s, t):
out, oi = [], w.find(s)
while oi != -1:
out.append(w[:oi] + t + w[oi+len(s):])
oi = w.find(s, oi+1)
return out
def moves(w): # moves for word w in MIU system, encoded as 310
nxt = []
if w[-1] == '1': nxt.append(w + '0') # Rule 1
if w[0] == '3': nxt.append(w + w[1:]) # Rule 2
nxt.extend(occurrence_swaps(w, '111', '0')) # Rule 3
nxt.extend(occurrence_swaps(w, '00', '')) # Rule 4
return nxt
def agen(): # generator of terms
frontier = ['31']
while len(frontier) > 0:
yield from [int(t) for t in frontier]
reach1 = [m for p in frontier for m in moves(p)]
frontier, reach1 = reach1, []
print(list(islice(agen(), 28))) # Michael S. Branicky, Jan 14 2024
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Jan 10 2024
STATUS
approved