<p>Since templates are a compile-time applicative language you may find it tedious to encode a stateful model of computation like a Universal Turing Machine. Encoding some other Turing-equivalent model, like the Lambda Calculus, is a more straight forward approach.</p>

CC BY-SA 2.5
2010-10-09T14:11:20.427Z
2010-10-09T14:11:20.427Z
Alex Rubinsteyn
<p>The following post on StackOverflow might be useful: <a href="https://stackoverflow.com/q/7284/459391">What is Turing Complete?</a> </p>

<p>You may also consult the corresponding <a href="http://en.wikipedia.org/wiki/Turing_completeness" rel="nofollow noreferrer">Wikipedia entry</a>.</p>

<p>Moreover, you may consider taking a look at <a href="http://savannah.nongnu.org/projects/turing-mach/" rel="nofollow noreferrer">C++ Simulator of a Turing Machine</a> before implementing one from scratch (unless your objective is to learn, rather than use).</p>

CC BY-SA 2.5
2010-10-09T16:40:00.210Z
Sadeq, he wants to do the implementation using C++ templates, not just regular C++. It's a whole new level of insanity.
Dave Clarke
CC BY-SA 2.5
2010-10-09T16:33:38.873Z
2010-10-09T16:33:38.873Z
2017-05-23T12:40:09.333Z
Sadeq Dousti
<p>The article you want is <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2003&amp;rep=rep1&amp;type=pdf">C++ Templates are Turing Complete</a> by Todd Verhuizen. It explains how things work in sufficient details. If you can faithfully encode a Turing machine and its behaviour in C++ templates, then this is sufficient to demonstrate Turing completeness.</p>

CC BY-SA 2.5
2010-10-09T12:01:15.437Z
2010-10-09T12:01:15.437Z
Dave Clarke
<p>I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will <em>actually</em> build a Turing machine ? I have read that C++ templates are Turing complete but I don't actually know how to prove this thing.</p>

<p>How should I proceed? Turing completeness is really tough to understand and so simulating a Turing Machine would be tougher I guess. What do you guys suggest?</p>

CC BY-SA 2.5
2010-10-09T11:37:35.517Z
(1) May I ask you why you want to implement a Turing machine using C++ templates?  (2) I do not know much about C++ and I do not know the proof of Turing completeness of C++ template metaprogramming either, but I would guess that you have to understand the proof first.
Tsuyoshi Ito
<pl.programming-languages><computability><turing-machines>
Template Metaprogramming and Turing Completeness
Prasoon Saurav
# Template Metaprogramming and Turing Completeness

(Asked by: username_0 on 2010-10-09)

I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will *actually* build a Turing machine ? I have read that C++ templates are Turing complete but I don't actually know how to prove this thing.

How should I proceed? Turing completeness is really tough to understand and so simulating a Turing Machine would be tougher I guess. What do you guys suggest?

**Tags:** pl.programming-languages, computability, turing-machines

> **Comments:**
> **username_1**: (1) May I ask you why you want to implement a Turing machine using C++ templates?  (2) I do not know much about C++ and I do not know the proof of Turing completeness of C++ template metaprogramming either, but I would guess that you have to understand the proof first.  

---

## 3 answers

### Answer by username_4 on 2010-10-09. Score: 9 | Accepted answer

The article you want is [C++ Templates are Turing Complete](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2003&rep=rep1&type=pdf) by Todd Verhuizen. It explains how things work in sufficient details. If you can faithfully encode a Turing machine and its behaviour in C++ templates, then this is sufficient to demonstrate Turing completeness.


---

### Answer by username_2 on 2010-10-09. Score: 2

Since templates are a compile-time applicative language you may find it tedious to encode a stateful model of computation like a Universal Turing Machine. Encoding some other Turing-equivalent model, like the Lambda Calculus, is a more straight forward approach.


---

### Answer by username_3 on 2010-10-09. Score: 1

The following post on StackOverflow might be useful: [What is Turing Complete?](https://stackoverflow.com/q/7284/459391)

You may also consult the corresponding [Wikipedia entry](http://en.wikipedia.org/wiki/Turing_completeness).

Moreover, you may consider taking a look at [C++ Simulator of a Turing Machine](http://savannah.nongnu.org/projects/turing-mach/) before implementing one from scratch (unless your objective is to learn, rather than use).

> **Comments:**
> **username_4**: Sadeq, he wants to do the implementation using C++ templates, not just regular C++. It's a whole new level of insanity.  

---

