Thursday, February 7, 2013

Wolfram's Cellular Automata, A New Kind of Science and Example Squaring Rule (2)


Overview - Playing the Game Of Life

When most computer users upload a profile image from their desktop to Facebook's website they don't stop to think about the simple binary math rules that are fundamental to most digital devices. We realize that 4 gigabytes of RAM is more memory than 512 megabytes but we don't visualize the logic chips that are involved in an xor $0x100, eax operation for a 32-bit CISC processor. Software developers have to consider memory management or how a computer's operating system loads their programs into memory. They don't normally consider VHDL logic circuit designs, the data paths, arithmetic logic units or the millions of transistors that make up a modern CPU. Those low-level details have been intentionally hidden from the user application developer. The modern CPU may have changed dramatically over the last decade but at the heart of early digital computing were simple Boolean operations. These simple rules were combined together and logic replicated to load programs into memory and then execute. The rules that control most digital devices are based on elementary Boolean rules. Cellular automata has a similar bottom-up approach, rules consist of simple programs (as Stephen Wolfram calls them) that apply to a set of cells on a grid.


Conway's Game of Life cellular automaton is one of the most prominent examples of cellular automata theory. The one dimensional program consists of a cell grid typically with several dozen or more rows and similar number of columns. Each cell on the grid has an on or off Boolean state. Every cell on the grid survives or dies to the next generation depending on the game of life rules. If there are too many neighbors surrounding a cell then the cell dies due to overcrowding. If there is only one neighbor cell, the base cell dies due to under-population. Activity on a particular cell is not interesting but when you run the entire system for many generations, a group of patterns begin to form.

More on Conway's Game of Life




Figure: Game of Life Output

You may notice some common patterns in the figure. After so many iterations through the game of life rules, only a few cells tend to stay alive. We started with a large random number of alive cells and over time those cells died off. In a controlled environment you may begin with carefully placed live cells and monitor the patterns that emerge to model some other natural phenomena.



Figure: Common Game of Life Surviving and Oscillating Patterns


A New Kind of Science

The name Stephan Wolfram has been mentioned several times in this post. He is the founder of Wolfram|Research, his company is known for the popular Mathematica software suite and Wolfram|Alpha knowledge engine. He did not initially discover cellular automata but recently he has been a prominent figure in its advocacy. He spent 10 years working on his book, A New Kind of Science. In the 1300 page tome, he discusses how cellular automata can be applied to every field of science from biology to physics. NKA is a detailed study of cellular automata programs.

Basic Cellular Automata




Figure: Wolfram's Elementary CA Rule 30. Look at 3 bit input and 1 bit output.


The diagram above depicts the rule 30 program (or rule 30 elementary cellular automaton). There are 8 input states (2 ^ 3) and an output state of one or zero. If you look at the diagram from left to right. The first sequence of blocks on the left depict an input state of { 1 1 1 } with an output of 0. Given input of cells { 1 1 1}, the output will be set to 0. Subsequently, the next set of blocks consist of an input state of { 1 1 0 } with an output of 0.

Here is python pseudo code for processing rule30 input:
def rule30(inputCell_0, inputCell_1, inputCell_1): {
  if inputCell_0 == 1 and inputCell_1 == 1 and inputCell_2 == 1
    return 0:
  else if inputCell_0 == 1 and inputCell_1 == 1 and inputCell_2 == 0:
    return 0:
  ...
}
grid = new Grid(100, 100)
grid[row0, col50] = 1 # Enable first cell on row zero
for j until 100:
  for i until 100:
    valsForNextRow[i] = rule30(inputLastRow[i - 1], inputLastRow[i], inputLastRow[i + 1])


Example of first three cases using a boolean notation:
{ 1 1 1 } -> 0
{ 1 1 0 } -> 0
{ 1 0 1 } -> 0
...
Example of first few cases with Scala programming language:

class CellularAutomataRule extends Rule {
 def rule(inputState:(Int, Int, Int)) : Rules.Output = 
   inputState match {
  case (1, 1, 1) => 0
  case (1, 1, 0) => 0
                case (1, 0, 1) => 0
                case (1, 0, 0) => 1
                ...                
 }
} // End of Rule



Figure: Scala Example with pattern matching





Figure: Elementary Automata Grid after several iterations, look at image from top to bottom


Cellular Automata and Squaring Application

How do you square two numbers?

With most popular programming languages you could use infix notation providing an input parameter on the left and an input parameter on the right side of some arithmetic function. With Java, you might write the following code:
int x = 4 * 4;
Output : 16

The above snippet is valid code used to multiply four times four with a result of sixteen but it does not say much about the native implementation of the multiplication operator. There are many layers involved with that particular function but they aren't visible to the developer. Is the function implemented and optimized by the compiler or implemented by the runtime environment? It is possible that the operating system may cache the result or build an implementation for the arithmetic operation. Ultimately for most basic integer multiplication or addition, those operations are performed at the hardware level. So how then does the hardware do it?

