0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ogiekako(Keigo Oka)

GNU find 4.9.0+ はチューリング完全

0
Last updated at Posted at 2026-01-09

概要

GNU の find コマンド (バージョン 4.9.0 以降) のみを使えるシステムはチューリング完全であることを示します。（2026年1月現在）

sed や awk コマンドが単体でチューリング完全であることはよく知られていますが、find が単体でチューリング完全になるという言及は探した限りでは見つからなかったので、ここに報告します。前回の記事では、find と mkdir のみが使えるシステムはチューリング完全であることを示しました。今回は、特に GNU find 4.9.0 を用いて mkdir がなくてもチューリング完全であることを示します。これは Ubuntu 24.04 などよくあるLinux環境にデフォルトでインストールされているコマンドです。

証明は、レジスタ2つの Minskyのprogram machineを実装することによって行います。

注意

ここで提示されているコードを実行する場合には自己責任でお願いします。非空ディレクトリで実行した場合さまざまなファイルが削除される危険がありますし、その他予期せぬバグによる結果についても責任を負いかねます。

リファレンス

実装

コード記述について

プログラム記述を読みやすくするためにシェル変数を用いますが、これらは実際には定数に展開できるため本質的には不要です。つまり我々の構成はシェル非依存です。

ループの構成

ループの構成自体がトリッキーなので順を追って説明します。

以下のコードは . を2回出力します。

find -fprintf input '.\0.\0' -quit
find -files0-from input -print -prune

1行目の find は -fprintf により input に ".\0.\0" を書き込み、-quit により終了します。2行目の find は -files0-from input により、NUL文字 (\0) 区切りの検索開始ポイント $s_1, s_2, \dots$を input から入力が尽きるまで読み込みます。今回の場合まず $s_1 = $ . であり、-print によってこれが出力されます。次に -prune によって . ディレクトリの走査が打ち切られ、$s_2 = $ . の処理に移り、同様に . のみが出力されます。$s_3$ は存在しないため、プログラムは終了し、結果として . が2回出力されることになります。

これを無限ループにするためのポイントは、$s_i$ が処理されている最中に input の書き換えを行い、$s_{i+1}$ を用意することです。以下のコードは . を表示し続け無限ループします。

find -fprintf input ".\0" -quit
find -files0-from input -print -prune \( \
  -exec find -files0-from input \( -name . -o -name first -delete \) -fprintf tmp ".\0" -false -fprint first \; \
  -exec find -files0-from tmp -prune -fprintf input ".\0" \; \
  -exec find tmp -delete \; \
\)

これが動くのは find や、それが使うライブラリの実装依存になりますが、その議論は補遺にまわすとして、まずは動作原理を説明します。
1行目で input を ".\0" として初期化します。2行目の find （これを外側のfindと呼ぶことにします）は -files0-from input により、input から1つずつ "\0" 区切りの開始点を読んでいきます。重要なこととして、"\0" を読み、. の探索を開始した時点ではまだファイルの終端（EOF）は読まれていません。-print -prune により、. を出力し、また . ディレクトリの中を走査しないことを決定します。続いて3,4,5 行目が実行されます。次の段落で詳しく説明しますが、3行目で tmp ファイルの中身を input ファイルよりも1つ多い ".\0" の繰り返しとし、4行目で tmp ファイルを input ファイルにコピーし、5行目で tmp ファイルを消しています。結果として、input は他の副作用なしで、".\0.\0" となります。すると、2つ目の . が外側の find によって読まれ、以下同様に input の中身が ".\0" の 3 回の繰り返し、4回の繰り返し、……、と増えていく無限ループが完成します。

3行目で起こっていることを説明します（4行目についても同様の説明が成り立ちます）。-exec ... \; は、... を fork/exec によって実行します。... 部分を抜き出し、改行して再掲します。

find -files0-from input \
  \( -name . -o -name first -delete \) -fprintf tmp ".\0" \
  -false -fprint first

上記コードにおける 3行目 -false -fprint first によって、この find の実行直後に first という（書き込まれない）空ファイルが作られます。これは仕様として、-fprint の対象となるファイルはたとえ条件がマッチしなくても truncate されるか空ファイルとして生成されるためです。その後、input が ".\0" の $n$ 回の繰り返しだとして、$n$ 個の . を順に読み込みます。1個目の . の走査においては、2行目において ./first と . がマッチするため、tmp の内容は ".\0.\0" になり、first は -delete があるため消されます。2個目以降の . の走査においては . のみがマッチするため、tmp には ".\0" が1つ追記されます。結果として tmp は ".\0" の $n+1$ 回の繰り返しとなります。

