Colossal turing machine made in city-building game

Dwarf Fortress, an intimidating old-school city-building game, is famous for its vast scope and difficulty. Technically a roguelike, it allows players to construct elaborate underground civilizations -- and even the entire world they are set in -- then crushes them with goblin invasions, lava flows and micromanagement. Players often show off their labyrinthine creations using 3D visualization apps, but Jong89's creation is especially worthy of your attention: his dwarf fortress is a vast turing machine.

The Dwarven Computer is finally complete! I've tested it and it functions as expected, though its performance is really lousy. ... Yellow gears represent gears that are disengaged by default. Grey gears are not linked to any pressure plates. Blue gears are engages by default. Unfortunately I didn't have enough cobaltite to make all the blue gears on the upper deck so I used orthoclase instead. This monumental build contains 672 pumps, 2000 logs, 8500 mechanisms and thousands of other assort bits and knobs like doors and rock blocks. I believe this is the first programmable digital computer that anyone has built in DF. I believe it is turing complete, for anyone who cares.

When examining the map, be sure to note it has multiple levels--and that the computer intersects with an underground river! Razorlength [Dwarf Fortress Map Archive] Thanks, Joel!

• [Chevan]

  What’s also really impressive is that this isn’t the only approach to building an in-game computer in Dwarf Fortress. There was another person who built a working calculator using a mechanism and switch design instead of a water-based system: http://df.magmawiki.com/index.php/User:BaronW

• [mramberg]

  So if I get this right, God exists and he’s making theoretical machines out of virtual dwarf cities. He is mad, then.

• [Guysmiley]

  Anyone looking to kill an hour or so while giggling uncontrollably should really read the saga of the fortress Boatmurdered. It’s insane and hilarious all at the same time.

  http://lparchive.org/LetsPlay/Boatmurdered/intro.html

• [SamLL]

  I think you get to declare that you won the game if you can get your fortress to contain a dwarf-computer that is, itself, running a copy of Dwarf Fortress.

  • [fxq]

    Yes, declare yourself the winner one microsecond before the crushing self-similarity rips the atoms from our bodies!

  • [Anonymous]

    Well, if a true turing machine can calaculate anything any other turing machine can calculate, which is the definition, then, yes, you could program it to play Dwarf Fortress.

• [dw_funk]

  Urist McTuring has been ecstatic. She admired a fine computer lately.

  But seriously, I derive a lot of pleasure just from reading these forums. It’s one thing to make a good game; it’s another thing entirely when one makes a game that inspires others to create. With the intricate stories, bloodline games, and architectural feats, Toady and his brother have really done something incredible.

  SamSam: he didn’t place all those objects himself. He had to convince an army of smelly, drunk, often bloodthirsty dwarfs to do it, probably by feeding them cats.

• [Anonymous]

  2 cats, lol

• [hadlock]

  I approve of this blog post! This is easily nerdy enough to make the /. front page. Keep ‘em coming, Rob!

• [ben]

  But can it run linux?

• [E-beth]

  Does anyone else think of the Legend of Zelda map when they see this?

• [Anonymous]

  So instead of computer bugs and crashes does it have cats and catsplosions?

  CAPTCHA: abilities stepping

• [Antijoe]

  Logopolis!

• [Lobster]

  That is the greatest test of true artificial intelligence: it must contain more than 2,000 logs.

• [Bob Rossney]

  One more shout-out to the BoatMurdered saga mentioned above. It’s a big rabbit hole to go down (appropriately, given the nature of DF), but it’s the best gaming saga I’ve ever read anywhere. To paraphrase J.B.S. Haldane, the internet is not only stranger than we imagine, it’s stranger than we CAN imagine.

• [djn]

  One of my plans if I ever have a lot of spare time is to sit down and find out how much logic it’s possible to implement with trains (and tracks, signals & routes, of course) in openTTD.

  Actually, I think I can see a way to make a NAND gate. Storage should be possible as well … say, how many gates are there in the simplest known turing-equivalent CPU?

• [kc0bbq]

  Every piece is etched with the image of a kitten watching two dwarves being crushed by an Elephant.

• [djn]

  Right, the CPU of a PDP-8/S (the really slow serial one) has 519 gates. That’d be a nightmare to do in openTTD, but (scarily) I think it would be possible, if the largest map has enough room. Oh, and that assumes it’s possible to find a good solution for memory.

• [Casey]

  This is like the nerd equivalent of a turducken.

• [djn]

  Since I forgot to say so earlier, btw: This is extremely impressive, more so because I know I would have thought about it and dismissed it as far too much work to even work out if it was possible. The sheer amount of labour is staggering on its own. :)

• [Chentzilla]

  I doubt that anyone but the creator himself can truly prove that it really is what he claims it is.

  • [Anonymous]

    There’s a video demonstrating proper operation, and he’s uploaded the map for people to verify. It’s legit.

  • [AndrW]

    Actually, as well as maps, a save was uploaded for others to play with. I think at least one person on the forum took up the offer (it takes quite the computer to manage all that, I’m sure).

    It’s really too bad that this save can’t be moved over to the new version just released. Odds are no one’s going to try a stunt like this again.

