マルコフアルゴリズム

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