変数の構成

前回の記事では、ディレクトリ構造を一次元のテープとして、タグシステムを実装しました。一方、今回の制約では、mkdir が使えないため、ディレクトリの深さには制限があります。1つのファイル名の長さには、（典型的には255という）制限があるため、我々はファイルパスを（チューリング完全性が要求する）無尽蔵のリソースとして使うことはできません。

そこで今回はファイル名ではなく、ファイルの内容を無尽蔵のリソースとして用いることにします。具体的には、非負整数の変数 $a$ について、ファイル a が存在しないことを $a=0$ と考え、a の中身が .\0 の $n$ 回の繰り返しであることを $a=n$ と考えます。この構成を用いると、定数回の find コマンドの実行で $a$ を1増減させることが可能になります。

# Fragment to increment a
INC_A=( \(
  \(
    -exec find a -quit \; # L1
    -exec find -files0-from a \( -name . -o -name first -delete \) -fprintf tmp ".\0" -false -fprint first \; # L2
    -exec find -files0-from tmp -prune -fprintf a ".\0" \; # L3
    -exec find tmp -delete \; # L4
  \) -o
  -exec find -fprintf a ".\0" -quit \; # L5
\) )

# Increment a
find . ${INC_A[@]} -prune 2> /dev/null

# Increment a twice
find . . ${INC_A[@]} -prune 2> /dev/null

INC_A は、外側の find 実行に埋め込むことで、そこが実行された回数だけ $a$ を1増やします。まず、L1 で、a の存在判定を行います。存在しない（$a=0$ の）場合 -exec の返り値が0でないため、L1 は偽となり、L5 が実行され、a に .\0 が書き込まれる、すなわち $a=1$ となります。a が存在する場合、L2, L3, L4 で a に ".\0" の $a+1$ 回の繰り返しが書き込まれます。これはループの構成で使ったロジックとまったく同じです。結果として副作用なしで $a\leftarrow a+1$ という操作が実現されます。

（ファイルが存在しないときなどに出るエラー出力を無視していますが、これは単に見栄えのためです。万一標準出力と標準エラーを区別できないシステムであったとしても、エラー文字列をパターンマッチで取り除くことは容易なので、計算能力を示すうえで問題にはなりません）

# Fragment to decrement a
DEC_A=( \(
  \(
    -exec find a -size 2c -delete \; # L1
    -exec find a -quit \; # L2
    -exec find -quit -fprint first \; # L3
    -exec find -files0-from a -depth -path ./first -delete -fprintf tmp skip -o -path ./tmp -fprintf tmp . -o -path . -fprintf tmp "\0" \; # L4
    -exec find -files0-from tmp -path . -fprint0 a -prune \; # L5
    -exec find tmp -delete \; # L6
  \) -o -true # L7
\) )

# Decrement a
find . ${DEC_A[@]} -prune 2> /dev/null

# Decrement a twice
find . . ${DEC_A[@]} -prune 2> /dev/null

DEC_A は、外側の find 実行に埋め込むことで、そこが実行された回数だけ $a$ を1減らします。まず L1 において、a が存在しない（$a=0$）ならば find は失敗し、L2 以降は実行されません。-size 2c によって、a の中身が .\0 である（$a=1$ の）場合のみ a は消去される、すなわち $a=0$ となります。L2 において、$a=0$ ならば find は失敗し、L3 以降は実行されません。つまり L3 が実行されるとき $a\ge 2$ です。L3 において、first というファイルを作成します。L4 において、まず -fprintf に指定されていることから、tmp という空ファイルが作られ、それから $a$ 個の . が順に開始点として処理されます。1回目の処理では -depth オプションにより、まず ./first と ./tmp が順不同で処理され、tmp には .skip または skip. のいずれかが書き込まれます。それから . が処理され tmp に \0 を書き込むため、その内容は skip.\0 または .skip\0 になります。また、first は削除されます。 2回目以降の処理では、./tmp と . がこの順で処理され、tmp に .\0 を追記します。つまり L5 において、tmp の中身は skip.\0 または .skip\0 と、.\0 の $a-1$ 回の繰り返しの結合となります。L5 では skip. または .skip と $a-1$ 個の . が処理されますが、skip. と .skip はいずれも存在しないため無視され、a にもともとより1つ少ない数の .\0 が書き込まれます。L6 で tmp を消去します。結果として副作用なしで $a \leftarrow a-1$ という操作が実現されます。L7 の -o -true により、いかなる場合でもこの一連のロジックが真として評価されることを保証しています。

