Paper shelf
C++ templates are Turing-complete
A short companion to the paper that established the C++ template system as a Turing-complete metalanguage. The result is interesting on its own and useful for understanding what compile-time work can buy you.
What the paper is
The paper establishes that the C++ template system, used as a metalanguage, can compute anything a Turing machine can compute. The proof works by encoding a Turing machine in templates and showing that the compiler steps the machine through its transitions.
The file is at /ubigraph/content/Papers/pdf/CppTuring.pdf.
Why the result matters
A naive reading of the result is that the C++ template system is more powerful than its designers expected. That is true and it is the part that gets quoted. The more useful reading is what the result enables.
If the template system can compute anything, it can compute the right specialisation for a particular use of a library at compile time. It can pick the right loop unrolling. It can pick the right data layout. It can decide whether to use a sparse or dense representation. It can do all of this without runtime cost.
That is the practical payoff. The Turing-completeness result is the formal underpinning of every C++ library that does serious compile-time work.
What the proof does not say
A few things the result does not claim.
- It does not say the template system is a good general-purpose programming language. Writing templates is harder than writing ordinary C++ code. The result establishes capability, not ergonomics.
- It does not say the compiler can decide every question about a template program. Many compile-time computations either fail to terminate or run into compiler implementation limits before they finish.
- It does not say every C++ library benefits from template metaprogramming. Most libraries are better off using the template system in simple, contained ways.
The result is a foundation, not a prescription.
How it connects to graph tooling
A graph viewer has the same library-design problem that any high-performance numerical library has. It needs to be flexible enough to be used and fast enough to be useful.
The Turing-completeness result is what lets a graph library make compile-time decisions about its data structures and inner loops. A library can specialise itself for dense graphs in one program and sparse graphs in another, without paying for the abstraction at runtime. A force-directed layout can specialise itself for the kind of force model the user actually wants, again without runtime cost.
This is one of the reasons the C++ template work and the graph tooling work belong on the same shelf. The connection is at the library-design layer.
The C++ template papers and graph tools lab note discusses this connection at more length.
A note on reading the paper
The paper is short by paper standards but dense. It assumes you are comfortable with C++ template syntax. If you are not, the proof itself will be harder to follow than the surrounding argument.
A reasonable reading path:
- Read the introduction and the conclusion first. Get the shape of the claim.
- Skim the proof. Do not try to internalise every detail.
- Read the section that motivates the claim. That is the part that has the most practical content.
The paper rewards a re-read after you have written some template code of your own.
A note on authorship
As with the other papers on this shelf, the exact provenance of any copy of the PDF requires verification before any claim can be made about authorship or version. This site presents the historical path and a careful summary. It does not present the file as a certified original until that check has been completed.