Editing 1223: Dwarf Fortress
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 20: | Line 20: | ||
A common CS nerd challenge is to prove the Turing-completeness of a system that wasn't intended to be that way — games in particular. The usual way to do this is to construct a Turing machine simulator within the system. It has been done for [http://mkv25.net/dfma/map-8269 Dwarf Fortress], [http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf (infinite) Minesweeper] (pdf), [http://www.toothycat.net/~hologram/Turing/HowItWorks.html Magic the Gathering], [http://www.youtube.com/watch?v=13GOFa1C4e4 Little Big Planet], [http://www.youtube.com/watch?v=1X21HQphy6I Minecraft] ([http://www.youtube.com/watch?v=7sNge0Ywz-M another Minecraft example])<sup>1</sup>, [http://aurellem.org/vba-clojure/html/total-control.html Pokémon Yellow] (through the elaborate use of many in-game glitches) and [http://cp4space.wordpress.com/2013/04/05/3d-chess-is-turing-complete/ 3D chess]. These kinds of proofs often involve formulating ridiculously complex creations just to simulate a little machine writing symbols on a tape!<sup>2</sup> | A common CS nerd challenge is to prove the Turing-completeness of a system that wasn't intended to be that way — games in particular. The usual way to do this is to construct a Turing machine simulator within the system. It has been done for [http://mkv25.net/dfma/map-8269 Dwarf Fortress], [http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf (infinite) Minesweeper] (pdf), [http://www.toothycat.net/~hologram/Turing/HowItWorks.html Magic the Gathering], [http://www.youtube.com/watch?v=13GOFa1C4e4 Little Big Planet], [http://www.youtube.com/watch?v=1X21HQphy6I Minecraft] ([http://www.youtube.com/watch?v=7sNge0Ywz-M another Minecraft example])<sup>1</sup>, [http://aurellem.org/vba-clojure/html/total-control.html Pokémon Yellow] (through the elaborate use of many in-game glitches) and [http://cp4space.wordpress.com/2013/04/05/3d-chess-is-turing-complete/ 3D chess]. These kinds of proofs often involve formulating ridiculously complex creations just to simulate a little machine writing symbols on a tape!<sup>2</sup> | ||
− | Finally, Randall makes a crack that users will try to nest their Turing-complete computers; after finishing his Turing-complete Dwarf Fortress computer, someone else will try to make the Dwarf Fortress computer run Minecraft (a highly inefficient process that would be a nightmare to | + | Finally, Randall makes a crack that users will try to nest their Turing-complete computers; after finishing his Turing-complete Dwarf Fortress computer, someone else will try to make the Dwarf Fortress computer run Minecraft (a highly inefficient process that would be a nightmare to co-ordinate, and would run incredibly slowly). |
<small> | <small> | ||
− | <sup>1</sup> The youtuber legomasta99 even | + | <sup>1</sup> The youtuber legomasta99 even build a whole programmable PC in MineCraft as can be seen [https://www.youtube.com/watch?v=SbO0tqH8f5I here]. |
<sup>2</sup>Technically, a computer is not really Turing-complete. A Turing-complete system has to have unlimited space, and that's not possible for a memory-limited computer or any software running inside it. But even if we don't have access to Turing-completeness, we can build a theoretical machine and show how it can be extended indefinitely. In a few of the games, we prove Turing-completeness in infinite variants. | <sup>2</sup>Technically, a computer is not really Turing-complete. A Turing-complete system has to have unlimited space, and that's not possible for a memory-limited computer or any software running inside it. But even if we don't have access to Turing-completeness, we can build a theoretical machine and show how it can be extended indefinitely. In a few of the games, we prove Turing-completeness in infinite variants. | ||
Line 46: | Line 46: | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
[[Category:Fiction]] | [[Category:Fiction]] | ||
− |