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.