Icon Tracing Functions in Python


Icon Still Things and Moving Things


Icon water.cpp


Icon Making Poetry in Piet


Icon Learning Motion Manifolds with Convolutional Autoencoders


Icon Learning an Inverse Rig Mapping for Character Animation


Icon Infinity Doesn't Exist


Icon Polyconf


Icon Raleigh


Icon The Skagerrak


Icon Printing a Stack Trace with MinGW


Icon The Border Pines


Icon You could have invented Parser Combinators


Icon Ready for the Fight


Icon Earthbound


Icon Turing Drawings


Icon Lost Child Announcement


Icon Shelter


Icon Data Science, how hard can it be?


Icon Denki Furo


Icon In Defence of the Unitype


Icon Maya Velocity Node


Icon Sandy Denny


Icon What type of Machine is the C Preprocessor?


Icon Which AI is more human?


Icon Gone Home


Icon Thoughts on Japan


Icon Can Computers Think?


Icon Counting Sheep & Infinity


Icon How Nature Builds Computers


Icon Painkillers


Icon Correct Box Sphere Intersection


Icon Avoiding Shader Conditionals


Icon Writing Portable OpenGL


Icon The Only Cable Car in Ireland


Icon Is the C Preprocessor Turing Complete?


Icon The aesthetics of code


Icon Issues with SDL on iOS and Android


Icon How I learned to stop worrying and love statistics


Icon PyMark


Icon AutoC Tools


Icon Scripting xNormal with Python


Icon Six Myths About Ray Tracing


Icon The Web Giants Will Fall


Icon PyAutoC


Icon The Pirate Song


Icon Dear Esther


Icon Unsharp Anti Aliasing


Icon The First Boy


Icon Parallel programming isn't hard, optimisation is.


Icon Skyrim


Icon Recognizing a language is solving a problem


Icon Could an animal learn to program?




Icon Pure Depth SSAO


Icon Synchronized in Python


Icon 3d Printing


Icon Real Time Graphics is Virtual Reality


Icon Painting Style Renderer


Icon A very hard problem


Icon Indie Development vs Modding


Icon Corange


Icon 3ds Max PLY Exporter


Icon A Case for the Technical Artist


Icon Enums


Icon Scorpions have won evolution


Icon Dirt and Ashes


Icon Lazy Python


Icon Subdivision Modelling


Icon The Owl


Icon Mouse Traps


Icon Updated Art Reel


Icon Tech Reel


Icon Graphics Aren't the Enemy


Icon On Being A Games Artist


Icon The Bluebird


Icon Everything2


Icon Duck Engine


Icon Boarding Preview


Icon Sailing Preview


Icon Exodus Village Flyover


Icon Art Reel




Icon One Cat Just Leads To Another

Is the C Preprocessor Turing Complete?

Created on Dec. 1, 2012, 1:24 p.m.

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.

github twitter rss