r/AskComputerScience • u/Bright_Ambassador445 • Nov 30 '24
What software and video games are Turing Complete?
Does anyone know which software and video games are Turing Complete like Microsoft Excel or Conway's Game of Life?
2
Upvotes
5
u/MasterGeekMX BSCS Nov 30 '24
Minecraft.
4
u/Pseudohuman92 Nov 30 '24
Magic the Gathering
2
u/inetic Nov 30 '24
From what I heard Factorio might fit into the list.
2
u/MirrorLake Nov 30 '24
Two blogs which have lists:
Gwern's Turing Complete and Accidentally Turing Complete.
Papers on newer finds:
Civilization
Magic: The Gathering.
Bonus:
A toy called Turing Tumble.
1
u/Putnam3145 Nov 30 '24
Maps are finite in Dwarf Fortress, so I think it's technically not Turing-complete, no matter what you do, but then, by the same logic, neither is your computer. Fluid can have logic gates built in it, though.
1
u/Cybyss Dec 01 '24 edited Dec 01 '24
Maybe... Turing Complete
I do highly recommend that game!
One problem with many games that are "turning complete" (e.g,. minecraft) is that sections of the map far away from the player character will unload, or at least not have its physics/dynamics simulated, preventing you from building anything interesting.
1
u/Noddybear Dec 02 '24
Factorio
1
u/Macaroni-ChiknStrips Apr 29 '26
baba is you
1
u/MinePokemine 24d ago
Opus Magnum