Notice this inability to predict has nothing to do with chaos. This follows from the fact that you can’t solve the Halting problem. One implication of this is that there are unanswerable physics questions even in a deterministic universe. The fact that billiard balls and cellular automata and laptops being equally powerful computationally has some interesting consequences. This falls under the realm of complexity theory. Later on we will also talk about not only what is computable but also how fast things can be computed. When we get to the section on quantum computing, we will ask this question again about the quantum world. Put together a sufficiently non-trivial set of local deterministic rules (cellular automata, billiard balls bouncing around etc.) and we get something that can both be simulated and simulate anything in this class. This suggests that everything classical in the universe has this property and this is generically true. Cellular Automata and your laptop are equally powerful with respect to what can be computed.
In fact, given just the rules for Conway’s game of life, and the right initial starting configuration for the grid, you can simulate a program running on your laptop. Any problem your laptop can solve, cellular automata can also solve. It is then an interesting question to ask how computationally powerful cellular automata are? Naively, one might think with such simple rules that there are things a laptop can compute but a cellular automata can’t. Turing Machines and your laptop are both equally as powerful with respect to the things they can compute. Turing machines (invented by Alan Turing) are also able to compute everything your laptop can compute (and visa versa). if you see a ‘V’ at the head, write instead a ‘W’ where the head is if you see a `W’ at the head move the tape to the right Your laptop is a type of machine called a Von Neumann machine (it has RAM, CPU, etc.) There is another class of machines called Turing Machines. The set of problems that your laptop can solve are called computable problems. Because you can do such a simulation, this means your laptop is at least as computationally powerful as a cellular automata. In spite of that, you’ve managed to write a simple program on your laptop that simulates this behavior. We’ve seen that cellular automata can produce fairly complicated behavior. In spite of the simplicity of the rules that there are various (in fact arbitrary) complicated behaviors which can happen. If you are white and there are exactly 3 black squares around you, become black. If you are black and there are exactly 2 or 3 black squares around you, do nothing. If you are black and there are more then 3 black squares around you, you become white. If you are black and there are fewer then 2 black squares around you, you become white. Notice that on a square lattice, every cell has eight cells around it. In this cellular automata, each square is either black or white. The most popular cellular automata is John Conway’s game of life.
#COOL OTOMATA HOW TO#
what do I have to store in my computer for it to Then there are some simple rules which tell you how to change the state of your automata. Throughout much of this course, the first question we will often ask ourself about a simulation is what describes its state - i.e. Cellular automata consists of a grid in space where each pixel on the grid is in some state (maybe black or white).
0 kommentar(er)