In the figure depicted below is an AND gate and truth table, the gate takes two Boolean input values and returns the output AND operation. If one is entered in input A and zero is entered into input B, then the output C returned by the AND gate is one. An arithmetic logic unit may perform basic Boolean operations or possibly some form of basic arithmetic. An ALU may consist of AND, XOR and other similar simple gates combined to ultimately perform basic arithmetic, increment, decrement or jump operations. (Most of my comments focus on older generation basic circuits, modern circuit design may not use such techniques or basic components)




Figure: Boolean AND Gate, InputA, B and Output


If you start from that basic piece of Java code 4 * 4, there are many levels of software and hardware layers that are involved to implement that operation and then return a result.

I wanted to present basic Boolean arithmetic so that you can see how basic rules can lead to more complex patterns and behavior. One two input AND gate will generate a Boolean result. Several million logic circuits may be used to build a complete CPU. You may already be familiar with the Conway's game of life, an initial grid is created with a random number of initial live cells. We can use a simple cellular automata program to square two integers use the rules described in Wolfram's A New Kind of Science. After so many iterations, a common pattern will emerge and that pattern holds the result of N * N. In our squaring example we started with the input number of enabled cells (N = 4) and after so many iterations a pattern emerged that contained the squaring of the input. In many of Wolfram's Elementary rules, a binary sequence is used for input and output. With the general CA squaring rule, an input and output number ranging from 0 to 7 are defined for each cell.

Squaring Rule



Figure: Applet Visual Output Grid for Squaring Cellular Automata

