1// RUN: %clang_cc1 -verify -std=c++11 %s
2
3// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.
4
5const unsigned halt = (unsigned)-1;
6
7enum Dir { L, R };
8struct Action {
9  bool tape;
10  Dir dir;
11  unsigned next;
12};
13using State = Action[2];
14
15// An infinite tape!
16struct 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};
29constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
30constexpr 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.
34constexpr 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.
42constexpr State bb3[] = {
43  { { true, R, 1 }, { true, L, 2 } },
44  { { true, L, 0 }, { true, R, 1 } },
45  { { true, L, 1 }, { true, R, halt } }
46};
47static_assert(run(bb3, Tape(), 0) == 14, "");
48
49// 4-state busy beaver. 108 steps.
50constexpr 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 } } };
55static_assert(run(bb4, Tape(), 0) == 108, "");
56