`find` と `mkdir` のチューリング完全性

 (ogiekako.vercel.app)
1 ポイント 投稿者 GN⁺ 2024-08-01 | 1件のコメント | WhatsAppで共有
  • GNU の find と mkdir だけでも、ディレクトリの生成と走査順序を利用してループと状態遷移を作れるため、単純なファイルユーティリティの組み合わせが計算モデルになる
  • 証明は タグシステム(tag system) の実装によって行われ、初版の Rule 110 ベースの証明は無限反復の処理問題のため修正された
  • 基本ループは find x -execdir mkdir x/x \; が新しいディレクトリを次々に発見する構造で、-regex を加えると FizzBuzz のような条件分岐も可能になる
  • タグシステムの実装では状態をファイルパスで表現し、後方参照(back-reference) で先頭の m 文字を除いた残りをコピーする
  • POSIX は検索中のディレクトリにファイルが追加された場合の動作を unspecified としているため、結論は GNU ツールで観察された動作と提示された環境に依存する

GNU find と mkdir で計算モデルを構成

  • 目標は、GNU の find と mkdir コマンドだけがあるシステムがチューリング完全であることを示すこと
  • 証明は タグシステム を実装する方法で進められる
  • 全体の流れは、ループ構成、FizzBuzz、タグシステム実装の順に続く
  • 2024年8月2日に初版の Rule 110 ベースの証明の誤りが修正され、現行版は タグシステム の実装に置き換えられた
    • 初版には無限の反復回数を処理できない問題があった
  • 関連論文 Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation は FUN with Algorithms 2026 に採択された

ディレクトリ生成が作るループ

  • 次のコードは再帰的にディレクトリを作成し、無限ループ に入る
mkdir x
find x -execdir mkdir x/x \;
  • find x は x 配下のファイルを列挙し、x 自体も含む
  • x が列挙されると mkdir が x/x を作成し、次の find の反復では新しく作られた x/x が含まれる
  • この過程が繰り返されることで、x/x/x、x/x/x/x のようなパスが次々に作られる
  • -maxdepth オプションを使えば生成の深さを制限できる
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
  • この例は x/x/x/x/x を作成したあと終了する

find -regex で実装した 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 が 30 個連なったパスを生成する
  • 3 行目は、x の個数が 15 の倍数なら FizzBuzz、5 の倍数なら Buzz、3 の倍数なら Fizz、それ以外では d からの深さを出力する
  • 実行結果は OneCompiler の例 で確認できる

タグシステムでチューリング完全性を示す

  • タグシステムは (m, A, P) で構成される
    • m は正の整数
    • A は停止記号 H を含む有限アルファベット
    • P は各アルファベットに対する生成規則
  • 初期文字列が与えられると、システムは次の過程を繰り返す
    • 文字列長が m より短いか、先頭文字が H なら停止する
    • そうでなければ先頭文字 x に対する P(x) を文字列の末尾に追加する
    • 先頭の m 文字を削除する
  • m=2、|A|=576 のタグシステムが万能チューリングマシンであることが知られており、このサイズのタグシステムを実行できるシステムは チューリング完全 である
  • 実際の実装例では、Wikipedia にある m=2、|A|=4 の単純な 2-tag system を使う

ファイルパスを状態として使う方法

  • 核心となるアイデアは、状態を表すファイルパスの後ろに次の状態を継続的に追加していくこと
  • 状態間の区切りとして _ を使う
    • 例: _/b/a/a/_
    • 次の状態が a/c/c/a なら、パスは _/b/a/a/_/a/c/c/a/_ になる
  • 実行中は 1 つのディレクトリ内に 2 個以上のファイルが入らないように構成されている
  • 実装は、停止記号に到達するか文字列長が m 以下になるまで次の状態を追加し続ける
  • find の条件式は大きく 3 つの部分で動作する
    • 停止条件 の検査
    • 後方参照を使って、前の状態から先頭の M 個の文字を除いた残りをコピーする
    • a、b、c に対する生成規則の適用
  • 例の生成規則は次のとおり
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
  • 実行結果として期待される _/H/c/c/c/c/c/c/a/_ が出力される
  • この実行結果も OneCompiler の例 で提供されている

後方参照と拡張可能性

  • FizzBuzz の実装は通常の正規表現を使うが、タグシステムの実装では 後方参照 \2 を使う
  • 後方参照により、前の状態から最初の m 文字を除いた部分をコピーできる
  • この構成は、より大きな定数サイズのアルファベットにも拡張できる
  • 使用できる文字が足りなければ、各ファイル名に 1 文字より長い文字列を使う方法で対応できる
  • したがって、find + mkdir の組み合わせはチューリング完全であるという結論に至る

