[scott_s]

There's some subtlety going on here, but I'm going to agree with CJefferson.

Turing completeness is about separating the expression of a computation from the machinery that carries out the computation. If your expression language can be mapped to the idealized Turing machine, then your expression language can express all computations that can be computed. (That is, it is Turing Complete.) This allows us to reason about the expression of computation outside of the machinery that carries it out - because the machinery will always have limits.

The subtlety is: where do we draw the line between the expression and the machinery?

That is, assuming the question is "is the C preprocessor Turing Complete?" I answer no. Because implied in that question is that the C preprocessor language is the expression language we are interested in, and the C preprocessor is the machinery. The reason why I say that the C preprocessor expression language is not Turing complete is simple: you cannot actually express recursion or unbounded loops. No, the above is not a counter example. Why? Because the simulated loops are bounded, always. If you can't express arbitrary loops or recursion, then you can't compute everything that can be computed.

Note that I stressed express. Yes, an actual C program is clearly limited in how much it can recurse, but the language itself can express unbounded recursion.

And that can make our reasoning a bit more interesting: what if rather than asking the question about the C preprocessor, we instead ask it about the implied functional language that the author defined? This implied functional language is implemented in the macros the author defined. If we assume that his implied functional language is the expression language, and the machinery is both the C preprocessor language and the by-hand macros that CJefferson pointed out, then yes, that implied functional language is turing complete. That is, we could take the semantics behind his top-level macros, and go implement a fully Turing Complete language with those semantics. That's what you are getting at when you consider those macros the same as physical memory. We can do that, but now we're reasoning about the author's implied functional language, not the C preprocessor itself.

If you still don't agree, consider that the author's macro language is essentially the same as BlooP: http://en.wikipedia.org/wiki/BlooP_and_FlooP

[orangeduck]

This is an excellent explanation.

As you say, if we assume that my set of macros are the machinery, then truly my "BRAINFUCK()" macro is Turing complete.

Using this distinction between language and machine, how peculiar that a Turing Complete thing can be expressed using a language which is not Turing Complete itself.

The question is really - are these distinctions between machine and language always meaningful and without contradiction.

[scott_s]

Using this distinction between language and machine, how peculiar that a Turing Complete thing can be expressed using a language which is not Turing Complete itself.

Ah, but that's the rub: we can't, and we didn't. You are imparting semantics on your macros that the C preprocessor has not. That is, the semantics that you imagine the macros to have are solely in your mind. They are not implied by the semantics of the C preprocessor.

[pfultz2]

So the expression of unbounded recursion can be expressed like this:

    #define EMPTY()
    #define DEFER(id) id EMPTY()

    #define FOREVER() \
        ? \
        DEFER(FOREVER_INDIRECT) () ()
    #define FOREVER_INDIRECT() FOREVER

This will print out `?` infinitely. Here is the machinery to evaluate the expression:

    #define EVAL(...) A(A(A(__VA_ARGS__)))
    #define A(...) B(B(B(__VA_ARGS__)))
    #define B(...) C(C(C(__VA_ARGS__)))
    #define C(...) D(D(D(__VA_ARGS__)))
    #define D(...) E(E(E(__VA_ARGS__)))
    #define E(...) __VA_ARGS__

    EVAL(FOREVER())

Which will expand to something like this:

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? FOREVER_INDIRECT () ()

Well at the end we see `FOREVER_INDIRECT () ()` which means the algorithm can expand further, so we could just apply more scans:

    EVAL(EVAL(FOREVER()))

And we get more `?`. And we didn't have to change the expression of the algorithm just the machinery to evaluate it.

This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself. This is different than BlooP, which the only possible way to express Turing completeness is through an external source(such as an input file).

Of course, for all practical purposes, the C preprocessor is near Turing-complete enough. The whole goal of the preprocessor is to output a file, we don't need it run indefinitely. We can express almost any useful algorithm, and if it reaches the recursion limit, we just simply apply more scans.

[scott_s]

This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself.

Unfortunately, "can act as Turing-complete" is not a well defined concept. It is clearly not the same thing, and the distinction is important. Consider, as pointed out elsewhere in this thread, that we can always solve the halting problem for a C preprocessor program. We're in danger of violent agreement, though: I think we agree on the main points, just perhaps not on their relevance.

Since we've gone this far down the rabbit hole, I'd like to point out that C++ templates are Turing complete: http://netvor.sk/~umage/docs/3rdparty/C++%20Templates%20are%...