最後に、$a=0$ であるかを評価するのは単にファイルの有無を評価すればよいです。

# Fragment evaluated to true if and only if a is zero.
IS0_A=( ! -exec find a -quit \; )

find . ${IS0_A[@]} -printf 'a is zero\n' -o -printf 'a is non-zero' , -prune 2> /dev/null

-exec find a -quit \; は a が存在する場合のみ（内側の find が成功するから）真として評価されるため、その否定をとれば、$a=0$ のときのみ真となる式になります。

以上が変数の操作と評価の方法となります。また、変数を定数個増やすことは容易で、例えば $b$ を導入したければ上記の INC_A, DEC_A, IS0_A に登場する a を b に置き換えたものを INC_B, DEC_B, IS0_B として導入し使用すればよいです。実際以下では2変数 $a, b$ を仮定します。

プログラムカウンタと万能機械

レジスタ2つの Minskyのprogram machine は、プログラムカウンタ $\textit{PC}$ と2つのレジスタ$a,b$ を持つ機械であって、以下の命令を持つものです。（厳密にはそのサブセットかもしれませんが今回の議論には影響しません）

  • INC(r): $r \leftarrow r + 1$ (rはレジスタ)
  • DEC(r): $r \leftarrow \max(r - 1, 0)$
  • J(x): $\mathit{PC}\leftarrow x$
  • JZ(r, x): $r=0$ ならば $\mathit{PC} \leftarrow x$
  • HALT: プログラムを停止する

有限長さのこの機械で実行できるプログラムであって、万能性をもつものが存在することが知られているため、我々の設定でそのようなプログラムの実行をエミュレートできれば、find はチューリング完全であることが言えます。ここでは、単純な $a \leftarrow a + b$ というプログラムを例として示します。

1 JZ(b, 5)
2 DEC(b)
3 INC(a)
4 J(1)
5 HALT

プログラムカウンタを pc というファイルの大きさで表すことにします。

$\mathit{PC} \leftarrow x$ とするには、-exec find -fprintf pc "..." -quit \; を使って、$x$ バイトの内容を書き込めばよいです。$x$ はつねに定数なので、すべてのプログラムカウンタの変更をこの形式で書いても問題ありません。また、プログラムカウンタの値がある定数（たとえば5）に一致しているかどうかは、-size 5c によって判定できます。また、HALT は単に -quit すればよいです。以上を組み合わせると、上記のプログラムは以下のように翻訳されます。

# If pc = 1, increment it to 2 and execute the following instruction.
IS_PC1=( -size 1c -exec find -fprintf pc "11" -quit \; )
IS_PC2=( -size 2c -exec find -fprintf pc "111" -quit \; )
IS_PC3=( -size 3c -exec find -fprintf pc "1111" -quit \; )
IS_PC4=( -size 4c -exec find -fprintf pc "11111" -quit \; )
IS_PC5=( -size 5c -exec find -fprintf pc "111111" -quit \; )

SET_PC1=( -exec find -fprintf pc "1" -quit \; )
SET_PC5=( -exec find -fprintf pc "11111" -quit \; )

# Example: initialize with a = 4, b = 3
find \
 ${INC_A[@]} ${INC_A[@]} ${INC_A[@]} ${INC_A[@]} \
 ${INC_B[@]} ${INC_B[@]} ${INC_B[@]} \
 -quit 2> /dev/null

# Initialize pc = 1
find ${SET_PC1[@]} -quit

# Initialize input
find -fprintf input ".\0" -quit

# Main program: add two numbers
find -files0-from input -path ./pc \( \
  -exec find -files0-from input \( -name . -o -name first -delete \) -fprintf tmp ".\0" -false -fprint first \; \
  -exec find -files0-from tmp -prune -fprintf input ".\0" \; \
  -exec find tmp -delete \; \
\) \( \
  ${IS_PC1[@]} ${IS0_B[@]} ${SET_PC5[@]} -o \
  ${IS_PC2[@]} ${DEC_B[@]} -o \
  ${IS_PC3[@]} ${INC_A[@]} -o \
  ${IS_PC4[@]} ${SET_PC1[@]} -o \
  ${IS_PC5[@]} -quit \
\) 2> /dev/null

