マルコフアルゴリズム

マルコフアルゴリズム（英: Markov algorithm）とは、記号の文字列に対して一種の文法的規則を適用していく文字列書き換え系である。マルコフアルゴリズムはチューリング完全であることがわかっており、計算の汎用モデルとして使え、任意の計算を単純な記法で表現できる。

アンドレイ・マルコフ・ジュニアが1951年にロシア語で発表し、1960年に英語に翻訳した。発表当初の呼び名は normal algorithm (Нормальный алгоритм) であった。考案者のアンドレイ・マルコフ・ジュニアは、マルコフ連鎖のアンドレイ・マルコフの息子である。

マルコフアルゴリズムに基づいた関数型プログラミング言語としてRefalがある。

アルゴリズム

変換規則は以下の表記を行う。パターンや置換文字列は空文字列でも良い。

• 停止規則で無い場合：パターン → 置換文字列
• 停止規則の場合：パターン → .置換文字列 （先頭に.を付けるがこれは目印であり、置換文字列には含めない）

以下のアルゴリズムで文字列を置換する。

1. 変換規則を上から順にチェックし、矢印の左辺のパターンが文字列に含まれているか調べる。
2. 見つからない場合は、アルゴリズムの実行を停止する。
3. 見つかった場合は、
   1. 文字列の中でも最も左端に近い部分にマッチしたパターンに変換規則を1回だけ適用し、矢印の右辺の置換文字列に置換する。
   2. 適用した規則が.で始まる停止規則（terminating rule）であった場合、アルゴリズムの実行を停止する。
4. ステップ1に戻って繰り返す。

例

以下の例は、マルコフアルゴリズムの基本操作を示したものである。

規則

1. A → apple
2. B → bag
3. S → shop
4. T → the
5. the shop → my brother
6. a never used → .terminating rule （このルールは有っても無くても挙動は同じ）

文字列

I bought a B of As from T S.

実行

このアルゴリズムが上記の例に適用された場合、記号文字列は次のように変化する。

1. I bought a B of apples from T S.
2. I bought a bag of apples from T S.
3. I bought a bag of apples from T shop.
4. I bought a bag of apples from the shop.
5. I bought a bag of apples from my brother.

そうして、このアルゴリズムは停止する。

別の例

次の例はやや興味深い例である。この規則群を適用すると、ある非負整数を2進法で書いたものが、その数の縦棒に置換される。例えば、101 は 5 本の縦棒に書き換えられる（ICの74138といったデコーダ・デマルチプレクサのような働きと言える）。

規則

1. |0 -> 0||
2. 1 -> 0|
3. 0 -> ""（空文字列）

文字列

101

実行

このアルゴリズムが上記の例に適用された場合、次のように変化して停止する。

1. 0|01
2. 00||1
3. 00||0|
4. 00|0|||
5. 000|||||
6. 00|||||
7. 0|||||
8. |||||

Python での実装

def markov(rules, s: str) -> str:
    print(s)
    while True:
        for pattern, replacement, terminate in rules:
            if pattern in s:
                s = s.replace(pattern, replacement, 1)  # 先頭を1つだけ置換
                print(s)
                if terminate:
                    return s  # 停止規則
                else:
                    break  # マッチしたら for ループを break して rules の先頭から確認
        else:
            return s  # 1つもマッチしなかった場合は終了

markov((
    # (pattern, replacement, terminate)
    ("|0", "0||", False),
    ("1", "0|", False),
    ("0", "", False),
), "101")

チューリングマシンをマルコフアルゴリズムで実装する方法

チューリングマシンをマルコフアルゴリズムで実装する方法の1つとしては、下記が成立し続けるようにチューリングマシンの状態遷移規則をマルコフアルゴリズムの変換規則に変換すれば良い。もし、チューリングマシンのテープも状態も二進法で表記するならば、例えば、テープに0,1を使い、状態にa,bを使うなど、使う文字を被らないようにすると良い。そうすると、テープ左側・状態・テープ右側がマルコフアルゴリズムで区別できる。

マルコフアルゴリズムの文字列 = （チューリングマシンのテープの読み書き位置を含めた左側）（チューリングマシンの状態）（チューリングマシンのテープの読み書き位置を除いた右側）

スタックマシンの実装

このテクニックを応用して、オペランドスタックを使用したスタックマシンを作ることが出来る。マルコフアルゴリズムの文字列を "オペランドスタック|オペコード" とする。オペコードは数値はスタックに積む命令、+はスタックから2つ取り出して計算結果をスタックに積む命令と解釈する。例えば、逆ポーランド記法で書かれたオペコード、12+3+ を実行するとする。

変換規則としては、下記のものを用意すれば、|12+3+ は 6| となりスタックに6が積まれている。

1. |1 → 1| （スタックに積む命令）
2. |2 → 2|
3. |3 → 3|
4. 12|+ → 3| （足し算命令）
5. 33|+ → 6|

この枠組みでジャンプ命令を扱いたい場合は "オペランドスタック|プログラムカウンタ" という形式にしてしまえば良い。プログラムカウンタは何番目のオペコードを実行中かという数値。

参考文献

• Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191-206.
• Andrey Andreevich Markov (1903-1979) 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

外部リンク

• Markov algorithm interpreter