• [Igloo]

  It is possible to build the basic gates in openttd. Two years ago I built a Not, And, Or gate and a memory storage. By combining these gates and memory I created a working LED counter that counted the number of trains that passed on a piece of rail.

  See http://blog.openttdcoop.org/2008/06/17/the-insane-led-counter-logic-gates-part-1/ for more screenies and details. Creating something with 519 gates within openttd should be possible, because the gates are rather small.

  • [Anonymous]

    Wow, I was about to post the link. Didn’t expect to find you here :) Good work.

    #16 There were several ottdcoop games where logic gates were routinely used, I remember one that was completely self-regulated using logic gates (around PSG 160)

    Fuco

• [Phil Ward]

  Any minute now, the shades of the good citizens of BoatMurdered will rampage through the halls causing GPF’s throughout.
  Chased by mandrills.

• [tgvaughan]

  Awesome! Babbage had nothing on this maniac! Just to correct though, the author’s claim is turing completeness. This is much more complex than a simple turing machine!

  • [retchdog]

    There is nothing more complex than a universal Turing machine, although maybe by simple you meant “non-universal”.

    At any rate, hardware generally isn’t Turing-complete, and this Dwarf Computer is not a Turing machine. It is a programmable digital computer (and assuming a beefy-enough machine running Dwarf Fortress, it’s probably one which can rival the computational capacity of a VIC-20!). I wish he’d summarize how many bits of memory the “8500 mechanisms” amount to. :)

    • [octopod]

      au contraire, it’s at the bottom, add oracles, and walk up the arithmetical hierarchy. sadly at each level, the halting problem remains an issue. you could try logging a bugzilla report on sunday, but nobody’ll get round to fixing it, so have a cup of tea instead.

    • [tgvaughan]

      By “more complex than a simple Turing machine” I was thinking of the roll of tape variety. (By complex I was thinking about the Kolmogorov complexity of the design, not the possible complexity of the output.) Thanks for your clarification.

      • [octopod]

        np

        heh, jk!

    • [pimlottc]

      I concur, this is much more complex than a simple Turing machine.

• [fxq]

  Dwarves are great a building intricate devices, but they make horrible programmers!

• [Anonymous]

  I’m so sad that this game isn’t open source. We could use the autoconf tools to fix up the linux version for everyone in a jiffy. Then we could all install from source. I’m itching to do this.

• [milovoo]

  given the hazards of carp, I would be totally afraid of a water-based dwarf computer.

• [Bahumat]

  Dwarf Fortress is amazing. The amount of narrative that evolves organically from the tiny granularity of game mechanics is magnificent.

  Can’t recommend the game enough. There are excellent tutorials on YouTube, for learning the scary-early-learning-curve of the game. And there’s tilesets if staring at raw ASCII hurts your eyes.

  Play it, live it, love it.

  Strike the earth!

  And remember: Losing Is Fun(TM)!

• [shanealeslie]

  I play Dwarf Fortress.
  Sometimes I wish I was a meth addict instead.

• [Maneki Nico]

  goblin invasions, lava flows and micromanagement

  Sounds just like my last workplace. XP

• [jasonjayr]

  This reminds me of http://en.wikipedia.org/wiki/ZZT , which allowed you to create your own world, and program objects into it ….

• [Anonymous]

  djn: Well Lunar lander ran on a pdp-10, so THAT’S something to shoot for…

• [Elijah Meeks]

  Urist McTuring cancels build computer: sexuality crisis.

• [SamSam]

  That is totally insane. Did he have to add all 10,000+ objects (just adding those mentioned above, don’t know if there are others) himself, or can this be done programmatically? How long did this take? And how was the logic designed?

  It would also be great if the goblin invasions and stuff could actually function as inputs to the machine. So as they enter through various gates, their entrance functioned as the initial piece of tape.

  • [Remus Shepherd]

    It’s even worse than you think, SamSam. He had to *construct* all those components. That involves telling a miner to dig out the stone, then a hauler takes it to the masonry, then you tell a mason to carve it into a gear/level/switch/whathaveyou, then you instruct a mechanic to install it in the correct location. All this while fending off goblin raids, dealing with liasons from human and elf kingdoms, and making food and beer for your population of insane alcoholics.

    The person who did this needs medication for OCD and awesomeness.

• [Davidget]

  This is a dwarf computer. All craftdwarfship is of the highest quality. This object menaces with spikes of awesome. On the item is an image of a dwarf computer. The dwarf computer is computing.

• [AndrW]

  Been watching that one develop for months. Between this and the functional in-game clock design, the dwarf-puter guys have really outdone themselves.

• [gijoel]

  April 16, 2010. Dwarfnet goes on-line. Dwarf decisions are removed from fortress defence. Dwarfnet begins learning at a geometric rate. It becomes self aware at 2:14am Eastern time.

  In a panic the Dwarfs try to pull the plug.

  It fought back.

  CHANG–CHANG CHANG CHACHANG!

• [JoshuaZ]

  Many years ago a friend of mine and I proved that given arbitrary map size Starcraft when used with the scenario editor was Turing complete. If I recall, in our first construction you needed the Brood War expansion because the basic form required moving zones over a specific probe that represented the reader (and would then determine what was living in that square to read the tape. Writing a new symbol consisted of killing the non-probe unit there and replacing it with another unit of the appropriate type). Later, we realized that one didn’t need the Brood War extension since one could without much work make a register machine using the minerals and vespene of a few sides.

  In general, a lot of games have a Turing complete analogue. But it is rare for someone to actually try to demonstrate this with an implementation. This construction in Dwarf Fortress is impressive.

  • [mdh]

    that was very insightful, thank you.