メインプログラムの 1-5行目がループの構成となります。. には pc が含まれるので -path ./pc は毎回マッチし、2-5行目で input に含まれる . の数を1増やして、その次の括弧の実行にうつります。./pc を受け取ったメインロジック（6行目以降）は、そのサイズ、すなわち $\mathit{PC}$ の値により分岐します。例えば $\mathit{PC} = 1$ の場合は、${IS_PC1[@]} にマッチし、$\mathit{PC} \leftarrow 2$ となり、その後${IS0_B[@]} ${SET_PC5[@]} によって、もし $b=0$ ならば $\mathit{PC} \leftarrow 5$ となり、そうでなければ $\mathit{PC}=2$ のまま次のループに移ります。

最後に $a$ の値を出力することもできます。

# Output a (= 7)
find -files0-from a -fprintf count . -prune 2> /dev/null
find count -printf "%s\n"

実行結果

このコードは count に . を $a$ 回書き込み、その後 count のバイト数を出力しているため、出力は $a$ と一致します。a が存在しない場合も count は空ファイルとして生成されるので、$a=0$ の場合も問題ありません。

この構成はあきらかにより大きなプログラムサイズに拡張可能です。よって、GNU find はチューリング完全であることがわかりました。

補遺

実装上、無限ループが成立することの説明

GNU find 4.9.0 の実装を読み、確かに無限ループが成立することをみます。ソースコードは https://ftp.gnu.org/gnu/findutils からダウンロードできます。ブラウザ上だと https://cgit.git.savannah.gnu.org/cgit/findutils.git/tree/?h=v4.9.0 で読むこともできるようです。依存する gnulib のバージョンは 6ef3d78 であり、https://cgit.git.savannah.gnu.org/cgit/gnulib.git/tree/?h=6ef3d78 で読めます。

-files0-from input が指定されると、process_all_startpoints^ は stream = fopen (options.files0_from, "r");^ でファイルを一度だけ開き、その FILE* を argv_iter_init_stream^ に渡します。メインループ^は argv_iter^ を呼んでNUL区切り文字列を1つずつ取り出し、各文字列を find(file_name) に渡した後で次の argv_iter を呼びます。argv_iter は、get_delim^ で今開いているストリームから直接読み進めるだけで、入力内容のバッファリングは行いません。get_delim は getc_maybe_unlocked でファイルを1文字ずつ読みます。getc_maybe_unlocked は環境によって getc または getc_unlocked を呼びますが、いずれにせよこれは fgetc^ と同じように振る舞います。fgetc はEOFをその返り値として読まない限りストリームのEOFフラグをセットすることは仕様上ないので、NUL文字 "\0" を返したとき、これがEOFをセットすることはありません。find(file_name) の中で複数の -exec find ... ; が呼ばれ、input が指すファイルは truncate された後で、もとのファイルに ".\0" が追加された内容になるのでした。これらのプロセス終了時には cleanup^ が （sharefile_destroy の hash_free 経由で p->table に登録された entry_free から）fclose^ を実行するので、書き込みバッファは親が次に getdelim を呼ぶ前に確実にディスクへ吐き出されています。
POSIX の truncate/write セマンティクスでは、既に開いている別の FD のファイル位置は変わらず、そこより後ろに新しいデータが書き足されれば次回の read() でそのバイト列が読み出せます。親の FILE* も同じで、前回読み終わったオフセットより後ろに子が再生成したレコードが存在する限り EOF になりません。古いバッファに残っている分は（あれば）そのまま消費し、バッファが尽きた時にカーネルから新たに読み込むと、そこには子が再生成した内容が載っています。したがって内部バッファがあろうと、それを消費し切った時点でファイル末尾がその先まで伸びており、getdelim は新しいトークンを取得し続けます。したがって、（ディスクサイズを無限とみなせば）たしかに実行は終わらないことが確かめられました。

予想される質問と答え

  • POSIX または GNU find の仕様で上記のコードが動くことは保証されているか
    • ともにいいえ。まず -files0-from は GNU 拡張であり、POSIXに規定されていません。また、GNU findutils のマニュアル自身が、-files0-from file について fileが実行中に変更された場合の結果は不定であると明記しています。また、file 内に特定のファイルが複数回記述されていた場合、それが複数回検索されることになるかどうかも不定です。いえるのは、find はLinux系の普及した実装においてチューリング完全、ということまでです
  • 古いLinuxディストリビューションで上記のコードは動くか
    • -files0-from は 2022年2月2日 にリリースされた GNU find 4.9.0 で追加されました。よって比較的新しいディストリビューションでないと上記のコードは動きません。私が試した環境は以下です
