| 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 | |
|---|