译自 Markov Algorithm。除非特殊声明，下文中「我」指原文作者 Oleg Kiselyov。
如果问一个人知道什么计算模型，得到的常见答案可能是「图灵机」和「λ-演算」。也许有的人会说「寄存器机」，但应该不会有人说「Post 系统（Post System）」1或「Markov 算法（Markov Algorithm）」 。这洵为一件憾事，因为逻辑学和理论计算机科学中常见的推理规则就是 Post 系统的一种表现形式，模板引擎、EBNF 规则、XSLT 或宏也是如此。仔细研究这些系统及其令人惊讶的表现力或许会令人有所启发，毕竟，Chomsky 就受到了 Post 系统启发，他的上下文无关生成文法以及其他一些生成文法都受到了 Post 系统的影响。除了作为计算模型的理论意义外，Markov 算法的思想也启发了一种真正的编程语言：Refal。在模式匹配被推广到普通的编程语言之前，Refal 就已经基于模式匹配。「窥孔优化（peephole optimizer）」也是一种 Markov 算法。
Post 系统（试想生成文法）基于重复的，甚至可能是上下文相关的字符串替换，即用新的字符串替换一个原有字符串的子串。替换规则由一组有限的规则序列（文法生成规则）组成，可以用任意顺序应用替换规则。而「正规 Markov 算法（Normal Markov Algorithm）」，顾名思义，是这种基于规则的替换系统的一种受限的「正规」形式。在正规 Markov 算法中，替换是上下文无关的，同时按照严格定义的顺序进行。因此整个字符串替换过程具有确定性，可以通过一种简单的机制（即「机器」）完成。正规 Markov 算法才能称之为「算法」2（这其实是一个俄语中的文字游戏，「算法」在俄语中是「алгоритм」，而 Markov 称他的系统为「алгорифм」）。
由上可知，正规 Markov 算法是一种机器，根据一串重写规则序列，通过按顺序反复应用规则重写输入字符串。规则由源 src 和替换目标 rplc 一对字符串组成，两者都可为空字符串。有的规则被标记为「终止规则」。机器的工作循环是：按重写规则序列的顺序，依次尝试用每条规则的 src 匹配输入字符。如果有匹配的，那么就用对应的 rplc 替换输入字符串中最左侧匹配到的 src 。匹配结束后，如果这条规则是一条终止规则，那么就停机。否则把改写后的字符串作为新的输入，然后重新开始循环。当没有可用的规则时也停机。
举个例子，下面是一个 OCaml 数组形式编写的规则序列。它可以把一个大端序二进制数字（由 0 和 1 组成的字符串）转换为由 | 组成的一进制数字字符串。
let bin_to_unary = [|
rule "1" "0|";
rule "|0" "0||";
rule "0" "";
|]
使用本文随附的代码运行 run bin_to_unary "110" 可以生成有六条杠的字符串 "||||||"。该代码还打印了重写过程中触发的所有规则以及对应生成的中间结果，以展示这一巧妙算法的工作原理。
具有好奇心的读者可能会想研究下面的规则是如何构造的：
let gcd = [|
rule "aA" "Aa";
rule "a#a" "A#";
rule "a#" "#B";
rule "B" "a";
rule "A" "C";
rule "C" "a";
rule "#" "";
|]
该规则把有 i 个字母 a 后面跟 # 以及 j 个字母 a 组成的字符串（形如 aaaaaaaa#aaaa），转换成 k 个字母 a 组成的字符串（如 aaaa），k 为 i 和 j 的最大公约数。
Markov 证明了，有限重写规则序列执行的所有已知类别的字符串变换都可以用正规 Markov 算法表示（即「可正规化」性质），他据此提出所有的算法都可正规化。他提出的论据比丘奇或图灵对他们的「丘奇-图灵论题（Church-Turing thesis）」提出的论据都要充分。下面节选自 V.M. Glushkov 的著作中对这些论据的描述（引自英译本）：
The validity of this [Markov normalization] principle is based first of all on the fact that all the algorithms known at the present time are normalizable. Since in the course of the long history of the development of the exact sciences a considerable number of different algorithms have been devised, this statement is convincing in itself.
译文：「Markov 正规性」的合法性首先基于以下事实：「目前所知的所有算法都是 Markov 可正规化的。」在精密科学发展的漫长历史进程中，人们发现了大量的不同的算法，它们都具有这种性质。因此「Markov 正规性」这一性质本身就十分具有说服力。
In actuality it is even more convincing. We can show that all the methods known at the present time for the composition of algorithms which make it possible to construct new algorithms from the already known ones do not go beyond the limits of the class of normalizable algorithms. …
译文：而更具说服力的一点是，我们可以证明：通过目前已知的所有算法任意组合构成的新算法，都不会超越「可正规化 Markov 算法」的范畴。 ……
However this is not all. A whole series of scientists have undertaken special attempts to construct algorithms of a more general form and all these attempts have not been carried beyond the limits of the class of normalizable algorithms.
译文：除了上述论证之外。有一系列科学家试图通过一些特殊的方法构建更一般形式的算法，但这些尝试也没有超越可正规化 Markov 算法的范畴。
我想澄清一个关于 A.A. Markov 提出其算法理论的具体时间的误解。我看到的所有英文资料都声称 Markov 算法是在 20 世纪 60 年代提出的，这一论据的来源很可能是 Markov 的作品的一个非常简短的英译本的出版日期。然而，该理论的俄文版发表的时间要更早一些。据下面列出的关于 A.A. Markov 的参考书目，第一篇论文《Theory of Algorithm》于 1951 年发表在 Steklov 的数学研究院的期刊上。三年后，即 1954 年，他出版了一本长达 376 页的同名著作。而早在 1947 年，他就开始从事字符串算法领域的工作，并发表了一个著名的研究成果：半群中字问题的不可判定性。3
引用文献
完整代码，仅使用 OCaml 标准库
该代码实现了所谓「Markov 机」。另外包含了多个示例，包括转换二进制到一进制、一进制的加减法，还模拟了图灵机执行一进制加减法的方式。
A.A. Markov 出版物总目录
Андрей Андреевич Марков (1903-1979)
该综合性网站还展示了一张少见的 Markov 家庭照片（上有 A.A. Markov 的父亲，Markov 链的发明人）以及 A.A. Markov 创作的诗歌。
Andrey Andreevich Markov 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.
В.М.Глушков. Введение в Кибернетику
Издательство Академии Наук Украинской ССР. Киев, 1964. 324 стр.
该著作有英译本
V.M.Glushkov. Introduction to Cybernetics
U.S. Air Force Systems Command. Wright-Patterson Air Force Base. Ohio. Translation division. Foreign technology division. FTD-TT-65-942/1+2. AFLC-WPAFB-Mar 66 72. Feb 17, 1966.
- V.F.Turchin. The Concept of a Supercompiler
ACM Transactions on Programming Languages and Systems, 1986, v8, 292–325. doi:10.1145/5956.5957
该论文的第 4 节可能是对 Refal 最好的英文介绍，展示了许多例子并与 Lisp 和 Prolog 比较。Turchin 强调 Refal 是一种纯函数式语言。