A note -- if you're linking to arXiv, it's better to link to the abstract (<a href="http://arxiv.org/abs/1412.0784" rel="nofollow">http://arxiv.org/abs/1412.0784</a>) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!
I felt sad when I finally completed Braid. It's still one of the best games I've ever played and I knew I was never going to find something like that again. This paper brought me back to that sense of wonder that I had the first time I played Braid.
What an excellently well written paper! It does all the basics right - describes it's objective, the domain of the problem, a quick example (Rush hour) to nudge some intuition toward the reader, before going on to prove undecidability. It even tackles the decidability of another "should-obviously-work" (Bounded braid) idea that the author had (turns out to be decidable).<p>Also, I wonder if most programmers have unknowingly built a ton of Braid intuition because of the way the time reversal tree matches the way we model the undo tree in $EDITOR.
It is rather easy to build behaviors in systems that are Turing-complete (thus undecidable). What is more complicated is building nontrivial models (i.e. showing complex behavior) that are still decidable or even decidable in polynomial time.
Jonathan Blow, creator of Braid, is coming out with a new game called "The Witness" pretty Soon™.<p><a href="http://the-witness.net/news/" rel="nofollow">http://the-witness.net/news/</a>
I could use some guidance, as I seem to have gotten lost.<p>The implementation of the counter is IO (the levers that Tim pulls), ADD, SUB (branch if 0), M1 (the counter).. and then M2.<p>M2 is the counter that holds the monsters as they are subtracted from M1. It is also used as IO for the branch part of SUB (if I understood the article correctly).<p>Therefore, if I call SUB with M2 = 0, then the counter will malfunction.<p>I think that the consequence of this is that the given function has a decided halting point.(Branching was taken out). I have no idea how to say this in a better way, sadly my computer science education is tragically lacking.