Knowledge

Creative and productive sets

Source đź“ť

1283:
that takes the diagonal of all enumerated 1-place computable partial functions and adds 1 to them is an example of a creative set. Post gave a version of Gödel's Incompleteness Theorem using his creative sets, where originally Gödel had in some sense constructed a sentence that could be freely
1284:
translated as saying "I am unprovable in this axiomatic theory." However, Gödel's proof did not work from the concept of true sentences, and rather used the concept of a consistent theory, which led to the
463: 685: 256: 345: 399: 172: 205: 1664: 1542: 1291:"The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative." 882: 790: 755: 720: 584: 546: 513: 88: 1726: 1427: 1281: 1066: 1027: 979: 823: 643: 849: 610: 1389: 1369: 1341: 303: 1602: 1582: 1562: 1492: 1472: 1450: 1312: 1219: 950: 276: 144: 1178: 1869: 910:
it contains other numbers, and moreover there is an effective procedure to produce an example of such a number from the index
1850: 408: 2043: 2013: 1911: 1736:
formalization of an effectively calculable partial function, which can neither be proved or disproved. Church used
1759: 1755: 347:
is productive. Not every productive set has a recursively enumerable complement, however, as illustrated below.
648: 210: 17: 2070: 1285: 322: 353: 1818: 1150: 149: 2036:
Recursively enumerable sets and degrees: A study of computable functions and computably generated sets
1173:
is a recursively enumerable set of true sentences, there is at least one true sentence that is not in
177: 1607: 1497: 854: 762: 725: 690: 554: 518: 483: 1740:, Turing an idealized computer, and later Emil Post in his approach, all of which are equivalent. 66: 1669: 1394: 1224: 1042: 1003: 955: 795: 615: 1154: 1110: 108: 932:
The following theorems, due to Myhill (1955), show that in a sense all creative sets are like
1751: 918:, because this would imply that its complement, a productive set, is recursively enumerable. 828: 589: 2053: 2023: 1994: 1960: 1929: 1921: 1892: 1830: 1374: 1354: 91: 1317: 8: 2001: 1899: 95: 1971:(1944), "Recursively enumerable sets of positive integers and their decision problems", 285: 1729: 1587: 1567: 1547: 1477: 1457: 1435: 1297: 1204: 1118: 1101: 1069: 1030: 935: 922: 480:
To see this, we apply the definition of a productive function and show separately that
261: 129: 44: 2039: 2009: 1907: 1883: 1846: 1985: 1980: 1948: 1878: 1838: 1181:, because no recursively enumerable set is productive. The complement of the set 1146: 28: 1288:. After Post completed his version of incompleteness he then added the following: 2049: 2031: 2019: 1990: 1956: 1926: 1917: 1888: 1826: 1737: 402: 1865:"Some remarks on witness functions for nonpolynomial and noncomplete sets in NP" 1162: 1968: 1860: 1743: 1348: 926: 123: 40: 2064: 1952: 1864: 915: 1169:
sentences in the system will be a productive set, which means that whenever
1936: 1825:, Series in Information Processing and Computers, New York: McGraw-Hill, 1763: 1732:
that says the mathematical notion of computable partial functions is the
1344: 1474:), and is universal in the sense that any calculable partial function 47:. They are a standard topic in mathematical logic textbooks such as 1189:
is an example of a productive set whose complement is not creative.
1201:
defined the concept he called a Creative set. Reiterating, the set
851:, but we have demonstrated the contrary in the previous point. So 1941:
Zeitschrift fĂĽr Mathematische Logik und Grundlagen der Mathematik
2038:, Perspectives in Mathematical Logic, Berlin: Springer-Verlag, 1351:
showed the existence of a universal computer that computes the
1221:
referenced above and defined as the domain of the function
1087:
be a set of natural numbers. The following are equivalent:
991:
be a set of natural numbers. The following are equivalent:
1758:, and used it to provide potential counterexamples to the 2006:
Theory of recursive functions and effective computability
1843:
Computability Theory: An Introduction to Recursion Theory
1666:, and the diagonal function arises quite naturally as 1672: 1610: 1590: 1570: 1550: 1500: 1480: 1460: 1438: 1397: 1377: 1357: 1320: 1300: 1227: 1207: 1140: 1045: 1006: 958: 938: 921:
Any productive set has a productive function that is
857: 831: 798: 765: 728: 693: 651: 618: 592: 557: 521: 486: 411: 356: 325: 288: 264: 213: 180: 152: 132: 69: 458:{\displaystyle {\bar {K}}=\{i\mid i\not \in W_{i}\}} 1720: 1658: 1596: 1576: 1556: 1536: 1486: 1466: 1444: 1421: 1383: 1363: 1335: 1306: 1275: 1213: 1145:The set of all provable sentences in an effective 1060: 1021: 973: 944: 876: 843: 817: 784: 749: 714: 679: 637: 604: 578: 540: 507: 457: 393: 339: 297: 270: 250: 199: 166: 138: 82: 2062: 1431:the result of applying the instructions coded by 1177:. This can be used to give a rigorous proof of 897:can be recursively enumerable, because whenever 63:For the remainder of this article, assume that 1973:Bulletin of the American Mathematical Society 1185:will not be recursively enumerable, and thus 319:is recursively enumerable and its complement 452: 427: 388: 363: 1859: 1747: 1728:. Ultimately, these ideas are connected to 2008:(2nd ed.), Cambridge, MA: MIT Press, 1834:. Reprinted in 1982 by Dover Publications. 1153:. If the system is suitably complex, like 1984: 1882: 680:{\displaystyle W_{i}\subseteq {\bar {K}}} 327: 251:{\displaystyle f(i)\in A\setminus W_{i}.} 160: 58: 1906:, Mineola, NY: Dover Publications Inc., 1837: 1801: 1925:. Reprint of the 1967 original, Wiley, 1117:, that is, there is a total computable 465:is productive with productive function 340:{\displaystyle \mathbb {N} \setminus A} 14: 2063: 2000: 1935: 1898: 1797: 1795: 1786: 394:{\displaystyle K=\{i\mid i\in W_{i}\}} 52: 2030: 1817: 1782: 914:. Similarly, no creative set can be 901:contains every number in an r.e. set 48: 1967: 1343:has its own historical development. 1314:defined using the diagonal function 1198: 1179:Gödel's first incompleteness theorem 722:, this leads to a contradiction. So 43:that have important applications in 1792: 1750:) formulated an analogous concept, 107:the corresponding numbering of the 24: 1611: 1516: 1398: 1378: 1358: 1141:Applications in mathematical logic 25: 2082: 1124:on the natural numbers such that 952:and all productive sets are like 331: 232: 167:{\displaystyle i\in \mathbb {N} } 200:{\displaystyle W_{i}\subseteq A} 126:recursive (computable) function 1986:10.1090/S0002-9904-1944-08111-1 1823:Computability and unsolvability 1756:computational complexity theory 1659:{\displaystyle \Phi (e,x)=](x)} 1537:{\displaystyle f(x)=\Phi (e,x)} 877:{\displaystyle i\not \in W_{i}} 785:{\displaystyle i\not \in W_{i}} 750:{\displaystyle i\in {\bar {K}}} 715:{\displaystyle i\in {\bar {K}}} 579:{\displaystyle i\in {\bar {K}}} 541:{\displaystyle i\not \in W_{i}} 508:{\displaystyle i\in {\bar {K}}} 350:The archetypal creative set is 1776: 1746: and Paul Young ( 1709: 1703: 1700: 1697: 1691: 1688: 1682: 1676: 1653: 1647: 1644: 1641: 1635: 1632: 1626: 1614: 1531: 1519: 1510: 1504: 1413: 1401: 1330: 1324: 1264: 1258: 1255: 1252: 1246: 1243: 1237: 1231: 1052: 1013: 965: 741: 706: 671: 570: 499: 418: 223: 217: 13: 1: 1811: 1286:second incompleteness theorem 888: 825:, then it would be true that 311:of natural numbers is called 118:of natural numbers is called 1884:10.1016/0304-3975(85)90140-9 1870:Theoretical Computer Science 1604:. Using the above notation 83:{\displaystyle \varphi _{i}} 7: 1760:Berman–Hartmanis conjecture 1721:{\displaystyle d(x)=](x)+1} 1584:codes the instructions for 1422:{\displaystyle \Phi (w,x)=} 1276:{\displaystyle d(x)=](x)+1} 401:, the set representing the 10: 2087: 1347:in a 1936 article on the 1192: 1151:recursively enumerable set 1061:{\displaystyle {\bar {K}}} 1022:{\displaystyle {\bar {K}}} 974:{\displaystyle {\bar {K}}} 818:{\displaystyle i\in W_{i}} 638:{\displaystyle i\in W_{i}} 1939:(1955), "Creative sets", 477:(the identity function). 1953:10.1002/malq.19550010205 1769: 1371:function. The function 1294:The usual creative set 1863:; Young, Paul (1985), 1722: 1660: 1598: 1578: 1558: 1538: 1488: 1468: 1446: 1423: 1385: 1365: 1337: 1308: 1277: 1215: 1155:first-order arithmetic 1111:recursively isomorphic 1062: 1023: 975: 946: 878: 845: 844:{\displaystyle i\in K} 819: 786: 751: 716: 681: 639: 606: 605:{\displaystyle i\in K} 580: 542: 509: 459: 395: 341: 299: 272: 252: 201: 168: 140: 109:recursively enumerable 84: 59:Definition and example 1752:polynomial creativity 1723: 1661: 1599: 1579: 1559: 1539: 1489: 1469: 1447: 1424: 1391:is defined such that 1386: 1384:{\displaystyle \Phi } 1366: 1364:{\displaystyle \Phi } 1338: 1309: 1278: 1216: 1197:The seminal paper of 1063: 1024: 976: 947: 879: 846: 820: 787: 752: 717: 682: 640: 607: 581: 543: 510: 460: 396: 342: 300: 273: 253: 202: 169: 141: 85: 39:are types of sets of 2071:Computability theory 1900:Kleene, Stephen Cole 1839:Enderton, Herbert B. 1670: 1608: 1588: 1568: 1548: 1498: 1478: 1458: 1436: 1395: 1375: 1355: 1336:{\displaystyle d(x)} 1318: 1298: 1225: 1205: 1043: 1004: 956: 936: 855: 829: 796: 763: 726: 691: 649: 616: 590: 555: 519: 484: 409: 354: 323: 286: 262: 211: 178: 150: 130: 96:computable functions 92:admissible numbering 67: 29:computability theory 2002:Rogers, Hartley Jr. 280:productive function 1904:Mathematical logic 1845:, Academic Press, 1804:, pp. 79, 80, 120. 1762:on isomorphism of 1744:Deborah Joseph 1718: 1656: 1594: 1574: 1554: 1534: 1484: 1464: 1442: 1419: 1381: 1361: 1333: 1304: 1273: 1211: 1058: 1019: 971: 942: 893:No productive set 874: 841: 815: 782: 747: 712: 677: 635: 602: 576: 538: 505: 455: 391: 337: 298:{\displaystyle A.} 295: 268: 248: 197: 164: 136: 122:if there exists a 80: 45:mathematical logic 1852:978-0-12-384958-8 1597:{\displaystyle f} 1577:{\displaystyle e} 1557:{\displaystyle x} 1487:{\displaystyle f} 1467:{\displaystyle x} 1445:{\displaystyle w} 1307:{\displaystyle K} 1214:{\displaystyle K} 1055: 1016: 968: 945:{\displaystyle K} 744: 709: 674: 645:, now given that 573: 502: 421: 405:. Its complement 271:{\displaystyle f} 139:{\displaystyle f} 16:(Redirected from 2078: 2056: 2032:Soare, Robert I. 2026: 1997: 1988: 1963: 1924: 1895: 1886: 1877:(2–3): 225–237, 1855: 1833: 1805: 1799: 1790: 1780: 1727: 1725: 1724: 1719: 1665: 1663: 1662: 1657: 1603: 1601: 1600: 1595: 1583: 1581: 1580: 1575: 1563: 1561: 1560: 1555: 1543: 1541: 1540: 1535: 1493: 1491: 1490: 1485: 1473: 1471: 1470: 1465: 1451: 1449: 1448: 1443: 1428: 1426: 1425: 1420: 1390: 1388: 1387: 1382: 1370: 1368: 1367: 1362: 1342: 1340: 1339: 1334: 1313: 1311: 1310: 1305: 1282: 1280: 1279: 1274: 1220: 1218: 1217: 1212: 1147:axiomatic system 1067: 1065: 1064: 1059: 1057: 1056: 1048: 1028: 1026: 1025: 1020: 1018: 1017: 1009: 980: 978: 977: 972: 970: 969: 961: 951: 949: 948: 943: 883: 881: 880: 875: 873: 872: 850: 848: 847: 842: 824: 822: 821: 816: 814: 813: 791: 789: 788: 783: 781: 780: 756: 754: 753: 748: 746: 745: 737: 721: 719: 718: 713: 711: 710: 702: 686: 684: 683: 678: 676: 675: 667: 661: 660: 644: 642: 641: 636: 634: 633: 611: 609: 608: 603: 585: 583: 582: 577: 575: 574: 566: 547: 545: 544: 539: 537: 536: 514: 512: 511: 506: 504: 503: 495: 464: 462: 461: 456: 451: 450: 423: 422: 414: 400: 398: 397: 392: 387: 386: 346: 344: 343: 338: 330: 304: 302: 301: 296: 277: 275: 274: 269: 257: 255: 254: 249: 244: 243: 206: 204: 203: 198: 190: 189: 173: 171: 170: 165: 163: 146:so that for all 145: 143: 142: 137: 89: 87: 86: 81: 79: 78: 21: 2086: 2085: 2081: 2080: 2079: 2077: 2076: 2075: 2061: 2060: 2046: 2016: 1914: 1861:Joseph, Deborah 1853: 1814: 1809: 1808: 1802:Enderton (2010) 1800: 1793: 1781: 1777: 1772: 1738:lambda calculus 1730:Church's thesis 1671: 1668: 1667: 1609: 1606: 1605: 1589: 1586: 1585: 1569: 1566: 1565: 1549: 1546: 1545: 1499: 1496: 1495: 1479: 1476: 1475: 1459: 1456: 1455: 1437: 1434: 1433: 1396: 1393: 1392: 1376: 1373: 1372: 1356: 1353: 1352: 1319: 1316: 1315: 1299: 1296: 1295: 1226: 1223: 1222: 1206: 1203: 1202: 1195: 1157:, then the set 1143: 1047: 1046: 1044: 1041: 1040: 1008: 1007: 1005: 1002: 1001: 960: 959: 957: 954: 953: 937: 934: 933: 909: 891: 868: 864: 856: 853: 852: 830: 827: 826: 809: 805: 797: 794: 793: 776: 772: 764: 761: 760: 736: 735: 727: 724: 723: 701: 700: 692: 689: 688: 666: 665: 656: 652: 650: 647: 646: 629: 625: 617: 614: 613: 591: 588: 587: 565: 564: 556: 553: 552: 532: 528: 520: 517: 516: 494: 493: 485: 482: 481: 446: 442: 413: 412: 410: 407: 406: 403:halting problem 382: 378: 355: 352: 351: 326: 324: 321: 320: 287: 284: 283: 263: 260: 259: 239: 235: 212: 209: 208: 185: 181: 179: 176: 175: 159: 151: 148: 147: 131: 128: 127: 106: 74: 70: 68: 65: 64: 61: 41:natural numbers 33:productive sets 23: 22: 15: 12: 11: 5: 2084: 2074: 2073: 2059: 2058: 2044: 2028: 2014: 1998: 1979:(5): 284–316, 1965: 1933: 1912: 1896: 1857: 1851: 1835: 1813: 1810: 1807: 1806: 1791: 1774: 1773: 1771: 1768: 1717: 1714: 1711: 1708: 1705: 1702: 1699: 1696: 1693: 1690: 1687: 1684: 1681: 1678: 1675: 1655: 1652: 1649: 1646: 1643: 1640: 1637: 1634: 1631: 1628: 1625: 1622: 1619: 1616: 1613: 1593: 1573: 1553: 1533: 1530: 1527: 1524: 1521: 1518: 1515: 1512: 1509: 1506: 1503: 1483: 1463: 1441: 1418: 1415: 1412: 1409: 1406: 1403: 1400: 1380: 1360: 1349:Turing machine 1332: 1329: 1326: 1323: 1303: 1272: 1269: 1266: 1263: 1260: 1257: 1254: 1251: 1248: 1245: 1242: 1239: 1236: 1233: 1230: 1210: 1194: 1191: 1142: 1139: 1138: 1137: 1104: 1095: 1078: 1077: 1054: 1051: 1038: 1015: 1012: 999: 998:is productive. 967: 964: 941: 905: 890: 887: 886: 885: 871: 867: 863: 860: 840: 837: 834: 812: 808: 804: 801: 779: 775: 771: 768: 758: 743: 740: 734: 731: 708: 705: 699: 696: 673: 670: 664: 659: 655: 632: 628: 624: 621: 601: 598: 595: 572: 569: 563: 560: 535: 531: 527: 524: 501: 498: 492: 489: 454: 449: 445: 441: 438: 435: 432: 429: 426: 420: 417: 390: 385: 381: 377: 374: 371: 368: 365: 362: 359: 336: 333: 329: 294: 291: 278:is called the 267: 247: 242: 238: 234: 231: 228: 225: 222: 219: 216: 196: 193: 188: 184: 162: 158: 155: 135: 102: 77: 73: 60: 57: 18:Productive set 9: 6: 4: 3: 2: 2083: 2072: 2069: 2068: 2066: 2055: 2051: 2047: 2045:3-540-15299-7 2041: 2037: 2033: 2029: 2025: 2021: 2017: 2015:0-262-68052-1 2011: 2007: 2003: 1999: 1996: 1992: 1987: 1982: 1978: 1974: 1970: 1969:Post, Emil L. 1966: 1962: 1958: 1954: 1950: 1947:(2): 97–108, 1946: 1942: 1938: 1934: 1931: 1928: 1923: 1919: 1915: 1913:0-486-42533-9 1909: 1905: 1901: 1897: 1894: 1890: 1885: 1880: 1876: 1872: 1871: 1866: 1862: 1858: 1854: 1848: 1844: 1840: 1836: 1832: 1828: 1824: 1820: 1819:Davis, Martin 1816: 1815: 1803: 1798: 1796: 1788: 1787:Rogers (1987) 1784: 1779: 1775: 1767: 1765: 1761: 1757: 1753: 1749: 1745: 1741: 1739: 1735: 1731: 1715: 1712: 1706: 1694: 1685: 1679: 1673: 1650: 1638: 1629: 1623: 1620: 1617: 1591: 1571: 1551: 1528: 1525: 1522: 1513: 1507: 1501: 1481: 1461: 1454: 1439: 1432: 1416: 1410: 1407: 1404: 1350: 1346: 1327: 1321: 1301: 1292: 1289: 1287: 1270: 1267: 1261: 1249: 1240: 1234: 1228: 1208: 1200: 1190: 1188: 1184: 1180: 1176: 1172: 1168: 1164: 1163:Gödel numbers 1160: 1156: 1152: 1148: 1135: 1131: 1127: 1123: 1120: 1116: 1112: 1108: 1105: 1103: 1099: 1096: 1093: 1090: 1089: 1088: 1086: 1082: 1075: 1071: 1049: 1039: 1036: 1032: 1010: 1000: 997: 994: 993: 992: 990: 986: 982: 962: 939: 930: 928: 924: 919: 917: 913: 908: 904: 900: 896: 869: 865: 861: 858: 838: 835: 832: 810: 806: 802: 799: 792:: in fact if 777: 773: 769: 766: 759: 738: 732: 729: 703: 697: 694: 668: 662: 657: 653: 630: 626: 622: 619: 599: 596: 593: 567: 561: 558: 551: 550: 549: 533: 529: 525: 522: 496: 490: 487: 478: 476: 472: 468: 447: 443: 439: 436: 433: 430: 424: 415: 404: 383: 379: 375: 372: 369: 366: 360: 357: 348: 334: 318: 314: 310: 305: 292: 289: 281: 265: 258:The function 245: 240: 236: 229: 226: 220: 214: 194: 191: 186: 182: 156: 153: 133: 125: 121: 117: 112: 110: 105: 101: 97: 93: 75: 71: 56: 54: 53:Rogers (1987) 50: 46: 42: 38: 37:creative sets 34: 30: 19: 2035: 2005: 1976: 1972: 1944: 1940: 1937:Myhill, John 1903: 1874: 1868: 1842: 1822: 1783:Soare (1987) 1778: 1742: 1733: 1494:is given by 1453:to the input 1452: 1430: 1293: 1290: 1196: 1186: 1182: 1174: 1170: 1166: 1158: 1149:is always a 1144: 1133: 1129: 1125: 1121: 1114: 1106: 1097: 1094:is creative. 1091: 1084: 1080: 1079: 1073: 1034: 995: 988: 984: 983: 931: 920: 911: 906: 902: 898: 894: 892: 479: 474: 470: 466: 349: 316: 312: 308: 306: 279: 119: 115: 113: 103: 99: 62: 49:Soare (1987) 36: 32: 26: 1764:NP-complete 1345:Alan Turing 1199:Post (1944) 1070:m-reducible 1031:1-reducible 1812:References 1102:1-complete 889:Properties 586:: suppose 120:productive 1612:Φ 1517:Φ 1399:Φ 1379:Φ 1359:Φ 1119:bijection 1053:¯ 1014:¯ 966:¯ 923:injective 916:decidable 836:∈ 803:∈ 742:¯ 733:∈ 707:¯ 698:∈ 672:¯ 663:⊆ 623:∈ 597:∈ 571:¯ 562:∈ 500:¯ 491:∈ 434:∣ 419:¯ 376:∈ 370:∣ 332:∖ 233:∖ 227:∈ 192:⊆ 157:∈ 72:φ 2065:Category 2034:(1987), 2004:(1987), 1902:(2002), 1841:(2010), 1821:(1958), 1544:for all 1081:Theorem. 985:Theorem. 862:∉ 770:∉ 687:we have 526:∉ 440:∉ 313:creative 2054:0882921 2024:0886890 1995:0010514 1961:0071379 1930:0216930 1922:1950307 1893:0821203 1831:0124208 1734:correct 1193:History 612:, then 94:of the 2052:  2042:  2022:  2012:  1993:  1959:  1920:  1910:  1891:  1849:  1829:  1766:sets. 1564:where 307:A set 114:A set 111:sets. 90:is an 1770:Notes 1754:, in 927:total 207:then 174:, if 124:total 2040:ISBN 2010:ISBN 1908:ISBN 1847:ISBN 1748:1985 1167:true 1132:) = 1083:Let 987:Let 925:and 515:and 473:) = 282:for 98:and 51:and 35:and 1981:doi 1949:doi 1879:doi 1165:of 1161:of 1113:to 1109:is 1100:is 1072:to 1068:is 1033:to 1029:is 315:if 27:In 2067:: 2050:MR 2048:, 2020:MR 2018:, 1991:MR 1989:, 1977:50 1975:, 1957:MR 1955:, 1943:, 1927:MR 1918:MR 1916:, 1889:MR 1887:, 1875:39 1873:, 1867:, 1827:MR 1794:^ 1785:; 981:. 929:. 548:: 55:. 31:, 2057:. 2027:. 1983:: 1964:. 1951:: 1945:1 1932:. 1881:: 1856:. 1789:. 1716:1 1713:+ 1710:) 1707:x 1704:( 1701:] 1698:] 1695:x 1692:[ 1689:[ 1686:= 1683:) 1680:x 1677:( 1674:d 1654:) 1651:x 1648:( 1645:] 1642:] 1639:e 1636:[ 1633:[ 1630:= 1627:) 1624:x 1621:, 1618:e 1615:( 1592:f 1572:e 1552:x 1532:) 1529:x 1526:, 1523:e 1520:( 1514:= 1511:) 1508:x 1505:( 1502:f 1482:f 1462:x 1440:w 1429:( 1417:= 1414:) 1411:x 1408:, 1405:w 1402:( 1331:) 1328:x 1325:( 1322:d 1302:K 1271:1 1268:+ 1265:) 1262:x 1259:( 1256:] 1253:] 1250:x 1247:[ 1244:[ 1241:= 1238:) 1235:x 1232:( 1229:d 1209:K 1187:T 1183:T 1175:W 1171:W 1159:T 1136:. 1134:K 1130:C 1128:( 1126:f 1122:f 1115:K 1107:C 1098:C 1092:C 1085:C 1076:. 1074:P 1050:K 1037:. 1035:P 1011:K 996:P 989:P 963:K 940:K 912:i 907:i 903:W 899:A 895:A 884:. 870:i 866:W 859:i 839:K 833:i 811:i 807:W 800:i 778:i 774:W 767:i 757:. 739:K 730:i 704:K 695:i 669:K 658:i 654:W 631:i 627:W 620:i 600:K 594:i 568:K 559:i 534:i 530:W 523:i 497:K 488:i 475:i 471:i 469:( 467:f 453:} 448:i 444:W 437:i 431:i 428:{ 425:= 416:K 389:} 384:i 380:W 373:i 367:i 364:{ 361:= 358:K 335:A 328:N 317:A 309:A 293:. 290:A 266:f 246:. 241:i 237:W 230:A 224:) 221:i 218:( 215:f 195:A 187:i 183:W 161:N 154:i 134:f 116:A 104:i 100:W 76:i 20:)

Index

Productive set
computability theory
natural numbers
mathematical logic
Soare (1987)
Rogers (1987)
admissible numbering
computable functions
recursively enumerable
total
halting problem
decidable
injective
total
1-reducible
m-reducible
1-complete
recursively isomorphic
bijection
axiomatic system
recursively enumerable set
first-order arithmetic
Gödel numbers
Gödel's first incompleteness theorem
Post (1944)
second incompleteness theorem
Alan Turing
Turing machine
Church's thesis
lambda calculus

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

↑