1
00:00:00,727 --> 00:00:04,282
On the face of it, elementary cellular
automata are extremely simple.
2
00:00:04,972 --> 00:00:07,550
Each cell is either black or white.
3
00:00:08,120 --> 00:00:11,093
Each cell communicates only with two
neighbors.
4
00:00:11,523 --> 00:00:13,980
The system is completely deterministic,
5
00:00:13,980 --> 00:00:16,662
and a rule is specified by only 8 values,
6
00:00:16,662 --> 00:00:20,588
that is the values of these update states
for the center cell.
7
00:00:20,588 --> 00:00:25,544
But what makes cellular automata so
interesting and so surprising in a way,
8
00:00:25,544 --> 00:00:31,560
is the degree of complexity that this
incredibly simple system can produce.
9
00:00:31,560 --> 00:00:39,307
So for example, suppose we extended to
this lattice to 200 cells and
10
00:00:39,307 --> 00:00:44,003
ran this same rule on this lattice with
some random initial configuration
11
00:00:44,003 --> 00:00:46,565
for a long number of iterations.
12
00:00:46,565 --> 00:00:48,362
Here's what it would look like.
13
00:00:49,792 --> 00:00:54,584
So here, at the top here, we see the
one-dimensional lattice with a
14
00:00:54,584 --> 00:00:59,535
random initial configuration and
time is going down the vertical.
15
00:00:59,555 --> 00:01:05,200
Here the individual cells are very tiny.
You can barely see an individual cell.
16
00:01:05,200 --> 00:01:08,257
You can just kind of see an overview of
black and white
17
00:01:08,757 --> 00:01:12,424
on this much bigger cellular automaton
lattice.
18
00:01:12,944 --> 00:01:17,479
And you can see that we don't get just
random looking behavior,
19
00:01:17,909 --> 00:01:22,628
we get some very structured looking
behavior that is hard to describe.
20
00:01:23,338 --> 00:01:27,417
So it seems like there's some regularities
here, but they're hard to describe.
21
00:01:28,337 --> 00:01:32,394
And that in a sense, is a definition of
complexity.
22
00:01:32,814 --> 00:01:37,321
We'll see later on that this particular
cellular automaton
23
00:01:37,321 --> 00:01:39,467
defined by the rule I just showed you
24
00:01:39,467 --> 00:01:42,925
actually is one of the more complex
cellular automata
25
00:01:42,925 --> 00:01:47,622
in the whole collection of 256 elementary
cellular automata
26
00:01:47,622 --> 00:01:50,188
and has some very special properties.
27
00:01:50,848 --> 00:01:54,104
Stephen Wolfram is a British mathematician
and physicist
28
00:01:54,104 --> 00:01:59,134
who has studied cellular automata
in great depth, and in particular
29
00:01:59,134 --> 00:02:02,293
he's studied these elementary cellular
automata.
30
00:02:02,293 --> 00:02:06,464
He's written a number of books and
articles on this subject.
31
00:02:06,464 --> 00:02:08,986
His most recent, called
"A New Kind of Science",
32
00:02:08,986 --> 00:02:15,999
is a 1200 page discussion of how science
itself could be rethought in terms of
33
00:02:15,999 --> 00:02:19,271
simple systems such as cellular automata
34
00:02:19,271 --> 00:02:22,158
that produce highly complex behavior.
35
00:02:22,158 --> 00:02:26,498
In this subunit and the next one,
we'll talk about some of the results that
36
00:02:26,498 --> 00:02:30,562
Stephen Wolfram found on the class of
elementary cellular automata.
37
00:02:31,372 --> 00:02:36,957
As I said before, to define an elementary
cellular automaton, or ECA,
38
00:02:36,957 --> 00:02:43,063
we have to list all the neighborhoods and
fill in the right side of the arrows with
39
00:02:43,063 --> 00:02:46,267
black and white boxes to
define the update state
40
00:02:46,267 --> 00:02:49,057
for the center cell at the next time step.
41
00:02:49,057 --> 00:02:52,660
We can notice that since each cell
can be either black or white,
42
00:02:52,660 --> 00:02:57,405
that there's two possibilities at each one
of these positions.
43
00:02:57,405 --> 00:03:02,155
This could be either black or white,
black or white, and so on.
44
00:03:02,185 --> 00:03:08,478
And so the total number of possibilities
is two times two times two, etc.,
45
00:03:08,478 --> 00:03:12,858
two raised to the eighth power,
which is equal to 256.
46
00:03:12,858 --> 00:03:18,825
So there's 256 possible elementary
cellular automata - not so many -
47
00:03:18,855 --> 00:03:25,106
and in fact Wolfram looked in great
detail at the behavior of all of them.
48
00:03:25,106 --> 00:03:30,283
In order to do a complete survey of
these 256 possible cellular automata,
49
00:03:30,283 --> 00:03:35,654
Wolfram came up with a way of giving each
one a unique numerical code.
50
00:03:35,654 --> 00:03:39,677
These codes are called Wolfram numbers
and here's how they work.
51
00:03:39,677 --> 00:03:43,493
Suppose that this is the rule that I'm
going to encode.
52
00:03:43,493 --> 00:03:48,077
What I would do is for each of the update
states over here,
53
00:03:48,077 --> 00:03:51,839
if a box is white, I give it a zero,
54
00:03:51,839 --> 00:03:54,547
if it's black, I give it a one.
55
00:03:54,547 --> 00:03:58,881
Now I take that series of
ones and zeros,
56
00:03:58,881 --> 00:04:05,818
I'm going to flip it over, like this, and
then I'm going to turn the numbers upright
57
00:04:05,818 --> 00:04:12,515
and what I would now do is interpret
this as an integer in base two.
58
00:04:12,515 --> 00:04:17,509
And the way to do that is to notice
that this corresponds to the ones place,
59
00:04:17,509 --> 00:04:21,337
this corresponds to the twos place,
the fours place,
60
00:04:21,337 --> 00:04:27,781
the eights, sixteen, thirty two,
sixty four, one twenty eight, etc.
61
00:04:27,781 --> 00:04:34,203
OK so here we have zero times two to the
seventh, one times two to the sixth,
62
00:04:34,203 --> 00:04:39,502
and so on. So this is just the normal way
in which you would encode a string of
63
00:04:39,502 --> 00:04:43,329
ones and zeros as an integer in base two
and if you multiply that out,
64
00:04:43,329 --> 00:04:47,101
you get that this is a hundred and ten
in decimal
65
00:04:47,101 --> 00:04:50,371
and Wolfram would call this rule 110.
66
00:04:51,041 --> 00:04:54,736
Let's do one more example, just to
make sure that you got it.
67
00:04:55,296 --> 00:04:57,533
So here's my new rule.
68
00:04:59,093 --> 00:05:02,731
I assign ones and zeros to the update
state.
69
00:05:03,701 --> 00:05:07,151
I turn it on its side by flipping it
over like this.
70
00:05:07,661 --> 00:05:11,505
And so I get one one zero zero zero zero
zero one
71
00:05:12,135 --> 00:05:16,361
Now I interpret this as a integer
in base two.
72
00:05:16,761 --> 00:05:21,714
So this is one times two to the seventh
plus one times two to the sixth
73
00:05:21,714 --> 00:05:25,797
plus zero times everything else
plus one times two to the zero
74
00:05:25,797 --> 00:05:27,273
which is just one
75
00:05:27,513 --> 00:05:33,720
so we get 128 + 64 + 1 = 193.
76
00:05:34,230 --> 00:05:37,515
So this would be Rule 193.
77
00:05:37,965 --> 00:05:41,142
Now let's have another little quiz
78
00:05:41,142 --> 00:05:44,273
just to test your understanding of
Wolfram numbering.