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

41–50 of 124 posts

Re: Cities: Skylines Is Turing Complete

#41

Post by gowld »

desmondw wrote: post #28
bduerst wrote: post #10

Earlier quoted context omitted.

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.

Minecraft 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?

Re: Cities: Skylines Is Turing Complete

#42

Post by bordercases »

gowld wrote: post #39
bordercases wrote: post #35

Earlier quoted context omitted.

> Hey, it's not better or worse than any other way to guess. Saying this is a kind of relativism that closes you off to receiving criticism for this view. Here is some disagreement from the philosopher of information Luciano Floridi, "Against Digital Ontology": http://philsci-archive.pitt.edu/4076/1/ado.pdf and its sister paper "A Defence of Informational Structural Realism": http://citeseerx.ist.psu.edu/viewdoc/down…

That article isn't particularly relevant. It argues that reality is not fundamentally digital. The article seems to argue that since a digital system can simulate an analog system (through a DAC), reality cannot be either digital nor analog. But that doesn't matter, since as long a reality can simulate digital or analog phenomena, it can simulate the digital phenomena and create Turing machines. The link to "A Defenc…

I interpreted the OP as implying a strong relationship between the laws of physics and computation. It's trivial to assert that there is a relationship between the laws and physics and computation because there are computers.

But saying that the laws of physics specifically lend themselves to computers involves finding reasons that this may be so.

Yet if there is no inherent computational property in physical nature (like say that the laws actually reflect cellular automata, or are fully deterministic and are not nominal), then we ought to be skeptical that Turing Machines are somehow essential to physics or physical constraints, or that we should be surprised if Turing Machines are common.

Maybe Turing Machines are common just because the definition of a Turing Machine is syntactically weak.

Re: Cities: Skylines Is Turing Complete

#43

Post by TheSpiceIsLife »

ethbro wrote: post #36
TheSpiceIsLife wrote: post #31

Earlier quoted context omitted.

To generalise: Perhaps most sufficiently complex domains are sufficient to build complexity-compounding realms.

Is there a postulate between a toolset's ability to reduce entropy and Turing completeness? I feel like most of the "X is Turing complete" posts are essentially saying "X can decrease entropy to an arbitrary fidelity" (while also having some simulation rules that run over the altered system).

If there isn't there should be.

Adam's Postulate: any sufficiently complex system can probably be coaxed in to reducing entropy in such a way that a set of simulation rules can act as an abstraction layer to form programmable systems.

Re: Cities: Skylines Is Turing Complete

#44

Post by waynecochran »

Swizec wrote: post #33
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.

> then maybe most laws of physics support computation Well since we know the laws of physics can be used to implement a Turing machine, we therefore know the laws of physics support computation. If I remember my college computability course correctly, any system that can be used to implement a Turing machine is itself Turing complete. Even if by no other means than to implement a Turing machine. Besides you really do…

Turing complete is not really a big deal. Two counter machines, two stack machines, and other really simple machines are Turing complete.

Re: Cities: Skylines Is Turing Complete

#45

Post by mdxn »

derefr wrote: post #29
jerf wrote: post #22

Earlier quoted context omitted.

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…

There is definitely a difference. The problem with the vast majority of "Turing-completeness in X" claims on HN is that they are just logically complete Boolean circuits that are overgeneralized (infinitely tessellated or scaled) for free and cannot handle arbitrarily large inputs. They can only handle constant sized input lengths. To handle an arbitrary input, the circuit has to be resynthesized and created to handle that particular case length. This ends up being a massive leap in computational complexity from constant-time to decidable.

Some of these claims are even wrong since the posters don't bother analyzing whether their suggested generalization technique (e.g. infinite tiling) actually do let you topologically embed every gate and batch of wires into any Boolean circuit you want. This is quite common in 2D side scrollers where you have constant y-height and infinite x length. It just is not possible to communicate all the information you need for a computation from one side of the map to the other. This was the case with Minecraft prior to bidirectional flying machines. You could actually prove that any finite sized "machine" could not communicate an arbitrary distance away (think arbitrarily long Turing tapes) without losing some part of it going off in the distance forever. Hence it was not "Turing-equivalent" unless you used command blocks or gave some overly general infinite tiling capabilities.

Actual descriptions of Turing machines are finite in size/length. These "Turing-equivalent" candidates that keep popping up are not when laid out. This makes it pretty easy to run into uncomputability situations when you try to feed the machines a description of itself and compute some property (like a number = 2x its length). A typical Turing machine would have no problem handling this, though a Boolean circuit would.

Re: Cities: Skylines Is Turing Complete

#47

Post by colordrops »

munk-a wrote: post #32
colordrops wrote: post #30

Earlier quoted context omitted.

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.

I 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 comple…

Yes, 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

Re: Cities: Skylines Is Turing Complete

#48

Post by krastanov »

bordercases wrote: post #35
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.

> Hey, it's not better or worse than any other way to guess. Saying this is a kind of relativism that closes you off to receiving criticism for this view. Here is some disagreement from the philosopher of information Luciano Floridi, "Against Digital Ontology": http://philsci-archive.pitt.edu/4076/1/ado.pdf and its sister paper "A Defence of Informational Structural Realism": http://citeseerx.ist.psu.edu/viewdoc/down…

I have not read the paper in detail, but a paper on "digital ontology" that does not mention computational complexity, the quantum Church-Turing thesis, or the fact that analog computation leads to unphysical "hypercomputation" makes any other claims in the paper extremely questionable. How can one take a philosopher of information seriously if they do not address the most typical arguments in computational complexity (you know, the actual science of processing information).

Edit: page 7 discusses some of the points I complained about, but it does not seem particularly convincing to me (it only brushes them off, without explaining them). Admittedly, the language of philosophy is frequently unconvincing to me, so maybe the problem is in me.

Re: Cities: Skylines Is Turing Complete

#49

Post by whatshisface »

bordercases wrote: post #40
whatshisface wrote: post #37

Earlier quoted context omitted.

That's a paper about ontology, I'm talking about the actual physical reality of "the multiverse," you know, the one with the meta-landscape of all possible string theories, and all the different spidermans.

In what way can statements about a multiverse not be ontological? Are you committing to modal realism, Platonic realism, or are you just pulling my leg? If you commit to the multiverse being physical, by extension you're making claims about ontological concerns, since all physical claims require there to be a notion of something existing, even if you're wanting to claim that something counterfactually exists. Then th…

Each universe gets its own version of Spiderman, and we live in the universe with the fictional Spiderman. That's one theory that matches our observations. Since basically every theory matches our observations, including the theory that there isn't a physical multiverse, every argument is equally specious and aesthetic.

Re: Cities: Skylines Is Turing Complete

#50

Post by unkulunkulu »

bordercases wrote: post #42
gowld wrote: post #39

Earlier quoted context omitted.

That article isn't particularly relevant. It argues that reality is not fundamentally digital. The article seems to argue that since a digital system can simulate an analog system (through a DAC), reality cannot be either digital nor analog. But that doesn't matter, since as long a reality can simulate digital or analog phenomena, it can simulate the digital phenomena and create Turing machines. The link to "A Defenc…

I interpreted the OP as implying a strong relationship between the laws of physics and computation. It's trivial to assert that there is a relationship between the laws and physics and computation because there are computers. But saying that the laws of physics specifically lend themselves to computers involves finding reasons that this may be so. Yet if there is no inherent computational property in physical nature…

Do you think the same (i.e. syntactical weakness) about evolution? Otherwise you must admit Turing Machines could be just fit?
Post reply on HN