Looking at Cellular Automata as computers is a huge subject, worthy of a course in and of itself Here I will give a cursory overview but I put some readings on the optional reading section of the course web page for you to look at on this topic Let's first talk about what we mean by computation. Computation is the processing of information In a computation information is input to the system, it's stored in memory in some way, it's transferred from one part of memory to another, and it's combined with other information and this could also be called processed. Finally, the processed information is output for the user or the whole system to use in some way So a little sketch, we have input, and then a program which performs the computation, and then output Sometimes, for example, in a dynamical system the output would go back and become the input. There is a notion that's very important in the field of computer science and in the field of complex systems which is the notion of the universal computation. Basically universal computation is the phenomenon of a computer being able to be programmed. That is a universal computer is a computer that can run any program. So it's like the computer on your desk if it only had an infinite amount of memory Then it could run any possible program and compute any possible function that was computable. So the idea here is that instead of just input we have an input and a program This goes into a universal computer and the result is an output You can think of this as the computer on your desk were you can input your data there is a program that's been input either by you or by somebody else that's in the memory of your computer. Your computer acts as a universal computer and runs that program on that input, and then it creates the output. One of the triumphs of the field of computer science was the discovery that only a small set of logical operations is needed to support universal computations. By support universal computation I mean to be able to build a programmable computer What this means is that if you can implement a particular set of logical operations, use them, and combine them in different ways You'll be able in principal to have a computer that can run any program on any input, that is a universal computer As I mentioned earlier, John Von Nuemann was one of the first scientist to look at cellular automaton as models of complex systems and in particular he was looking at the idea of self reproduction in machines or automata. He built a cellular automaton, a two dimensional one. Each cell could be in one of 29 states, and this cellular automaton could replicate any pattern that was input to it including itself. This is a schematic picture of this kind of self reproduction, here is a complicated machine. It has a input space, output space, and it creates a copy of itself. or any other pattern that you give it. but Von Nuemann also made it into a universal computer. That is, this can not only self-replicate it can compute any computable function. Many people have simplified Von Neumann's self-reproducing automaton to have fewer states, but it was the first creation of a universal computer inside a cellular automaton The Game of Life has also been shown to support universal computation In 1970 John Conway showed that Life can implement the simple logic operations that are needed in principle for universal computation. He also sketched how a universal computer can be constructed. Then in the 1990s , Paul Rendell constructed the universal computer Here is a picture of part of the universal computer that he constructed A little hard to see, but it uses some of those structures we looked at earlier Such as gliders, glider guns, and so on to implement these logical operations needed for universal computation I have to say that this is a fantastically complicated undertaking to actually implement this kind of computation in a cellular automaton. For a long time, Stephen Wolfram suspected that some elementary cellular automata could support universal computation This would be significant in that elementary cellular automata, if you recall, are extremely simple and the question was could the complex behavior that they created be complex enough to implement this most powerful form of information processing Well, Wolfram's hypothesis was that all class 4 cellular automata can support universal computation. Remember, class 4 were those in between periodic and chaotic, those Edge of Chaos cellular automata. This hypothesis is hard to evaluate. Well, one problem is that there is not really a formal definition of Class 4 cellular automata. Also, it turns out to be very hard to actually prove that some system is capable of universal computation However, Wolfram and his colleague, Matthew Cook, were successful in proving that Rule 110 can support universal computation This proof was described in a long chapter of Wolfram's book, A New Kind of Science You can actually read this for free online I put a link at our course materials web page. It's a rather technical proof but the general idea is that Rule 110 supports these so called moving particles, that is these localized structures that move in space and time, Remember, time goes down the vertical space goes along the horizontal in one dimension, and so, these moving particles can integrate information from different spatial locations and collide with one another. So, for example, we see here this particle colliding with this particle and creating a new particle The idea is that information can be stored in these more regular patterns, transferred via these particles, and processed via the particle collisions In principle, these can support a universal computation In practice, however, it's hard if not impossible to actually program these cellular automata to do any useful task Well, universal computation in cellular automata is very interesting, and even surprising given how simple they are, especially the elementary CAs. It's not very practical way to perform computation. It's too slow to simulate a universal computer in a cellular automaton It's also to hard to program. So no one really does computations for any practical purpose using the universal computational abilities of cellular automata. However, CAs have been harnessed for more practical parallel computations. For example, in the field of image processing. I'm not going to talk much about that here, but in the next subunit I'm going to talk about one particular project in which genetic algortihms were used to evolve cellular automata to perform practical computations. Finally, let me just say a few words on the significance of cellular automata for complex systems Well, you've seen that cellular automata are really idealized complex systems that can produce very complex behavior from simple rules You've seen that natural complex systems can be modeled using cellular automata like architectures, and that cellular automata give a framework for understanding how complex dynamics can produce collective information processing, that is information processing that emerges from a collection of simple components in a life like system. Where life like, means decentralized, relatively simple components, limited communication, among components, and so on.