13 ms·
Cities: Skylines Is Turing Complete
- jepler 7y agoIntended link may be https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a https://medium.com/@balidani/cities-skylines-is-turing-compl... -- an edit link was posted by mistake
- jakear 7y agoWait a tick. I can’t open medium at all, says I must log in. Is this a new thing?
- 0xdada 7y agoMy mistake, it was an edit link I posted, it should be accessible without Medium, I also opted out of the monetized content thing.
- altmind 7y agoI remember that classic TDD (transport tycoon) was also turing-complete. You can make logical gates there using trains and railroad signals. Minecraft is not only turing complete, there are multiple complete projects of calculators and microcontrollers done using red stone.
- zokier 7y agoRedstone is by design made for implementing logic, so it belongs to slightly different category. Although I think Redstones introduction was prompted by people building logic without it in the olden days.
- Macha 7y agoI think Redstone's inspiration was people building computers in Dwarf Fortress with floodgates and pressure plates, rather than Minecraft specifically.
- munk-a 7y agoDwarfputers are a wonderful tangent of their own, with a not-unlikely possibility of flooding your entire computer with firey death in the form of magma in some of the more impressive approaches - this has been possible (but quite difficult) for some time, more recent game versions have made non-fluid based logic gates[1] more realistic and usable. Someone has built an (admittedly simple) space-invaders game[2] using df which is rather impressive. 1. http://dwarffortresswiki.org/index.php/DF2014:Computing#Disciplines http://dwarffortresswiki.org/index.php/DF2014:Computing#Disc... 2. https://www.youtube.com/watch?v=j2cMHwo3nAU https://www.youtube.com/watch?v=j2cMHwo3nAU
- Rotten194 7y agoBack in the day I used to build single-shot logic using sand supported by torches holding back water. Water knocks out torches, sand falls releasing more water, etc. When redstone came along everything got much simpler :-)
- soulofmischief 7y agoI miss the days before command blocks when it was still just about getting clever with good old redstone and a couple gates. The piston update was massive. I've built some ridiculous contraptions such as color displays and tape reels and programmable mob traps and variable-clock-rate machinery. And how could I forget minecarts... And IndustrialCraft took all of this to the next level. Wow, I miss the golden days of Minecraft.
- hcnews 7y agoTrying to understand the excitement around this. Is it uncommon for games to be turing complete? I imagine a lot of modern games are complex enough to pass turing completeness check.
- bduerst 7y agoIt's more or less an feat in problem solving. Given a specific set of limitations in simulation, can you recreate and solve this computation problem? For some games, like Minecraft (redstone) and Factorio (logic gates) it's easy, but for others it's difficult enough that you get to see some creativity. This is one of those latter instances.
- desmondw 7y agoInterestingly, Minecraft only added redstone to explicitly allow logic gates after users had found out how to create them out of flowing water and other select blocks.
- gowld 7y agoMinecraft construction is weird. Minecraft's reason for existing is that people think it's fun to make simple things mind-numbingly hard by using the crudest lowest-level building blocks, each block simualting with horridly monstrous gobs of computing powes). So it's the worst of both worlds -- an expensive simulator for tediously manipulting low-level primitives. Why not manipulate primivitives efficiently, or use high-level constructs? Then serious Minecraft constructors build mods and tools to automate the tedium back out anyway, so they design whatever nice things using high level tools, but then execute and inspect the builds on inefficient computing systems of cryptocurrency-level of wastefulness. Why not just make whatever thing you want out of good (virtual or physical) materials in the first place, and then put it under the microscope/oscilloscop/decompiler/hex-editor to marvel at its complex structure?
- empath75 7y agoMinecraft is a game about killing zombies and building forts. You just happen to also be able to compute with it.
- ekiwi 7y agoWouldn't you also need a way of storing information (preferably an unlimited amount of information) for Skylines to be turing complete? How would you implement the tape of the turing machine?
- davrosthedalek 7y agoYou can make memory out of logic gates.
- zokier 7y agoAdders belong to category of combinational logic, which by definition excludes memory. So OP is right, they do not yet demonstrate Turing Completeness. I imagine, but don't actually know, that they would be about as expressive as dfa, which are few steps below turing machines
- davrosthedalek 7y agoHe builds the adders from ANDs, ORs and NOTs. With these, you can also build flip-flops, which are memory. (Actually, it's enough to have only NAND (or NOR) to build all logic circuits, including memory)
- accrual 7y agoA flip-flop or latch is one way to store a single bit using just logic gates, using two NOR gates or two NAND gates. [0] [0] https://en.wikibooks.org/wiki/Electronics/Flip_Flops https://en.wikibooks.org/wiki/Electronics/Flip_Flops
- jerf 7y agoYes. By convention we ignore that requirement for calling something Turing-complete, since in the absolute sense, nothing in the universe is Turing-complete.
- derefr 7y agoIs there some distinction to be made between Turing machines with tapes of fixed capacity, and ones whose capacities are limited by their execution substrate, such that they’ll support as much memory as they are “given” by the environment? I’m picturing here the difference between Turing machines in the Game of Life that take place on a fixed area of the grid, vs. ones that attempt to just index out to whatever grid position they need, whether that causes wraparound or not.
- ngcc_hk 7y agoAlways wonder what happen if you are alone in a primitive society.
- deleted 7y ago[deleted]
- sowbug 7y agoIf anyone is looking to buy this game, it's currently on sale at Humble Bundle for $7.50. https://www.humblebundle.com/store/cities-skylines https://www.humblebundle.com/store/cities-skylines
- tda 7y agoDon't forget the $150 dlc, that is probably not included. And the base game is pretty minimal
- Arn_Thor 7y agoNot really, the base game is well worth it on its own, especially at sale price
- fsloth 7y agoDevelopment needs resources. I don't see why there is so much hate towards well crafted DLC content. The base game is great as it is, and nobody forces you to buy the DLC.
- swarnie_ 7y agoDLC released every few months which adds new features or mechanics is perfectly fine. I'm not sure if its still the case by Skyline's team used to release DLC in two parts, a bit for a free and an extra bit you had to pay for, they do it really really well. Generally there's a stigma around DLC cut out of the original game to be sold as extras on top, See anything EA / Ubisoft crap out.
- whatshisface 7y agoI think this has some meaning for the abundance of life in the multiverse. If most human-created systems of sufficient complexity turn out to accidentally support computation, then maybe most laws of physics support computation. Hey, it's not better or worse than any other way to guess.
- colordrops 7y agoWell, this game is really just a layer built on top of Turing complete software so is it really all that surprising that the game itself is Turing complete? I wouldn't be surprised if most complex simulation games are Turing complete.
- munk-a 7y agoI wouldn't say it'd be unsurprising to build a turing complete game - building a game (or like, any software) is an exercise in reducing the functionality of a computer, if a machine can originally do X things then your program can do Y things where Y ⊆ X - I think that programs maintaining turing completeness sort of need to go out of their way to be so feature full. For instance, HTML[1] is (IIRC) not turing complete, the computation power once you step into a layer of pure HTML prevents you from ever assembling a turing machine - no matter how many gigs of HTML you can pump out you'd never be able to produce a turing machine[2]. [1] Pure HTML, HTML + CSS apparently is turing complete. [2] This disregards merely using HTML as a data definition format and using other logical components to enable the construction of a turing machine - a turing machine's tape is as simple as can be, so we don't really care about storage formats that can replicate the tape portion, we care about things that can replicate the full machine.
- colordrops 7y agoYes, it makes sense that the program can do a subset of what the computer is capable of. Regarding HTML, I wouldn't say it's analogous to a simulation game. Maybe the map, but the running game is more like HTML + CSS + JS
- unkulunkulu 7y ago
- DonHopkins 7y agoI love how it combines dangerously antagonistic elements like water and electricity. Somebody's going to get hurt! In that vein, can you build logic gates out of cars and pedestrians?
- em-bee 7y agoso douglas adams was right, the earth is just a giant computer
- dingo_bat 7y agoI bought the game in steam sale for ₹180 ($2.6). It is probably the best purchase of my life.
- dnos 7y agoThe idea of creating computers out of virtual objects has always fascinated me since I first saw someone do it in Minecraft. It really brings up some interesting scenarios that I like to day dream about sometimes. For instance, in a real world simulation, you could build a processor with a gazillion transistors because you don’t have to worry about the same physical limitations like size or heat. Could it take an input and compute an output faster than something in the real world? Would you be bound by the speed of light in the virtual world? You control the physics in your virtual world, so technically nothing prevents it right? Information can travel faster than the speed of light relative to your virtual objects. Say you model the earth at 1:1 scale in the simulation and have avatars on complete opposite sides of earth. They could exchange messages faster than they could in the real world since the information wouldn’t have to physically travel across physical space. (e.g. send message directly to memory address X instead of sending light through fiber optic physics simulator). Essentially, in a simulation of the physical world that has tweaked physics, could information be processed faster than the processor running the simulation? Is there some sort of conservation of energy law, but for information?
- bordercases 7y agoThe information would "appear" to be processed "faster" to the digital system merely because the digital system would have no memory of there being a moment in between its current state and the next computed state. Even supposing that it's possible for there to be a subjective experience of a computer: this goes in to physical time and psychological time and whether the two bear a strict relation, as well as the relative nature of time in physical space. On the first topic, if you can stomach having to reformat a PDF, the "No Free Lunch in Machine Learning" guy wrote a paper on thermodynamics and psychological time: https://www.researchgate.net/publication/226069884_Memory_systems_computation_and_the_second_law_of_thermodynamics https://www.researchgate.net/publication/226069884_Memory_sy... On the second one... I think it's more interesting to think if there's a theory of relativity for computation. Imagine if two systems were updating one another's state but were separated by physical distance. Wouldn't you have to hold the state of one to only update when it a receives a message from the other, for the systems to "experience" instantaneous communication? That would mean there would be a third system for whom time would have to pass to transfer the message and compute it in such a way that the amount of updating required for the receiving systems are minimal. Maybe we have to guarantee that at least one system has to experience time more slowly than the others, to compute the information necessary for instanaeity to be true for the communicating systems.
- Causality1 7y agoI could very well be dead wrong about this, but isn't any game that allows you to construct the equivalent of a transistor turing-complete with enough work?
- seaish 7y agoKind of, but the interesting part is finding out how to make the transistor in the first place. These things usually take a few years to be found despite the popularity of such games.
- drainyard 7y agoDoesn't Turing completeness require conditional loops? Considering the fact that he has AND and OR gates he can represent conditionals, but he doesn't show it. And the fact that it always terminates by design also means it solves the halting problem which by definition means it isn't Turing complete (I think?).
- lou1306 7y agoWhat do you mean by "it always terminates by design?" However, as the comments to the post say, the author should provide a proof that the "game physics" allows to construct a functioning latch from these logic gates. Conditional loops are not essential: the lambda calculus is TC despite lacking any loop primitives.
- entropy_ 7y agoHe built an adder, which does always complete(by design). But having the ability to build AND and NOT gates(which he demonstrates) should be enough to build any computer from just those 2 components[1]. I'm not familiar with the game to comment on the correctness of the AND + NOT implementation itself though: If NOT is modeled by flooding a power plant and causing it to turn off, would it go back to being on after a while if we stop actively flooding it? Ie, If the input goes to 0, does the output go back to 1 or not? If this doesn't hold then it's not a proper NOT gate to begin with(turns 1 to 0 but doesn't turn 0 to 1) and the implementation is flawed. [1] https://stackoverflow.com/questions/4908893/what-logic-gates-are-required-for-turing-completeness https://stackoverflow.com/questions/4908893/what-logic-gates...
- aduitsis 7y agoA similar thing is described in Cixin Liu's "The Three Body Problem", where soldiers holding flags emulate the circuitry of a computer.
- tomclive 7y agoI really enjoyed that part of the book. If I remember correctly, the soldiers were just representations of the Trisolarans as they were too alien for us to identify with. The actual Trisolarans emitted light to build their living computer.
- helb 7y agoSomewhat related: turing complete (Open)TTD. segment display: https://www.tt-forums.net/viewtopic.php?f=29&t=37902 https://www.tt-forums.net/viewtopic.php?f=29&t=37902 (2008) digital clock: https://www.youtube.com/watch?v=mkQBGJeh12U https://www.youtube.com/watch?v=mkQBGJeh12U (2011) binary adder: https://www.youtube.com/watch?v=fwWo9fL-GZs https://www.youtube.com/watch?v=fwWo9fL-GZs and https://www.youtube.com/watch?v=YyEzm1ghAsU https://www.youtube.com/watch?v=YyEzm1ghAsU (2015)
- vzola 7y agoAm I the only one who didn't enjoy Cities: Skylines? I played without any expansion (wasn't really hooked enough by the base game to go looking for them) and found the gameplay quite limited compared to the few old city building games I played as a kid. I still play Pharaoh to this day 20 years later and it's still challenging and complex and there's tons of gameplay to explore. In comparison, I played Cities: Skylines for about a weekend, got over the initial difficulty with managing finances, and then it became a matter of building pretty roads and forcefully read people's complaints on in-game-Twitter.
- want2know 7y agoThe game is most about traffic management. This is not very surprising because the company behind it was focused on traffic games. I like the game a lot. But to be fair: you must download a good traffic control mod to setup traffic lights and road settings to keep the traffic under control.
- AQuantized 7y agoThe only real difficulty with Cities is in managing the logistics once your city gets to an extreme scale. Otherwise it's much more about aesthetic and maximizing efficiency than overcoming obstacles. Old Pharaoh style city builders certainly have a good deal more challenge when it comes to survival, but they're quite discrete and once you have a few templates for housing and industry nailed down I don't think they have much more difficulty to offer either.
- jpindar 7y agoI think most people enjoy it for the sake of creativity, not for 'gameplay'. Hence the popularity of mods that unlock everything and give you infinite money.
- volkl48 7y agoI describe Cities:Skylines as a "city painter". You can make nice looking things in it, but there's little challenge and most of the mechanics don't have a lot of depth. I'd suggest looking at SimCity 4 for the peak of the in-depth city simulator. The systems in it go way deeper, it isn't limited by inevitable scaling problems with agent simulations (Tropico, even C:S), and there's a large, long-running modding community for it. There's a few mods that would be considered basically essential, namely the Network Addon Mod (which overhauls the traffic simulator, in addition to a vast amount of content).
- espressomachiat 7y agoWhat does turing complete mean?
- dhagz 7y agoIn the most basic sense, you can make a computer with it.
- bspammer 7y agoEssentially it means that City Skylines could compute anything that it is possible to compute, given enough time. Therefore it is functionally equivalent to the computer you're typing on. In reality, like all computers, it has memory constraints which limit what it can do. A true Turing machine needs infinite memory, which is impossible.
- t0mek 7y agoIdea for the sci-fi story: after the civilization collapse, the only computing device that has survived is an arcade machine, with a difficult game that accidentally is Turing complete. People need to program it, so they can use the results to reboot the power/transportation/medical equipment/etc.