1 // RUN: %clang_cc1 -verify -std=c++11 %s 2 // expected-no-diagnostics 3 4 // A direct proof that constexpr is Turing-complete, once DR1454 is implemented. 5 6 const unsigned halt = (unsigned)-1; 7 8 enum Dir { L, R }; 9 struct Action { 10 bool tape; 11 Dir dir; 12 unsigned next; 13 }; 14 using State = Action[2]; 15 16 // An infinite tape! 17 struct Tape { 18 constexpr Tape() : l(0), val(false), r(0) {} 19 constexpr Tape(const Tape &old, bool write) : 20 l(old.l), val(write), r(old.r) {} 21 constexpr Tape(const Tape &old, Dir dir) : 22 l(dir == L ? old.l ? old.l->l : 0 : &old), 23 val(dir == L ? old.l ? old.l->val : false 24 : old.r ? old.r->val : false), 25 r(dir == R ? old.r ? old.r->r : 0 : &old) {} 26 const Tape *l; 27 bool val; 28 const Tape *r; 29 }; 30 constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); } 31 constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); } 32 33 // Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of 34 // steps taken until halt. 35 constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) { 36 return state == halt ? 0 : 37 run(tm, move(update(tape, tm[state][tape.val].tape), 38 tm[state][tape.val].dir), 39 tm[state][tape.val].next) + 1; 40 } 41 42 // 3-state busy beaver. S(bb3) = 21. 43 constexpr State bb3[] = { 44 { { true, R, 1 }, { true, R, halt } }, 45 { { true, L, 1 }, { false, R, 2 } }, 46 { { true, L, 2 }, { true, L, 0 } } 47 }; 48 static_assert(run(bb3, Tape(), 0) == 21, ""); 49 50 // 4-state busy beaver. S(bb4) = 107. 51 constexpr State bb4[] = { 52 { { true, R, 1 }, { true, L, 1 } }, 53 { { true, L, 0 }, { false, L, 2 } }, 54 { { true, R, halt }, { true, L, 3 } }, 55 { { true, R, 3 }, { false, R, 0 } } }; 56 static_assert(run(bb4, Tape(), 0) == 107, ""); 57
