U1L2f.txt

#
# File:   content-mit-8370x-subtitles/U1L2f.txt
#
# Captions for course module
#
# This file has 216 caption lines.
#
# Do not add or delete any lines.  If there is text missing at the end, please add it to the last line.
#
#----------------------------------------

Reversible computing was born historically
as a topic motivated by these connections between physics
and computation.
And the way I would like to frame it
to you in this discussion is via this question,
is kT log 2 fundamental?

Well, if you look at a primitive gate like the AND gate
we have spent so much attention on today,
we have an x, y, and x and y, and the four possibilities.
And it gives these outputs over here.
And you know, if you stare at this output,
you realize that this is irreversible.

Every time you use an AND gate, you can't go backwards anymore.
And that means if you had a random xy coming in,
you have less randomness of the output.
And so some entropy was charged to your credit card here.
Maybe banks should always charge in units
of entropy instead of dollars.
I know some of my kids would love that.
But that loss of information means that an AND gate cannot
but cost some energy every time it's used.
But can we build a computation without using AND gates
without this kind of a cost?
It turns out the answer is yes.
And the way I can show you the answer is yes is really neat.
And it's this answer which fascinated
Richard Feynman, and in many ways also got me started.

And that is by showing that you can build a computer out
of just billiard balls, pool table balls knocking together
and hitting each other.

This is a mechanical model of computation.
And yet it is so inspiring to look at this model
because all it requires is the laws of Newtonian mechanics.
It's frictionless.
All the balls will roll around.
And I will now show you how he we
build logic gates out of balls moving around and colliding.
Let's say we have a ball here and it's going
to shoot off in some direction.
Another ball may or may not be present here.
It will also shoot off in a direction.
Let's call the absence or presence
of this ball x, and the absence or presence of this ball y.
Now the two balls will collide because they
have a finite radius at some point
and subject to the accuracy of my drawing.
And then they will bounce off and go
to certain final positions.
So this ball, if there were another ball here,
would bounce off, come here.
But if this ball had not been present, if y had been 0,
this would have gone somewhere over here.
Now if both balls were present, we'd get the ball over here.
If x were 0, this would have gone straight and ended
up somewhere over here.
And therefore, we now have a logical assignment
for the output values.
What is this one?
Somebody tell me.
Purple shirts are OK.

How do I express the presence or absence of this top ball
in terms of x and y?

Hey, you can do one.
Anyone?

Go ahead, purple shirt.
Oh, OK.
I would say both balls have to be [INAUDIBLE]..
So [INAUDIBLE].
In terms of x and y.
Yeah, oh, xy, sorry.
xy.
Exactly.
OK, fellow in the corner over there.
What's the next ball over here?
How do I represent this?
[INAUDIBLE] there happens-- so it would be--
so y would go there [INAUDIBLE].
That's right, x bar y.
And then this one it follows this by symmetry x y bar.
And this one is the same as the top.
It's xy.
Look at that.
So I have a gate here.
And I can make an AND gate because this is x and y.
I can make a NOT gate by always having a bar y over here,
and then it will select--
this line will be x bar because y will always be equal to 1.
So I have an AND gate and I have a NOT gate,
and I get all computation just by having balls collide.
So this is a famous result. I encourage
you to read more about this and its models Fredkin and Toffoli
wrote about this in a paper called
"Conservative Logic" in the International Journal
of Theoretical Physics--
no computer scientists here--
in 1982, volume 21, page 219.
OK, there's much more with regard to this.
And I'm not going to go into that in detail
for lack of time, but I want to now share
with you a little more of their story
and how they then built a language of gates,
reversible circuits, and reversible computation.
And that's where we'll end in 10 minutes.

By the way, I can't resist but tell you
a little bit about this fellow.
So Ed Fredkin is, to my knowledge,
the only person who's become a faculty member at MIT
with no graduate degree, no PhD, no bachelor's degree,
and no high school degree.
And he owns, or owned an island in the Caribbean.
Who knows where it is these days,
or if it exists anymore for many reasons.
But he's quite a character.
And he got started by working not just on this,
but ideas with cellular automata.
And I think he gave a talk at the Center for Theoretical
Physics just two or three years ago.
A very creative individual.
And one of the things he is known for is a family of gates.
And I want to introduce to you now such
a family of reversible gates.
Oh, by the way, also, I know nobody
who's actually built a physical billiard ball computer.
If you're an aspiring [INAUDIBLE],, why not?
Because maybe you could build one that operates
with very little energy.
Why doesn't Intel build its computers out
of balls inside processors, banging around?
Anyone know?

Speed might be an issue.
Speed might be an issue?
No.
So that's not quite the reason.
You know, practically speaking, you're probably right.
But not from a fundamental principles standpoint.
Yes, please.
Would space or crossover?
Space or crossover?
So there is a way to cross over.
If I have these things, which are
hard walls that are known as barriers,
I can have x and y come in.
And you can stare at this and convince yourself
that x and y bouncing, they'll bounce here,
they'll go off, bounce, bounce, bounce off of each other
again, and always go like this.
For x and y in, you get y and x out, works great.
Not for Intel.
Yes, please.
[INAUDIBLE] small enough and quantum tunneling
becomes an issue.
If it's small enough, quantum tunneling becomes an issue.
You're too smart for this question.
The answer is no, not that.
But an expert might say that.
Others?
Yes, please.
I guess it's really hard to find the [INAUDIBLE]..
It's very hard to find a material that
has the right kind of elastic properties.
Actually, you want these to be inelastic as much as possible.
[INAUDIBLE]
Oh, good.
Hard to find an inelastic hard sphere model--
material.
Well, there are some very hard materials.
I bet, I bet if you're an undergraduate at MIT,
you could solve that problem.

[INAUDIBLE] difficult to do fan out?
No, it's actually very easy to do fan out.
But I haven't shown it quite here.
Actually, you can turn this gate into a fan out
if you think about it for a moment.
Yes, please.
It's hard to reset after you've used it.
It's hard to reset after you've used it.
You're almost getting the idea I'm looking for.
And this is the thing, the crux of the issue.
If you have a small error, a small misalignment,
a small mistiming of a bar that went a little too fast
or started a little too late, then you
have to correct for that error.
Because otherwise the error will just cascade and grow
into bigger and bigger errors.
And pretty soon the balls will all be moving chaotically
all over the place.
It turns out the only reason you need
to plug your computer into the wall is because you need
your computer to be reliable, to kind of always
put up the blue screen of death at exactly the same time.
Because otherwise, at least from a fundamental principle
standpoint, you do not need to consume energy for computation.
And that's the main point I want you to gather in the last five
minutes of the lecture.
Question?
Me?
Yes.
So is this true for all reversible gates?
This tolerance--
This sort of tolerance [INAUDIBLE]..
This susceptibility to errors.
Yes and no.
But I'd like to come back to that when
we talk about error correction.