みんな大好き構造化定理の話2025年版。

https://doi.org/10.1145/3704861

構造化定理は連接・分岐・繰り返しで全ての制御構造を表せるというものだが、実はプログラム側から直接操作できない変数が必要という前提がある。

そういったものが無い場合、表せない制御構造があることが知られていた(条件式の値が変化する限り繰り返す、とか)。

一方、有限状態に対する非決定的な演算については小さな言語KATで任意の構造を表せることがわかっている。

この論文では、有限個の正規制御構造(KATへのローカルな書き換えで表現できる演算)を用意しても、表せない制御構造が常に存在する、というのを示している。