1 // RUN: %clang_cc1 -verify -std=c++11 %s
2 
3 // A direct proof that constexpr is Turing-complete, once DR1454 is implemented.
4 
5 const unsigned halt = (unsigned)-1;
6 
7 enum Dir { L, R };
8 struct Action {
9   bool tape;
10   Dir dir;
11   unsigned next;
12 };
13 using State = Action[2];
14 
15 // An infinite tape!
16 struct Tape {
17   constexpr Tape() : l(0), val(false), r(0) {}
18   constexpr Tape(const Tape &old, bool write) :
19     l(old.l), val(write), r(old.r) {}
20   constexpr Tape(const Tape &old, Dir dir) :
21     l(dir == L ? old.l ? old.l->l : 0 : &old),
22     val(dir == L ? old.l ? old.l->val : false
23                  : old.r ? old.r->val : false),
24     r(dir == R ? old.r ? old.r->r : 0 : &old) {}
25   const Tape *l;
26   bool val;
27   const Tape *r;
28 };
29 constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
30 constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }
31 
32 // Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
33 // steps taken until halt.
34 constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
35   return state == halt ? 1 :
36          run(tm, move(update(tape, tm[state][tape.val].tape),
37                       tm[state][tape.val].dir),
38              tm[state][tape.val].next) + 1;
39 }
40 
41 // 3-state busy beaver. 14 steps.
42 constexpr State bb3[] = {
43   { { true, R, 1 }, { true, L, 2 } },
44   { { true, L, 0 }, { true, R, 1 } },
45   { { true, L, 1 }, { true, R, halt } }
46 };
47 static_assert(run(bb3, Tape(), 0) == 14, "");
48 
49 // 4-state busy beaver. 108 steps.
50 constexpr State bb4[] = {
51   { { true, R, 1 }, { true, L, 1 } },
52   { { true, L, 0 }, { false, L, 2 } },
53   { { true, R, halt }, { true, L, 3 } },
54   { { true, R, 3 }, { false, R, 0 } } };
55 static_assert(run(bb4, Tape(), 0) == 108, "");
56