Is the C Preprocessor Turing Complete?

01/12/2012

Recently I put together a version of Brainfuck written entirely in the C Preprocessor. At the time I believed it was the first demonstrative proof of the Turing completeness of the C preprocessor. Posing it online caused quite a stir, and heated up an argument as to if the C Preprocessor really is Turing complete.

So is the C preprocessor Turing complete? The short answer - I don't know. You'll have to make up your own mind.

The main argument against completeness is that the C preprocessor cannot express unbounded recursion, making it incompatible with the definition of requiring an infinite tape, or running indefinitely. But no physical system can have an infinite tape, or run till the end of time, so what is the big deal? The subtle difference is on the separation of "machine" from "language". The "language" of the C preprocessor cannot express unbounded recursion independent of what machine it is run on. The question of if that machine itself supports unbounded recursion (or an infinite tape) is unimportant.

This is a fairly clear distinction and a compelling argument. Clearly there are languages where you can effectively express unbounded recursion function() { function() } and the C preprocessor is not one of them.

But there are a number of subtleties going on here. For example, if we consider the set of macros I created to be the "machinery", and the "language" to be the Brainfuck input to my system, then it is indeed Turing complete. That is - I have created machinery which can simulate Turing complete languages. Taking all the above definitions into account, consider how odd it is that Turing complete machinery can be expressed in a non Turing complete language.

A second curiosity is that although the C Preprocessor cannot express unbounded recursion it can express an infinite tape. More precisely the list type data structure I created was not limited in size. Perhaps this fact could be used to create infinite computations. But if so I haven't worked out how.

The unbounded recursion restrictions on Turing completeness would also dismiss many languages commonly believed to be Turing complete from being so. Any system which simulates finite machinery to achieve it's goal. This includes many of our favorites such as Minecraft and Conway's game of life. It may even include others such as C, which have hard limits on pointers and other items in the specification.

How many practical languages remain Turing Complete under this definition? Is there really this clear distinction between machinery and language that makes sense? Can we be sure the two language classes do not fold into one?

Unknowingly considering the C Preprocessor opens up a closet full of skeletons which we now have to consider more carefully.