5 ms·

Baba Is Turing Complete: A Sketch of a Proof

105 points by lelf 7y ago

taneq 7y ago
That's pretty neat. Is there a name for the thing where you generalise something to be an infinite version of itself, then show that that infinite version is Turing complete, then transfer that back to the original finite thing? Sort of like we are willing to call real physical computers 'Turing complete' despite them clearly not having infinite memory.
- davidgrenier 7y ago
  Closest thing I could find was involved in proving the finite version of Ramsey's Theorem from the infinite version as a compactness argument. https://en.wikipedia.org/wiki/Compactness_theorem https://en.wikipedia.org/wiki/Compactness_theorem That being said, I'm a little curious as to why one would want to prove something is Turing complete. I tend to assume something is Turing complete unless shown otherwise. For instance, I would never have gambled MTG wasn't Turing complete.
  - mannykannot 7y ago
    At the very least, proving that a game is Turing complete can be as entertaining a challenge as playing it. One case where Turing completeness was useful was in proving wrong those programmers who claimed that there were some programs that just could not be written using structured programming. Also, if we did not know about Turing completeness, there would be constant futile research trying to find alternative architectures and languages that could solve problems that cannot be solved with what we have.
  - Retra 7y ago
    I think it is probably more useful to prove that something isn't Turing complete, and explain why. Finding things that are Turing complete is the basically the same task through a complementary lens.
- mannykannot 7y ago
  It is more or less obligatory to do it this way; if you tried to avoid generalizing to an infinite version, you would have to qualify various arguments with something like "assuming sufficient resources...", which amounts to the same thing. No finite state machine is strictly Turing-complete, but the category of those that would be, but for the resource limitation, is an extremely useful one.
  - taneq 7y ago
    I guess I was hoping for a snappy term like "finite Turing-complete" or something.
    - theoh 7y ago
      The "generalizing" process is called idealization. Whenever Turing machines are mentioned, it's an idealized version of a machine that is being referred to. Every finite physical machine is limited in different way, so it doesn't make much sense to try to lump them together. Whereas every Turing-complete machine is equivalent.
- empath75 7y ago
  Every time someone says something like minesweeper or PowerPoint is turing complete, some pedant will chime in that it isn’t, because it doesn’t have an infinite board/slides/whatever.
  - barbecue_sauce 7y ago
    But with that line of reasoning, would there be anything that is actually turing complete?
    - mcphage 7y ago
      Just mathematical constructs.
crtasm 7y ago
This is concerning an award winning puzzle game in which you can manipulate even the most basic rules of play: https://en.wikipedia.org/wiki/Baba_Is_You https://en.wikipedia.org/wiki/Baba_Is_You
- minimaxir 7y ago
  Baba is You is a good metaphor for programming; the puzzle design is dependent on recognizing the "trick", but even if you do recognize the trick, there will always be a catch or a one-off error that's difficult to solve.
  - nlawalker 7y ago
    Plus many of the puzzles iterate on previous puzzles. You'll solve a puzzle, then find that the next one is almost the same but has one tiny difference that completely closes the door on your previous solution without opening any obvious new ones. These are great, because it often makes the second puzzle look completely impossible on first glance.
- deleted 7y ago
  [deleted]
