Knowledge (XXG)

Markov algorithm

Source đź“ť

22: 499: 300: 494:{\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.} 1370:. Moreover, inherent in the definition of a normal algorithm are a number of ideas used in programming languages aimed at handling symbolic information – for example, in 1525:
These rules give a more interesting example. They rewrite binary numbers to their unary counterparts. For example, 101 will be rewritten to a string of 5 consecutive bars.
671: 255: 51: 859: 696: 642: 617: 592: 547: 834: 186: 1170: 1136: 1038: 292: 1232: 1201: 1102: 1071: 1002: 969: 1316: 1286: 1258: 931: 885: 808: 722: 1343: 905: 782: 762: 742: 567: 522: 226: 206: 1948: 1843: 1882: 1808: 1813: 1611:
In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, the Netherlands, 1968, pp. 191–206.
1621:
American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189)
1818: 1614: 1803: 2029: 1897: 1838: 1710: 73: 1745: 1678: 1925: 2070: 2060: 524:
in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that
1930: 1785: 569:, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the 228:
are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form
87: 34: 2009: 1735: 1859: 44: 38: 30: 2065: 2014: 1892: 1795: 1765: 2024: 1920: 1864: 1719: 103: 1823: 55: 2019: 1755: 1367: 1968: 115: 95: 1494:
If the algorithm is applied to the above example, the Symbol string will change in the following manner.
1973: 1915: 1775: 1703: 150:. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of 1780: 1360: 128: 933:
is considered to be the result of the current step, subject to further processing in the next step.
1978: 647: 231: 1907: 1874: 139:
Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.
119: 1366:
Normal algorithms have proved to be a convenient means for the construction of many sections of
1557:
If the algorithm is applied to the above example, it will terminate after the following steps.
2039: 2034: 2004: 1958: 1760: 1696: 1646: 813: 165: 1363:
formulated in relation to the normal algorithm is called the "principle of normalization."
1141: 1107: 1007: 594:, then the algorithm terminates, and the result of its work is considered to be the string 263: 1887: 1828: 1740: 1206: 1175: 1076: 1043: 974: 939: 107: 1291: 1263: 1237: 910: 864: 787: 701: 1321: 839: 784:
is chosen. Then the algorithm terminates and the result of its work is considered to be
676: 622: 597: 572: 527: 1940: 1833: 1595: 1356: 1352: 890: 767: 747: 727: 552: 507: 211: 191: 99: 1651: 2054: 1750: 1727: 619:. Otherwise, the first of the substitution formulae whose left sides are included in 118:
from its simple notation. Markov algorithms are named after the Soviet mathematician
1683: 1953: 1770: 1441:
Note that after each rule application the search starts over from the first rule.
549:
is the word obtained in the previous step of the algorithm (or the original word
1963: 111: 936:
For example, the process of applying the algorithm described above to the word
260:
Here is an example of a normal algorithm scheme in the five-letter alphabet
1673: 1999: 1449:
The following example shows the basic operation of a Markov algorithm.
1405:
Check the Rules in order from top to bottom to see whether any of the
162:. Simple substitution formulas are represented by strings of the form 1386:
are a sequence of pairs of strings, usually presented in the form of
1634: 1434:
If the rule just applied was a terminating one, the algorithm stops.
504:
The process of applying the normal algorithm to an arbitrary string
1423:
of them to replace the leftmost occurrence of matched text in the
1371: 124: 142:
The definition of any normal algorithm consists of two parts: an
1983: 1669:
Yad Studio - Markov algorithms IDE and interpreter (Open Source)
1668: 836:, then out of all of the possible representations of the string 1692: 1609:
String processing languages and generalized Markov algorithms.
15: 673:, then out of all of possible representations of the string 488: 110:, which means that they are suitable as a general model of 1688: 1359:
is equivalent to some normal algorithm. A version of the
644:
is selected. If the substitution formula is of the form
810:. However, if this substitution formula is of the form 1635:"Markov's constructive analysis; a participant's view" 309: 1324: 1294: 1266: 1240: 1209: 1178: 1144: 1110: 1079: 1046: 1010: 977: 942: 913: 893: 867: 842: 816: 790: 770: 750: 730: 704: 679: 650: 625: 600: 575: 555: 530: 510: 303: 266: 234: 214: 194: 168: 106:
of symbols. Markov algorithms have been shown to be
1992: 1939: 1906: 1873: 1852: 1794: 1726: 1394:. Each rule may be either ordinary or terminating. 1337: 1318:, after which the algorithm stops with the result 1310: 1280: 1252: 1226: 1195: 1164: 1130: 1096: 1065: 1032: 996: 963: 925: 899: 879: 853: 828: 802: 776: 756: 736: 716: 690: 665: 636: 611: 586: 561: 541: 516: 493: 286: 249: 220: 200: 180: 764:are arbitrary strings) the one with the shortest 43:but its sources remain unclear because it lacks 1704: 1684:Markov algorithm interpreters at Rosetta-Code 8: 1513:"I bought a bag of apples from my brother." 1351:Any normal algorithm is equivalent to some 1711: 1697: 1689: 1650: 1510:"I bought a bag of apples from the shop." 1330: 1325: 1323: 1303: 1298: 1293: 1273: 1265: 1239: 1216: 1208: 1185: 1177: 1154: 1143: 1120: 1109: 1083: 1078: 1058: 1050: 1045: 1025: 1017: 1009: 989: 978: 976: 956: 951: 943: 941: 912: 892: 866: 841: 815: 789: 769: 749: 729: 703: 678: 649: 624: 599: 574: 554: 529: 509: 464: 426: 406: 383: 378: 333: 312: 308: 302: 267: 265: 233: 213: 193: 167: 74:Learn how and when to remove this message 1883:Comparison of regular-expression engines 1625: 1507:"I bought a bag of apples from T shop." 1416:If none is found, the algorithm stops. 1355:, and vice versa – any 1844:Zhu–Takaoka string matching algorithm 7: 1615:Andrey Andreevich Markov (1903-1979) 1504:"I bought a bag of apples from T S." 1809:Boyer–Moore string-search algorithm 1517:The algorithm will then terminate. 146:, which is a set of symbols, and a 1501:"I bought a B of apples from T S." 907:is chosen, after which the string 14: 1898:Nondeterministic finite automaton 1839:Two-way string-matching algorithm 971:results in the sequence of words 1633:Kushner, Boris A. (1999-05-28). 20: 1486:"I bought a B of As from T S." 1419:If one (or more) is found, use 1348:For other examples, see below. 1814:Boyer–Moore–Horspool algorithm 1804:Apostolico–Giancarlo algorithm 1498:"I bought a B of As from T S." 1331: 1326: 1304: 1299: 1274: 1217: 1186: 1155: 1121: 1084: 1059: 1051: 1026: 1018: 990: 979: 957: 952: 944: 820: 654: 478: 465: 456: 436: 427: 413: 390: 384: 370: 350: 334: 322: 313: 268: 238: 172: 1: 1652:10.1016/S0304-3975(98)00291-6 1470:"the shop" -> "my brother" 154:. Each formula can be either 1819:Knuth–Morris–Pratt algorithm 1746:Damerau–Levenshtein distance 1679:Markov algorithm interpreter 1674:Markov algorithm interpreter 1639:Theoretical Computer Science 666:{\displaystyle L\to \cdot D} 250:{\displaystyle L\to \cdot D} 131:based on Markov algorithms. 88:theoretical computer science 2010:Compressed pattern matching 1736:Approximate string matching 2087: 2015:Longest common subsequence 1926:Needleman–Wunsch algorithm 1796:String-searching algorithm 887:the one with the shortest 102:-like rules to operate on 2025:Sequential pattern mining 1865:Commentz-Walter algorithm 1853:Multiple string searching 1786:Wagner–Fischer algorithm 1619:The Theory of Algorithms. 1607:Caracciolo di Forino, A. 2035:String rewriting systems 2020:Longest common substring 1931:Smith–Waterman algorithm 1756:Gestalt pattern matching 1368:constructive mathematics 29:This article includes a 1969:Generalized suffix tree 1893:Thompson's construction 116:mathematical expression 96:string rewriting system 58:more precise citations. 1921:Hirschberg's algorithm 1339: 1312: 1282: 1254: 1228: 1197: 1166: 1132: 1098: 1067: 1034: 998: 965: 927: 901: 881: 855: 830: 829:{\displaystyle L\to D} 804: 778: 758: 738: 718: 692: 667: 638: 613: 588: 563: 543: 518: 495: 288: 251: 222: 202: 182: 181:{\displaystyle L\to D} 114:and can represent any 2071:Models of computation 2061:Theory of computation 1776:Levenshtein automaton 1766:Jaro–Winkler distance 1473:"a never used" -> 1340: 1313: 1283: 1255: 1229: 1198: 1167: 1165:{\displaystyle baa|*} 1133: 1131:{\displaystyle aba|*} 1099: 1068: 1035: 1033:{\displaystyle ba|*|} 999: 966: 928: 902: 882: 856: 831: 805: 779: 759: 739: 719: 693: 668: 639: 614: 589: 564: 544: 519: 496: 289: 287:{\displaystyle |*abc} 252: 223: 203: 183: 152:substitution formulas 1824:Rabin–Karp algorithm 1781:Levenshtein distance 1409:can be found in the 1361:Church-Turing thesis 1322: 1292: 1264: 1238: 1227:{\displaystyle aa|c} 1207: 1196:{\displaystyle aa|*} 1176: 1142: 1108: 1097:{\displaystyle a|b*} 1077: 1066:{\displaystyle a|*|} 1044: 1008: 997:{\displaystyle |b*|} 975: 964:{\displaystyle |*||} 940: 911: 891: 865: 840: 814: 788: 768: 748: 728: 702: 677: 648: 623: 598: 573: 553: 528: 508: 301: 264: 232: 212: 192: 166: 129:programming language 1979:Ternary search tree 1311:{\displaystyle c||} 1281:{\displaystyle ac|} 1253:{\displaystyle aac} 926:{\displaystyle RDS} 880:{\displaystyle RLS} 803:{\displaystyle RDS} 717:{\displaystyle RLS} 1908:Sequence alignment 1875:Regular expression 1477:"terminating rule" 1338:{\displaystyle ||} 1335: 1308: 1278: 1250: 1224: 1193: 1162: 1128: 1094: 1063: 1030: 994: 961: 923: 897: 877: 854:{\displaystyle V'} 851: 826: 800: 774: 754: 734: 714: 691:{\displaystyle V'} 688: 663: 637:{\displaystyle V'} 634: 612:{\displaystyle V'} 609: 587:{\displaystyle V'} 584: 559: 542:{\displaystyle V'} 539: 514: 491: 486: 284: 247: 218: 198: 178: 120:Andrey Markov, Jr. 31:list of references 2066:Rewriting systems 2048: 2047: 2040:String operations 1645:(1–2): 268, 284. 1458:"A" -> "apple" 900:{\displaystyle R} 777:{\displaystyle R} 757:{\displaystyle S} 737:{\displaystyle R} 562:{\displaystyle V} 517:{\displaystyle V} 221:{\displaystyle D} 201:{\displaystyle L} 84: 83: 76: 2078: 2005:Pattern matching 1959:Suffix automaton 1761:Hamming distance 1713: 1706: 1699: 1690: 1657: 1656: 1654: 1630: 1534:"|0" -> "0||" 1464:"S" -> "shop" 1427:string with its 1344: 1342: 1341: 1336: 1334: 1329: 1317: 1315: 1314: 1309: 1307: 1302: 1287: 1285: 1284: 1279: 1277: 1259: 1257: 1256: 1251: 1233: 1231: 1230: 1225: 1220: 1202: 1200: 1199: 1194: 1189: 1171: 1169: 1168: 1163: 1158: 1137: 1135: 1134: 1129: 1124: 1103: 1101: 1100: 1095: 1087: 1072: 1070: 1069: 1064: 1062: 1054: 1039: 1037: 1036: 1031: 1029: 1021: 1003: 1001: 1000: 995: 993: 982: 970: 968: 967: 962: 960: 955: 947: 932: 930: 929: 924: 906: 904: 903: 898: 886: 884: 883: 878: 860: 858: 857: 852: 850: 835: 833: 832: 827: 809: 807: 806: 801: 783: 781: 780: 775: 763: 761: 760: 755: 743: 741: 740: 735: 723: 721: 720: 715: 697: 695: 694: 689: 687: 672: 670: 669: 664: 643: 641: 640: 635: 633: 618: 616: 615: 610: 608: 593: 591: 590: 585: 583: 568: 566: 565: 560: 548: 546: 545: 540: 538: 523: 521: 520: 515: 500: 498: 497: 492: 490: 487: 468: 430: 422: 410: 402: 387: 382: 374: 337: 316: 293: 291: 290: 285: 271: 256: 254: 253: 248: 227: 225: 224: 219: 207: 205: 204: 199: 187: 185: 184: 179: 92:Markov algorithm 79: 72: 68: 65: 59: 54:this article by 45:inline citations 24: 23: 16: 2086: 2085: 2081: 2080: 2079: 2077: 2076: 2075: 2051: 2050: 2049: 2044: 1988: 1935: 1902: 1888:Regular grammar 1869: 1848: 1829:Raita algorithm 1790: 1741:Bitap algorithm 1722: 1717: 1665: 1660: 1632: 1631: 1627: 1604: 1592: 1555: 1547: 1531: 1523: 1521:Another example 1492: 1484: 1467:"T" -> "the" 1461:"B" -> "bag" 1455: 1447: 1380: 1320: 1319: 1290: 1289: 1262: 1261: 1236: 1235: 1205: 1204: 1174: 1173: 1140: 1139: 1106: 1105: 1075: 1074: 1042: 1041: 1006: 1005: 973: 972: 938: 937: 909: 908: 889: 888: 863: 862: 861:of the form of 843: 838: 837: 812: 811: 786: 785: 766: 765: 746: 745: 726: 725: 700: 699: 680: 675: 674: 646: 645: 626: 621: 620: 601: 596: 595: 576: 571: 570: 551: 550: 531: 526: 525: 506: 505: 485: 484: 476: 470: 469: 459: 454: 445: 444: 439: 434: 423: 421: 416: 411: 403: 401: 393: 388: 375: 373: 368: 362: 361: 353: 348: 339: 338: 325: 320: 304: 299: 298: 262: 261: 230: 229: 210: 209: 190: 189: 164: 163: 137: 108:Turing-complete 80: 69: 63: 60: 49: 35:related reading 25: 21: 12: 11: 5: 2084: 2082: 2074: 2073: 2068: 2063: 2053: 2052: 2046: 2045: 2043: 2042: 2037: 2032: 2027: 2022: 2017: 2012: 2007: 2002: 1996: 1994: 1990: 1989: 1987: 1986: 1981: 1976: 1971: 1966: 1961: 1956: 1951: 1945: 1943: 1941:Data structure 1937: 1936: 1934: 1933: 1928: 1923: 1918: 1912: 1910: 1904: 1903: 1901: 1900: 1895: 1890: 1885: 1879: 1877: 1871: 1870: 1868: 1867: 1862: 1856: 1854: 1850: 1849: 1847: 1846: 1841: 1836: 1834:Trigram search 1831: 1826: 1821: 1816: 1811: 1806: 1800: 1798: 1792: 1791: 1789: 1788: 1783: 1778: 1773: 1768: 1763: 1758: 1753: 1748: 1743: 1738: 1732: 1730: 1724: 1723: 1718: 1716: 1715: 1708: 1701: 1693: 1687: 1686: 1681: 1676: 1671: 1664: 1663:External links 1661: 1659: 1658: 1624: 1623: 1622: 1612: 1603: 1600: 1599: 1598: 1596:Formal grammar 1591: 1588: 1587: 1586: 1583: 1580: 1577: 1574: 1571: 1568: 1565: 1562: 1554: 1551: 1546: 1543: 1542: 1541: 1538: 1537:"1" -> "0|" 1535: 1530: 1527: 1522: 1519: 1515: 1514: 1511: 1508: 1505: 1502: 1499: 1491: 1488: 1483: 1480: 1479: 1478: 1471: 1468: 1465: 1462: 1459: 1454: 1451: 1446: 1443: 1439: 1438: 1435: 1432: 1417: 1414: 1379: 1376: 1357:Turing machine 1353:Turing machine 1333: 1328: 1306: 1301: 1297: 1276: 1272: 1269: 1249: 1246: 1243: 1223: 1219: 1215: 1212: 1192: 1188: 1184: 1181: 1161: 1157: 1153: 1150: 1147: 1127: 1123: 1119: 1116: 1113: 1093: 1090: 1086: 1082: 1061: 1057: 1053: 1049: 1028: 1024: 1020: 1016: 1013: 992: 988: 985: 981: 959: 954: 950: 946: 922: 919: 916: 896: 876: 873: 870: 849: 846: 825: 822: 819: 799: 796: 793: 773: 753: 733: 713: 710: 707: 686: 683: 662: 659: 656: 653: 632: 629: 607: 604: 582: 579: 558: 537: 534: 513: 502: 501: 489: 483: 480: 477: 475: 472: 471: 467: 463: 460: 458: 455: 453: 450: 447: 446: 443: 440: 438: 435: 433: 429: 425: 424: 420: 417: 415: 412: 409: 405: 404: 400: 397: 394: 392: 389: 386: 381: 377: 376: 372: 369: 367: 364: 363: 360: 357: 354: 352: 349: 347: 344: 341: 340: 336: 332: 329: 326: 324: 321: 319: 315: 311: 310: 307: 283: 280: 277: 274: 270: 246: 243: 240: 237: 217: 197: 177: 174: 171: 136: 133: 82: 81: 39:external links 28: 26: 19: 13: 10: 9: 6: 4: 3: 2: 2083: 2072: 2069: 2067: 2064: 2062: 2059: 2058: 2056: 2041: 2038: 2036: 2033: 2031: 2028: 2026: 2023: 2021: 2018: 2016: 2013: 2011: 2008: 2006: 2003: 2001: 1998: 1997: 1995: 1991: 1985: 1982: 1980: 1977: 1975: 1972: 1970: 1967: 1965: 1962: 1960: 1957: 1955: 1952: 1950: 1947: 1946: 1944: 1942: 1938: 1932: 1929: 1927: 1924: 1922: 1919: 1917: 1914: 1913: 1911: 1909: 1905: 1899: 1896: 1894: 1891: 1889: 1886: 1884: 1881: 1880: 1878: 1876: 1872: 1866: 1863: 1861: 1858: 1857: 1855: 1851: 1845: 1842: 1840: 1837: 1835: 1832: 1830: 1827: 1825: 1822: 1820: 1817: 1815: 1812: 1810: 1807: 1805: 1802: 1801: 1799: 1797: 1793: 1787: 1784: 1782: 1779: 1777: 1774: 1772: 1769: 1767: 1764: 1762: 1759: 1757: 1754: 1752: 1751:Edit distance 1749: 1747: 1744: 1742: 1739: 1737: 1734: 1733: 1731: 1729: 1728:String metric 1725: 1721: 1714: 1709: 1707: 1702: 1700: 1695: 1694: 1691: 1685: 1682: 1680: 1677: 1675: 1672: 1670: 1667: 1666: 1662: 1653: 1648: 1644: 1640: 1636: 1629: 1626: 1620: 1616: 1613: 1610: 1606: 1605: 1601: 1597: 1594: 1593: 1589: 1584: 1581: 1578: 1575: 1572: 1569: 1566: 1563: 1560: 1559: 1558: 1552: 1550: 1545:Symbol string 1544: 1539: 1536: 1533: 1532: 1528: 1526: 1520: 1518: 1512: 1509: 1506: 1503: 1500: 1497: 1496: 1495: 1489: 1487: 1482:Symbol string 1481: 1476: 1472: 1469: 1466: 1463: 1460: 1457: 1456: 1452: 1450: 1444: 1442: 1437:Go to step 1. 1436: 1433: 1430: 1426: 1422: 1418: 1415: 1412: 1408: 1404: 1403: 1402: 1400: 1395: 1393: 1389: 1385: 1377: 1375: 1373: 1369: 1364: 1362: 1358: 1354: 1349: 1346: 1295: 1270: 1267: 1247: 1244: 1241: 1221: 1213: 1210: 1190: 1182: 1179: 1159: 1151: 1148: 1145: 1125: 1117: 1114: 1111: 1091: 1088: 1080: 1055: 1047: 1022: 1014: 1011: 986: 983: 948: 934: 920: 917: 914: 894: 874: 871: 868: 847: 844: 823: 817: 797: 794: 791: 771: 751: 731: 711: 708: 705: 684: 681: 660: 657: 651: 630: 627: 605: 602: 580: 577: 556: 535: 532: 511: 481: 473: 461: 451: 448: 441: 431: 418: 407: 398: 395: 379: 365: 358: 355: 345: 342: 330: 327: 317: 305: 297: 296: 295: 281: 278: 275: 272: 258: 244: 241: 235: 215: 195: 175: 169: 161: 157: 153: 149: 145: 140: 134: 132: 130: 126: 122: 121: 117: 113: 109: 105: 101: 97: 93: 89: 78: 75: 67: 57: 53: 47: 46: 40: 36: 32: 27: 18: 17: 1954:Suffix array 1860:Aho–Corasick 1771:Lee distance 1642: 1638: 1628: 1618: 1608: 1556: 1548: 1540:"0" -> "" 1524: 1516: 1493: 1485: 1474: 1448: 1440: 1428: 1424: 1420: 1410: 1406: 1398: 1396: 1391: 1387: 1383: 1381: 1365: 1350: 1347: 935: 698:of the form 503: 259: 159: 155: 151: 147: 143: 141: 138: 123: 91: 85: 70: 61: 50:Please help 42: 1964:Suffix tree 1429:replacement 1392:replacement 135:Description 112:computation 56:introducing 2055:Categories 1602:References 1576:"000|||||" 98:that uses 1579:"00|||||" 1573:"00|0|||" 1553:Execution 1490:Execution 1421:the first 1401:string: 1397:Given an 1378:Algorithm 1191:∗ 1160:∗ 1126:∗ 1092:∗ 1056:∗ 1023:∗ 987:∗ 949:∗ 821:→ 658:⋅ 655:→ 482:⋅ 479:→ 457:→ 437:→ 414:→ 408:∗ 399:∗ 391:→ 380:∗ 371:→ 351:→ 323:→ 273:∗ 242:⋅ 239:→ 173:→ 1590:See also 1582:"0|||||" 1570:"00||0|" 1407:patterns 848:′ 685:′ 631:′ 606:′ 581:′ 536:′ 188:, where 144:alphabet 64:May 2020 2030:Sorting 2000:Parsing 1720:Strings 1585:"|||||" 1567:"00||1" 1445:Example 1413:string. 1388:pattern 724:(where 104:strings 100:grammar 52:improve 1617:1960. 1564:"0|01" 1549:"101" 1345:. 156:simple 148:scheme 1993:Other 1949:DAFSA 1916:BLAST 1561:"101" 1529:Rules 1453:Rules 1425:input 1411:input 1399:input 1384:Rules 1372:Refal 160:final 127:is a 125:Refal 94:is a 37:, or 1984:Trie 1974:Rope 1382:The 1288:and 744:and 208:and 90:, a 1647:doi 1643:219 158:or 86:In 2057:: 1641:. 1637:. 1390:→ 1374:. 1260:, 1234:, 1203:, 1172:, 1138:, 1104:, 1073:, 1040:, 1004:, 294:: 257:. 41:, 33:, 1712:e 1705:t 1698:v 1655:. 1649:: 1475:. 1431:. 1332:| 1327:| 1305:| 1300:| 1296:c 1275:| 1271:c 1268:a 1248:c 1245:a 1242:a 1222:c 1218:| 1214:a 1211:a 1187:| 1183:a 1180:a 1156:| 1152:a 1149:a 1146:b 1122:| 1118:a 1115:b 1112:a 1089:b 1085:| 1081:a 1060:| 1052:| 1048:a 1027:| 1019:| 1015:a 1012:b 991:| 984:b 980:| 958:| 953:| 945:| 921:S 918:D 915:R 895:R 875:S 872:L 869:R 845:V 824:D 818:L 798:S 795:D 792:R 772:R 752:S 732:R 712:S 709:L 706:R 682:V 661:D 652:L 628:V 603:V 578:V 557:V 533:V 512:V 474:c 466:| 462:c 452:c 449:a 442:c 432:c 428:| 419:c 396:b 385:| 366:b 359:a 356:b 346:b 343:a 335:| 331:a 328:b 318:b 314:| 306:{ 282:c 279:b 276:a 269:| 245:D 236:L 216:D 196:L 176:D 170:L 77:) 71:( 66:) 62:( 48:.

Index

list of references
related reading
external links
inline citations
improve
introducing
Learn how and when to remove this message
theoretical computer science
string rewriting system
grammar
strings
Turing-complete
computation
mathematical expression
Andrey Markov, Jr.
Refal
programming language
Turing machine
Turing machine
Church-Turing thesis
constructive mathematics
Refal
Formal grammar
Andrey Andreevich Markov (1903-1979)
"Markov's constructive analysis; a participant's view"
doi
10.1016/S0304-3975(98)00291-6
Yad Studio - Markov algorithms IDE and interpreter (Open Source)
Markov algorithm interpreter
Markov algorithm interpreter

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

↑