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

11–20 of 124 posts

Re: Cities: Skylines Is Turing Complete

#11

Post by Macha »

zokier wrote: post #8
altmind wrote: post #7

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

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.

Re: Cities: Skylines Is Turing Complete

#12

Post by Rotten194 »

zokier wrote: post #8
altmind wrote: post #7

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

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

Re: Cities: Skylines Is Turing Complete

#13

Post by skybrian »

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 not unusual, but if you know the game, it's fun to see how it's done.

Re: Cities: Skylines Is Turing Complete

#15

Post by keyle »

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.

What's partly amusing and partly astounding is the time this person took to do it, re-do it, test it, write it and prove it. I think that's where most of the excitement comes from. We get excited by things that are theoretically possibly but no one would waste their time doing it until someone does.

Re: Cities: Skylines Is Turing Complete

#19

Post by H8crilA »

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.

Two/three counters with increment, decrement and test for zero operations is a Turing complete system:

https://en.m.wikipedia.org/wiki/Counter_machine

In practice it's actually hard to make something with a potentially infinite memory that is not Turing complete.

Re: Cities: Skylines Is Turing Complete

#20

Post by zokier »

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.

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