马尔科夫算法

A．A．马尔科夫1936年提出的一种符号演算体系。

一个马尔科夫算法包括以下内容：

1．一个非空的有穷集∑，称为字母表，其元素称为字母。字母的有穷序列(包括空序列)称为∑上的字(空字记作)，由∑上的全体字组成的集合称为字集，记作∑。

2．一个有穷的替换公式序列：

其中每个替换公式都具有

g→h

的形式，g，h都是∑上的字。其作用是将字α中最左边的子字g变为h。

Q中可以有一个替换公式标有一个特殊的记号*，称为终止的替换公式，一旦使用了这个替换公式，计算即告结束。

马尔科夫算法的计算可以从任何一个字α∈∑(输入)开始，逐次使用Q中的替换公式生成新的字。如果对字β有不止一个替换公式可用，使用序号最小的一个。如果做到某一步Q中不再有合适的替换公式可用，或使用了终止的替换公式，计算即告结束。最后生成的字称为输出。

对于任何一个马尔科夫算法，其输出与输入之间的关系是一个部分字函数。

马尔科夫算法可以用来计算自然数函数，具体方法是：

以连续x个1所组成的字表示自然数x(空字表示0)，用b表示逗号，则字母表∑=｛1，b｝上的字都表示自然数组。例如

　　11b1 表示二元数组(2，1)

　　1bb11 表示三元数组(1，0，2)

　　111 表示自然数(一元数组)3等等。

设f(x，……x)是n元数函数，如果有在字母表∑(∑∑)上的马尔科夫算法，使当输入为字。

时，有输出当有仅当f(x1，，…x)有定义且f(x，，…x)=y，则称f为马尔科夫算法可计算函数，为计算f的(一个)马尔科夫算法。

∑∑意味着用马尔科夫算法计算一个函数时可能要用到1、b以外的字母，但这种字母只在中间过程中出现。

例如马尔科夫算法：∑=∑=｛1，b｝，Q=｛q｝，其中q是替换公式

b→，

则是计算二元函数x+y的马尔科夫算法。

再如，马尔科夫算法，∑=｛1，b，α｝，Q=｛q，q，…q｝，其中

q： 111→1

q： b→1

q： a→A　　　　(终止的替换公式)

q： 11→ba

q： 1→a

q： →11

是计算函数

的马尔科夫算法。

马尔科夫对他所提出的算法(包括许多判定问题)作了相当详尽的讨论。结果都收在他所著的《算法论》(1954)一书中(中译本：胡世华、唐稚松、何成武译，科学出版社，1959)。但马尔科夫并未讨论他的算法理论与其他理论之间的关系。1958年杰特洛夫斯基证明：

f是马尔科夫算法可计算的当且仅当f是部分递归的。