C99预处理器Turing是否已完成？ [英] Is the C99 preprocessor Turing complete?
问题描述
发现提高预处理器的功能我发现自己很纳闷：C99预处理器Turing是否已完成？
After discovering the Boost preprocessor's capabilities I found myself wondering: Is the C99 preprocessor Turing complete?
如果没有，缺少什么不符合条件？
If not, what does it lack to not qualify?
推荐答案
此处是滥用行为的一个示例实现图灵机的预处理器。请注意，需要一个外部构建脚本来将预处理器的输出反馈回其输入，因此预处理器本身并不完整。
Here is an example of abusing the preprocessor to implement a Turing machine. Note that an external build script is needed to feed the preprocessor's output back into its input, so the preprocessor in and of itself isn't Turing complete. Still, it's an interesting project.
从先前链接的项目的描述中：
From the description of the afore-linked project:
预处理器是 not 图灵完成的，至少在
中该程序仅预处理一次。即使
允许程序包含其自身也是如此。 （原因是
，对于一个给定程序，预处理器只有有限的
个状态，加上一个堆栈，其中包括文件所包含的
的位置。这仅是一个下推式自动机。）
the preprocessor is not Turing complete, at least not if the program is preprocessed only once. This is true even if the program is allowed to include itself. (The reason being that for a given program, the preprocessor has only a finite number of states, plus a stack consisting of the places which the file has been included from. This is only a push-down automaton.)
Paul Fultz II的回答令人印象深刻，而且肯定比我以为预处理器可以得到的距离更近，但这不是真正的图灵机。 C预处理器有一定的限制，即使您有无限的内存和时间，它也无法像Turing机器一样执行任意程序。 C规范的第5.2.4.1节给出C编译器的以下最低限制：
The answer by Paul Fultz II is quite impressive and certainly closer than I thought the preprocessor could ever get, but it's not a true Turing machine. The C preprocessor has certain limits that prevent it from executing an arbitrary program like a Turing machine could, even if you had infinite memory and time. Section 5.2.4.1 of the C spec gives the following minimum limits for a C compiler:
- 在一个完整表达式中包含63个嵌套表达式的嵌套级别
- 内部标识符或宏名称中的63个有效初始字符
- 4095个在一个预处理翻译单元中同时定义的宏标识符
逻辑源行中的- 4095个字符
- 63 nesting levels of parenthesized expressions within a full expression
- 63 significant initial characters in an internal identifier or a macro name
- 4095 macro identifiers simultaneously defined in one preprocessing translation unit
- 4095 characters in a logical source line
下面的计数器机制要求每个宏定义值，因此宏定义限制将限制循环的次数（ EVAL（REPEAT（4100，M，〜））会产生未定义的行为）。这从本质上限制了您可以执行的程序的复杂性。多级扩展的嵌套和复杂性也可能会达到其他限制之一。
The counter mechanism below requires a macro definition per value, so the macro definition limit will limit how many times you can loop (EVAL(REPEAT(4100, M, ~)) would yield undefined behavior). This essentially puts a cap on the complexity of the program that you can execute. The nesting and complexity of the multi-level expansions may hit one of the other limits as well.
这与无限内存限制根本不同。在这种情况下，规范特别指出，即使具有无限时间，内存等，也仅需要符合标准的C编译器即可。任何超出这些限制的输入文件都可以以不可预测或不确定的方式处理（或直接拒绝）。某些实施可能会有更高的限制，或者根本没有限制，但这被认为是特定于实现的，而不是标准的一部分。可能可以使用Paul Fultz II的方法在某些特定的编译器实现上实现图灵机之类的东西，而没有任何限制，但是从一般意义上来说，这可以在任意任意条件下完成，符合标准的C99预处理程序，答案是否定的。由于这里的限制是语言本身所固有的，而不仅仅是我们无法构建无限计算机的副作用，所以我说这破坏了图灵的完整性。
This is fundamentally different than the "infinite memory" limitation. In this case, the spec specifically says that a standards-conforming C compiler is only required to conform to these limits, even if it has infinite time, memory, etc. Any input file exceeding these limits can be processed in an unpredictable or undefined manner (or outright rejected). Some implementations may have higher limits, or no limits at all, but that's considered "implementation-specific" and not part of the standard. It may be possible to use Paul Fultz II's method to implement something like a Turing machine on some specific compiler implementation that has no finite limits, but in a general sense of "can this be done on any arbitrary, standards-conforming C99 pre-processor", the answer is no. Since the limit here is built into the language itself and not simply a side-effect of our inability to construct an infinite computer, I say that breaks Turing completeness.
这篇关于C99预处理器Turing是否已完成？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
