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 RAGE

 

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 LOL I DREW THIS DRAGON

 

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