2
$\begingroup$

It's written in wikipedia https://en.wikipedia.org/wiki/Turing_completeness#Games that the video game Braid is Turing-complete.

I've played Braid before but I can hardly reconcile it with Turing completeness. In what sense is it Turing-complete?

$\endgroup$
  • $\begingroup$ Well first, I wonder in what sense any game is "Turing complete". (For example, what is the input and what is the output?) $\endgroup$ – usul Dec 19 '16 at 3:56
1
$\begingroup$

Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard.

Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing machine, and thus determining if any general Braid level is solvable is similar to solving the halting problem, which is undecidable.

$\endgroup$
  • 2
    $\begingroup$ How does the first paragraph answer the question? How does the undecidability of a question imply that it is Turing-complete? $\endgroup$ – Raphael Oct 16 '16 at 18:52
  • $\begingroup$ @Raphael I looked over the paper and I saw that their argument was exactly that. The author declares Braid is at least PSPACE because you can simulate a PSPACE game in it and that it is possibly undecidable because you can simulate a Turing machine in it. $\endgroup$ – VermillionAzure Oct 17 '16 at 1:18
  • 3
    $\begingroup$ 1) What does it mean if you say "a game is (at least) PSPACE"? Which decision problem are we looking at? 2) Simulating a Turing machine does not imply anything about decidability. Again, decidability of which problem? 3) Even if you could simulate all TMs, "the problem" may be decidable. 4) The question asks about Turing-completeness, not decidability. 5) Undecidability (of what?) does not imply Turing-completeness. $\endgroup$ – Raphael Oct 17 '16 at 8:19
  • $\begingroup$ Also, which paper? $\endgroup$ – Raphael Oct 17 '16 at 8:20
  • $\begingroup$ @Raphael arxiv.org/abs/1412.0784 $\endgroup$ – VermillionAzure Oct 17 '16 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.