Turing machine: But why use template metaprogramming ?

Question

Hi there.

I am a final year engineering student. Me and my friends have decided that our final year project would be "Simulation of Turing Machine using Template Metaprogramming".

I understand what "Turing Machine" and "Template Metaprogramming" are but my question is why the simulation would be tedious if we design the Turing Machine without TMP? What advantages can we get if we us TMP and what would we miss/gain if we don't using TMP but use a conventional approach?

Any suggestions as to how we shall proceed?

Answer 1

The primary reason why one would implement Turing machines using template metaprogramming is not because it's easier than in "ordinary" C++ (it isn't), but to demonstrate that C++ templates are Turing complete.

Answer 2

I don't think there are advantages to designing a Turing machine simulation using template metaprogramming. It's actually rather more like fencing with both hands tied behind your back, holding your foil between your teeth.

The reason you'd do this is to familiarize yourself with the power of the C++ template system, and to prove that C++ templates (and therefore the C++ compiler) are Turing complete.

Answer 3

To show its TM-completeness, it is sufficient to implement the Lambda calculus.

Anyway, it might be easy to implement a restricted TM with bits as symbols and a max band length of 64bit, where the blanks are 0. An alternative could be to disallow to write the blancs and count the relative position of the left and right terminator; then it will be 65bit wide. An uint64_t will hold all bits to the right in BigEndian, and to the left in LittleEndian; the active bit has to be in an own template parameter. Either one bit on the band has to stay 0, or there are counters to mark the end of the band.