[解決済み] C99プリプロセッサーはチューリング完全か？

質問

を発見した後 Boost プリプロセッサの機能 私は不思議に思っていることに気づきました。C99 プリプロセッサはチューリング完全か？

もしそうでないなら、修飾しないために何が欠けているのでしょうか？

どのように解決するのですか？

ここで はチューリングマシンを実装するためにプリプロセッサを悪用した例です。 プリプロセッサの出力を入力に戻すために、外部のビルドスクリプトが必要であることに注意してください。 それでも、これは興味深いプロジェクトです。

前述のリンクされたプロジェクトの説明より。

プリプロセッサは ではなく チューリング完全ではない、少なくとも プログラムが一度だけプリプロセスされる場合、少なくともそうではありません。これは プログラムが自分自身を含むことが許されている場合でも同様です。(その理由は あるプログラムに対して、プリプロセッサは有限の状態 というのも，プリプロセッサは有限個の状態と，ファイルがインクルードされた場所からなるスタックを持つからである。 からなるスタックを持っているからです。これはプッシュダウン オートマトンに過ぎないのです)。

Paul Fultz II による回答は非常に印象的で、確かに私がプリプロセッサが到達できると考えていたよりも近いものでしたが、これは真のチューリングマシンではありません。 Cプリプロセッサにはある種の限界があり、たとえメモリと時間が無限にあっても、チューリングマシンができるような任意のプログラムを実行することはできないのです。 の 5.2.4.1 節を参照してください。 C 仕様 では、C コンパイラの最小限の制限を次のように定めています。

• 完全な式の中にある括弧で囲まれた式の63のネストレベル
• 内部識別子またはマクロ名における 63 の重要な初期文字
• 1 つの前処理翻訳ユニットで同時に定義された 4095 個のマクロ識別子
• 論理的なソース行の 4095 文字

下のカウンターの仕組みは、値ごとにマクロ定義が必要なので、マクロ定義の制限によりループできる回数が制限されます( EVAL(REPEAT(4100, M, ~)) を使用すると未定義の動作になります)。 これは本質的に、実行可能なプログラムの複雑さに上限を設けることになります。 マルチレベル展開の入れ子と複雑さは、他の制限の 1 つにも当たる可能性があります。

これは、無限メモリの制限とは根本的に異なります。 この場合、仕様では、標準に準拠した C コンパイラーは、たとえ時間やメモリなどが無限であっても、これらの制限に準拠することだけが要求されると明確に述べています。 この制限を超えた入力ファイルは、予測不能または未定義の方法で処理される可能性があります（または完全に拒否される可能性もあります）。 実装によっては、より高い制限を設けたり、全く制限を設けないこともできますが、それは実装固有のものとみなされ、標準の一部ではありません。 Paul Fultz II の方法を使って、チューリングマシンのようなものを ある特定のコンパイラの実装 しかし、一般的な意味での「任意の、標準に準拠した C99 プリプロセッサーでこれを行うことができるか」というと、答えはノーです。 ここでの限界は言語自体に組み込まれており、無限コンピュータを構築できないことによる単なる副作用ではないため、チューリングの完全性を破っていると言えるのです。