Baba Is Turing Complete: A Sketch of a Proof | Hacker News Reader

Baba Is Turing Complete: A Sketch of a Proof

twitlonger.com

105 pointslelf23 comments

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

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.

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.

Some visual proofs of Turing completeness:

https://twitter.com/shr_em/status/1127922245743960064

https://twitter.com/mattar0d/status/1109987662608384000

The game for those who are new to it — well worth playing!

https://hempuli.itch.io/baba

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

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.

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.

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

> 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

(baba is you is an amazingly elegant game)

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

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

At a glance it looks a LOT like

https://en.wikipedia.org/wiki/Chip%27s_Challenge

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.

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

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.

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.

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.

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.

I guess I was hoping for a snappy term like "finite Turing-complete" or something.

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.

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.

But with that line of reasoning, would there be anything that is actually turing complete?

Just mathematical constructs.

Everything is Turing complete until proven otherwise.

Reply on news.ycombinator.com