clang/test/SemaCXX/constexpr-turing.cpp

   1 // RUN: %clang_cc1 -verify -std=c++11 %s
   2 // RUN: %clang_cc1 -verify -std=c++11 %s -fexperimental-new-constant-interpreter
   3 // expected-no-diagnostics
   4
   5 // A direct proof that constexpr is Turing-complete, once DR1454 is implemented.
   6
   7 const unsigned halt = (unsigned)-1;
   8
   9 enum Dir { L, R };
  10 struct Action {
  11   bool tape;
  12   Dir dir;
  13   unsigned next;
  14 };
  15 using State = Action[2];
  16
  17 // An infinite tape!
  18 struct 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 : false
  25                  : 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 };
  31 constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
  32 constexpr 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 of
  35 // steps taken until halt.
  36 constexpr 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.
  44 constexpr State bb3[] = {
  45   { { true, R, 1 }, { true, R, halt } },
  46   { { true, L, 1 }, { false, R, 2 } },
  47   { { true, L, 2 }, { true, L, 0 } }
  48 };
  49 static_assert(run(bb3, Tape(), 0) == 21, "");
  50
  51 // 4-state busy beaver. S(bb4) = 107.
  52 constexpr 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 } } };
  57 static_assert(run(bb4, Tape(), 0) == 107, "");