Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: Is Dwarf Fortress Turing complete?  (Read 4847 times)

King Ink

  • Bay Watcher
  • [spoiler]
    • View Profile
    • We must not look at Goblin men
Is Dwarf Fortress Turing complete?
« on: September 27, 2013, 01:48:31 pm »

Specifically the switches and the minecarts.

if not how can we fix it?

Snaake

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #1 on: September 27, 2013, 02:09:23 pm »

I seem to remember one of the old fluid-logic dwarfputers being touted as Turing-complete, so I guess DF is, even if minecart systems aren't. Minecarts are fully deterministic by behaviour though, so I don't see why a Turing-complete system couldn't be made
Logged

King Ink

  • Bay Watcher
  • [spoiler]
    • View Profile
    • We must not look at Goblin men
Re: Is Dwarf Fortress Turing complete?
« Reply #2 on: September 27, 2013, 02:27:35 pm »

I seem to remember one of the old fluid-logic dwarfputers being touted as Turing-complete, so I guess DF is, even if minecart systems aren't. Minecarts are fully deterministic by behaviour though, so I don't see why a Turing-complete system couldn't be made

fluid logic meaning pressure plates and water depths?
old meaning it does not work anymore?

Snaake

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #3 on: September 27, 2013, 02:40:00 pm »

Yes, and they should still work the same, it's just that the focus of dwarfputing enthusiasts has moved onto minecart systems because they're so much simpler to build: minimal or no power, no messing around with leftover 1/7 water, much less components to craft (a pump, hatch and pressure plate per bit IIRC, at least), and so on.
Logged

King Ink

  • Bay Watcher
  • [spoiler]
    • View Profile
    • We must not look at Goblin men
Re: Is Dwarf Fortress Turing complete?
« Reply #4 on: September 27, 2013, 02:45:08 pm »

very interesting now if one could devise detectors he could make a fortress that responds to changing needs.

Snaake

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #5 on: September 27, 2013, 04:28:15 pm »

very interesting now if one could devise detectors he could make a fortress that responds to changing needs.

You don't really need to have a Turing-complete system for that I think, but anyway...

... for possible detectors, there's quite a few options. Besides pressure plates directly detecting fluids, hostile creatures, all creatures (also can filter based off creature size), and item weights(?), you also have more complicated options, like pasturing a civilian or possibly a non-grazing domestic herbivore that will flee from hostiles in such a place that it fleeing will trigger a pressure plate. Or the opposite, place a war-trained creature so it attacking enemies will path it over a pressure plate triggering some defensive feature. In the astronomy thread, we were throwing about ideas about things that could be useful to do once per calendar month (12/year) or once per lunar month (13/year), which are pretty easy with a vampire defending a different burrow each month or a werecreature becoming trapavoid for 3 days each lunar month respectively. Other timers/repeaters are possible with minecart loops, or e.g. with a vampire eternally patrolling the same loop. A repeater that only repeats once per season, or only during one season, could be easily done with a pressure plates in the hallway access to a farm plot set to only plant in the seasons desired. And so on. Anything else you wanted?
Logged

Larix

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #6 on: September 27, 2013, 06:02:36 pm »

As i understand it, logic machinery in DF can emulate a (finite storage) Turing machine, so a sufficiently advanced DF computer is nominally turing-complete. Only one universally programmable computer has been reported, but another roundabout proof has been produced by Sphalerite, who built a machinery to play Conway's Game of Life, a cellular automaton that can be used to construct universally programmable computers (although the actually built Life field was 128 tiles large, while computers _inside_ Life need hundreds of thousands of squares). Advanced computers in DF take completely silly amounts of space, machinery, power and work. The fabled fully programmable computer had, i think, 31 bytes of memory and performed eight-bit operations at speeds in the 10^-3 Hz range. Minecarts and pure fluid also allow powerless computing, but tend to consume even more machinery and space than powered constructions.

Other detection tricks: depending on the local climate, water-triggered pressure plates can give seasonal signals - from freezing/thawing of water or evaporation. Creatures which don't trigger pressure plates but pick locks or demolish doors can indirectly be spotted by allowing fluids or minecarts through the opened/destroyed door.
Logged

King Ink

  • Bay Watcher
  • [spoiler]
    • View Profile
    • We must not look at Goblin men
Re: Is Dwarf Fortress Turing complete?
« Reply #7 on: September 28, 2013, 09:57:22 am »

I was thinking about something that detected sadness and turned on misters.
but how would one build a sadness detector?

wierd

  • Bay Watcher
  • I like to eat small children.
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #8 on: September 28, 2013, 10:06:39 am »

Sad and morose dwarves take breaks more often. This is merely a correlation, not exactly causal-- but you could turn on the mist generators when more then a fixed value of dwarves go to the meeting/dining hall and just stand around.

If you want on/offable happiness generators, make them turn on when dwarves enter, but turn off when they leave.

Logged

King Ink

  • Bay Watcher
  • [spoiler]
    • View Profile
    • We must not look at Goblin men
Re: Is Dwarf Fortress Turing complete?
« Reply #9 on: September 28, 2013, 10:17:36 am »

water conserving mist showers?

Snaake

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #10 on: September 29, 2013, 03:09:29 pm »

water conserving mist showers?

The basic misters with small (1-2 z) drops are usually closed loops in terms of water supply to begin with.

It's really only when you get to larger waterfall systems when an aquifer/river source and draining off the map edge/into caverns may be easier, and even with larger systems, it's still possible to have a closed loop for the water supply, you just might need a largish cistern at the bottom to be safe from flooding.
Logged

Idranel

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #11 on: September 30, 2013, 04:02:41 am »

Specifically the switches and the minecarts.

if not how can we fix it?

There are designs for universal logic gates available using various things like water/pumps/gears/mechanical power and minecarts

http://dwarffortresswiki.org/index.php/DF2012:Computing
http://dwarffortresswiki.org/index.php/DF2012:Minecart_logic

As usual the limitations are in the length of toilet paper you get to compute on and the complexity of building and understanding the machine.
Logged

Larix

  • Bay Watcher
    • View Profile
Re: Is Dwarf Fortress Turing complete?
« Reply #12 on: September 30, 2013, 06:57:12 am »

For actual logic gates, the most configurable and easiest in terms of space and devices is mechanical logic. Everything on the minecart logic pages is signal conversion and signal storage, while it's assumed that the actual logical operations are done through pure mechanics.

Unfortunately, the http://dwarffortresswiki.org/index.php/Mechanical_logic page is rather difficult to pierce. The best thing you can do to grasp it is build some mechanical devices and see if you can get them to work by yourself. Once you got past the deep end of the learning curve, it's understandable (if not exactly intuitive).

For some of the funnier stuff you can do with DF logic, take a look around the subsections - 'repeaters', 'memory' and 'adders' and the user pages.
With mechanical logic, you can perform binary additions and subtractions quite elegantly: the sum can be generated with a single gear assembly per bit, the carry calculations take a bit more work but _no time at all_, thanks to instant power transmission. The carry calculator used by Jong in the Dwarven Computer is pretty much state of the art (it's using more gears than are really necessary):
http://dwarffortresswiki.org/index.php/User:Jong/Dwarven_Computer#Carry-look-ahead_adder

I've built the basic logic gates using ramp-bug-powered minecarts and nothing else, but they are slow to react and use inordinate amounts of space, so trying to fulfill Turing conditions like this might be possible but wouldn't be worth the bother.
Logged