バグのないソフトウェアの作れない理由 を読んで徒然と思ったこと。厳密な議論ではないので悪しからず。
なぜ C には翻訳限界があるのでしょうか。つまり、なぜ「規格として」定める必要があったのかという話です。
もし、規格に限界が定められていなければどうなるでしょうか。もし限界が無いとすると、例えば、コンパイラは無限にネストしたブロックを受理できなければなりません。もちろん、コンピュータの物理メモリは有限ですから、これは不可能です。従って、規格として「ブロックのネスト回数は無制限である」と書くことは不可能であり、限界を定める必要があったのです。
「無制限と書かなくても『メモリの許す限り』と定めれば良いではないか」と思われるかもしれません。しかし、あるコンパイラがメモリの許す限り無制限のネストを受理できるということを、どうやって証明するのでしょうか？ ある処理系がその規格に適合しているかどうかを検証できないのであれば、それは規格と呼ぶに値しません。
限界を定めるのと定めないのとで何が違うのか。それは限界を定めないとチューリングマシンでしか受理できないが、限界があれば有限オートマトンで受理できるということです。チューリングマシンと有限オートマトンの違いで重要な点は、チューリングマシンは、任意の2つのチューリングマシンが等価であることを証明できないという点にあります。つまり、コンパイラがチューリングマシンでしか実現できないとすると、そのコンパイラが仕様通り動くかどうか、言語規格に適合しているかどうかを数学的に証明できないということになってしまいます。
さて、こう書くと「ではC言語はチューリング完全ではないということか」と勘違いする人が出るでしょう。落ち着いてください。「C言語で書いたあるプログラムがチューリングマシンであるかどうか」と「C言語のコンパイラがチューリングマシンであるかどうか」は全く異なる概念です。明らかにチューリングマシンでなくても受理できるアセンブラのような文法でも、チューリングマシンをプログラムできます。C言語のチューリング完全性は、文法の複雑さからではなく、その背後にある計算モデルから来ているのです。
そもそもチューリングマシンとはどのような物だったかというと、遷移表とか機能表と呼ばれる有限オートマトンと、ヘッドで読み書きできる無限長のテープの組み合わせでした。C言語で「無限長のテープ」に対応するのは、プログラム自体ではなく、「常に読み書きできると仮定できる標準入出力」とか、「決してオーバーフローしないと仮定したスタック」に該当します。つまり、プログラムが無限大と見なせる領域にアクセスできて、それによって動作が変わるということが重要なのであって、プログラム自体がどのような文法の言語で記述されているかによって決まるのではありません。