マルコフアルゴリズム（英: Markov algorithm）とは、記号の文字列に対して一種の文法的規則を適用していく文字列書き換え系である。マルコフアルゴリズムはチューリング完全であることがわかっており、計算の汎用モデルとして使え、任意の数式を単純な記法で表現できる。Refal はマルコフアルゴリズムに基づいたプログラミング言語である。考案者のアンドレイ・マルコフは、マルコフ連鎖のアンドレイ・マルコフの同名の息子である。以下の例は、マルコフアルゴリズムの基本操作を示したものである。"I bought a B of As from T S."このアルゴリズムが上記の例に適用された場合、記号文字列は次のように変化する。そうして、このアルゴリズムは停止する。次の例はやや興味深い例である。この規則群を適用すると、ある非負整数を2進法で書いたものが、その数の縦棒に置換される。例えば、101 は 5 本の縦棒に書き換えられる（ICの74138といったデコーダ・デマルチプレクサのような働きと言える）。"101"このアルゴリズムが上記の例に適用された場合、次のように変化して停止する。

出典:wikipedia