チューリング完全とは、ざっくり説明すると、一部を除くほとんど全ての計算が可能な能力を意味します。言い換えると、ほとんど全ての計算問題を解く能力を意味します。(あとでもう少し詳しく説明します。)プログラミング言語は一般にチューリング完全であり、例えば TypeScript や Python はチューリング完全です。プログラミング言語以外にも、TypeScript の型システムやスーパーマリオメーカー、マジック・ザ・ギャザリングもまたチューリング完全であることが知られています[1][2][3]。直近では find と mkdir だけでチューリング完全になると報告されていましたね[4]。 逆にチューリング完全でない例としては正規表現[5]があります。チューリング完全ならば正規表現で解ける問題を全て解けますが、その逆は不可能です。例えば回文の判定は正規表現だと無理です。このように、数ある計算能力
![GitHub Actions はチューリング完全](https://cdn-ak-scissors.b.st-hatena.com/image/square/9b61a3ebc3d48242e343f7563886d579563eb402/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--xa_Qze1Z--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3AGitHub%252520Actions%252520%2525E3%252581%2525AF%2525E3%252583%252581%2525E3%252583%2525A5%2525E3%252583%2525BC%2525E3%252583%2525AA%2525E3%252583%2525B3%2525E3%252582%2525B0%2525E5%2525AE%25258C%2525E5%252585%2525A8%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_34%3AajfAfg%252Cx_220%252Cy_108%2Fbo_3px_solid_rgb%3Ad6e3ed%252Cg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyL2RmZGEyOTIyNDQuanBlZw%3D%3D%252Cr_20%252Cw_90%252Cx_92%252Cy_102%2Fco_rgb%3A6e7b85%252Cg_south_west%252Cl_text%3Anotosansjp-medium.otf_30%3A%2525E3%252582%2525B5%2525E3%252582%2525A4%2525E3%252583%25259C%2525E3%252582%2525A6%2525E3%252582%2525BA%252520%2525E7%252594%25259F%2525E7%252594%2525A3%2525E6%252580%2525A7%2525E5%252590%252591%2525E4%2525B8%25258A%2525E3%252583%252581%2525E3%252583%2525BC%2525E3%252583%2525A0%252520%252520%252Cx_220%252Cy_160%2Fbo_4px_solid_white%252Cg_south_west%252Ch_50%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyLzc0YzQ3MjY3NWMuanBlZw%3D%3D%252Cr_max%252Cw_50%252Cx_139%252Cy_84%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)