Knowledge (XXG)

MU puzzle

Source 📝

2226: 1743: 1825:
to anything: it is simply a game involving meaningless strings. Working within the system, an algorithm could successively generate every valid string of symbols in an attempt to generate MU, and though it would never succeed, it would search forever, never deducing that the quest was futile. For a
1837:
The inability of the MIU system to express or deduce facts about itself, such as the inability to derive MU, is a consequence of its simplicity. However, more complex formal systems, such as systems of mathematical logic, may possess this ability. This is the key idea behind
1820:
It also demonstrates the contrast between interpretation on the "syntactic" level of symbols and on the "semantic" level of meanings. On the syntactic level, there is no knowledge of the MU puzzle's insolubility. The system does not
33:
involving a simple formal system called "MIU". Hofstadter's motivation is to contrast reasoning within a formal system (i.e., deriving theorems) against reasoning about the formal system itself. MIU is an example of a
781: 434: 891: 1834:
divisibility by three. This is the "semantic" level of the system — a level of meaning that the system naturally attains. On this level, the MU puzzle can be seen to be impossible.
1048: 809: 678: 1146: 1826:
human player, however, after a number of attempts, one soon begins to suspect that the puzzle may be impossible. One then "jumps out of the system" and starts to reason
842: 303:
by repeatedly applying the given rules. In other words, MU is not a theorem of the MIU formal system. To prove this, one must step "outside" the formal system itself.
1251: 1218: 986: 950: 705: 617: 590: 1303: 1277: 1934: 1080: 1006: 915: 725: 2125: 317:
in a string. Only the second and third rules change this number. In particular, rule two will double it while rule three will reduce it by 3. Now, the
1973:." As the Example column illustrates, a rule may be applied only to an entire MIU-number, not to an arbitrary part of its decimal representation. 2181: 1729:
in the first rule. Also, in this rendering, the arrangement of factors in this rule was made consistent with that of the other three rules.)
1470:
gives a mapping of the MIU system to arithmetic, as follows. First, every MIU-string can be translated to an integer by mapping the letters
2142: 1839: 2030: 1782: 2118: 730: 1093:
count can always be made even, by applying the first rule once, if necessary. Applying the fourth rule sufficiently often, all
1907:
are variables, standing for strings of symbols. A rule may be applied only to the whole string, not to an arbitrary substring.
380: 2321: 1813:
The MU string and the impossibility of its derivation is then analogous to a statement of mathematical logic which cannot be
1764: 1713:
The rendering of the first rule above differs superficially from that in the book, where it is written as "f we have made 10
2376: 2386: 2371: 2111: 1760: 1753: 2381: 2259: 62:
which can be combined to produce strings of symbols. The MU puzzle asks one to start with the "axiomatic" string
2083: 847: 1875: 307: 39: 2211: 2366: 2151: 1466: 1011: 29: 1802:— an encapsulation of mathematical and logical concepts using symbols. The MI string is akin to a single 35: 2225: 2062: 786: 2316: 2191: 1880: 1859: 634: 2327: 2264: 2201: 1830:
the system, rather than working within it. Eventually, one realises that the system is in some way
1108: 2254: 2171: 2134: 2003: 1814: 1807: 363: 24: 814: 2342: 2310: 2269: 2026: 343:
Subtracting 3 from a number that is not divisible by 3 does not make it divisible by 3 either.
1223: 1190: 958: 2294: 2279: 928: 683: 595: 568: 2284: 2249: 464: 2161: 2048:, Third Edition, Brooks/Cole, 2004. Chapter 8.4, "General Recursive Definitions," p. 501. 1282: 1256: 1919: 1855: 1065: 991: 900: 710: 2360: 2019: 1799: 1795:
The MIU system illustrates several important concepts in logic by means of analogy.
2289: 310:; that is, some quantity or property that doesn't change while applying the rules. 1936:
always exists, since the powers of 2 alternatingly evaluate to 1 and 2, modulo 3.
1742: 1725:
was reserved for use in exponents of 10 only, and therefore it was replaced by
1995: 306:
In order to prove assertions like this, it is often beneficial to look for an
340:
Doubling a number that is not divisible by 3 does not make it divisible by 3.
326: 2244: 1767: in this section. Unsourced material may be challenged and removed. 2103: 2087: 1482:
to the numbers 3, 1, and 0, respectively. (For example, the string
295:
The puzzle cannot be solved: it is impossible to change the string
1803: 2100:
An online JavaScript implementation of the MIU production system.
2079:
An online interface for producing derivations in the MIU System.
2107: 1496:
Third, the four formal rules given above become the following:
1957:
is any natural number smaller than 10. Each rule of the form "
1736: 1489:
Second, the single axiom of the MIU system, namely the string
70:
using in each step one of the following transformation rules:
2066: 776:{\displaystyle N\equiv 1{\text{ or }}N\equiv 2{\pmod {3}}} 16:
Puzzle in Douglas Hofstadter's book "Gödel, Escher, Bach"
1717: + 1, then we can make 10 × (10 429:{\displaystyle n\equiv 2^{a}\not \equiv 0{\pmod {3}}.\,} 1922: 1285: 1259: 1226: 1193: 1111: 1068: 1014: 994: 961: 931: 903: 850: 817: 789: 733: 713: 686: 637: 598: 571: 383: 2347:
By Hofstadter and the Fluid Analogies Research Group
1862:, and begins the relevant chapter with a quote from 2303: 2233: 2141: 1490: 1483: 1479: 1475: 1471: 1452: 1439: 1426: 1413: 1400: 1387: 1374: 1361: 1348: 1335: 1322: 1309: 1184: 1168: 1156: 1152: 1148: 1102: 1098: 1094: 1090: 1086: 1082: 1059: 1055: 1051: 952: 922: 918: 894: 624: 620: 548: 540: 536: 532: 528: 524: 504: 497: 487: 483: 479: 456: 371: 352: 348: 334: 322: 314: 300: 296: 280: 272: 267: 250: 237: 229: 224: 220: 211: 197: 184: 176: 171: 162: 151: 141: 133: 128: 124: 118: 107: 67: 63: 59: 55: 51: 2018: 1928: 1541:× 10 + 1)           1297: 1271: 1245: 1212: 1140: 1074: 1042: 1000: 980: 944: 909: 885: 836: 803: 775: 719: 699: 672: 611: 584: 428: 313:In this case, one can look at the total number of 1806:, and the four transformation rules are akin to 1151:. Applying the third rule to reduce triplets of 1858:uses the MU puzzle to introduce the concept of 1721: + 1)". Here, however, the variable 2119: 1187:, which respects properties 1 to 3, leads to 443:counts how often the second rule is applied. 8: 2021:Gödel, Escher, Bach: An Eternal Golden Braid 451:More generally, an arbitrarily given string 1998:Gödel, Escher, Bach: A Mental Space Odyssey 2126: 2112: 2104: 1798:It can be interpreted as an analogy for a 1953:stand for arbitrary natural numbers, and 1921: 1783:Learn how and when to remove this message 1284: 1258: 1231: 1225: 1198: 1192: 1132: 1116: 1110: 1067: 1022: 1015: 1013: 993: 966: 960: 936: 930: 902: 867: 855: 849: 822: 816: 797: 796: 788: 757: 743: 732: 712: 691: 685: 664: 648: 636: 603: 597: 576: 570: 471:respects the three following properties: 425: 406: 394: 382: 1514: 1509: 886:{\displaystyle 2^{n}\equiv N{\pmod {3}}} 1994:Justin Curry / Curran Kelleher (2007). 1986: 1892: 2046:Discrete Mathematics with Applications 1852:Discrete Mathematics with Applications 1305:; it can be hence derived as follows: 1179:To illustrate the construction in the 988:is divisible by 3, by construction of 551:respects properties 1 and 2. As shown 447:A decidable criterion for derivability 2182:Fluid Concepts and Creative Analogies 1965:" should be read as "if we have made 531:, or introduces any character out of 7: 1765:adding citations to reliable sources 1097:can then be deleted, thus obtaining 1043:{\displaystyle {\frac {2^{n}-N}{3}}} 1817:or disproven by the formal system. 1507:          875: 765: 414: 337:s is 1 which is not divisible by 3. 127:to the end of any string ending in 81:          14: 804:{\displaystyle n\in \mathbb {N} } 707:cannot be divisible by 3, hence, 552: 66:and transform it into the string 2224: 2017:Hofstadter, Douglas R. (1999) , 1741: 565:respects properties 1 to 3, let 333:In the beginning, the number of 1752:needs additional citations for 1159:in the right spots will obtain 868: 758: 555:, it also respects property 3. 460: 407: 2322:Indiana University Bloomington 1840:Gödel's Incompleteness Theorem 1183:part of the proof, the string 879: 869: 769: 759: 673:{\displaystyle N=N_{I}+3N_{U}} 418: 408: 50:Suppose there are the symbols 1: 1085:, followed by some number of 355:cannot be achieved because 0 38:and can be reformulated as a 1612:× 10 + 111 × 10 + 1141:{\displaystyle N_{I}+3N_{U}} 727:cannot be, either. That is, 680:. By property 3, the number 170:Double the string after the 1679: 1658: 1629: 1608: 1583: 1564: 1543: 1527: 1486:would be mapped to 31010.) 897:, applying the second rule 893:. Beginning from the axiom 271: 246: 228: 193: 175: 150: 132: 103: 2403: 1688: 1638: 1592: 1552: 1008:, applying the third rule 837:{\displaystyle 2^{n}>N} 478:is only composed with one 2341:Edited by Hofstadter and 2337: 2222: 2063:"Hofstadter's MIU System" 1574:10 × (3 × 10 + 1493:, becomes the number 31. 93: 83: 631:, respectively, and let 527:, changes the number of 1876:Invariant (mathematics) 1246:{\displaystyle N_{U}=1} 1213:{\displaystyle N_{I}=4} 981:{\displaystyle 2^{n}-N} 40:string rewriting system 2260:Hofstadter's butterfly 1930: 1299: 1273: 1247: 1214: 1167:has been derived from 1142: 1076: 1044: 1002: 982: 946: 911: 887: 838: 805: 777: 721: 701: 674: 613: 586: 511:is not divisible by 3. 430: 321:is that the number of 23:is a puzzle stated by 2212:Surfaces and Essences 1931: 1860:recursive definitions 1733:Relationship to logic 1300: 1274: 1248: 1215: 1143: 1077: 1045: 1003: 983: 947: 945:{\displaystyle 2^{n}} 912: 888: 839: 806: 778: 722: 702: 700:{\displaystyle N_{I}} 675: 614: 612:{\displaystyle N_{U}} 587: 585:{\displaystyle N_{I}} 431: 374:obeys the congruence 36:Post canonical system 2377:Independence results 2317:Egbert B. Gebstadter 2192:Le Ton beau de Marot 1920: 1881:Unrestricted grammar 1761:improve this article 1283: 1257: 1224: 1191: 1109: 1066: 1012: 992: 959: 929: 901: 848: 815: 787: 731: 711: 684: 635: 596: 569: 455:can be derived from 381: 90:Informal explanation 2328:Victim of the Brain 2202:I Am a Strange Loop 2152:Gödel, Escher, Bach 1467:Gödel, Escher, Bach 1298:{\displaystyle n=4} 1272:{\displaystyle N=7} 543:. Therefore, every 362:In the language of 30:Gödel, Escher, Bach 2387:1979 introductions 2372:Unsolvable puzzles 2172:Metamagical Themas 2135:Douglas Hofstadter 2004:MIT OpenCourseWare 1926: 1808:rules of inference 1295: 1269: 1243: 1210: 1138: 1072: 1050:times will obtain 1040: 998: 978: 942: 907: 883: 834: 801: 773: 717: 697: 670: 609: 582: 523:No rule moves the 482:and any number of 426: 364:modular arithmetic 347:Thus, the goal of 319:invariant property 25:Douglas Hofstadter 2354: 2353: 2343:Daniel C. Dennett 2311:Robert Hofstadter 2270:Hofstadter points 1929:{\displaystyle n} 1850:In her textbook, 1793: 1792: 1785: 1705: 1704: 1362:MIIIIIIIIIIIIIIII 1075:{\displaystyle N} 1038: 1001:{\displaystyle n} 910:{\displaystyle n} 746: 720:{\displaystyle N} 619:be the number of 286: 285: 2394: 2382:Formal languages 2295:Superrationality 2280:Platonia dilemma 2265:Hofstadter's law 2228: 2217: 2207: 2197: 2187: 2177: 2167: 2157: 2128: 2121: 2114: 2105: 2099: 2097: 2095: 2086:. Archived from 2078: 2076: 2074: 2065:. Archived from 2049: 2043: 2037: 2036:Here: Chapter I. 2035: 2024: 2014: 2008: 2007: 1991: 1974: 1943: 1937: 1935: 1933: 1932: 1927: 1914: 1908: 1897: 1846:Pedagogical uses 1788: 1781: 1777: 1774: 1768: 1745: 1737: 1501: 1500: 1492: 1485: 1481: 1477: 1473: 1454: 1451: 1450: 1449: 1446: 1441: 1438: 1437: 1436: 1433: 1428: 1425: 1424: 1423: 1420: 1415: 1412: 1411: 1410: 1407: 1402: 1399: 1398: 1397: 1394: 1389: 1386: 1385: 1384: 1381: 1376: 1373: 1372: 1371: 1368: 1363: 1360: 1359: 1358: 1355: 1350: 1347: 1346: 1345: 1342: 1337: 1334: 1333: 1332: 1329: 1324: 1321: 1320: 1319: 1316: 1311: 1304: 1302: 1301: 1296: 1278: 1276: 1275: 1270: 1252: 1250: 1249: 1244: 1236: 1235: 1219: 1217: 1216: 1211: 1203: 1202: 1186: 1170: 1158: 1154: 1150: 1147: 1145: 1144: 1139: 1137: 1136: 1121: 1120: 1104: 1100: 1096: 1092: 1088: 1084: 1081: 1079: 1078: 1073: 1061: 1057: 1053: 1049: 1047: 1046: 1041: 1039: 1034: 1027: 1026: 1016: 1007: 1005: 1004: 999: 987: 985: 984: 979: 971: 970: 954: 951: 949: 948: 943: 941: 940: 924: 920: 916: 914: 913: 908: 896: 892: 890: 889: 884: 882: 860: 859: 843: 841: 840: 835: 827: 826: 810: 808: 807: 802: 800: 782: 780: 779: 774: 772: 747: 744: 726: 724: 723: 718: 706: 704: 703: 698: 696: 695: 679: 677: 676: 671: 669: 668: 653: 652: 626: 622: 618: 616: 615: 610: 608: 607: 591: 589: 588: 583: 581: 580: 550: 542: 538: 534: 530: 526: 506: 499: 489: 485: 481: 458: 435: 433: 432: 427: 421: 399: 398: 373: 359:divisible by 3. 354: 350: 336: 324: 316: 302: 298: 282: 274: 269: 252: 239: 231: 226: 222: 213: 199: 186: 178: 173: 164: 153: 143: 135: 130: 126: 120: 109: 75: 74: 69: 65: 61: 57: 53: 2402: 2401: 2397: 2396: 2395: 2393: 2392: 2391: 2357: 2356: 2355: 2350: 2333: 2299: 2285:Six nines in pi 2250:BlooP and FlooP 2238: 2236: 2229: 2220: 2215: 2205: 2195: 2185: 2175: 2165: 2155: 2137: 2132: 2093: 2091: 2082: 2072: 2070: 2069:on 4 March 2016 2061: 2058: 2053: 2052: 2044: 2040: 2033: 2025:, Basic Books, 2016: 2015: 2011: 1993: 1992: 1988: 1983: 1978: 1977: 1944: 1940: 1918: 1917: 1915: 1911: 1898: 1894: 1889: 1872: 1848: 1789: 1778: 1772: 1769: 1758: 1746: 1735: 1464:Chapter XIX of 1462: 1460:Arithmetization 1447: 1444: 1443: 1442: 1434: 1431: 1430: 1429: 1421: 1418: 1417: 1416: 1408: 1405: 1404: 1403: 1395: 1392: 1391: 1390: 1382: 1379: 1378: 1377: 1375:MIIIIIIIUIIIIII 1369: 1366: 1365: 1364: 1356: 1353: 1352: 1351: 1343: 1340: 1339: 1338: 1330: 1327: 1326: 1325: 1317: 1314: 1313: 1312: 1281: 1280: 1255: 1254: 1227: 1222: 1221: 1194: 1189: 1188: 1177: 1128: 1112: 1107: 1106: 1064: 1063: 1062:, with exactly 1018: 1017: 1010: 1009: 990: 989: 962: 957: 956: 932: 927: 926: 899: 898: 851: 846: 845: 818: 813: 812: 785: 784: 729: 728: 709: 708: 687: 682: 681: 660: 644: 633: 632: 599: 594: 593: 572: 567: 566: 518: 465:if, and only if 449: 390: 379: 378: 293: 48: 17: 12: 11: 5: 2400: 2398: 2390: 2389: 2384: 2379: 2374: 2369: 2359: 2358: 2352: 2351: 2349: 2348: 2345: 2338: 2335: 2334: 2332: 2331: 2324: 2319: 2314: 2307: 2305: 2301: 2300: 2298: 2297: 2292: 2287: 2282: 2277: 2272: 2267: 2262: 2257: 2252: 2247: 2241: 2239: 2234: 2231: 2230: 2223: 2221: 2219: 2218: 2208: 2198: 2188: 2178: 2168: 2158: 2147: 2145: 2139: 2138: 2133: 2131: 2130: 2123: 2116: 2108: 2102: 2101: 2090:on 14 May 2018 2080: 2057: 2056:External links 2054: 2051: 2050: 2038: 2031: 2009: 1985: 1984: 1982: 1979: 1976: 1975: 1938: 1925: 1909: 1891: 1890: 1888: 1885: 1884: 1883: 1878: 1871: 1868: 1856:Susanna S. Epp 1847: 1844: 1791: 1790: 1749: 1747: 1740: 1734: 1731: 1707: 1706: 1703: 1702: 1687: 1684: 1681: 1678: 1669: 1666: 1657: 1653: 1652: 1637: 1634: 1631: 1628: 1619: 1616: 1607: 1603: 1602: 1591: 1588: 1585: 1582: 1572: 1569: 1565:3 × 10 + 1563: 1559: 1558: 1551: 1548: 1545: 1542: 1535: 1532: 1526: 1522: 1521: 1518: 1513: 1508: 1461: 1458: 1457: 1456: 1401:MIIIIIIIUUIIIU 1294: 1291: 1288: 1268: 1265: 1262: 1242: 1239: 1234: 1230: 1209: 1206: 1201: 1197: 1176: 1173: 1163:. Altogether, 1135: 1131: 1127: 1124: 1119: 1115: 1071: 1037: 1033: 1030: 1025: 1021: 997: 977: 974: 969: 965: 939: 935: 917:times obtains 906: 881: 878: 874: 871: 866: 863: 858: 854: 833: 830: 825: 821: 799: 795: 792: 771: 768: 764: 761: 756: 753: 750: 745: or  742: 739: 736: 716: 694: 690: 667: 663: 659: 656: 651: 647: 643: 640: 606: 602: 579: 575: 517: 514: 513: 512: 503:the number of 501: 491: 448: 445: 437: 436: 424: 420: 417: 413: 410: 405: 402: 397: 393: 389: 386: 345: 344: 341: 338: 292: 289: 288: 287: 284: 283: 278: 275: 270: 264: 259: 256: 245: 241: 240: 235: 232: 227: 217: 206: 203: 192: 188: 187: 182: 179: 174: 168: 160: 157: 149: 145: 144: 139: 136: 131: 121: 113: 110: 102: 98: 97: 92: 87: 82: 47: 44: 15: 13: 10: 9: 6: 4: 3: 2: 2399: 2388: 2385: 2383: 2380: 2378: 2375: 2373: 2370: 2368: 2367:Logic puzzles 2365: 2364: 2362: 2346: 2344: 2340: 2339: 2336: 2330: 2329: 2325: 2323: 2320: 2318: 2315: 2312: 2309: 2308: 2306: 2302: 2296: 2293: 2291: 2288: 2286: 2283: 2281: 2278: 2276: 2273: 2271: 2268: 2266: 2263: 2261: 2258: 2256: 2253: 2251: 2248: 2246: 2243: 2242: 2240: 2232: 2227: 2214: 2213: 2209: 2204: 2203: 2199: 2194: 2193: 2189: 2184: 2183: 2179: 2174: 2173: 2169: 2164: 2163: 2159: 2154: 2153: 2149: 2148: 2146: 2144: 2140: 2136: 2129: 2124: 2122: 2117: 2115: 2110: 2109: 2106: 2089: 2085: 2081: 2068: 2064: 2060: 2059: 2055: 2047: 2042: 2039: 2034: 2032:0-465-02656-7 2028: 2023: 2022: 2013: 2010: 2005: 2001: 2000: 1997: 1990: 1987: 1980: 1972: 1968: 1964: 1961: →  1960: 1956: 1952: 1948: 1942: 1939: 1923: 1913: 1910: 1906: 1902: 1896: 1893: 1886: 1882: 1879: 1877: 1874: 1873: 1869: 1867: 1865: 1861: 1857: 1853: 1845: 1843: 1841: 1835: 1833: 1829: 1824: 1818: 1816: 1811: 1809: 1805: 1801: 1800:formal system 1796: 1787: 1784: 1776: 1766: 1762: 1756: 1755: 1750:This section 1748: 1744: 1739: 1738: 1732: 1730: 1728: 1724: 1720: 1716: 1712: 1700: 1696: 1692: 1685: 1683: →  1682: 1677: 1673: 1670: 1668: →  1667: 1665: 1661: 1655: 1654: 1650: 1646: 1642: 1635: 1633: →  1632: 1627: 1623: 1620: 1618: →  1617: 1615: 1611: 1605: 1604: 1600: 1596: 1589: 1587: →  1586: 1581: 1577: 1573: 1571: →  1570: 1568: 1561: 1560: 1556: 1549: 1547: →  1546: 1540: 1536: 1534: →  1533: 1531:× 10 + 1 1530: 1524: 1523: 1519: 1517: 1512: 1506: 1503: 1502: 1499: 1498: 1497: 1494: 1487: 1469: 1468: 1459: 1388:MIIIIIIIUUIII 1308: 1307: 1306: 1292: 1289: 1286: 1266: 1263: 1260: 1240: 1237: 1232: 1228: 1207: 1204: 1199: 1195: 1182: 1174: 1172: 1166: 1162: 1133: 1129: 1125: 1122: 1117: 1113: 1069: 1035: 1031: 1028: 1023: 1019: 995: 975: 972: 967: 963: 937: 933: 904: 876: 872: 864: 861: 856: 852: 831: 828: 823: 819: 793: 790: 766: 762: 754: 751: 748: 740: 737: 734: 714: 692: 688: 665: 661: 657: 654: 649: 645: 641: 638: 630: 604: 600: 577: 573: 564: 560: 556: 554: 547:derived from 546: 522: 515: 510: 502: 495: 492: 477: 474: 473: 472: 470: 466: 462: 454: 446: 444: 442: 422: 415: 411: 403: 400: 395: 391: 387: 384: 377: 376: 375: 369: 366:, the number 365: 360: 358: 342: 339: 332: 331: 330: 328: 320: 311: 309: 304: 290: 279: 276: 265: 263: 260: 257: 255: 249: 243: 242: 236: 233: 218: 216: 210: 207: 204: 202: 196: 190: 189: 183: 180: 169: 167: 161: 158: 156: 147: 146: 140: 137: 122: 117: 114: 111: 106: 100: 99: 96: 91: 88: 86: 80: 77: 76: 73: 72: 71: 45: 43: 41: 37: 32: 31: 27:and found in 26: 22: 2326: 2290:Strange loop 2274: 2235:Concepts and 2210: 2200: 2190: 2180: 2170: 2162:The Mind's I 2160: 2150: 2092:. Retrieved 2088:the original 2071:. Retrieved 2067:the original 2045: 2041: 2020: 2012: 1999: 1996: 1989: 1970: 1969:we can make 1966: 1962: 1958: 1954: 1950: 1946: 1941: 1912: 1904: 1900: 1895: 1863: 1851: 1849: 1836: 1831: 1827: 1822: 1819: 1812: 1797: 1794: 1779: 1770: 1759:Please help 1754:verification 1751: 1726: 1722: 1718: 1714: 1710: 1708: 1698: 1694: 1690: 1675: 1674:× 10 + 1671: 1663: 1662:× 10 + 1659: 1648: 1644: 1640: 1625: 1624:× 10 + 1621: 1613: 1609: 1598: 1594: 1579: 1575: 1566: 1554: 1538: 1528: 1515: 1510: 1504: 1495: 1488: 1465: 1463: 1414:MIIIIIIIUUUU 1180: 1178: 1164: 1160: 628: 562: 558: 557: 544: 520: 519: 508: 496:begins with 493: 475: 468: 452: 450: 440: 438: 367: 361: 356: 346: 318: 312: 305: 294: 261: 253: 247: 219:Replace any 214: 208: 200: 194: 165: 154: 115: 104: 94: 89: 84: 78: 49: 28: 20: 18: 2084:"MU Puzzle" 2073:29 November 1537:10 × ( 1511:Formal rule 463:four rules 266:Remove any 85:Formal rule 2361:Categories 1981:References 1427:MIIIIIIIUU 811:such that 351:with zero 46:The puzzle 2275:MU puzzle 1773:July 2013 1349:MIIIIIIII 1029:− 973:− 862:≡ 794:∈ 752:≡ 738:≡ 388:≡ 327:divisible 308:invariant 21:MU puzzle 2313:(father) 2245:Ambigram 2237:projects 1916:Such an 1870:See also 1440:MIIIIIII 955:. Since 521:Only if: 401:≢ 291:Solution 2304:Related 2255:Copycat 1689: ( 1639: ( 1630:3111011 1593: ( 1553: ( 1520:  1516:Example 1448:→ 1435:→ 1422:→ 1409:→ 1396:→ 1383:→ 1370:→ 1357:→ 1344:→ 1331:→ 1318:→ 1175:Example 1155:into a 459:by the 325:is not 223:with a 95:Example 2216:(2013) 2206:(2007) 2196:(1997) 2186:(1995) 2176:(1985) 2166:(1981) 2156:(1979) 2094:13 May 2029:  1945:Here, 1899:Here, 1815:proven 1701:= 11) 1651:= 11) 1636:30011 1601:= 10) 1590:31010 1478:, and 1453:MIIUII 1185:MIIUII 1089:. The 783:. Let 553:before 439:where 329:by 3: 230:MUIIIU 123:Add a 58:, and 2143:Books 1887:Notes 1832:about 1828:about 1823:refer 1804:axiom 1697:= 2, 1693:= 3, 1680:30011 1647:= 3, 1643:= 3, 1597:= 2, 1557:= 3) 1484:MIUIU 1336:MIIII 1105:with 925:with 516:Proof 500:, and 461:above 299:into 185:MIUIU 2096:2018 2075:2016 2027:ISBN 1949:and 1903:and 1686:311 1578:) + 1550:310 1099:MIII 1052:MIII 919:MIII 844:and 829:> 623:and 592:and 486:and 273:MUUU 238:MUUU 19:The 1864:GEB 1763:by 1711:NB: 1656:4. 1606:3. 1584:310 1562:2. 1525:1. 1505:Nr. 1323:MII 1101:... 1058:... 1054:... 921:... 873:mod 763:mod 627:in 561:If 559:If: 507:in 412:mod 370:of 244:4. 221:III 198:III 191:3. 177:MIU 148:2. 142:MIU 101:1. 79:Nr. 2363:: 2002:. 1866:. 1854:, 1842:. 1810:. 1544:31 1491:MI 1474:, 1310:MI 1279:, 1253:, 1220:, 1181:If 1171:. 1169:MI 1056:IU 895:MI 549:MI 539:, 535:, 467:, 457:MI 357:is 349:MU 301:MU 297:MI 281:MU 277:to 268:UU 262:xy 251:UU 234:to 181:to 166:xx 138:to 134:MI 119:IU 68:MU 64:MI 54:, 42:. 2127:e 2120:t 2113:v 2098:. 2077:. 2006:. 1971:y 1967:x 1963:y 1959:x 1955:n 1951:m 1947:k 1924:n 1905:y 1901:x 1786:) 1780:( 1775:) 1771:( 1757:. 1727:k 1723:m 1719:m 1715:m 1709:( 1699:n 1695:m 1691:k 1676:n 1672:k 1664:n 1660:k 1649:n 1645:m 1641:k 1626:n 1622:k 1614:n 1610:k 1599:n 1595:m 1580:n 1576:n 1567:n 1555:k 1539:k 1529:k 1480:U 1476:I 1472:M 1455:. 1445:3 1432:4 1419:4 1406:3 1393:1 1380:3 1367:3 1354:2 1341:2 1328:2 1315:2 1293:4 1290:= 1287:n 1267:7 1264:= 1261:N 1241:1 1238:= 1233:U 1229:N 1208:4 1205:= 1200:I 1196:N 1165:x 1161:x 1157:U 1153:I 1149:I 1134:U 1130:N 1126:3 1123:+ 1118:I 1114:N 1103:I 1095:U 1091:U 1087:U 1083:I 1070:N 1060:U 1036:3 1032:N 1024:n 1020:2 996:n 976:N 968:n 964:2 953:I 938:n 934:2 923:I 905:n 880:) 877:3 870:( 865:N 857:n 853:2 832:N 824:n 820:2 798:N 791:n 770:) 767:3 760:( 755:2 749:N 741:1 735:N 715:N 693:I 689:N 666:U 662:N 658:3 655:+ 650:I 646:N 642:= 639:N 629:x 625:U 621:I 605:U 601:N 578:I 574:N 563:x 545:x 541:U 537:I 533:M 529:M 525:M 509:x 505:I 498:M 494:x 490:, 488:U 484:I 480:M 476:x 469:x 453:x 441:a 423:. 419:) 416:3 409:( 404:0 396:a 392:2 385:n 372:I 368:n 353:I 335:I 323:I 315:I 258:→ 254:y 248:x 225:U 215:y 212:U 209:x 205:→ 201:y 195:x 172:M 163:M 159:→ 155:x 152:M 129:I 125:U 116:x 112:→ 108:I 105:x 60:U 56:I 52:M

Index

Douglas Hofstadter
Gödel, Escher, Bach
Post canonical system
string rewriting system
invariant
divisible
modular arithmetic
above
if, and only if
before
Gödel, Escher, Bach

verification
improve this article
adding citations to reliable sources
Learn how and when to remove this message
formal system
axiom
rules of inference
proven
Gödel's Incompleteness Theorem
Susanna S. Epp
recursive definitions
Invariant (mathematics)
Unrestricted grammar
Gödel, Escher, Bach: A Mental Space Odyssey
MIT OpenCourseWare
Gödel, Escher, Bach: An Eternal Golden Braid
ISBN
0-465-02656-7

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.