Edited at

C++のtemplateのチューリング完全性について

More than 1 year has passed since last update.


まずはソースコードを見てましょう

#include <iostream>

using namespace std;

template <int N>
class Turing{
public:
void print(){
cout << N << endl;
}

Turing<N + 1> incl(){
return Turing<N + 1>();
}

template<int M>
Turing<N + M> add(Turing<M> a){
return Turing<N + M>();
}

void fizzbuzz(){
if(N > 0){
Turing<N - 1>().fizzbuzz();
}

if(N % 15 == 0){
cout << "fizzbuzz" << endl;
}if(N % 3 == 0){
cout << "fizz" << endl;
}if(N % 5 == 0){
cout << "buzz" << endl;
} else {
cout << N << endl;
}
}
};

template<>
class Turing<0>{
public:
void fizzbuzz(){
}
};

int main() {
Turing<5> a;
Turing<6> b;
Turing<100>().add(b).print();
Turing<-1> t;
t.fizzbuzz();
// your code goes here
return 0;
}


解説

上のソースコードではtemplateののNの部分をチューリングマシンのテープとして扱い、関数内部の処理をチューリングマシンのヘッダとして扱います。なので、二つ変数を使いたいときは template のようにしたり、配列を使いたいときは可変長引数にすればいいですよね。関数の名前はLisp風にしたので比較的直感的に理解できると思います


#include <iostream>

using namespace std;

template<int head = 0, int... tail>
class Turing{
public:
template <int new_head>
Turing<new_head, head, tail...> cons(){
return Turing<new_head, head, tail...>();
}

void print(){
cout << head << " ";
if(sizeof...(tail) != 0){
Turing<tail...>().print();
}else{
cout << endl;
}
}

Turing<head * 2, (tail * 2)...> map_double(){
return Turing<head * 2, (tail * 2)...>();
}

template<int... appended>
Turing<head, tail..., appended...> append(){
return Turing<head, tail..., appended...>();
}

Turing<head> car(){
return Turing<head>();
}

Turing<tail...> cdr(){
return Turing<tail...>();
}
};

int main(){
Turing<1, 2, 3>().map_double().print();
return 0;
}