1 // RUN: %clang_cc1 -verify -std=c++2a %s
2 // expected-no-diagnostics
3
4 const unsigned halt = (unsigned)-1;
5
6 enum Dir { L, R };
7 struct Action {
8 bool tape;
9 Dir dir;
10 unsigned next;
11 };
12 using State = Action[2];
13
14 // An infinite tape!
15 struct Tape {
16 constexpr Tape() = default;
~TapeTape17 constexpr ~Tape() {
18 if (l) { l->r = nullptr; delete l; }
19 if (r) { r->l = nullptr; delete r; }
20 }
leftTape21 constexpr Tape *left() {
22 if (!l) { l = new Tape; l->r = this; }
23 return l;
24 }
rightTape25 constexpr Tape *right() {
26 if (!r) { r = new Tape; r->l = this; }
27 return r;
28 }
29 Tape *l = nullptr;
30 bool val = false;
31 Tape *r = nullptr;
32 };
33
34 // Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
35 // steps taken until halt.
run(const State * tm)36 constexpr unsigned run(const State *tm) {
37 Tape *tape = new Tape;
38 unsigned state = 0;
39 unsigned steps = 0;
40
41 for (state = 0; state != halt; ++steps) {
42 auto [val, dir, next_state] = tm[state][tape->val];
43 tape->val = val;
44 tape = (dir == L ? tape->left() : tape->right());
45 state = next_state;
46 }
47
48 delete tape;
49 return steps;
50 }
51
52 // 3-state busy beaver. S(bb3) = 21.
53 constexpr State bb3[] = {
54 { { true, R, 1 }, { true, R, halt } },
55 { { true, L, 1 }, { false, R, 2 } },
56 { { true, L, 2 }, { true, L, 0 } }
57 };
58 static_assert(run(bb3) == 21, "");
59
60 // 4-state busy beaver. S(bb4) = 107.
61 constexpr State bb4[] = {
62 { { true, R, 1 }, { true, L, 1 } },
63 { { true, L, 0 }, { false, L, 2 } },
64 { { true, R, halt }, { true, L, 3 } },
65 { { true, R, 3 }, { false, R, 0 } } };
66 static_assert(run(bb4) == 107, "");
67