67 lines · cpp
1// RUN: %clang_cc1 -verify -std=c++2a %s2// expected-no-diagnostics3 4const unsigned halt = (unsigned)-1;5 6enum Dir { L, R };7struct Action {8 bool tape;9 Dir dir;10 unsigned next;11};12using State = Action[2];13 14// An infinite tape!15struct Tape {16 constexpr Tape() = default;17 constexpr ~Tape() {18 if (l) { l->r = nullptr; delete l; }19 if (r) { r->l = nullptr; delete r; }20 }21 constexpr Tape *left() {22 if (!l) { l = new Tape; l->r = this; }23 return l;24 }25 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 of35// steps taken until halt.36constexpr 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.53constexpr State bb3[] = {54 { { true, R, 1 }, { true, R, halt } },55 { { true, L, 1 }, { false, R, 2 } },56 { { true, L, 2 }, { true, L, 0 } }57};58static_assert(run(bb3) == 21, "");59 60// 4-state busy beaver. S(bb4) = 107.61constexpr 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 } } };66static_assert(run(bb4) == 107, "");67