2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Oct 9 '10 at 11:37
9
$\begingroup$

The article you want is C++ Templates are Turing Complete 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The following post on StackOverflow might be useful: What is Turing Complete?

You may also consult the corresponding Wikipedia entry.

Moreover, you may consider taking a look at C++ Simulator of a Turing Machine before implementing one from scratch (unless your objective is to learn, rather than use).

$\endgroup$
  • 4
    $\begingroup$ Sadeq, he wants to do the implementation using C++ templates, not just regular C++. It's a whole new level of insanity. $\endgroup$ – Dave Clarke Oct 9 '10 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.