find + mkdir はチューリング完全

英語版 (English version)

更新履歴

• 2024-08-02 初版に存在した証明のミスを修正しました。初版では Rule 110 を実装することでチューリング完全性を示したと主張していましたが、状態の幅が固定になってしまっているという問題がありました。現在のバージョンでは、Rule 110 でなく Tag system を実装し、問題を解消できていると思います

概要

GNU の find と mkdir コマンドのみを使えるシステムはチューリング完全であることを示します。

sed や awk コマンドが単体でチューリング完全であることはよく知られていますが、find + mkdir がチューリング完全になるという言及は探した限りでは見つからなかったので、ここに報告します。

証明は、タグシステム を実装することによって行います。

完成形のコードは下の方にありますが、順を追って、ループの構成、FizzBuzz の構成、タグシステムの実装を見ていきます。

リファレンス

実装

ループの構成

以下のコードは再帰的にディレクトリを作り続け無限ループします。

mkdir x
find x -execdir mkdir x/x \;

find x は x を含みそれ以下のファイルをリストアップしますが、　x のリスト時に x/x が作られるため、find は x/x を次にリストします。その際に x/x/x が作られ、以下同様です。このループは指定した定数で止めることができ、以下のコードは、x/x/x/x/x を作って停止します。3 の代わりに $N$ を指定した場合 $N+2$ 個の x がある状態で停止します。

mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;

FizzBuzz の構成

find は -regex オプションにより、それに対して後続のアクションを実行するファイル名をフィルタすることができます。これを使って x/ の 3,5,15の倍数回の繰り返しをフィルタすることができ、これをループと組み合わせることで FizzBuzz を実装できます。
以下では読みやすさのために -regextype posix-extended を使っていますが、どの正規表現文法でも同じことができるはずです。

mkdir -p d/x
find d/x -regextype posix-extended -regex 'd(/x){0,29}' -execdir mkdir x/x \;
find d -regextype posix-extended \
-regex 'd((/x){15})+' -printf "FizzBuzz\n" -o \
-regex 'd((/x){5})+' -printf "Buzz\n" -o \
-regex 'd((/x){3})+' -printf "Fizz\n" -o \
-regex 'd(/x)+' -printf "%d\n"

実行結果

2行目までで、d 以下に x/.../x (x が30個) を作り、3行目でそれをたどりながら、x の個数が 15 の倍数ならば FizzBuzz, それ以外で 5 の倍数ならば Buzz, 3 の倍数ならば Fizz, それ以外ならばそのファイルの d からの深さ、すなわち x の個数を出力しています。

タグシステムの実装

タグシステムは三つ組 $(m, A, P)$ で表され、それぞれ

• $m$ - 正の整数
• $A$ - 停止記号Hを含む有限アルファベット
• $P$ - アルファベットに対する生成規則

を意味します。初期文字列に対して

1. 文字数が$m$未満、または先頭の文字$x$がHなら停止する。そうでなければ $P(x)$ を末尾に追加する
2. 先頭 $m$ 文字を消す

を繰り返し、停止した時点での文字列を出力します。

特に $m=2, |A|=576$ のタグシステムであって万能チューリングマシンであるようなものの存在が知られている (De Mol, L., 2008) ため、この大きさのあるタグシステムを模倣できるようなシステムはチューリング完全です。

ここでは、Wikipedia にある $m=2, |A|=4$ のタグシステムの例 を用い、その実装を示します。

実装の方針は、ある状態を表すファイルパスに対して、_ をセパレータとして次の状態を結合することを繰り返すというものです。例えば、_/b/a/a/_ に対して、次の状態 a/c/c/a が結合された _/b/a/a/_/a/c/c/a/_ というファイルパスを作り、次にそれに a/c/c/a の次状態を結合するということを終了条件が満たされるまで繰り返します。あるディレクトリの中にファイルが2つ以上作られることはありません。

# Demonstrate 2-tag system can be implemented with `find` and `mkdir` only,
# using an example from Wikipedia.
# en.wikipedia.org/wiki/Tag_system#Example:_A_simple_2-tag_illustration

