Repost on Cellular Automata - More Scientific GPT

 This is a repost from an earlier blog post.  More scientific sounding.

Abstract

Modern software systems present computation through increasingly high levels of abstraction. An expression such as 4 * 4 appears to the programmer as a primitive operation, while its physical realization ultimately depends on a hierarchy of compiler transformations, instruction execution, digital logic, and state transitions. Cellular automata provide an alternative model in which global computation arises explicitly from repeated applications of simple local rules.

This paper examines cellular automata from the perspective of software computation rather than exclusively as mathematical dynamical systems. Beginning with Boolean state transitions and Conway's Game of Life, we develop the connection between elementary cellular automata and conventional digital computation. We then examine a multi-state cellular automaton capable of representing the computation of . Rather than invoking an explicit multiplication operator, the system encodes an integer into an initial spatial configuration and repeatedly applies a local transition function. After a finite number of generations, the resulting spatial structure encodes the square of the original integer.

The purpose of the experiment is not to propose cellular automata as an efficient replacement for conventional arithmetic hardware. Instead, it demonstrates a more fundamental computational principle: complex and semantically meaningful transformations need not be explicitly represented at the level at which the system evolves. Computation may instead emerge from local interactions among simple stateful components.

More

A cellular automaton can be described formally as a tuple

where:

    • is a discrete lattice of cells, 

    • is a finite set of possible cell states, 

    • defines the neighborhood associated with each cell, and 

    • is the local transition function. 

At discrete time , the complete configuration of the automaton can be written

The system evolves synchronously according to

The important property is locality.

A cell does not normally examine the complete configuration of the automaton. It receives information only from a bounded neighborhood. Nevertheless, repeated local interactions can propagate information over increasingly large spatial distanc


Comments

Post a Comment

Popular posts from this blog

JVM Notebook: Basic Clojure, Java and JVM Language performance

Image
"Measure, don't guess. The primary goal of all performance tuning exercises should be maximize the end user experience given the resource constraints." [1] "It isn't so much a "farewell to the J" as an expansion of the platform opportunities Java provides. Sun's investment to power ongoing development of JRuby and Jython broadens the range and reach of Java, as a whole." -- Rick Ross Overview and JVM Languages    One of the exciting trends to recently emerge from the Java community is the concept of the JVM language. These technologies are all that you would expect them to be. They are implementations of languages that run on the Java Virtual Machine. Some are newly created and some are based on existing, more mature languages. JRuby, Jython are two JVM languages based on CRuby and CPython. Groovy, Scala, Clojure are three completely new JVM languages that were created to add new language features that weren't supported by the core Ja...
Read more

On Unit Testing, Java TDD for developers to write

It has been a while, let's kick off 2017 with a blog entry. I have read and I am reading about four or five posts a day about unit testing. It really has been a long time obsession for me. I have moved past the technical and practical considerations on unit testing frameworks and done with the debates with "should you use Junit or Mockito or Karma?" I am more interested in the psychology of unit testing, who does it, likes it, hates it? It really is one of those easy to learn, hard to master concepts. For example, many many may play chess when they are young and can end up being horribly chess players most of their life, I am part of that majority. Unfortunately, I have never played chess and sat down for hours and tried to master it. I never see the common patterns or have a developed end game. I mostly just play with a knowledge of the basic rules. Following good unit testing practices within your software development shop is a lot like playing chess. It is easy to le...
Read more

Application server performance testing, includes Django, ErlyWeb, Rails and others

Image
The following represents a set of toy benchmark results for various web application servers including ErlyWeb, Hunchentoot, Django and other application servers. The goal was to test out of the box performance through a simple VIEW page. For example, I was trying to avoid static files but going through the controller and the view. In the Rails example, there is a simple controller that then activates the view template. The same approach is used with the ErlyWeb example. Ideally, we are trying to avoid the server loading the static files but in our case the server may be loading cached content. Overall, Erlang's ErlyWeb/Yaws had great performance and out of the box Django did very well. Tomcat and my various low-level simple JSP/Servlet apps also had stable performance. Software and Hardware Configuration used in the Benchmark Two machines were used in the benchmark, a Win32 dual core machine and a single CPU Linux machine. Win32 Box: Microsoft Windows XP, Vers 2002, Service ...
Read more