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?
$\begingroup$
$\endgroup$
1
-
$\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$– usulDec 19, 2016 at 3:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
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, 2016 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$ Oct 17, 2016 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, 2016 at 8:19
-
-