ADD_STATE(A);
ADD_RULE(A, 1, 0, Right, A);
ADD_RULE(A, 0, 1, Right, A);
ADD_RULE(A, Blank, Blank, Hold, Stop);
using tape = Tape<1, 1, 0, 1, Blank>;
using machine = Machine<A, 0, tape>;
using result = Run<machine>::type;
int main() {
print(tape());
print(result());
return 0;
}
The output of this program is1 1 0 1 _ 0 0 1 0 _I'm going to break the whole task of constructing a Turing Machine (TM further) into comprehensible sub-tasks:
1. A tape containing symbols or numbers
2. A way to read and modify the tape
3. A way to move the tape right and left and extend the tape if needed
4. A system of states and transition rules
5. A way to calculate one execution step
6. A way to run the execution until the Stop state is reached
All calculations we are going to perform must be performed on types and constant expressions, rather than on usual variables. To comply with C++ standard library, the following way of computing things will be used further on:
// a declaration of operation template:
template<class>
class Operation;
// a specialization of operation for some particular input type:
template<class Input>
class Operation {
public:
// a type holding an output of operation
using type = typename Output;
}
Using "type" as an alias for result of the operation will allow some nice tricks with std::conditional and std::integral_constant.1. As long as TM uses a finite alphabet, we can map all possible symbols to ints as use them as contents of the tape without loss of generality. Let's assume that Blank symbol is represented by -1.
constexpr int Blank = -1;Here comes the Tape:
template<int... xs>
class Tape {
public:
using type = Tape<xs...>;
constexpr static int length = sizeof...(xs);
};
One of the first thing to do with the tape is to print it to screen, so we can see it's contents. The print function is going to be the only function in the whole system:
template<class T>
void print(T);
template<>
void print(Tape<>) {
std::cout << std::endl;
}
template<int x, int... xs>
void print(Tape<x, xs...>) {
if (x == Blank) {
std::cout << "_ ";
} else {
std::cout << x << " ";
}
print(Tape<xs...>());
}
A standard template recursion trick is used. Here is the ideone run with what we have so far https://ideone.com/DBHSC62. Before getting to reading and writing, we will have to create some helper operations:
template<class, class>
class Concatenate;
template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
using type = Tape<xs..., ys...>;
};
Concatenation is pretty straightforward and easy.
template<class>
class Invert;
template<>
class Invert<Tape<>> {
public:
using type = Tape<>;
};
template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
using type = typename Concatenate<
typename Invert<Tape<xs...>>::type,
Tape<x>
>::type;
};
Inversion is a bit trickier: we take the first symbol of the tape, put it in the end and concatenate it with inversion of the tail. Under the hood this construction causes a template recursion which ends up with desired result. Here is a sample run: https://ideone.com/47GKNpReading symbols from the tape is where the magic comes in:
template<int, class>
class Read;
template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant<int, x>,
Read<n - 1, Tape<xs...>>
>::type::type;
};
The logic is quite simple: if n equals zero, we return the first symbol wrapped in std::integral_constant, if n is greater than zero, we decrement it and throw away the first symbol. What does ::type::type stand for? The first one refers to std::conditional: std::conditional<T, A, B>::type equals to A if T is true and to B otherwise. So depending on the value of n the whole construction will transform to one of the following:using type = std::integral_constant<int, x>::type; using type = Read<n - 1, Tape<xs...>>::type;The the first line is equivalent to type = std::integral_constant<int, x> and the second one will cause a recursion calculation. But why can't we just write the that code like this:
template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant<int, x>,
typename Read<n - 1, Tape<xs...>>::type
>::type;
};
? Here's the tricky part: in the first case a template Read<n - 1, Tape<xs...>> will be instantiated depending on the value of n, in the second it will be instantiated always, because we explicitly access inner alias (::type). So if we just mention a template it won't be instantiated, if we access any member of it in normal or instantiated code, the compiler will create an instance. In the second exampletypename Read<n - 1, Tape<xs...>>::typewill cause an infinite recursion to unfold and the compilation will eventually stop with an error. ::type::type approach will be extensively used in the code below. Here are some examples of the Read operation: https://ideone.com/vEyASt
Writing a symbol is the hardest part here. Writing can be viewed as breaking the tape into three parts: head, symbol and tail, replacing the symbol with a new symbol and concatenating everything back. To perform such an operation we need a way to retrieve a head and a tail.
template<int, class>
class NLast;
template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
using type = typename std::conditional<
(n == sizeof...(xs)),
Tape<xs...>,
NLast<n, Tape<xs...>>
>::type::type;
};
template<int, class>
class NFirst;
template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
using type = typename Invert<
typename NLast<
n, typename Invert<Tape<xs...>>::type
>::type
>::type;
};
To get n last symbols we shorten the tape by removing the first symbol until it's length equals n. And to get first n symbols we revert the tape, take n last symbols and revert it back. Usage examples: https://ideone.com/igYF3W You can use the fork button to modify the code, check other inputs and better understand what is going on.
template<int, int, class>
class Write;
template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
using type = typename Concatenate<
typename Concatenate<
typename NFirst<pos, Tape<xs...>>::type,
Tape<x>
>::type,
typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
>::type;
};
It may look scary, but is actually pretty straightforward knowing how it works. Examples: https://ideone.com/w2mUdhAt this moment we have a way to store the tape and to read and write arbitrary symbols. The next step is to move things.
3. Our TM will support three moving operations: Hold, Left and Right. Each of them must calculate two things: a new position and a new tape, given the current tape and position. If we are in position 0 and we want to move left, the tape must be expanded, same for moving right when we reach the tail. The default symbol will be Blank.
template<int, class>
class Hold;
template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
constexpr static int position = pos;
using tape = Tape<xs...>;
};
template<int, class>
class Left;
template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
constexpr static int position = typename std::conditional<
(pos > 0),
std::integral_constant<int, pos - 1>,
std::integral_constant<int, 0>
>::type();
using tape = typename std::conditional<
(pos > 0),
Tape<xs...>,
Tape<Blank, xs...>
>::type;
};
template<int, class>
class Right;
template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
constexpr static int position = pos + 1;
using tape = typename std::conditional<
(pos < sizeof...(xs) - 1),
Tape<xs...>,
Tape<xs..., Blank>
>::type;
};
Here a constant expression is used to calculate position. After we obtained a std::integral_constant holding a new position, we invoke a () operator to get the actual number. Here are some example runs: https://ideone.com/m5OTaT4. And now we can get to states. If the machine is in some particular state and it reads some particular symbol from the tape, we want to know three things: what to write, where to move and what is the next state. I've decided to implement a state system as a group of template specializations corresponding to each transition rule where the input symbol is a template parameter. Some transition rule for state some state will look like this:
template<>
class A<0> {
public:
constexpr static int write = 1;
template<int pos, class tape>
using move = Right<pos, tape>;
template<int x>
using next = B<x>;
};
Here a cool C++ feature is used called alias template. "move" and "next" fields of A<0> are not just types, they are class templates, which will be directly used by TM for the calculation of the next step. To make adding new states and transition rules easy we can use preprocessor macros. A state used to indicate that simulation should is called Stop.5. Now we are going to create a Machine class that will hold the whole system. Machine will be parameterized by current state, position and tape with symbols. The only thing we want Machine to do is to make a simulation step by calculating it's next state.
template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
using state = State<symbol>;
template<int x>
using nextState = typename State<symbol>::template next<x>;
using move = typename state::template move<pos, modifiedTape>;
constexpr static int nextPos = move::position;
using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
using nextTape = typename move::tape;
public:
using step = Machine<nextState, nextPos, nextTape>;
};
At first we read the tape at current position and save the result as "symbol". After that we instantiate a State template, which will give us a transition rule. Next state given by the following expression.template<int x> using nextState = typename State<symbol>::template next<x>;Note the "template" keyword prior to "next<x>". According to the standard, the member template name must be prefixed by the keyword "template" when used after "::".
To calculate the next version of the tape, we need to write a new symbol ("using modifiedTape =") and extend the tape if necessary ("using nextTape ="). Getting the new position is pretty obvious.
Finally, when everything is set up we can return the next state of the system as step. At this point we can actually program our TM and watch how it moves by adding a few dump functions: https://ideone.com/XuBDry In this example we can see how our machine actually moves right and replaces symbols with other symbols.
6. It seems like everything is working, but we need to go deeper: an input to the computation is an initial state, position and tape, and the output should be a modified tape when the machine reaches "Stop" state.
template<class>
class Run;
template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
using step = typename Machine<State, pos, Tape<xs...>>::step;
public:
using type = typename std::conditional<
std::is_same<State<0>, Stop<0>>::value,
Tape<xs...>,
Run<step>
>::type::type;
};
To check if the machine should stop, we instantiate it's current state and the Stop state with 0 as a parameter and compare resulting types with std::is_same. If they are equal, current tape is returned as a result, otherwise another step is performed.Now is a perfect time to write something serious, let's do binary increment. Assuming that binary number is written on the tape as we would normally write it on paper, here's code:
ADD_STATE(S0);
ADD_STATE(S1);
ADD_STATE(S2);
ADD_RULE(S0, Blank, Blank, Left, S1);
ADD_RULE(S0, 0, 0, Right, S0);
ADD_RULE(S0, 1, 1, Right, S0);
ADD_RULE(S1, Blank, 1, Right, S2);
ADD_RULE(S1, 0, 1, Left, S2);
ADD_RULE(S1, 1, 0, Left, S1);
ADD_RULE(S2, Blank, Blank, Hold, Stop);
ADD_RULE(S2, 0, 0, Right, S2);
ADD_RULE(S2, 1, 1, Right, S2);
using tape = Tape<Blank, 1, 1, 0, Blank>;
using result = Run<Machine<S0, tape::length - 1, tape>>::type;
int main() {
print(tape());
print(result());
return 0;
}
Here's the ideone run: https://ideone.com/AgK4nxBut what if we want to make several increments? No problem, let's wrap the whole operation into a class.
template<class>
class Increment { };
template<int... xs>
class Increment<Tape<xs...>> {
public:
using type = typename Run<Machine<S0, Tape<xs...>::length - 1, Tape<xs...>>>::type;
};
using tape = Tape<Blank, 1, 1, 0, Blank>;
int main() {
print(tape());
print(Increment<tape>::type());
print(Increment<Increment<tape>::type>::type());
print(Increment<Increment<Increment<tape>::type>::type>::type());
print(Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type());
print(Increment<Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type>::type());
return 0;
}
https://ideone.com/zPyu6B Well, it definitely looks like a binary increment to me.And that's it, thanks for reading. You can check out the code on github along with some busy beavers and other examples: https://github.com/fnz/CTTM
