Thread by @AlanZucconi

This is a list of TEN (plus one) games that are "accidentally" TURING COMPLETE. 🖥️

In a nutshell, when a game is Turing Complete you can use it to build a WORKING COMPUTER. 🤯

If you are a parent: please don't underestimate games as a creative medium.

Let's start with...

🧵👇

1⃣ Minecraft ⛏️

Unsurprisingly, @Minecraft is indeed Turing Complete. 🖥️

This is possible thanks to the so-called REDSTONE CIRCUITS, which allow to build simple logic gates. 🟥

And if you are really, REALLY committed ...you can even build a computer!

2⃣ Portal 2 🟠🔵

Yes. Everybody's favourite game is Turing Complete! 🥰

@anklejbiter used Portal 2 level editor to create a 3-Digit Binary Calculator. De-facto proving it can be used for arbitrary computation.

steamcommunity.com/sharedfiles/fi…

3⃣ Conway's Game of Life ⠠⠵

Building a computer is not the only way to prove that something is Turing Complete.

GoL is a game driven by simple rules, proven to be TC. Creating GoL in any system proves that the system itself is TC.

4⃣ Baba Is You 🔴

It might not be immediately obvious that @babaisyou_ is Turing Complete.

However, there are a lot of user creations that clearly prove that. Such as @TheDevinDanko's real-time Conway's Game of Life simulator.

5⃣ Cadence ⚫️

Cadence is a beautiful rhythm game with an open sandbox mode. As it turns out, some of its puzzle elements can be used to build logic gates.

I've recently streamed with @thefuntastic how to build a simple counter in Cadence. ⏲️

store.steampowered.com/app/362800/Cad…

6⃣ Cities: Skylines 🏙️

@balidani exploited the way in which power generation and sewage pipes work in @CitiesSkylines to create a poop-powered computer. 💩

Below, a 4-bit adder which takes 15 in-game months to run (about 20 minutes in real-time).

6⃣ Infinifactory 🏗️

Most @zachtronics' games (TIS-100, Shenzhen I/O, Opus Magnum, ...) are TC. Unsurprisingly, Infinifactory is not an exception.

Inspired by an earlier video posted by @notch, I made a programmable cellular automata simulator.

7⃣ Dwarf Fortress 🏰

The "Dwarven Computer" by Jong89 is the first programmable digital computer ever built in DF, consisting of 672 pumps, 2000 logs & 8500 mechanism.

mkv25.net/dfma/map-8269

@BaronWable even made a fully-functioning Space Invaders.

8⃣ Minesweeper 💣

Yes, *THAT* Minesweeper we all played on Windows.

As it turns out, Minesweeper is NP-Complete, while its infinite variant is Turing Complete.

Richard Kaye wrote extensively about this.
Below, a XOR, AND and OR gates.

web.mat.bham.ac.uk/R.W.Kaye/mines…

9⃣ Factorio ⚙️

As a pretty open-ended game, many have created all sort of computational contraptions in @factoriogame.

@ArrowGMaximus built some of the most amazing machines, including Facto-RayO (a raycasting engine) and even a demake of Pacman! 🤯

🔟 Magic: The Gathering 🧙‍♂️

And I couldn't end this list without the most surprising and unexpected Turing Complete games of all: @wizards_magic!

@alextfish, @BlancheMinerva & @Stroodle76 wrote about this in a recent paper.

arxiv.org/abs/1904.09828

🟦 BONUS: PowerPoint 🟧

Did you know that @powerpoint is Turing Complete? 🧐

@standupmaths & @MouldS made a very nice video about this. And for a more formal, comprehensive discussion, check out Tom Wildenhain's videos on YouTube. ✨

✨ 𝒕𝒉𝒂𝒏𝒌 𝒚𝒐𝒖 𝒇𝒐𝒓 𝒄𝒐𝒎𝒊𝒏𝒈 𝒕𝒐 𝒎𝒚 𝒕𝒆𝒅 𝒕𝒂𝒍𝒌 ✨

I write about Game Development, Shader Coding & Artificial Intelligence.

If you are interested in any of those topics, feel free to check my work on @Patreon and follow me! 😎

patreon.com/AlanZucconi