POSIX の制約と実行環境

  • ファイルパス長の制限により任意サイズのオートマトンを実行できない可能性はあるが、提示されたコードは任意長のファイルパスを mkdir に直接渡さないよう構成されている
  • テストでは find は 30000 文字を超えるパスでも動作し、特別な制限は見つからなかった
  • POSIX 仕様上の保証はない
    • POSIX find 文書 には、検索中のディレクトリにファイルが追加された場合の動作は unspecified であると明記されている
    • GNU 以外のツールの動作は確認していない
  • 使用された環境は次のとおり
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

関連記事

1件のコメント

 
GN⁺ 2024-08-01
Hacker News のコメント

  • ページの一番上にはすでにこう書かれている: find + mkdir のチューリング完全性という主張は撤回された
    証明に欠陥があるため、find + mkdir がチューリング完全であることを証明したという主張を撤回するとされており、https://news.ycombinator.com/item?id=41117141 を参照するよう案内されている
    証明を修正できれば記事を更新するとのこと

    • すでに修正済み

  • これで Folders を実装できるのか？
    https://www.danieltemkin.com/Esolangs/Folders/

    • Windows でフォルダがディスク容量をまったく使わないという説明は、厳密には違う
      ディレクトリエントリは MFT 内で容量を占めるが、Explorer は別の場所に割り当てられたブロックだけを数えるため表示されないだけ
      空のディレクトリを作り続けると MFT が大きくなり、最終的には容量の問題が起きる
      小さなファイルも同様で、空のテキストファイルはサイズ 0 バイト・ディスク上のサイズ 0 バイトと表示され、約 400 バイトを入れてもデータは事前に割り当てられた MFT のディレクトリエントリ内に収まり、Explorer ではディスク上のサイズ 0 と表示される
      データを倍に増やすとディスクブロックが割り当てられ、長さ 800 バイト、ディスク上のサイズ 4,096 バイトと表示され、再び 400 バイトに減らしてもデータは MFT に戻らず、4,096 バイトを占有し続ける
      それでも全体として素晴らしい成果物を楽しむ妨げにはならない

  • これがどう チューリング完全性を示しているのか理解できない
    ルール 110 オートマトンの実装は、幅の制限にも反復回数の制限にも引っかかっているように見える
    与えられた幅での状態数は有限なのでチューリング完全ではなく、常に停止するのでやはりチューリング完全ではない
    任意の、つまり無限に拡張可能な幅と深さを持つ ルール 110 の実装を書けるのか？

    • 制限が概念ではなく実装だけにあるなら問題ない
      実際のコンピュータも無限テープではなく有限メモリを使うので、言語や手法に関係なくその条件は満たせない
    • C も厳密にはチューリング完全ではないかもしれない: https://cs.stackexchange.com/questions/60965/is-c-actually-t...
    • 記事の著者はその後記事を更新した: 証明に欠陥があるため、find + mkdir がチューリング完全であることを証明したという主張を撤回すると述べ、https://news.ycombinator.com/item?id=41117141 を参照するよう案内している
      証明を修正できれば記事を更新するとのこと

  • 撤回済み
    「証明に欠陥があるため、find + mkdir がチューリング完全であることを証明したという主張を撤回する」と書かれている

  • 興味深い形の ラムダ計算を使うのかと思ったが、実際には計算のために find の正規表現パーサに依存しているだけだった

    • 正規表現を無理やり使ってかなり複雑な計算をさせた例は、これが初めてではない
      記憶に残っている例として http://realgl.blogspot.com/2013/08/battlecode.html があり、「Regular Expression Pathfinding」の部分を見るとよい

  • この証明は セル・オートマトンの代わりにタグシステム（https://en.m.wikipedia.org/wiki/Tag_system）を使えば、ずっと単純になりそう

  • どんな実装も無限にはなれないが、この場合、一般的な値が 4096 の PATH_MAX は特に低く見える

    • 「Expected questions and answers」セクションを見るとよい
      GNU では 4096 より長いパス長でも動作するようだ
    • 記事では 相対パスを使ってこの問題に対処している
      どうやらパス長 30k までテストしたとのこと

  • 正規表現（RE、RegExp）を実装または消費するソフトウェア／サービス、あるいはソフトウェア／サービスのチェーン内の構成要素は、潜在的に チューリング完全になり得る
    その文脈でセキュリティが重要なら、チューリング完全性の有無を監査すべき

    • 厳密に言えば、本来の意味での正規表現にはスタックのない 有限状態機械だけで十分
      チューリング完全性を得るにはスタックが 2 つ必要
      ただし多くの正規表現ライブラリは、単純な「正規表現」よりはるかに多くの機能をサポートしている

  • 私の find は証明可能なほどチューリング完全であるだけでなく、Turing Tarpit でもなく、ネイティブコードにコンパイルされる