c++ - C++ は再帰的に列挙可能な言語ですか?

Question

C++ が決定可能でないことはわかっています。しかし、それは再帰的に列挙可能ですか?

有効な C++ プログラムのセットを、現在の C++ 標準の下で適切に定義されたプログラムと定義しましょう。

有効な C++ プログラムを常に有限時間で識別できるコンパイラを構築することは可能ですか?

それとも再帰的に列挙可能ですか？

有限時間内に無効なC++ プログラムを常に識別できるコンパイラを構築することは可能ですか?

それともどちらでもない？

Answer 1

有効な C++ プログラムを常に有限時間で識別できるコンパイラを構築することは可能ですか?

はい。十分な時間とリソースがあれば、C++ コンパイラは有効な C++ プログラムのコンパイルを完了できるはずです。再帰的に列挙可能な言語には、文字列が言語内にある場合に常に終了して肯定的な答えを提供するチューリングマシンが必要であり、コンパイラーは本質的にそれを行います。

有限時間内に無効な C++ プログラムを常に識別できるコンパイラを構築することは可能ですか?

いいえ。C++ テンプレート言語はチューリング完全であるため、無限再帰を記述できます。停止の問題により、プログラムのコンパイルが完了するかどうかを判断することは不可能です。したがって、C++ プログラムが正常にコンパイルされるかどうかを判断することは不可能です。

C++ テンプレートで無限再帰を記述し、gcc でコンパイルしようとしたことがあります。gcc には構成可能な再帰の深さの制限があることがわかりました。