GitHub Actions はチューリング完全

チューリング完全とは、ざっくり説明すると、一部を除くほとんど全ての計算が可能な能力を意味します。言い換えると、ほとんど全ての計算問題を解く能力を意味します。（あとでもう少し詳しく説明します。）プログラミング言語は一般にチューリング完全であり、例えば TypeScript や Python はチューリング完全です。プログラミング言語以外にも、TypeScript の型システムやスーパーマリオメーカー、マジック・ザ・ギャザリングもまたチューリング完全であることが知られています[1][2][3]。直近では find と mkdir だけでチューリング完全になると報告されていましたね[4]。 逆にチューリング完全でない例としては正規表現[5]があります。チューリング完全ならば正規表現で解ける問題を全て解けますが、その逆は不可能です。例えば回文の判定は正規表現だと無理です。このように、数ある計算能力

[tohokuaiki]

なるほど、チューリング完全ってよく聞くがこういうことか。わからん。

[akymrk]

"一般的な証明方法は、証明対象を用いて、すでにチューリング完全と知られているものを模倣（実装）すること”

[everybodyelse]

シェルスクリプトのコマンドをどこまで許すかは議論がありそうだけど、こういう試みは好きw