Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Braid is undecidable (2014) [pdf]

arxiv.org

Post reply on HN
Print view View original

1–10 of 31 posts

Re: Braid is undecidable (2014) [pdf]

#2

Post by wolfgke »

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.

Re: Braid is undecidable (2014) [pdf]

#3

Post by spranesh »

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).

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.

Re: Braid is undecidable (2014) [pdf]

#4

Post by xacaxulu »

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.

Re: Braid is undecidable (2014) [pdf]

#5

Post by pdpi »

xacaxulu wrote: post #4

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.

That very last stage stands in my memory as one of the best uses of game mechanics as part of the story telling I've ever seen. It's the rare sort of thing that truly makes games an art of its own, rather than some sort of "interactive movie".

Re: Braid is undecidable (2014) [pdf]

#7

Post by Sniffnoy »

A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/1412.0784) 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!

Re: Braid is undecidable (2014) [pdf]

#9

Post by mushishi »

xacaxulu wrote: post #4

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.

Yes it is. Hopefully Blow's the Witness will as awesome.

Also consider playing the following if you have thirst for puzzle games

    - The Swapper
    - Snakebird
    - Spacechem
    - Starseed Pilgrim (this one I haven't played but Blow recommended it, iirc)

Re: Braid is undecidable (2014) [pdf]

#10

Post by secant »

wolfgke wrote: post #2

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.

I'm a bit of a math novice, but is the term "decidable" analogous with satisfiability (SAT), or is this a completely different set of modelling?
Post reply on HN