sedコマンドはチューリング完全

チューリング完全とは、万能チューリングマシンと同じ計算能力を持つこと。ざっくり言うと、条件分岐やループが実現できて普通のプログラミング言語で実現できるアルゴリズムを作れる能力を持つことです。

sedコマンド

sed コマンドは、テキスト処理を手軽にできるコマンド。シェル上で手軽にテキスト処理をしたいときによく使う。

たとえば文字列置換ができる。次の例はパイプでつないで正規表現で文字列置換する。

$ echo 'hello hello hello' | sed -e 's/hello/bye/g'
bye bye bye

テキストの行を抽出したりもできる。次の例は、偶数行目だけを出力する。

$ cat foo.txt
01
02
03
04
05
06
$ cat foo.txt | sed -ne '0~2p'
02
04
06

sedコマンドはチューリング完全である。つまり、普通のプログラミング言語と同等のアルゴリズム力がある。

ここに証明があった。

ソースコードでは何をしているのかよくわからなかったが、条件分岐とループをうまく実装しているっぽい。つよい。