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...
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...
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!
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!
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. https://steamcommunity.com/sharedfiles/filedetails/?id=1788462873
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. https://steamcommunity.com/sharedfiles/filedetails/?id=1788462873
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.
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.
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.
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.
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.
https://store.steampowered.com/app/362800/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.
https://store.steampowered.com/app/362800/Cadence/
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).
@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).
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.
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.
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.
https://mkv25.net/dfma/map-8269
@BaronWable even made a fully-functioning Space Invaders.
The "Dwarven Computer" by Jong89 is the first programmable digital computer ever built in DF, consisting of 672 pumps, 2000 logs & 8500 mechanism.
https://mkv25.net/dfma/map-8269
@BaronWable even made a fully-functioning Space Invaders.
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.
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf
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.
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf
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!
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.
https://arxiv.org/abs/1904.09828
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.
https://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.
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! https://www.patreon.com/AlanZucconi
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! https://www.patreon.com/AlanZucconi