Richard Smith | 83587db | 2012-02-15 02:18:13 +0000 | [diff] [blame] | 1 | // RUN: %clang_cc1 -verify -std=c++11 %s |
Andy Gibbs | 8e8fb3b | 2012-10-19 12:44:48 +0000 | [diff] [blame] | 2 | // expected-no-diagnostics |
Richard Smith | 83587db | 2012-02-15 02:18:13 +0000 | [diff] [blame] | 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 ? 1 : |
| 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. 14 steps. |
| 43 | constexpr State bb3[] = { |
| 44 | { { true, R, 1 }, { true, L, 2 } }, |
| 45 | { { true, L, 0 }, { true, R, 1 } }, |
| 46 | { { true, L, 1 }, { true, R, halt } } |
| 47 | }; |
| 48 | static_assert(run(bb3, Tape(), 0) == 14, ""); |
| 49 | |
| 50 | // 4-state busy beaver. 108 steps. |
| 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) == 108, ""); |