# WSL2
➜  ~ uname -a ; lsb_release -a | grep Description ; find --version | head -1
Linux home2 6.6.87.2-microsoft-standard-WSL2 #1 SMP PREEMPT_DYNAMIC Thu Jun  5 18:30:46 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Description:    Ubuntu 24.04.3 LTS
find (GNU findutils) 4.9.0

# Chromebook linux
$ uname -a ; lsb_release -a | grep Description ; find --version | head -1
Linux penguin 6.6.99-08879-gd6e365e8de4e #1 SMP PREEMPT_DYNAMIC Thu, 23 Oct 2025 06:15:52 -0700 x86_64 GNU/Linux
Description:    Debian GNU/Linux 12 (bookworm)
find (GNU findutils) 4.9.0
  • GNU find 4.10.0（最新バージョン）や uutils find もチューリング完全か
    • GNU find 4.10.0 については、おそらくはい。uutils find については不明です。両方を上記環境にインストールして実験したところ、4.10.0 については同様に動きましたが、uutils find については無限ループしませんでした。（バグではなく、仕様外の振る舞いの差によるものでしょう）

おまけ： find + mkdir は後方参照なしでもチューリング完全

前回の記事の補遺です。前回、我々は find の -regex が後方参照をサポートしていることを利用して find + mkdir のチューリング完全性を示しました。しかし regex の後方参照は man regex によれば "ひどく出来の悪い代物" であり、使用は非推奨です。そこで考えてみたところ、ファイルパスに正規表現を埋め込むという方法で、後方参照をサポートしない -regextype awk のみを使った場合でも任意の計算ができることがわかりました。（-files0-from も不使用）

以下では、前回も使ったタグシステムの例の後方参照を使わない実装を示します。この構成は任意の2-タグシステムに拡張可能なので、find + mkdir は後方参照なしでもチューリング完全です。

実装の詳細についてはまた時間があれば追記するかもしれません。よかったら解読してみてください。

# 2-Tag system implemented in find + mkdir without back references.

sep=')?('
a='[aA-z+-]+'
b='[bA-z+-]+'
c='[cA-z+-]+'
h='[hA-z+-]+' # halt

AL='[A-z+-]+'

SEP='.\?.'
NS='[^?]'
A='.a.......'
B='.b.......'
C='.c.......'
H='.h.......'

# 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"

mkdir -p "$sep/$b/$a/$a/$sep"

# 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)
find "$sep" -regextype awk -empty \( \
  -regex ".*\." -prune -o \
  -regex ".*$SEP/$H.*$SEP" -quit -o \
  -execdir mkdir {}/$A {}/$B {}/$C {}/$H \; \
  \( \
    -exec find "$sep" -regextype awk -empty -regex ".*$SEP/$AL/$AL({}/$A$NS*$SEP)$NS*$A" -delete \; \
    -exec find "$sep" -regextype awk -empty -regex ".*$SEP/$AL/$AL({}/$B$NS*$SEP)$NS*$B" -delete \; \
    -exec find "$sep" -regextype awk -empty -regex ".*$SEP/$AL/$AL({}/$C$NS*$SEP)$NS*$C" -delete \; \
    -exec find "$sep" -regextype awk -empty -regex ".*$SEP/$AL/$AL({}/$H$NS*$SEP)$NS*$H" -delete \; \
  \) \
  \( \
    -execdir mkdir {}/$A \; -a -execdir mkdir {}/$a \; -o \
    -execdir mkdir {}/$B \; -a -execdir mkdir {}/$b \; -o \
    -execdir mkdir {}/$C \; -a -execdir mkdir {}/$c \; -o \
    -execdir mkdir {}/$H \; -a -execdir mkdir {}/$h \; -o \
    -false \
  \) -o \
  -regex ".*$SEP/$A$NS*$SEP/$NS*" -execdir mkdir -p "{}/$PROD_A/$sep" \; -o \
  -regex ".*$SEP/$B$NS*$SEP/$NS*" -execdir mkdir -p "{}/$PROD_B/$sep" \; -o \
  -regex ".*$SEP/$C$NS*$SEP/$NS*" -execdir mkdir -p "{}/$PROD_C/$sep" \; -o \
  -false \
\) 2> /dev/null

find "$sep" -name "*." -delete

# Output the result. ($sep/$h/$c/$c/$c/$c/$c/$c/$a/$sep)
find "$sep" -depth ! -empty -name "$sep" -execdir find "$sep" -empty \; -quit

実行結果

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?