马尔可夫算法

在理论计算机科学中，马尔可夫算法是一种字符串重写系统，它使用类似语法的规则对符号字符串进行操作。 马尔可夫算法已被证明是图灵完备的，这意味着它们适合作为通用计算模型，可以用简单的符号表示任何数学表达式。 马尔可夫算法以苏联数学家小安德烈·马尔可夫的名字命名。

Refal 是一种基于马尔可夫算法的编程语言。

普通算法是口头的，也就是说，旨在应用于不同字母表的字符串。

任何普通算法的定义都由两部分组成：算法字母的定义（算法将应用于这些字母符号的字符串），以及其方案的定义。 普通算法的方案是一组有限有序的所谓替代公式，每个替代公式都可以是简单的或最终的。 简单替换公式由 L → D {displaystyle Lto D} 形式的字符串表示，其中 L {displaystyle L} 和 D {displaystyle D} 是算法字母表中的两个任意字符串 （分别称为公式的左右两边代入）。 类似地，最终替换公式由 L → ⋅ D {displaystyle Lto cdot D} 形式的字符串表示，其中 L {displaystyle L} 和 D {displaystyle D} 是两个任意字符串 在算法的字母表中。 这假设辅助字符 → {displaystyle to } 和 → ⋅ {displaystyle to cdot } 不属于算法的字母表（否则另外两个字符执行它们作为分隔符的角色 应选择不在算法字母表中的左侧和右侧）。

将普通算法应用于该算法字母表中的任意字符串 V {displaystyle V} 的过程是一个离散的基本步骤序列，包括以下内容。 让我们假设 V ′ {displaystyle V’} 是在算法的前一步中获得的单词（如果当前步骤是xxx步，则为原始单词 V {displaystyle V} ）。 如果替换公式中没有包含在 V ′ {displaystyle V’} 中的左侧，则算法终止，其工作结果被认为是字符串 V ′ { 显示样式 V’} 。 否则，选择左边包含在 V ′ {displaystyle V’} 中的xxx个替换公式。 如果替换公式的形式为 L → ⋅ D {displaystyle Lto cdot D} ，那么在字符串 V ′ {displaystyle V’} 的所有可能表示中，形式为 R L S {displaystyle RLS}（其中 R {displaystyle R} 和 S {displaystyle S} 是任意字符串）选择具有最短 R {displaystyle R} 的字符串。 然后算法终止，其工作结果被认为是 R D S {displaystyle RDS} 。 然而，如果这个替换公式的形式为 L → D {displaystyle Lto D} ，那么在字符串 V ′ {displaystyle V’} 的所有可能表示中，形式为 R L S {displaystyle RLS} 最短的 R {displaystyle R} 被选择，之后字符串 R D S {displaystyle RDS} 被认为是当前步骤的结果，在下一步进一步处理 步。

任何普通算法都等同于某种图灵机，反之亦然——任何图灵机都等同于某种普通算法。 Church-Turing 论文的一个版本是关于正常算法制定的，称为规范化原则。

普通算法已被证明是构建构造性数学的许多部分的便捷手段。 此外，在普通算法的定义中固有的是一些在旨在处理符号信息的编程语言中使用的想法——例如，在 Refal 中。