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

51–60 of 124 posts

Re: Cities: Skylines Is Turing Complete

#51

Post by unkulunkulu »

colordrops wrote: post #30
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.

If you take bugs and security issues into account then almost any layer built on top of Turing complete software is Turing complete

Re: Cities: Skylines Is Turing Complete

#52

Post by mys_721tx »

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…

Turing machine has unbounded memory. There is a difference between unbounded and unlimited memory: You can extend the tape as needed, but at any given step of computation, the used space is finite.

A Turing machine with bounded memory is called linear bounded automaton. Although LBA is less powerful than a Turing machine in the absolute sense, it is not trivial to form a problem that a Turing machine could decide but a LBA could not.

Re: Cities: Skylines Is Turing Complete

#53

Post by bordercases »

unkulunkulu wrote: post #50
bordercases wrote: post #42

Earlier quoted context omitted.

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?

I'm not sure what you mean by your second question, but even though the set of postulates required for natural selection is compact, each concept that supports it is quite rich.

More general statements about evolution (the kind that I'm guessing Universal Darwinists endorse) would be uninteresting to me because they begin to eliminate details about the system which would render the claims less trivial to talk about... although, I know that there are serious theorists of self-organization that might be better equipped to understand how to talk about fundamental truths of this kind (like Stuart Kauffman).

I'd be less combative in this thread if there were discussions about the ways in which Turing-Completeness come about in the different realizations of the machine, or if comparisons were made between these machines. But so far there hasn't been a lot to prove.

Re: Cities: Skylines Is Turing Complete

#55

Post by empath75 »

gowld wrote: post #41
desmondw wrote: post #28

Earlier quoted context omitted.

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 h…

Minecraft is a game about killing zombies and building forts. You just happen to also be able to compute with it.

Re: Cities: Skylines Is Turing Complete

#56

Post by bordercases »

whatshisface wrote: post #49
bordercases wrote: post #40

Earlier quoted context omitted.

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.

Every theory matches observations given interpretations of those theories, and it's impossible to engage in discourse without additionally engaging in interpretation. So some theories are going to be eliminated from view given one perspective or the other since interpretations must be chosen over others. I think where you're wrong is thinking it's possible to evade this and make the claim that all arguments are specious without simultaneously gesturing that you don't want to engage in the discourse anymore: it's a self-defeating claim.

Notice that none of this prevents there from being a singular subject that we can talk about, but there can still be substantial disagreement as to the nature of the thing be discussed. If we are disputing whether or not there is a multiverse I would just ask you, what are your grounds for accepting that we occupy a multiverse and what brought you to do so?

Re: Cities: Skylines Is Turing Complete

#57

Post by dnos »

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

Re: Cities: Skylines Is Turing Complete

#58

Post by bordercases »

dnos wrote: post #57

The 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 inp…

The 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_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.

Re: Cities: Skylines Is Turing Complete

#59

Post by natpalmer1776 »

gowld wrote: post #41
desmondw wrote: post #28

Earlier quoted context omitted.

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 h…

To actually answer your question: Barrier of Entry.

Re: Cities: Skylines Is Turing Complete

#60

Post by alexjray »

dnos wrote: post #57

The 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 inp…

At the end of the day it's all just energy.
Post reply on HN