mcv 7y ago
I'm not remotely surprised that Baba Is You is Turing Complete. I shudder at the thought of a Turning Machine running on it, though. It sounds like the worst possible self-modifying code hell.
- vanderZwan 7y ago
  If you look at it with the perspective of an engineer, it's the worst If you look at it with the perspective of an artist, it's absolutely glorious I think there is enough space in the world for both (as long as they don't get mixed up at the wrong moment). See also Daniel Temkin's "The Less Humble Programmer" [0] https://esoteric.codes/blog/the-less-humble-programmer https://esoteric.codes/blog/the-less-humble-programmer
- pdkl95 7y ago
  > I shudder at the thought of a Turning Machine running on it A mechanical bf interpreter in Opus Magnum[1]. Self modifying code hell appears to result in a much more compact machine... at the cost of sanity. [1] https://www.youtube.com/watch?v=Ll0qHlx_qLg https://www.youtube.com/watch?v=Ll0qHlx_qLg (baba is you is an amazingly elegant game)
modernerd 7y ago
Some visual proofs of Turing completeness: https://twitter.com/shr_em/status/1127922245743960064 https://twitter.com/shr_em/status/1127922245743960064 https://twitter.com/mattar0d/status/1109987662608384000 https://twitter.com/mattar0d/status/1109987662608384000 The game for those who are new to it — well worth playing! https://hempuli.itch.io/baba https://hempuli.itch.io/baba
- sp332 7y ago
  And here's one for Conway's Game of Life https://twitter.com/fengchuiyulin/status/1110423064020480000 https://twitter.com/fengchuiyulin/status/1110423064020480000
ayakura 7y ago
Baba is one of those games where the learning curve is absolutely sublime and gives the player so much satisfaction after figuring out some of the puzzles. Don't play this sitting on the toilet though, it's going to be a long toilet session
dharma1 7y ago
The author talks about the game and how he created it - https://www.youtube.com/watch?v=Vd_-4lp7hZk https://www.youtube.com/watch?v=Vd_-4lp7hZk
daenz 7y ago
Baba Is You is one of my top 3 games for programming-minded people (the other two being Factorio and Shenzhen IO). It's an amazing game to play with non-programmers as well. Basically each puzzle design is crafted to hinge on some incorrect assumption you hold about the rules of the game. Only by thinking very carefully can you uncover this wrong assumption, and then it becomes a tool in your toolbox for future levels.
joker3 7y ago
Everything is Turing complete until proven otherwise.
emmelaich 7y ago
At a glance it looks a LOT like https://en.wikipedia.org/wiki/Chip%27s_Challenge https://en.wikipedia.org/wiki/Chip%27s_Challenge

105 points by lelf 7y ago

That's pretty neat. Is there a name for the thing where you generalise something to be an infinite version of itself, then show that that infinite version is Turing complete, then transfer that back to the original finite thing? Sort of like we are willing to call real physical computers 'Turing complete' despite them clearly not having infinite memory.

davidgrenier 7y ago
Closest thing I could find was involved in proving the finite version of Ramsey's Theorem from the infinite version as a compactness argument. https://en.wikipedia.org/wiki/Compactness_theorem https://en.wikipedia.org/wiki/Compactness_theorem That being said, I'm a little curious as to why one would want to prove something is Turing complete. I tend to assume something is Turing complete unless shown otherwise. For instance, I would never have gambled MTG wasn't Turing complete.
- mannykannot 7y ago
  At the very least, proving that a game is Turing complete can be as entertaining a challenge as playing it. One case where Turing completeness was useful was in proving wrong those programmers who claimed that there were some programs that just could not be written using structured programming. Also, if we did not know about Turing completeness, there would be constant futile research trying to find alternative architectures and languages that could solve problems that cannot be solved with what we have.
- Retra 7y ago
  I think it is probably more useful to prove that something isn't Turing complete, and explain why. Finding things that are Turing complete is the basically the same task through a complementary lens.
mannykannot 7y ago
It is more or less obligatory to do it this way; if you tried to avoid generalizing to an infinite version, you would have to qualify various arguments with something like "assuming sufficient resources...", which amounts to the same thing. No finite state machine is strictly Turing-complete, but the category of those that would be, but for the resource limitation, is an extremely useful one.
- taneq 7y ago
  I guess I was hoping for a snappy term like "finite Turing-complete" or something.
  - theoh 7y ago
    The "generalizing" process is called idealization. Whenever Turing machines are mentioned, it's an idealized version of a machine that is being referred to. Every finite physical machine is limited in different way, so it doesn't make much sense to try to lump them together. Whereas every Turing-complete machine is equivalent.
empath75 7y ago
Every time someone says something like minesweeper or PowerPoint is turing complete, some pedant will chime in that it isn’t, because it doesn’t have an infinite board/slides/whatever.
- barbecue_sauce 7y ago
  But with that line of reasoning, would there be anything that is actually turing complete?
  - mcphage 7y ago
    Just mathematical constructs.

crtasm 7y ago

This is concerning an award winning puzzle game in which you can manipulate even the most basic rules of play: https://en.wikipedia.org/wiki/Baba_Is_You https://en.wikipedia.org/wiki/Baba_Is_You

minimaxir 7y ago
Baba is You is a good metaphor for programming; the puzzle design is dependent on recognizing the "trick", but even if you do recognize the trick, there will always be a catch or a one-off error that's difficult to solve.
- nlawalker 7y ago
  Plus many of the puzzles iterate on previous puzzles. You'll solve a puzzle, then find that the next one is almost the same but has one tiny difference that completely closes the door on your previous solution without opening any obvious new ones. These are great, because it often makes the second puzzle look completely impossible on first glance.
deleted 7y ago
[deleted]

mcv 7y ago

I'm not remotely surprised that Baba Is You is Turing Complete. I shudder at the thought of a Turning Machine running on it, though. It sounds like the worst possible self-modifying code hell.

vanderZwan 7y ago
If you look at it with the perspective of an engineer, it's the worst If you look at it with the perspective of an artist, it's absolutely glorious I think there is enough space in the world for both (as long as they don't get mixed up at the wrong moment). See also Daniel Temkin's "The Less Humble Programmer" [0] https://esoteric.codes/blog/the-less-humble-programmer https://esoteric.codes/blog/the-less-humble-programmer
pdkl95 7y ago
> I shudder at the thought of a Turning Machine running on it A mechanical bf interpreter in Opus Magnum[1]. Self modifying code hell appears to result in a much more compact machine... at the cost of sanity. [1] https://www.youtube.com/watch?v=Ll0qHlx_qLg https://www.youtube.com/watch?v=Ll0qHlx_qLg (baba is you is an amazingly elegant game)

modernerd 7y ago

Some visual proofs of Turing completeness: https://twitter.com/shr_em/status/1127922245743960064 https://twitter.com/shr_em/status/1127922245743960064 https://twitter.com/mattar0d/status/1109987662608384000 https://twitter.com/mattar0d/status/1109987662608384000 The game for those who are new to it — well worth playing! https://hempuli.itch.io/baba https://hempuli.itch.io/baba

sp332 7y ago
And here's one for Conway's Game of Life https://twitter.com/fengchuiyulin/status/1110423064020480000 https://twitter.com/fengchuiyulin/status/1110423064020480000

ayakura 7y ago

Baba is one of those games where the learning curve is absolutely sublime and gives the player so much satisfaction after figuring out some of the puzzles. Don't play this sitting on the toilet though, it's going to be a long toilet session

dharma1 7y ago

The author talks about the game and how he created it - https://www.youtube.com/watch?v=Vd_-4lp7hZk https://www.youtube.com/watch?v=Vd_-4lp7hZk

daenz 7y ago

Baba Is You is one of my top 3 games for programming-minded people (the other two being Factorio and Shenzhen IO). It's an amazing game to play with non-programmers as well. Basically each puzzle design is crafted to hinge on some incorrect assumption you hold about the rules of the game. Only by thinking very carefully can you uncover this wrong assumption, and then it becomes a tool in your toolbox for future levels.

joker3 7y ago

Everything is Turing complete until proven otherwise.

emmelaich 7y ago

At a glance it looks a LOT like https://en.wikipedia.org/wiki/Chip%27s_Challenge https://en.wikipedia.org/wiki/Chip%27s_Challenge