Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cities: Skylines Is Turing Complete

medium.com

Post reply on HN
Print view View original

21–30 of 124 posts

Re: Cities: Skylines Is Turing Complete

#21

Post by davrosthedalek »

zokier wrote: post #20
davrosthedalek wrote: post #17

Earlier quoted context omitted.

You can make memory out of logic gates.

Adders 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

He 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)

Re: Cities: Skylines Is Turing Complete

#22

Post by jerf »

ekiwi wrote: post #14

Wouldn'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?

Yes. By convention we ignore that requirement for calling something Turing-complete, since in the absolute sense, nothing in the universe is Turing-complete.

Re: Cities: Skylines Is Turing Complete

#24

Post by accrual »

davrosthedalek wrote: post #17
ekiwi wrote: post #14

Wouldn'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?

You can make memory out of logic gates.

A 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

Re: Cities: Skylines Is Turing Complete

#25

Post by whatshisface »

I 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.

Re: Cities: Skylines Is Turing Complete

#26

Post by soulofmischief »

Rotten194 wrote: post #12
zokier wrote: post #8

Earlier quoted context omitted.

Redstone 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.

Back 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 :-)

I 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.

Re: Cities: Skylines Is Turing Complete

#27

Post by munk-a »

Macha wrote: post #11
zokier wrote: post #8

Earlier quoted context omitted.

Redstone 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.

I think Redstone's inspiration was people building computers in Dwarf Fortress with floodgates and pressure plates, rather than Minecraft specifically.

Dwarfputers 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#Disc...

2. https://www.youtube.com/watch?v=j2cMHwo3nAU

Re: Cities: Skylines Is Turing Complete

#28

Post by desmondw »

bduerst wrote: post #10
hcnews wrote: post #9

Trying 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.

It'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.

Interestingly, 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.

Re: Cities: Skylines Is Turing Complete

#29

Post by derefr »

jerf wrote: post #22
ekiwi wrote: post #14

Wouldn'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?

Yes. By convention we ignore that requirement for calling something Turing-complete, since in the absolute sense, nothing in the universe is Turing-complete.

Is 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.

Re: Cities: Skylines Is Turing Complete

#30

Post by colordrops »

whatshisface wrote: post #25

I 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.

Well, 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.
Post reply on HN