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

概要

• GNU の find と mkdir コマンドだけでシステムがチューリング完全であることを証明しようとする試み
• sed や awk コマンドはチューリング完全であることがよく知られているが、find と mkdir のチューリング完全性に関する参考資料は見当たらない
• 証明には、Rule 110 を実行できることを示す一般的な手法を用いる
• ループ、FizzBuzz、Rule 110 の実装の順で説明

実装

ループの構成

• 次のコードはディレクトリを再帰的に生成し、無限ループを作る

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

• find x は x 配下のファイルを列挙し、x が列挙されると x/x を生成する
• ディレクトリ生成の深さを制限するには -maxdepth オプションを使う

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

FizzBuzz

• find の -regex オプションを使ってファイル名をフィルタリングし、ループと組み合わせて FizzBuzz を実装する

  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"
  

Rule 110 の実装

• ループと条件分岐が使えるようになれば、任意のプログラムを記述できる
• それを証明するために Rule 110 を実装する

  WIDTH=16
  ITER=15
  mkdir -p p/0/0/0/0/0/0/0/0/0/0/0/0/0/0/0/1
  O='(/?1)'
  Z='(/?[0p])'
  X='(/?[01p])'
  W0="($X{$WIDTH})"
  W1="($X$W0)"
  W2="($X$W1)"
  ZERO="($Z$Z$Z|$O$Z$Z|$O$O$O)"
  ONE="($O$O$Z|$O$Z$O|$Z$O$O|$Z$O$Z|$Z$Z$O)"
  find p -regextype posix-extended \
  -regex "$W1$W2{$ITER}" -fprint /dev/null \
  -o -regex "$W1$W2{0,$ITER}" \( -execdir mkdir 0/p 1/p \; -o -execdir mkdir 0/p/p 1/p/p \; \) \
  -o -regex "$W2*" -fprint /dev/null \
  -o -regex "$X*$ZERO$W0" -execdir mkdir 0/0 1/0 p/0 \; \
  -o -regex "$X*$ONE$W0" -execdir mkdir 0/1 1/1 p/1 \; \
  2> /dev/null
  find p -regextype posix-extended \
  -regex "p$W2{0,$ITER}" -execdir find p -mindepth $WIDTH -maxdepth $WIDTH \;
  

想定される質問と回答

• ファイルパス長の制限により、任意サイズのオートマトンは実行できないのか？

  • mkdir は一定以上の長さのファイルパスを渡すと失敗するが、上のコードはこれを回避している
  • find は 30000 を超えるパスでも動作する

• 上のコードは POSIX 仕様に従って動作が保証されるのか？

  • そうではなく、ディレクトリ探索中にファイルが追加された場合の動作は未規定である
  • 使用したツールのバージョン:

    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
    

GN⁺ のまとめ

• find と mkdir コマンドだけでチューリング完全性を証明しようとする試みは興味深い
• Rule 110 の実装によってそれを証明しようとするアプローチは創造的である
• POSIX 仕様に基づく動作保証はないが、GNU ツールでは正常に動作する
• 類似の機能を持つプロジェクトとして sed や awk がある