Transient Theory
Posted on: May 18th, 2005 5:19 PM GMT
Topic: information theory, cellular automata, tech
Okay, this is going to be bizarre, but interesting. Last year I read Stephen Wolfram's A New Kind of Science, where he uses Cellular Automata (CA) to illustrate, among other things, the relationship between complexity and simplicity in nature. Here's an example of a CA:
@ @ @ @ @ @@@ @ @ @@@ @ @@ @ @@@ @ @ @@@@ @ @@ @@@@ @ @@@ @@@@ @ @@ @@@ @@@ @@ @ @ @ @ @ @ @@ @@ @@@@ @ @ @ @@@ @ @ @@@ @ @ @ @@ @ @@@ @@ @@ @ @@ @@ @@@@ @ @@ @ @@ @@ @@ @ @ @ @@ @@@@ @ @ @ @ @ @ @@@@@ @@@ @ @ @ @ @ @ @ @ @ @ @@ @@@ @ @@@@@@@ @ @@@@@@ @@@ @ @ @ @ @@@ @@@@@@ @@@@@@@@ @@ @@@@ @ @@@@ @ @@@ @ @@@@ @@ @ @ @ @ @@ @@ @@@ @ @@@ @ @ @ @@@@@@ @@ @@ @ @ @ @ @@ @ @ @ @@@ @@@ @ @@@ @@ @@@@ @@ @@ @@ @ @@ @ @@ @ @@ @@ @@ @ @ @ @ @ @ @ @@@@ @@ @ @@ @@@ @@@ @ @ @ @@ @ @@@@ @@@@ @ @ @@ @@@@ @ @ @@ @@@@@ @@@ @@@@ @@ @ @ @@ @@@@@@ @@ @@ @@@@ @@@ @@@@@@@ @ @ @ @ @ @ @@ @ @ @@@@@@ @ @@@ @ @ @@@ @ @@ @ @@ @@@ @@ @ @@@@@ @@ @ @ @@@ @@ @ @ @ @ @@@@@ @ @ @@ @ @@@ @ @ @@ @@@ @ @ @@@ @ @ @ @@@ @@ @@ @@@@@ @@ @@@@ @ @ @ @ @@ @@ @@@ @@@ @@ @@ @@@ @ @@@@ @@@ @ @@ @ @@@ @ @@ @@@@ @@ @@ @ @ @ @ @@@ @ @@@ @@@ @ @ @@@ @@@@ @@@@ @@ @@ @@ @ @@ @ @ @ @@ @ @@@@@@ @ @@ @ @ @ @@ @@ @@ @ @@ @ @@@ @ @@ @ @@@@ @ @@@@@@@@ @ @ @ @@@ @ @@ @@@@@ @ @ @ @@@ @ @ @@@ @@ @ @ @@@@@@ @@@@ @@@@ @@ @@ @@@@ @ @@@@@@@ @ @ @@@@ @ @ @@ @ @ @ @@ @ @@ @@ @ @@ @ @@ @@@@ @@ @@ @@ @ @ @@ @ @ @ @@ @@@@@ @ @@@ @@ @ @ @ @ @ @ @ @@ @ @@ @ @@ @ @@ @@ @ @ @@@@ @ @ @@ @ @ @ @@ @@@ @@@ @@@@ @ @ @ @ @@ @ @@ @@ @@@@@@ @ @@@@ @ @ @ @ @ @@ @@@@@@@ @@@ @@ @ @ @ @ @ @ @@@@ @ @@ @ @@@@@@ @@ @@ @ @ @@ @@ @ @ @ @ @ @@@ @@ @ @ @ @@@@ @ @ @@@@ @@ @ @@ @@@ @ @ @ @ @@@@ @@@@@ @ @ @ @@@ @ @ @ @ @ @@ @ @ @ @@ @ @@@@@ @ @@@ @ @@@@ @ @ @@ @ @ @@@@ @@@ @ @ @@ @@@@@ @ @@ @@ @ @@ @@ @@@@@@ @ @ @@ @@@ @@ @ @ @ @ @@@ @ @ @ @ @@@ @ @ @@@@ @ @ @@ @ @@ @@ @@ @ @ @@ @@ @@@ @@ @@ @ @@ @ @@@@@ @@ @@@@@@@ @@@ @@@@ @ @@ @ @ @@@ @@@@ @@@@@ @ @ @ @ @@@ @ @ @ @@@ @ @@ @ @@ @ @@ @@ @@@@ @ @ @ @@@ @@ @@@@@ @ @@@@ @@ @@ @ @ @ @@ @ @ @@@ @@ @ @@@ @@ @@@ @@@ @@ @ @ @@ @@ @ @@@ @ @@ @ @@ @@ @ @ @ @@@ @@@ @ @ @@ @ @@@ @@@ @ @ @@@@ @@ @ @ @@ @ @ @ @ @ @@@ @@@ @ @@@@ @ @@@@@@@ @@@@@@ @@@ @ @ @ @ @@ @@@ @@@@ @@ @@ @@@@ @ @ @ @ @ @ @@@ @@ @ @@@ @ @@ @ @@ @@ @ @ @ @@@ @ @ @ @@ @@@ @@ @@ @@ @ @ @ @@@ @@ @@@ @ @ @ @ @@@@@ @@@ @@ @@@@@@@ @@ @ @ @ @ @ @@ @@ @@ @@ @ @@ @@@ @@@@ @@@@@@@ @ @ @@@ @@@ @@@@@ @@@@@@@@@@@ @ @ @ @@ @@@ @ @ @ @@ @@ @ @@@ @@ @ @ @@ @@@ @ @@@@@@ @ @ @ @@@@@@@ @ @ @ @ @@@ @@ @ @@@@@ @@ @@@ @ @@@ @@ @ @@@@@ @@ @ @@@ @@ @@ @ @ @@@@@ @@@ @ @@@@ @@ @ @@ @ @@ @ @ @ @@ @ @@ @@@ @ @@ @ @ @ @@ @@@@@@ @ @@@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @ @ @ @ @@ @@@@@ @@@ @ @@ @ @ @@ @@@ @@@ @@@ @ @@ @ @ @@ @@@ @ @@@@ @@ @@@@ @ @@@ @ @ @@@@@ @@ @@@@@ @ @ @ @ @ @@@ @ @ @ @
RULESET:
111 110 101 100 011 010 001 000
0 0 0 1 1 1 1 0
This is Wolfram's "rule 30"; a binary, one-dimensional CA consisting of eight rules where each horizontal line is generated based on the state of the line before it. Specifically, each cell's state is determined by the combined state of the three cells above it. It's a simple algorithm; the Java class I generated it with is posted below. Notice that the above CA begins and ends with complex noise. This isn't suprizing, however the same CA can be set up in another way that ends noisily, but doesn't start that way. The CA begins with a single dot placed exactly in the center:
@
@@@
@@ @
@@ @@@@
@@ @ @
@@ @@@@ @@@
@@ @ @ @
@@ @@@@ @@@@@@
@@ @ @@@ @
@@ @@@@ @@ @ @@@
@@ @ @ @@@@ @@ @
@@ @@@@ @@ @ @ @@@@
@@ @ @@@ @@ @@ @ @
@@ @@@@ @@ @@@ @@@ @@ @@@
@@ @ @ @@@ @ @@@ @ @
@@ @@@@ @@ @ @ @@@@@ @@@@@@@
@@ @ @@@ @@@@ @ @@@ @
@@ @@@@ @@ @@@ @@ @@ @ @@@
@@ @ @ @@@ @ @@ @@@ @@@@ @@ @
@@ @@@@ @@ @ @@@@@@ @ @ @@@ @@@@
@@ @ @@@ @@@@ @@@@ @@@ @@ @ @
@@ @@@@ @@ @@@ @ @@ @ @ @ @@@ @@@
@@ @ @ @@@ @ @@@ @@ @ @@@ @@ @ @ @ @
@@ @@@@ @@ @ @@@ @ @ @@@@ @ @ @@ @@@@@@
@@ @ @@@ @@@@ @@ @@@@@ @ @@@@@ @ @ @
@@ @@@@ @@ @@@ @ @@ @ @ @@ @ @@@@@ @@@
@@ @ @ @@@ @ @@ @ @@@@ @@ @ @@ @@ @ @@ @
@@ @@@@ @@ @ @@@ @ @ @ @@@ @@@@ @ @@ @ @@ @ @@@@
@@ @ @@@ @@@@ @@@@ @@ @@ @@@ @ @ @@@@ @ @ @
@@ @@@@ @@ @@@ @ @@ @ @ @@@ @ @@ @@@@ @@@ @@ @@@
@@ @ @ @@@ @ @@ @ @ @@@@@ @ @@@@@@ @ @ @@ @ @ @
@@ @@@@ @@ @ @@@ @ @ @@@@ @@@@ @@@@ @@ @ @ @@@@@@@@@
@@ @ @@@ @@@@ @@@@ @ @ @@ @ @@ @ @ @ @ @
@@ @@@@ @@ @@@ @ @@ @@ @@@ @@ @ @@@ @@ @ @@@@@ @ @@ @@@
@@ @ @ @@@ @ @@ @ @ @@ @ @ @ @ @ @@@@ @ @ @ @@ @
@@ @@@@ @@ @ @@@ @ @ @@@@ @@@@ @@@@@ @@ @@@@@ @ @@ @ @@ @@ @@@@
@@ @ @@@ @@@@ @@@@ @ @ @ @ @ @ @@@ @@ @ @ @@@ @ @
@@ @@@@ @@ @@@ @ @@ @@ @@@ @@@ @@@@@@ @@ @ @ @@@ @ @ @@@@ @@@
@@ @ @ @@@ @ @@ @ @ @@ @@@ @@@ @ @@ @@@ @@ @@ @ @ @@@@ @ @
@@ @@@@ @@ @ @@@ @ @ @@@@ @ @@@ @@@ @ @ @@ @@@ @ @@ @@ @ @ @@@@@@
RULESET:
111 110 101 100 011 010 001 000
0 0 0 1 1 1 1 0
Wolfram didn't mention this, but a phenomenon in the realm of acoustical physics is interesting in a similar way. Two methods exist to generate sound that (theoretically) has an even distribution of energy across the frequency spectrum. First is the tried-and-true method of generating raging white noise. Another is to produce an extremely narrow transient, which on a graph would look like a vertical spike intersecting an otherwise flat line. Such a waveform actually has a potentially infinite bandwidth.
In terms of information theory these are both transient data; a single interesting bit surrounded by emptiness. In one case the transient undergoes a series of mutations described by a discrete ruleset, yielding a large amount of data, whereas in the other case a wide range of information is revealed by running the transient through that portion of sine wave mathematics used to calculate energy distribution. Perhaps there's a correlation here. Just because waveform mathematics happen to model real systems in the Universe doesn't mean that on some level they aren't just as arbitrary a ruleset as a CA. In light of different rulesets, then, transient data are potentially the source of a staggering amount of information, provided you have the processing power (mental or computational) to execute the ruleset and realize some of it, and if the ruleset happens to model something in the real world, you can learn something interesting to boot.
Given this, the apparent simplicity of a transient is an illusion. Our minds are good at partitioning the Universe to create simplicity, and so taken by itself, the emptiness surrounding the transient is cyclical nothingness, yielding a single, easy to understand, bit. The transient itself is something, but also just a single bit. A single bit of somethingness in the context of infinite bits of nothingness, however, can yield a potentially infinite amount of information in the context of certain rulesets. No modelling algorithm can ever ferret out all the information available from such a state of affairs, because no computer is truly infinite. Perhaps this reveals that no single thing in the Universe can ever really be considered simple and that ultimately, everything you encounter in this Universe is utterly complex and you'll just have to accept it.
Class to generate CA:
import java.util.*;
/** class to generate cellular automata */
class CellularAutomata
{
private boolean[] rule = // rule 30 (00011110)
{
false,false,false,true,true,true,true,false
};
private boolean[] line = null;
private boolean[][] template =
{{true,true,true}
,{true,true,false}
,{true,false,true}
,{true,false,false}
,{false,true,true}
,{false,true,false}
,{false,false,true}
,{false,false,false}};
public CellularAutomata()
{
setWidth(101);
}
public void randomizeLine()
{
randomizeLine(0.5);
}
public void randomizeLine(double balance)
{
for (int i=0;i<line.length;i++)
{
line[i]=(Math.random()>balance)?true:false;
}
}
public void setWidth(int width)
{
if (width<3) return;
int oddset = width%2;
int side = (int) Math.round((width-oddset) / 2);
line = new boolean[width];
for (int i=0;i<line.length;i++)
{
line[i] = (i!=side) ? false : true;
}
}
public String getLine()
{
StringBuffer result = new StringBuffer("");
for (int i=0;i<line.length;i++)
{
if (line[i]) result.append("#");
else result.append(" ");
}
incrementToNext();
return result.toString();
}
private void incrementToNext()
{
boolean[] newLine = new boolean[line.length];
for (int i=0;i<line.length;i++)
{
int left=i-1;if(left<0)left+=line.length;
int mid=i;
int right=i+1;if(right>=line.length)right=0;
newLine[i]=getCell(line[left],line[mid],line[right]);
}
line = newLine;
}
private boolean getCell(boolean left,boolean mid,boolean right)
{
for (int i=0;i<template.length;i++)
{
if(template[i][0]==left
&&template[i][1]==mid
&&template[i][2]==right)
{ return rule[i]; }
}
return false;
}
public void setRule(int num)
{
String bin = Integer.toBinaryString(num);
while (bin.length()<8) bin = "0" + bin;
if (bin.length()>8) bin=bin.substring(8,bin.length());
char[] arr=bin.toCharArray();
int counter = 0;
for (int i=arr.length-8;i<arr.length;i++)
{
rule[counter++]=(arr[i]=='1')?true:false;
}
}
public int getRule()
{
int result = 0;
for (int i=rule.length;i>0;i--)
{
if (rule[i-1])
{ result += (int) Math.pow(2, rule.length-i); }
}
return result;
}
public static void main(String[] args)
{
CellularAutomata ca = new CellularAutomata();
int iterations = 300;
String usage =
"Usage:\n -width=<integer> Sets the width "
+"of the automation. Default is 101.\n"
+" -len=<integer> Sets the number of "
+"iterations. Default is "+iterations+".\n"
+" -rule=<integer> Sets the rule used. "
+"(0-255) Default is 30.\n"
+" -ran[=<float>] If set, starts it "
+"from random initial conditions instead of "
+"single point.\n"
+" If floating point number "
+"between 0 and 1 is provided it weights the "
+"randomization.\n\n";
if(args!=null&&args.length>0)
{
try
{
for (int i=0;i<args.length;i++)
{
if (args[i].startsWith("-width="))
{
ca.setWidth(Integer.parseInt(args[i]
.substring("-width=".length(),
args[i].length())));
}
else if (args[i].startsWith("-len="))
{
iterations = Integer.parseInt(args[i]
.substring("-len=".length(),
args[i].length()));
}
else if (args[i].startsWith("-rule="))
{
ca.setRule(Integer.parseInt(args[i]
.substring("-rule=".length(),
args[i].length())));
}
else if (args[i].startsWith("-ran"))
{
if (args[i].startsWith("-ran="))
{
ca.randomizeLine(Double.parseDouble(
args[i].substring("-ran=".length(),
args[i].length())));
}
else ca.randomizeLine();
}
else if (args[i].startsWith("-help"))
{
System.out.println(usage);
System.exit(0);
}
}
}
catch (Exception e)
{
System.out.println(e.getClass().getName()
+": "+e.getMessage());
System.out.println(usage);
System.exit(0);
}
}
else
{
ca = new CellularAutomata();
}
for (int i=0;i<iterations;i++)
{
System.out.println(ca.getLine());
}
}
}
(Originally posted on 02 Aug 2004 at my work blog)