CellularAutomaton[{ 
 { 0, Blank[], 3} -> 0, 
 { Blank[], 2, 3} -> 3, 
 { 1, 1, 3 }   -> 4, 
 { Blank[], 1, 4} -> 4, 
 { Alternatives[1, 2], 3, Blank[]} -> 5, 
 { Pattern[$`p, Alternatives[0, 1]], 4, Blank[]} -> 7 - $`p,
 { 7, 2, 6} -> 3, 
 { 7, Blank[], Blank[]} -> 7,  
 { Blank[], 7, Pattern[$`p, Alternatives[1, 2]]} -> $`p,
 { Blank[], Pattern[$`p, Alternatives[5, 6]], Blank[]} -> 7 - $`p,  
 { Alternatives[5, 6], Pattern[$`p, Alternatives[1, 2]], Blank[]} -> 7 - $`p,
 { Alternatives[5, 6], 0, 0} -> 1, 
 { Blank[], Pattern[$`p, Alternatives[1, 2]], Blank[]} -> $`p,
 { Blank[],  Blank[], Blank[]} -> 0}, {
 ...
 Append[Table[1, {$CellContext`n$$}], 3], 0}, 
 Table -> Expression to N
 Append -> Table to 3



Figure: Notebook Source File For Mathematica, General CA Rule for Squaring Automaton


The general rules for the squaring automaton are similar to the rules that were mentioned for the elementary rule30 program. Integer values (range 0 - 7) are used instead of binary inputs and outputs. The initial row and initial number of cells are represented by the input parameter (N = 4 in our example).
Example Row: 0 0 0 0 0 3 3 3 3 1 0 0 0 0 

Besides the first row, the initial grid contains all zeros. On the next sequence, the CA rule for squaring is run against each cell on the second row. On the sequence after that, the CA rule is run against the third row and so on until the last row in the grid has been reached. With a 100 x 100 grid, the output pattern will emerge before row 100 is reached.
class SquaringRule extends Rules.GeneralRule {
 def ruleId() = 132
 def rule(inputState:Rules.RuleInput) : Rules.Output = 
   inputState match {
  case (0, _, 3) => 0
  case (_, 2, 3) => 3
  case (1, 1, 3) => 4
  case (_, 1, 4) => 4
  case (1 | 2, 3, _) => 5
  case (0 | 1, 4, _) => 7 - inputState._1
  case (7, 2, 6) => 3
  case (7, _, _) => 7           
  case (_, 7, 1 | 2) => inputState._3
  case (_, 5 | 6, _) => 7 - inputState._2
  case (5 | 6, 1 | 2, _) => 7 - inputState._2
  case (5 | 6, 0, 0) => 1
  case (_, 1 | 2, _) => inputState._2
  case _   => 0            
 }
} // End of Rule



Figure: Scala Source for Squaring Rule uses Pattern Matching


Applied Cellular Automata

Cellular automata is often used with data compression, cryptography, artificial intelligence, urban planning, financial market modeling, music generation, and 3D terrain generation. If you are a software engineer, you may have to step back and consider how cellular automata patterns emerge and understand the nature of the dynamic system before looking for a typical software library. CA is not normally seen in everyday applications. Consider this when you look at some random pattern, don't think of the phenomenon as a random sequence of events that cannot be replicated, think of the event in terms of a cellular automaton. Try to imagine the rules that could model that natural behavior. Modeling seemingly random patterns is an area where cellular automata is being widely used. Urban planning departments are integrating geographic information systems (GIS) with cellular automata in an attempt to predict growth in an area of a city.

Summary

The simple squaring example mentioned in this post merely gives you an overview of a basic cellular automata system. Scientists, biologists, computer scientists and software engineers want to find better ways to observe relationships and patterns that occur in our world. Review Stephen Wolfram's A New Kind of Science to give you an idea for what is possible with seemingly simple rules.

Source Code and Applet

1. doingitwrongnotebook/wiki/CelluarAutomataSquaringApplet
2. SVN source repository directory
3. CelluarAutomataApplet - Test of Elementary Rules
4. Game of Life Applet
5. Full Download Applet Examples (keywords: Scala, Rule30, Rule190, GameOfLife, Wolfram Squaring Rule)



Figure: Squaring Cellular Automaton Output, Input = 4 (top of grid), Output = 16 (pattern towards the bottom)

Resources
1. http://www.wolframscience.com/
2. http://www.scala-lang.org/ - Scala Programming Language

--- Berlin Brown (2012)

11 comments:

Digitalbit said...

This is a good article & good site.Thank you for sharing this article. It is help us following categorize:
healthcare, e commerce, programming, it consulting, retail, manufacturing, CRM, digital supply chain management, Delivering high-quality service for your business applications,
Solutions for all Industries,
Getting your applications talking is the key to better business processes,
Rapid web services solutions for real business problems,
Web-based Corporate Document Management System,
Outsourcing Solution,
Financial and Operations Business Intelligence Solution,

prologic-corp

techhighway said...

I am expecting more interesting topics from you. And this was nice content and definitely it will be useful for many people.
Hospitality Software Provide

emailtaai said...

Software development company in Noida help clients leverages strong value propositions. Techsaga offers our clients reduced development costs and quality manpower to help them get the most eminent results. it is the goal for every project is to enrich your work and improve your productivity with software & apps that deliver better business results.

Yes done - Best Professional On Demand Home Service Provider in Jaipur said...

Thanks for sharing this information.
Yes Done is the best online site for on demand home services, professional service providers in Jaipur, Rajasthan. We are providing top services like carpenter, cleaning, TV, best pest control services in Jaipur, ro repair service in Jaipur, ac repair service in Jaipur online by Yes Done is there for services at your doorstep in Jaipur, Rajasthan. For more service visit our website. For more services visit our website.

GIEC Global - Best Migration Agent Melbourne & Education Consultant in Melbourne, Australia said...

It's a great blog, shares a piece of good information.

GIEC Global is the leading education and migration consultants in Australia. We are top Education consultants in Melbourne, Sydney, Perth, Brisbane, Adelaide and Australia. We are best education consultants for Canada in Australia. We also helps people in studying in USA and have been awarded as education consultants for USA in Melbourne and education consultant for UK in Australia.

GIEC Global - Best Migration Agent Melbourne & Education Consultant in Melbourne, Australia said...

The awesome blog shares good information with everyone. I will bookmark it in the future.

France Education Consultants in Australia is GIEC Global. We are top Education consultants for Norway in Melbourne, Sydney, Perth, Brisbane, Adelaide and Australia. We are best education consultants for Netherlands in Australia. We also helps people in studying in Ireland and have been awarded as education consultants for Ireland in Melbourne and education consultant for Finland in Australia.

GIEC Global - Best Migration Agent Melbourne & Education Consultant in Melbourne, Australia said...

Nice Blog, worth reading it. I have also bookmarked it for the future.

If you are looking to Work in Australia , Work in Canada, Work in USA, Work in UK, or Work in Ireland then GIEC Global will be the best consultant for you in Australia.

GIEC Global - Best Migration Agent Melbourne & Education Consultant in Melbourne, Australia said...

It's a really good blog and I am in love while reading it.

If you are looking to migrate to Australia , Migrate to Canada, Migrate to USA, Migrate to UK, Migrate to France, or Migrate to Ireland then GIEC Global will be the best consultant for you in Australia.

GIEC Global - Best Migration Agent Melbourne & Education Consultant in Melbourne, Australia said...

Good One. Worth reading it once.

If you are looking to Visit to Australia , Visit to Canada, Visit to USA, or Visit to UK then GIEC Global will be the best consultant for you in Australia.

Apparrant Technologies - Web and Mobile Application Development Company said...

Nice Information. I really liked it and admire you for posting it on the internet for the benefit of a larger Audience.

If you are looking for best App design and development company in Noida, Delhi NCR, Gurgaon, Faridabad and India then Apparrant is Awesome. We have been known as leading Mobile and web application development company in Noida, India. Work of Apparrant can be checked on our website along with the processes we follow in to the web or App design and technologies we use at Apparrant.

Ratnavali Arts : Best Jewellery Wholesaler in Jaipur, Jewellery shop in Jaipur said...

Wow its a great blog.
Best Jewellery Wholesaler in Jaipur is Ratnavali. It is a best place to buy silver jewellery Jaipur, Jaipuri gold jewellery, gemstone figures in Jaipur, Rajasthan. We have skilled craftsmanship who made best designer collection of jewellery for you.