58 lines · cpp
1// RUN: %clang_cc1 -verify -std=c++11 %s2// RUN: %clang_cc1 -verify -std=c++11 %s -fexperimental-new-constant-interpreter3// expected-no-diagnostics4 5// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.6 7const unsigned halt = (unsigned)-1;8 9enum Dir { L, R };10struct Action {11 bool tape;12 Dir dir;13 unsigned next;14};15using State = Action[2];16 17// An infinite tape!18struct Tape {19 constexpr Tape() : l(0), val(false), r(0) {}20 constexpr Tape(const Tape &old, bool write) :21 l(old.l), val(write), r(old.r) {}22 constexpr Tape(const Tape &old, Dir dir) :23 l(dir == L ? old.l ? old.l->l : 0 : &old),24 val(dir == L ? old.l ? old.l->val : false25 : old.r ? old.r->val : false),26 r(dir == R ? old.r ? old.r->r : 0 : &old) {}27 const Tape *l;28 bool val;29 const Tape *r;30};31constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }32constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }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, const Tape &tape, unsigned state) {37 return state == halt ? 0 :38 run(tm, move(update(tape, tm[state][tape.val].tape),39 tm[state][tape.val].dir),40 tm[state][tape.val].next) + 1;41}42 43// 3-state busy beaver. S(bb3) = 21.44constexpr State bb3[] = {45 { { true, R, 1 }, { true, R, halt } },46 { { true, L, 1 }, { false, R, 2 } },47 { { true, L, 2 }, { true, L, 0 } }48};49static_assert(run(bb3, Tape(), 0) == 21, "");50 51// 4-state busy beaver. S(bb4) = 107.52constexpr State bb4[] = {53 { { true, R, 1 }, { true, L, 1 } },54 { { true, L, 0 }, { false, L, 2 } },55 { { true, R, halt }, { true, L, 3 } },56 { { true, R, 3 }, { false, R, 0 } } };57static_assert(run(bb4, Tape(), 0) == 107, "");58