Tip:
Highlight text to annotate it
X
My name is Emma and I read Turing's Cathedral,
and I am here with Professor of Computer Science, Christos.
What is the Turing Machine and what did it do?
The Turing Machine is in many ways the first computer.
It was designed by an undergraduate, Alan Turing. Computers were just under the horizon.
People were talking about them, dreaming them, but Turing's take was special.
He was working on a theorem to prove something was impossible.
His theorem: you cannot take a logical statement and decide that it has a proof.
Paradoxically, everyone else was trying to create a computer for a practical reason.
This is his paper: "On computable numbers with an application to the unpronounceable."
How old was he when he wrote this? 23
He had just finished his undergraduate education
Among mathematicians trying to define computation, Turing got physical.
He dreamed it with states and tape.
Imagine this tape, divided into squares, can go as long as you want in either direction.
Each square contains a symbol. Immediately this is digital.
Can you give us an example of a Turing Machine? Oh, sure. (Emma laughs)
That's better. Here's it's tape, extends ad infinitum left and right,
and this 3x3 table is its program
What's a program in a Turing machine? It's a table that tells you what to do under any
circumstance.
Turing did not only say that a computer writes concrete discrete symbols
He also said that at any moment a computer can be in one of a finite number of states.
This computer is simple: it can be in one of three states of mind: A, B or C.
Angry, confused, and whatever B is. (Emma laughs)
What would each state of mind imply?
If you see you are in this state, and you see this symbol, do this.
This tape has mostly zeroes. In Turing's notations zeroes were the blanks.
In this tape there is a one somewhere.
This machine wants to find it. The mission of this machine is to find the one and stop.
Even this task is not trivial: if you are here you don't know whether to go left or
right.
If you go right you will go on forever; if you go left you are lucky.
What this machine does is sort of clever
It goes right one, then left twice . . . until it finds the zero.
So let's see. We are in state A and we are looking at the symbol zero.
What should we do? (Emma points) Yes,
and what else? We erase (cross out) the zero and put a two instead.
So now we are here. We are in state B and we see a two.
[C] What do we do? [E] One to the right.
[C] Now we are still in state B, but [E] we see a zero.
So we have to overwrite a 2 here again.
[E] and move to state C. [C] Exactly. [E] and now we are in C and we see a 2.
Yes, which brings us here. And now we are in C and still see a 2 so we move left.
[E] Now we are in C and we see a zero, [C] which means we have to [E] mark it with a
2 and go to B.
[E] then we are in B and see a 2
So we go here, here, here, erase, C, here, here, here, VICTORY!
Of course! So this is what a Turing Machine does?
[C] The Turing Machine accomplished this. [E] And why was that important?
No matter what a computer (which means the person computing) does,
they are going to be writing symbols and changing states of mind and doing something like that.
You said earlier that universality was one of the most important things Turing came up
with.
[C] Yes. [E] What is universality, how does it work, and had it not existed before?
This machine we just saw is not a universal machine. It does one particular thing.
[E] Which is? [C] Finding a 1 on a tape. It does this very well.
Even Turing himself later came up with a machine, in England, whose only purpose was to break
the German code.
Successfully.
All these other people were thinking about computers to do one specific thing.
So if there weren't universality we would have a different computer for adding . . .
[C] Exactly. You would go to a computer store and find many departments
The dept of scientific calculations, of business calculations,
or sending emails, or browsing the web, or doing your taxes . . .
[E] and it would all be separate computers. [C] Right. This was how people were seeing
the future.
Turing came up with this idea. I showed you a simple machine. Turing came up with another
machine -- a universal machine.
What does universality mean? It means that this computer can take a description from
another machine
and then mimic that other machine.
How would it get that description?
Looking into the code of the other machine. This is the beginning of software.
The reason we don't have a different computer for every task is we download software and
it does it for us.
Software is the most important in the world of the computer.
The software says the following: that the symbols you have on the tape, in your computer's
memory,
can be both nouns and verbs, can be both data and code.
[E] How does that work? [C] People write programs for these things that need to be done on a
machine.
Then there is a universal Turing machine called a compiler, or interpreter,
that takes these programs and makes them into simple symbols that go into the computer's
memory.
These symbols make the computer do nice or nasty things on other symbols.
These are so to speak the "verbs." [E] Other digits? [C] Other digits.
Von Neumann was very much influenced by Turing's ideas.
Especially universality. That's why von Neumann's machine is almost pointedly universal
through the software, which uses symbols to write code, which tells symbols what to do
with other symbols.
It's the duality of computers, with programs and data -- the same thing.
In some sense computers are the only device that's universal.
When some physicist in Switzerland in 1999 discovered how to click . . .
[E] click a mouse. [C] yes, click a mouse and go somewhere else-
All these computers, thanks to Turing, were universal
[E] So they could be taught how to click. [C] They could be taught in an instant.
The reason that the internet spread like wildfire is that computers were universal.
[E] Because of Turing. [C] Because of Turing.
What happened to Turing? What did he go on to do? He was so young when he invented the
He came to the U.S.and got his PhD from Princeton,
The war broke out, he went back to England,
and he was one of the scientific leaders of the efforts to break the German codes.
[E] which he successfully did. [C] yes.
He went on to help kickstart the British computer industry after the war.
Then, as the book says, he had an incredible death.
He was essentially murdered by the state that he had helped to win the war.
How did they kill him?
Turing was homosexual. That was illegal in the UK 1952.
Turing was an amazing man. As a scientist he lived 30-40 years ahead of his time.
Unfortunately he got carried away with his personal life, as if it was 30-40 years ahead
of his time.
So he volunteered to a police officer that he was a homosexual.
[E] He told the police officer? [C] Yes.
He was asking about something else and he asked "Do you know this man?" and he said
"Yes,"
And he asked "Do you know him well?" and he said "Yes"; "How well?", "He's my lover."
He was given a choice: either go to jail or take hormones.
[E] And they were believed to be a "cure" for being ***? [C] Yes.
[E] And it did something to his mind. [C] He committed suicide.
[E] How old was he when he died? [C] 42. He would be a very old man now,
but it's not unthinkable that he would be alive. We just celebrated 100 years from his
birth.
[E] Hearing the story about Turing interests me because it shows that the discipline of
computer science . . .
Was actually built by Jewish exiles, by *** men, by women
and that is a very different story than I would have expected.
The way that computer science is presented, and many disciplines, you don't know who built
it until you read their stories.
That's right. That's a wonderful observation. Women were very active in the beginnings of
computers.
What von Neumann succeeded in was to build a computer like today's computers with software.
Actually his wife, Klari, was in some sense the first programmer.
There are some beautiful photos of Klari computing and von Neumann kibitzing over her shoulder.
A strange thing happened: if I look at my class only 20% of the students are female.
The reason --my theory-- is that in the 80's and 90's and 00's a "hacker culture" prevailed.
I really think that the computer scientist today must understand humans, must understand
many other sciences . . .
must understand social sciences, psychology, physics, must understand the history.
Thank you for talking to me -- I loved learning about Turing machines, and if I were an undergraduate
I would probably take a Computer Science class.
[C] Great! [E] I was always afraid to when I was an undergrad. I regret that.
[C] You can do it now, you know! [E] That's true. (Both laugh)
[E] Thank you. [C] Thank you.