This post is a follow up to the previous article about Turing machines and Turing computability.
While I was researching about Turing machines for the article mentioned above, I stumbled upon some interesting facts: there are video games that can be considered Turing complete! This post will look at how the popular video game Minecraft can be considered Turing complete.
Minecraft is a sandbox video game which has capabilities that allow you to work with your imagination and build whatever you want with it. It turns out that you can pretty much create working computers in both games, which allow them to be considered Turing complete since the components that are used to build these computers inside these games can compute any algorithm given enough memory and time.
In Minecraft, you can use redstone blocks (the electricity blocks of Minecraft) to build circuits, which allow you to pretty much build logical gates (AND gates, NOR gates etc.), memory circuits (latches, flip-flops etc.) and clock circuits (repeater clock, comparator clock etc.) that are used in computer systems to perform operations with memory basically and even create loops with them. This article for redstone circuits in Minecraft Wiki shows all the possible circuits that can be created with redstone blocks.
My previous article about Turing machines stated that by strict definitions, it is impossible to build a Turing complete machine since an infinite amount of memory and time is needed to build one. But we know that while practically defining Turing completeness in modern computer systems, we can ignore these infinite assumptions, since we can never consider any modern computer system to be Turing complete with current physical limitations, and therefore ignore the world size limitations of Minecraft as well to build a functional Turing complete considerable computer inside it.
Minecraft also includes a command block that can be used to clone blocks which would allow to generate more memory circuits and therefore allowing for unbounded memory in theory (if we ignore the limitations like how we describe Turing completeness). It is amazing to be able to see that we can build functional computer systems in a single video game! Here are some computing examples realised in Minecraft:
- This video by the user “neonsignal” shows a Universal Turing machine built physically in Minecraft, which means a Turing machine that can be used to essentially simulate any other Turing machine:
- This video by the user “legomasta99” shows the latest version of a 8-bit computer with a 4-core processor, built entirely with redstone circuits:
- Finally, you may say that “well, have we reached to the point of having Minecraft in Minecraft”? Yes, we finally have in 2022. This video by the user “sammyuri” is a demonstration of a 3D Minecraft game built in a computer that was built with redstone circuits in actual Minecraft:
All of these videos mentioned above are sped up, but this should not distract you from the fact that Minecraft is capable of such amazing computation projects. Who knows, maybe one day the technology will evolve to a point of having easily accessible quantum computers running Minecraft and having enough power to simulate practical virtual machines in it. It’s all up to our potential of pushing the boundaries in technology.
