Okay, just to summarize.
If we have n bits, this corresponds to 2^n possibilities,
and we'll always define 2^n to be N, if we have a little n.
If we have N possibilities, where N could be three, this corresponds to log base 2 of n bits,
which doesn't have to be a number, for instance, log to the base 2 of 3 is between one and two bits.
I guess, it's still a number but it's not a natural number.
Then we also looked at probabilities.
So if the frequency of heads is m_h/m,
I have a sequence of heads and tails,
I count the total number of heads, I count the total number of tails,
I define this to be q(h) and I define q(t),
this is equals 1-q(t), because it's either heads or tails,
our coins are not landing on their sides and just staying there like that,
then the log base 2 of the number of sequences with frequency q(h) for heads and q(t) of tails,
this is equal to m(-q(h) log base 2 q(h) - q(t) log base 2 q(t)),
and we define this to be the amount of information or entropy, and so sequences.
And if the logarithm of this number is equal to this,
that implies that the total number of such sequences, that is, sequences with this frequency,
is approximately equal to 2^(mI) or 2^(mS).
So this special formula, almost magical but not magical because it's just mathematical,
this formula which shows up all the time in information theory,
minus the sum of q log q or minus the sum of p log p,
is just a way of counting numbers of sequences
if you're given a particular kind of frequency.
So there's an intrinsic relationship between frequency, probability and information,
and that relationship is given by this formula.
In a bit, maybe a lecture or two down the line in these ten minute lectures,
we'll talk about how to apply this fundamental formula about information theory to the
problem of communication.
How many bits of information can you send down a communication channel?
For example, I'm talking right now.
My larynx is wiggling, they're sending vibrations through the air,
this is a physical system, information is being conveyed,
but because it's a physical communication channel, there are physical limits to how much
information I could probably communicate to you,
assuming, of course, you think I am communicating any information at all.
These fundamental formulas of information theory allows us to put limits on the capacity of any
communication channel, any communication channel that's realized by a physical medium,
and those are the only communication channels I know about.
But before we do this, let's talk about the relationship between information and computation.
Let's talk about information processing.
This also goes under the name of computation,
and it also goes under the name of Boolean logic.
Boolean logic, what is Boolean logic?
Well George Boole was a 19th century logician who came up with Boolean logic.
He actually was married to Mary Everest, who was the daughter of the surveyor of the
British Raj of the same name after whom Mount Everest is named.
Boole wrote a modestly-titled book called the Laws of Thought.
He'd fit in right well with the kind of modesty that goes on in the Santa Fe Institute nowadays,
I'm sure we'd welcome him with open arms.
So what is the content of Boole's laws of thought?
Boole was interested in logical propositions,
and logical propositions can either be true or false.
By the way, if we're going to map this the way computers do this,
often we call true - 1 and false - 0.
This is just a convention.
Those of you who are more fond of zero than one can have the opposite convention if you like,
but I'm going to adopt this convention right here.
So Boole was interested in questions like, suppose I have a proposition X,
so X is 'it's sunny'.
And I have another proposition Y, and Y is, for example, 'it's raining'.
So either it's sunny or it's not sunny.
So it could be true if it's sunny or it's false if it's sunny.
It could be true if it's raining or it's false if it's raining.
And Boole was interested in propositions of the form X AND Y.
X AND Y means that it's sunny and it's raining.
Now actually where Boole lived in Ireland, it was probably, usually, false.
Usually false in this case.
And he was also interested in propositions like X OR Y.
Now, either it's sunny or it's raining.
It could also be cloudy and not raining.
So sometimes true.
And he was also interested in propositions like, if X then (NOT Y).
So if it's sunny then it's not raining.
Probably largely true.
So he wanted to break down logical statements into propositions of this form,
using ideas like X AND Y, that a proposition is true if and only if its constituents are true.
X OR Y, this proposition is true if and only if one or more of its constituents were true.
Or more complicated propositions like if X then NOT Y,
which is some Boolean function of its constituent propositions.
Here is a glorious fact.
If I say X AND Y, I write this as X ⋂ Y.
X OR Y, I can write this as X ⋃ Y,
this is the notation that Boole developed.
NOT X, I write this as X with a little twiddle in front of it (~X) to say that it is not true.
If X then Y, I write this as X → Y, if X is true then Y is true.
Then Boole had a beautiful theorem that says, "Any possible logical expression can be written
down in terms of composing these kinds of propositions.
So, for example, X ⋂ (Y ⋃ ~X) → Y ⋂ (X ⋃ ~Y).
Now I've no idea what this means.
And what Boole gave is a set of rules to evaluate when such expressions could be true
and when they're not true.
So if I just speak this out in terms of sunny and raining,
it's sunny and it's raining or it's not sunny then it's raining and it is sunny or not raining.
Sounds false to me.
But what Boole showed is that any possible logical proposition could be written in this way.
And this is why he modestly entitled his book, "The Laws of Thought".
Because he was interested in logic, he noted that any possible logic proposition could be
written out in terms of these simple rules,
and here is a even more remarkable fact,
and the fact is, and this is not a mid-19th-century thing,
this is a beginning-of-the-21st-century thing,
all digital computers are doing is evaluating such Boolean expressions.
A computer just breaks up things into operations.
And we can have an operation, this is how I write the same kind of thing in computer language,
this says X AND Y, and this is what's called an AND gate.
An AND gate is simply a device in the computer that takes in the inputs X AND Y, which are zero and one,
and outputs X AND Y, and this is equal to one if and only if X = 1, Y = 1, otherwise it's equal to zero.
Similarly, we have an OR gate, which is written like this, and the output is X OR Y,
this is equal to one if X OR Y is equal to one.
It's equal to zero if X = 0 and Y = 0.
It's a physical device that implements this logical operation OR.
The AND gate is something that implements the physical operation AND.
And we have something that implements NOT X.
So NOT X = 0 if X = 1 and it's NOT X = 1 if X = 0.
So this is AND, OR, NOT and the final operation is a COPY operation.
So I take X and I make two copies of it.
So these are the computer digital versions of Boolean logic,
they are actually physical devices that implement Boole's universal laws of thought.
Mind you, there are plenty of ways of thinking that I do and that other people do and the
dogs and cats do that cannot obviously be broken down into this Boolean logic,
so I'm not sure how universal it is.
We have these four different kinds of gates: AND, OR, NOT and COPY.
And now here's a remarkable thing.
So Boole's theorem, his universal theorem, says that any set of digital logic operations,
that is to say what a digital computer can do,
including your iPhone, or if you're an Android person, your Android phone,
can be broken down into AND operations, which looks like this in computer science lingua,
OR operations, which looks like this,
NOT operations, which are written like this for some historical reasons,
and COPY operations, which are written like this.
So all your smartphone is doing, all your computer is doing
is breaking down logical processes and information processing into fundamental units of combining
these operations of AND, OR, NOT and COPY.
And as George Boole showed in the 1840s and fifties, it's possible to break down any kind of logical expression
into the set of operations.
So we have information, we have bits, we have ways of processing and transforming those information,
or that information, sorry,
using elementary physical systems which are logic gates,
and all the digital computation is doing is combining these sets of operations in arbitrarily
complicated ways.