In A New Kind of Science, Wolfram argues that Rule 30, one of his favorites, is a random number generator, for which the sequence of numbers produced has properties that are entirely unpredictable without actually running the rule. Wolfram wrote of this, which he called "probably the single most surprising scientific discovery" he has ever made: "none of the tests I have ever done on it [the sequence of colors directly below the initial black cell] show any meaningful deviation at all from perfect randomness" (op. cit., p. 28). The mystical properties ascribed to Rule 30 are perhaps most eloquently described in an article in Fortune magazine by Michael S. Malone, Forbes ASAP, 11.27.00:
Rule 30, a pattern that grew more intricate and unpredictable with each step. It was stuffed with what mathematicians call "emergent effects": events that cannot be predicted in advance. From the simplest of parts, Wolfram had created infinite complexity. The aha! moment had arrived. "The Rule 30 automaton is the most surprising thing I've ever seen in science," Wolfram told London's Daily Telegraph. "'Even though it starts off from just one black cell, applying the same simple rule over and over again makes Rule 30 produce [an] amazingly complex pattern.
"It took me several years to absorb how important this was. But in the end, I realized that this one picture contains the clue to what's perhaps the most long-standing mystery in all of science: where in the end, the complexity of the natural world comes from."
The more Wolfram studied Rule 30, the more incredible it became. For example, though the black-and-white triangle, the product of 2 million calculations, seemed to exhibit a certain symmetry, it was, in fact, chaotic. In particular, following the single line of black and white tiles that ran vertically from the peak of the pyramid, Wolfram found perfect chaos—i.e., a pure random number generator. He showed it to his old Caltech physics mentor, the late Nobel laureate Richard Feynman. Feynman was convinced there had to be some regularity in Rule 30. He took off for Hawaii on vacation and, for fun, spent the time there bent on proving Wolfram wrong. When he returned, he admitted he'd failed to find any sign of order.
Now, I admire Richard Feynman like I admire nobody but Albert Einstein, yet I hypothesized based on preliminary visual inspection that two successive whites would predict the next one is white more often than not. This was indeed confirmed. The plot below shows the probability that a square in the centra column is white given that the preceding N squares are black, in rows 26,400 through 40,795:
As you can see, the distribution is far from a random homogeneous distribution. QED.
Wolfram himself gives 8 tests of randomness, the first of which is "frequency or equidistribution test (possible elements should occur with equal frequency)" (op. cit., p. 1084). It is this first test that Rule 30's sequence fails to pass: sequences with many identical colors are more common than a quasi-identical sequence of the same length with the last color reversed.
Unless, of course, there is a bug in my programs. But I did write two different versions, and both seem to yield the same sequence.
See below for computational details.
--Alex Backer, Ph.D., Caltech, Pasadena, California, May 31st, 2002.
function [cen,pval]=rule30lomem(Niter,start,cen)
% function [cen,pval]=rule30lomem(Niter,start,cen)
% See if I can predict central column better than chance (50-50)
% AB May 02
%
% Default START = 3; used as start of interval for prediction at bottom, end of interval=Niter
%
% Supersedes RULE30 - uses less memory xq does not store pattern matrix, and is newer
if nargin<2,
start=3; % Must be >=3 xq uses previous 2
end
saveeveryN=100;
cm
cd Automata
h=timebar(0);
if nargin<3,
% Calculate pattern necessary for central column up to Niter iterations:
% Inductive:
% Boundary cond:
c=zeros(2,Niter*2); % Initial conditions
c(1,Niter)=1; % c(lin,col); 1=black, 0=white
cen(1)=1;
%c=uint8(c);
% Induction:
% In order to calculate central column value at iteration Niter, you need 1 value each way of previous iteration, 2 values each way
% of the one before, etc.
% Because values more than iter-1 columns out of the central one are zero, we need to calculate a rhombus of values to get
% central column value at iteration Niter
nb=0;nw=0;
a=2;
lin=2;
for col=Niter-(lin-1):Niter+(lin-1),
if ~c(a-1,col) & ~c(a-1,col+1), % if above and above right are white,
c(a,col)=c(a-1,col-1); % keep color of above left
else,
c(a,col)=1-c(a-1,col-1); % else use opposite color
end
end
cen(lin)=c(a,Niter);
im=c;
colormap gray
c(1,:)=c(a,:);
for lin=3:floor(Niter/2)+1,
timebar(lin/Niter,h,'Calculating pattern');
for col=Niter-(lin-1):Niter+(lin-1),
if ~c(a-1,col) & ~c(a-1,col+1),
c(a,col)=c(a-1,col-1);
else,
c(a,col)=1-c(a-1,col-1);
end
end
cen(lin)=c(a,Niter);
im=[im;c(a,:)];
c(1,:)=c(a,:);
if ~cen(lin-1) & ~cen(lin-2),
if cen(lin),
nb=nb+1; % # black
else,
nw=nw+1; % # white
end
% nb & nw don't add to Niter because they only include elements for which previous two where white
end
%[nb,nw]
if ~rem(lin,saveeveryN),
save rule30 lin cen c
imagesc(1-im(:,Niter-lin:Niter+lin))
end
end
width=Niter-lin;
for lin=floor(Niter/2)+2:Niter,
timebar(lin/Niter,h,'Calculating pattern');
for col=Niter-width:Niter+width,
if ~c(a-1,col) & ~c(a-1,col+1),
c(a,col)=c(a-1,col-1);
else,
c(a,col)=1-c(a-1,col-1);
end
end
cen(lin)=c(a,Niter);
c(1,:)=c(a,:);
width=width-1;
if ~cen(lin-1) & ~cen(lin-2),
if cen(lin),
nb=nb+1; % # black
else,
nw=nw+1; % # white
end
% nb & nw don't add to Niter because they only include elements for which previous two where white
end
%[nb,nw]
if ~rem(lin,saveeveryN),
save rule30 lin cen c
end
end
% Recursive:
% recursion uses previous results more than once, so keep track
%c(Niter,Niter)=
else,
% Predict
%timebar(0,h,'Calculating frequencies...')
[nb,nw]=predict(cen,start,Niter)
end
% X-corr:
XCORR=0;
if XCORR,
xc=xcorr(cen,'unbiased');
figure(2);plot(xc)
m=mean(xc(1:Niter-2))
xc1=xc(Niter-1)
pval=sum(xc(1:Niter-2)>xc1)/(Niter-2)
end
% Significance:
Nrand=100;
npos=0;
rand('state',sum(100*clock));
for i=1:Nrand,
timebar(i/Nrand,h,'Evaluating significance...');
r=floor(rand(1,Niter)*2);
[cnb,cnw]=predict(r,start,Niter);
if abs(cnw-cnb)>=abs(nw-nb),
npos=npos+1;
end
end
cnb,cnw
pval=npos/Nrand
close(h)
function [nb,nw]=predict(cen,start,Niter)
% Predict
nb=0;nw=0;
for i=start:Niter,
if ~cen(i-1) & ~cen(i-2),
if cen(i),
nb=nb+1; % # black
else,
nw=nw+1; % # white
end
% nb & nw don't add to Niter because they only include elements for which previous two where white
end
end
%[nb,nw]
function pwhitefnn(maxn,white,cenrange,nv)
if nargin<1,
maxn=15;
end
if nargin<2,
white=1;
end
if nargin<4,
nv=1:maxn;
end
Nrand=0; %100;
cm;
cd Automata
load rule30iter40795 %31300 %26400
if nargin<3,
cenrange=1:length(cen);
end
cen=cen(cenrange);
Niter=length(cen);
start=[];
h=timebar(0);
for n=nv,
timebar(n/maxn,h);
[cen,pval(n),nb,nw]=rule30lomemn(Niter,start,cen,n,Nrand,white);
pwhite(n)=nw/(nb+nw);
end
close(h);
figure
plot(pwhite)
xlabel('N')
if white,
ylabel('p(white|N previous samples were white)')
else,
ylabel('p(white|N previous samples were black)')
end
figure
plot(pval)
xlabel('N')
ylabel('p-value')
function pwhitefnnfncen(maxn,white,cenrange,nv,cen)
% pwhitefnnfncen(maxn,white,cenrange,nv,cen)
if nargin<1,
maxn=15;
end
if nargin<2,
white=1;
end
if nargin<4,
nv=1:maxn;
end
Nrand=0; %100;
cm;
cd Automata
%load rule30iter40795 %31300 %26400
if nargin<3,
cenrange=1:length(cen);
end
cen=cen(cenrange);
Niter=length(cen);
start=[];
h=timebar(0);
for n=nv,
timebar(n/maxn,h);
[cen,pval(n),nb,nw]=rule30lomemn(Niter,start,cen,n,Nrand,white);
pwhite(n)=nw/(nb+nw);
end
close(h);
figure
plot(pwhite,'x')
xlabel('N')
if white,
ylabel('p(white|N previous samples were white)')
else,
ylabel('p(white|N previous samples were black)')
end
% figure
% plot(pval)
% xlabel('N')
% ylabel('p-value')
>> cen=rule30lomem(1000);
nb = 127
nw = 156
>> cen=rule30lomem(2000,1000);
nb = 121
nw = 144
>> cen1=rule30lomem(2000,3,cen);
nb = 248
nw = 300
pval = 0 (Nrand=100)
After long run that I lost:
[nb,nw]= 2548 2505
pval<0.001 (using absolute values)
After long strings of white, white is much more probable than black. The longer the string, the more the asymmetry.
The reverse happens with long strings of black (see below).
Note that p-values below are double-sided, so real p-values are half of that shown.
0 below means white string:
>> pwhitefnn(14,0,26401:40200)
nb = 3377
nw = 3414
pval = 0.6600
nb = 1702
nw = 1675
pval = 0.6400
nb = 863
nw = 839
pval = 0.5500
nb = 454
nw = 409
pval = 0.1600
nb = 249
nw = 205
pval = 0.0300
nb = 128
nw = 121
pval = 0.5900
nb = 67
nw = 61
pval = 0.6500
nb = 37
nw = 30
pval = 0.4400
nb = 23
nw = 14
pval = 0.1200
nb = 14
nw = 9
pval = 0.1700
nb = 11
nw = 3
pval = 0.0500
nb = 9
nw = 2
pval = 0.0200
nb = 8
nw = 1
pval = 0
nb = 7
nw = 1
pval = 0
Black strings:
>> pwhitefnn(14,1,26401:40795,10:14)
nb = 10
nw = 15
pval = 0.2100
nb = 4
nw = 11
pval = 0
nb = 3
nw = 8
pval = 0.0300
nb = 2
nw = 6
pval = 0
nb = 1
nw = 5
pval = 0.0100
pwhitefnn(14,0,26401:40795)
To start rule30lomemcontfast using data from rule30lomemcont:
load rule30iter44100
newc=ones(1,Niter*2-1);
newc(1000000-110000:1000000-110000+size(c,2)-1)=c(1,:);
Niter=1000000;[cen,pval]=rule30lomemcontfast(Niter,11,cen,newc,lin);
>> pwhitefnnfncen(20,1,cen)
nb = 35037
nw = 35092
nb = 17565
nw = 17527
nb = 8676
nw = 8851
nb = 4428
nw = 4423
nb = 2211
nw = 2212
nb = 1100
nw = 1112
nb = 558
nw = 554
nb = 267
nw = 287
nb = 139
nw = 148
nb = 61
nw = 87
nb = 28
nw = 59
nb = 22
nw = 37
nb = 13
nw = 24
nb = 9
nw = 15
nb = 6
nw = 9
nb = 3
nw = 6
nb = 3
nw = 3
nb = 2
nw = 1
nb = 1
nw = 0
nb = 0
nw = 0
>> pwhitefnnfncen(20,0,cen)
nb = 35133
nw = 35037
nb = 17620
nw = 17513
nb = 8840
nw = 8780
nb = 4484
nw = 4356
nb = 2323
nw = 2161
nb = 1183
nw = 1140
nb = 596
nw = 587
nb = 313
nw = 283
nb = 156
nw = 157
nb = 76
nw = 80
nb = 43
nw = 33
nb = 20
nw = 23
nb = 11
nw = 9
nb = 9
nw = 2
nb = 7
nw = 2
nb = 5
nw = 2
nb = 4
nw = 1
nb = 3
nw = 1
nb = 2
nw = 1
nb = 1
nw = 1
Vectorized form shown to produce same sequence as non-vectorized one for 1st 20 iterations. If I made a mistake, it could only have been in the sequence passed to the vectorized to continue after 43300.
All iterations after conversion to vectorized form feeding the last line inverted:
>> length(cen),pwhitefnnfncen(20,0,cen(43301:end))
ans = 140300
nb = 24191
nw = 24240
nb = 12102
nw = 12089
nb = 6025
nw = 6077
nb = 2995
nw = 3030
nb = 1510
nw = 1485
nb = 750
nw = 760
nb = 370
nw = 380
nb = 190
nw = 180
nb = 92
nw = 98
nb = 40
nw = 52
nb = 20
nw = 20
nb = 5
nw = 15
nb = 0
nw = 5
nb = 0
nw = 0
nb = 0
nw = 0
nb = 0
nw = 0
nb = 0
nw = 0
nb = 0
nw = 0
nb = 0
nw = 0
nb = 0
nw = 0
>> pwhitefnnfncen(20,1,cen(43301:end))
nb =
24241
nw =
24327
nb =
12192
nw =
12135
nb =
6024
nw =
6111
nb =
3076
nw =
3035
nb =
1536
nw =
1499
nb =
764
nw =
735
nb =
371
nw =
364
nb =
181
nw =
183
nb =
91
nw =
92
nb =
37
nw =
55
nb =
17
nw =
38
nb =
14
nw =
24
nb =
9
nw =
15
nb =
6
nw =
9
nb =
4
nw =
5
nb =
2
nw =
3
nb =
2
nw =
1
nb =
1
nw =
0
nb =
0
nw =
0
nb =
0
nw =
0
To start rule30lomemcontfast using data from rule30lomemcont: correctly:
load rule30iter44100
cen=1-cen;
c=1-c;
newc=ones(1,Niter*2-1);
newc(1000000-110000:1000000-110000+size(c,2)-1)=c(1,:);
Niter=1000000;[cen,pval]=rule30lomemcontfast(Niter,11,cen,newc,lin);
--Alex Backer, Ph.D., May 31st, 2002.
Comments (0)
You don't have permission to comment on this page.