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