summaryrefslogtreecommitdiff
path: root/clang/test/SemaCXX/constexpr-turing.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clang/test/SemaCXX/constexpr-turing.cpp')
-rw-r--r--clang/test/SemaCXX/constexpr-turing.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/clang/test/SemaCXX/constexpr-turing.cpp b/clang/test/SemaCXX/constexpr-turing.cpp
new file mode 100644
index 0000000..c515378
--- /dev/null
+++ b/clang/test/SemaCXX/constexpr-turing.cpp
@@ -0,0 +1,55 @@
+// RUN: %clang_cc1 -verify -std=c++11 %s
+
+// A direct proof that constexpr is Turing-complete, once DR1454 is implemented.
+
+const unsigned halt = (unsigned)-1;
+
+enum Dir { L, R };
+struct Action {
+ bool tape;
+ Dir dir;
+ unsigned next;
+};
+using State = Action[2];
+
+// An infinite tape!
+struct Tape {
+ constexpr Tape() : l(0), val(false), r(0) {}
+ constexpr Tape(const Tape &old, bool write) :
+ l(old.l), val(write), r(old.r) {}
+ constexpr Tape(const Tape &old, Dir dir) :
+ l(dir == L ? old.l ? old.l->l : 0 : &old),
+ val(dir == L ? old.l ? old.l->val : false
+ : old.r ? old.r->val : false),
+ r(dir == R ? old.r ? old.r->r : 0 : &old) {}
+ const Tape *l;
+ bool val;
+ const Tape *r;
+};
+constexpr Tape update(const Tape &old, bool write) { return Tape(old, write); }
+constexpr Tape move(const Tape &old, Dir dir) { return Tape(old, dir); }
+
+// Run turing machine 'tm' on tape 'tape' from state 'state'. Return number of
+// steps taken until halt.
+constexpr unsigned run(const State *tm, const Tape &tape, unsigned state) {
+ return state == halt ? 1 :
+ run(tm, move(update(tape, tm[state][tape.val].tape),
+ tm[state][tape.val].dir),
+ tm[state][tape.val].next) + 1;
+}
+
+// 3-state busy beaver. 14 steps.
+constexpr State bb3[] = {
+ { { true, R, 1 }, { true, L, 2 } },
+ { { true, L, 0 }, { true, R, 1 } },
+ { { true, L, 1 }, { true, R, halt } }
+};
+static_assert(run(bb3, Tape(), 0) == 14, "");
+
+// 4-state busy beaver. 108 steps.
+constexpr State bb4[] = {
+ { { true, R, 1 }, { true, L, 1 } },
+ { { true, L, 0 }, { false, L, 2 } },
+ { { true, R, halt }, { true, L, 3 } },
+ { { true, R, 3 }, { false, R, 0 } } };
+static_assert(run(bb4, Tape(), 0) == 108, "");