Edit - Stack Overflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Rev

Required fields*

Is the C99 preprocessor Turing complete?

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?

Answer*

[Here][1] 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:

> 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.)

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][2] gives the following minimum limits for a C compiler:

> - 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

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.

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.

  [1]: http://www.ioccc.org/2001/herrmann1.hint
  [2]: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

Required fields are marked with *

Edit Summary*

Cancel

If you mean the 115 point answer by Paul Fultz II below: it confirms this answer.

reinierpost
– reinierpost

2017-08-20 10:56:50 +00:00
Commented Aug 20, 2017 at 10:56
3

The limit is in the language itself, but not because of the spec, but because we must write the scans to evaluate the algorithm in the language itself, which there is no mechanism to apply an infinite number of scans.

Paul Fultz II
– Paul Fultz II

2017-10-18 23:26:21 +00:00
Commented Oct 18, 2017 at 23:26
To add to the lack of recursiveness, that seems to be (under)specified by the standard. §6.10.3.5 paragraph 4 shows an example of two macros calling each other and states: "There are cases where it is not clear whether a replacement is nested or not [...]. Strictly conforming programs are not permitted to depend on such unspecified behavior. "

Luiz Martins
– Luiz Martins

2021-03-13 15:51:42 +00:00
Commented Mar 13, 2021 at 15:51
@reinierpost technically, the 217 point answer (now above smh) doesn't actually confirm this answer, as someone else could still prove that CPP is TC. However, it seems like no-one has, and all who attempt use LARGE NUMBERS of macros. The fact that the algorithm is designed to always terminate is enough for me (see alinsoar's answer).

Nathan Chappell
– Nathan Chappell

2022-04-30 11:18:14 +00:00
Commented Apr 30, 2022 at 11:18

Add a comment |

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
indent code by 4 spaces
backtick escapes `like _so_`
quote by placing > at start of line
to make links (use https whenever possible)

<https://example.com>

[example](https://example.com)

<a href="https://example.com">example</a>

formatting help »
answering help »

Collectives™ on Stack Overflow

Is the C99 preprocessor Turing complete?

Answer*