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