# _'s are used as a separator between states.
mkdir _

# Production rules for an M-tag system given as constants.
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"

# Initial state (surrounded by _'s).
mkdir -p _/b/a/a/_

# Alphabets (constant size)
S="(/[abcH])"

# Keep appending the next state to the end of the state until seeing the halting symbol. e.g.
# _/b/a/a/_ -> _/b/a/a/_/a/c/c/a/_ -> _/b/a/a/_/a/c/c/a/_/c/a/c/c/b/a/H/_ -> ... -> .../_/H/c/c/c/c/c/c/a/_ (halt)
#
# Line 2:    Halting condition
# Line 3-6:  Copy the previous state removing M characters from the start, utilizing back-references.
# Line 7-29: Apply the production rule for a, b, c.
find _ -regextype posix-extended -empty \( \
    -regex ".*_/H.*_|.*_(/[^/]?){,$M}_" -prune -o \
    -regex ".*_$S{$M}($S*)/a$S*/_\2" \( -execdir mkdir a/a b/a c/a H/a _/a \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/b$S*/_\2" \( -execdir mkdir a/b b/b c/b H/b _/b \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/c$S*/_\2" \( -execdir mkdir a/c b/c c/c H/c _/c \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/H$S*/_\2" \( -execdir mkdir a/H b/H c/H H/H _/H \; -o -true \) -o \
    \( \
        -regex ".*_/a$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_A/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_A/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_A/_ \; -o \
            -execdir find H \; -execdir mkdir -p H/$PROD_A/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_A/_ \; \
        \) -o \
        -regex ".*_/b$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_B/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_B/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_B/_ \; -o \
            -execdir find H \; -execdir mkdir -p H/$PROD_B/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_B/_ \; \
        \) -o \
        -regex ".*_/c$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_C/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_C/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_C/_ \; -o \
            -execdir find H \; -execdir mkdir -p H/$PROD_C/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_C/_ \; \
        \) \
    \) \
\) &> /dev/null

# Output the result. (_/H/c/c/c/c/c/c/a/_)
find _ -depth ! -empty -name _ -execdir find _ -empty \; -quit

実行結果

確かに期待される結果である _/H/c/c/c/c/c/c/a/_ が出力されていることがわかります。FizzBuzz までの例では通常の正規表現が使われていましたが、ここでは後方参照 (\2) が使われていることがポイントで、これによって先頭 $M$ 文字を除いた文字列のコピーが可能になっていると思います。

この構成はあきらかにより大きなアルファベットサイズに拡張可能です。（文字種の不足は、ファイルの文字数を複数にすることで容易に対処できます）
よって、find + mkdir はチューリング完全であることがわかりました。

予想される質問と答え

• ファイルパスの長さ制限のせいで任意の大きさのオートマトンを実行できないということはないか

  • おそらくないと思います。mkdir は一定以上の長さのファイルパスを直接渡された場合失敗しますが、上記のコードは注意深く mkdir に直接任意長さのファイルパスを渡すことを避けています。find については実験した限りではパスの長さが 30000 以上でも動き、上限は見つかりませんでした

• POSIX の仕様で上記のコードが動くことは保証されているか

  • 残念ながらされていません。むしろ以下のように、実行中にディレクトリ内のファイルを変更した場合の動作は未定義であることが明記されています（ソース）。つまり厳密には find + mkdir は普及した実装においてチューリング完全、となります

  If a file is removed from or added to the directory hierarchy being searched it is unspecified whether or not find includes that file in its search.

  • 使用したツールのバージョンを以下に明記します

-> % find --version | head -1 && mkdir --version | head -1 && uname -a
find (GNU findutils) 4.8.0
mkdir (GNU coreutils) 8.32
Linux DESKTOP-5JU1LI7 5.15.153.1-microsoft-standard-WSL2 #1 SMP Fri Mar 29 23:14:13 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux

謝辞

• 初版に存在した証明のミスを指摘 し、修正をレビュー してくださった deredede さんに感謝します
• タグシステムについてコメントされた niederman さんに感謝します