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.

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"

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

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.

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.

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.

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.

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.

https://en.wikipedia.org/wiki/Baba_Is_You

reply