subt
Alan Turing was born in 1912 and died in 1954, at the age of 41.

In the meantime he invented the computer and won WWII.

Nothing less.

As a child, Alan Turing was quite

an excellent, assiduous and interested student. He was in fact so assiduous

that the local press spoke of him

when, at the age of 13, he rode his bike 90 km to school to attend

the first day of term

despite the 1926 General Strike.

He even stopped overnight

at an inn.

Just imagine French children riding their bicycle to school every time there’s a strike…

In 1927, he befriended Christopher Morcom, who also was a maths enthusiast

and whom Turing held in high esteem. So, when Morcom died in 1930

of bovine tuberculosis,

Turing considered it his duty to accomplish what

his friend Christopher should have accomplished during his mathematician’s life…

Turing tried then to generalise the “decision problem”, which is linked

to Gödel’s work on incompleteness.

We’ll talk about that later (I’ve said that already).

Simply put, the “decision problem”

is determining if a theorem can be validated by a

mechanical and automatic procedure

– an algorithm.

An algorithm is a set of very clear operations

to be performed in order to solve a given problem.

For example, when a cooking recipe says:

“separate the egg white from the yolk, mix the yolk”,

it’s an algorithm. But when it says “then add a tad of sugar”

it’s not an algorithm, it’s not clear.

Turing developed a hypothetical device,

that can also be seen as a very docile human being,

capable of performing instructions in the following way: he imagined a strip of tape

containing as many cells as we want,

and in each cell, there’s either nothing, or a symbol, which can be a digit, a letter, etc.

So here we are, in the initial state

and the machine reads one and only one cell at a time.

The first being the initial cell. And then it follows the instructions

step by step, depending on the state in which the machine is.

For example if an instruction says “if we are in the state 54

and the scanned symbol is “1”, write a “0” and move right,

then change to state 92″. A good example would be a device

which simply increments numbers, so adds 1 to them.

So in state 0: if the cell is not empty, the device

moves right and stays in state 0

and if the cell is empty

it moves left and then changes to state 1.

In state 1, if the number is less than 9, it adds 1 then moves left

and changes to state 2.

and if the number is 9, then it writes 0 and moves left,

but stays in state 1. If the cell is empty,

it writes 1 and stop, it’s finished.

And in state 2, if the cell is not empty, it moves left

and stays in state 2. And if the cell is empty, it stops.

State 0: cell not empty, move right, stay in state 0.

State 0: cell not empty, move right, stay in state 0.

State 0: cell not empty, move right, stay in state 0.

State 0: cell empty, move left and change to state 1.

State 1: if <9, add 1, move left, and change to state 2.

State 2: cell not empty, move left, stay in state 2.

State 2: cell not empty, move left, stay in state 2.

State 2: cell is empty -> END

This so-called “Turing machine” is the basis of a computer.

The instructions being the program,

and the tape its memory.

Right before WWII, Turing was hired by a

secret government cryptanalysis centre,

where he took part in the cracking of ENIGMA, which was said to be unbreakable.

ENIGMA is a cipher machine, which means that it

turns a message

into another unreadable message,

changing each letter with another.

This method is called “substitution cipher” which consists in

replacing one letter with another.

And it always replaces

a given letter with the same other letter.

e.g. if we replace an A with a K, all As will be Ks,

which means that it is generally quite easy to decipher a message

because, for any given language, we know which letters

are most used – so the longer the message, the better we can guess

which letters are the most used.

But that’s not the case with ENIGMA! Nope!

How does an ENIGMA machine actually work?

There are 3 rotors with 26 positions that are electrically wired

in series, like an odometer. When the rotor on

the right makes a full turn, it makes the middle rotor turn

which, after a full turn, makes the rotor

on the left turn.

There’s also a manual wiring,

where 10 pairs of letters are swapped,

on the plugboard.

So from the 26 letters of the alphabet, only 6 remains the same.

When a letter is pressed, the rotors start turning,

and the letter coming out of the machine is never the same.

So if the same letter is pressed 20 times in a row, 20 different letters should come out.

It’s freaking annoying!

Ingenious, indeed, but nothing exceptional yet.

What’s really insane is

the combination complexity offered by the possibilities

of the initial settings.

The 3 rotors are completely interchangeable

and chosen among five possible rotors.

Which means that for the 1st rotor, there are 5 choices,

then 4 choices for the 2nd rotor, and 3 choices

for the 3rd rotor. Which means 60 possibilities

only for putting the rotors together.

Moreover, each rotor has 26 possible positions. So there are

26 possibilities for the 1st rotor, 26 for the 2nd, and 26 for the 3rd.

In all: 17,576 possibilities

only for the rotors’ positions, once they’ve been chosen.

So, rotors and positions already add up to 1,054,560 possibilities (so quite a few).

And that’s nothing compared to what can be done with the wiring

on the plugboard with the ten pairs of letters,

which is… pure madness!

Here is the calculus to figure how many possibilities there are,

which gives: 150,738,274,937,250 possibilities.

So if we take into account the rotors, their positions and the wiring

it gives us: 158,962,555,217,826,360,000

It is more or less

humanely impossible

to break such a device, without knowing its setting beforehand.

They changed everyday, at midnight.

The Germans had a list, and they’d have new orders every day.

If they were told to use setting “143”, they’d check line 143,

which told them “use rotors 2, 4 and 5 and this wiring”, and voila, go!

So Turing decided to create a machine,

which could test every possibility to decipher the message,

and he named it the BOMBE machine.

But even if you could test 1000 settings every second,

you’d still need 5 billion years to test

every single possibility (it’s long).

So Turing and his team tried to reduce the number of possibilities,

to avoid having to analyse the 159 billion billion possibilities

and to have

something more…

simply something they could work with.

There, two things came into play: the first one was an obvious flaw

of ENIGMA,

and the second one was a security weakness

on the German side.

ENIGMA’s flaw is rather simple in fact,

one letter, pressed 20 times in a row, could become

any letter.

But couldn’t become just any letter.

It could become any OTHER letter.

Which means that an A could never give an A.

It could give any other letter

apart from A.

A letter could never be encoded into itself.

It seems nothing, but it’s important.

The security weakness was that Germans tended to

show too much discipline for some messages. In particular,

every morning at 6 o’clock, they’d send a weather report

which would always follow the same pattern,

(although the content changed, because… well it’s the weather)

It always began with the word “WETTERBERICHT”

which means “weather report”

and always ended with a nice “HEIL HITLER”.

So the cryptanalysts would try to decipher weather reports.

And in order to do so, they’d take the word “WETTERBERICHT” and try

to put it on the enciphered message they had

and they would drag it on the message, up to the point where there would be

no common letter.

since an A could not give an A, a W could not give a W,

an E could not give an E, etc.

Then, they would make

an assumption on the plugboard’s wiring.

e.g. “let’s say, A is enciphered into C”. And then, they’d

test every rotors’ possibility.

They’d test every rotors, and every rotors’ position. It usually wouldn’t take long

before they’d know whether their assumption was the right one.

And most of the time, they’d face a contradiction.

For example, let’s say that they assumed that an A would give a C,

and after testing this assumption, they saw that an A gave in fact a K,

which was not possible, so their assumption was wrong. The device was made in such a way that

when they dealt with a contradiction

every intermediate step they had made also had to be rejected.

None of them could be right, because they were all linked.

They were all subsequent to one another…

So it reduced the time needed to compute the message,

and moreover, since they’d only look for a few words which were

WETTERBERICHT,

HEIL and HITLER, they could make assumptions that were more and more

precise, and have faster results, up to the point where they

would only need 20 minutes to break

the ENIGMA code.

So they went from 5 billion years

to 20 minutes – and that’s beautiful.

That’s the way Turing was… He was interested in a lot of other things.

He also worked on morphogenesis, the biological process

that causes organisms and organs to develop their shape

and structure.

He put up theories…

and in a paper published in 1952, he predicated

three kinds of patterns

which were experimentally confirmed in the 90’s. Simply Turing.

We know the end of the story: Turing was a homosexual

and was charged with “gross indecency and sexual perversions”.

Yes, that was 60 years ago.

It was not 200 years ago,

but only 60 years ago.

All his friends and the people he had worked with defended him,

they all praised him and were very laudatory.

But since they worked in the deepest secrecy,

no one could explained what the nation owed him

so it couldn’t save him. Turing was given the choice between serving jail time

or undergoing chemical castration, and since he wanted to keep working,

he wouldn’t go to jail,

and chose chemical castration.

The drugs had a physical impact on him

and made him fall in a severe depression.

He was found dead in 1954 with a lot of cyanide by his side, so the investigation determined

he had committed suicide.

Since then, a few things has been said on his death and we

don’t know if they are true or not.

The first thing is that we found an half-eaten

apple by his side, which

has never been tested, but may have been filled

with cyanide, so it could be how

he killed himself,

as a tribute to Snow White.

No kidding.

The second thing is that Apple would have adopted his current logo,

which is an half-eaten apple, as a tribute to Turing.

For a long time, this has been denied by Apple’s executives.

But,

they’ve also denied this denial.

Truth is, we don’t know.

In any case, most historians agree that,

left aside the simple fact that everybody uses

computers today, and that there wouldn’t be any computer

without Turing’s work,

without the

breaking of ENIGMA

by Turing and his team,

the war would have most likely lasted two more years, killing 14,000,000 more people.

That’s all…

Thanks to everyone, since you’re more and more willing to e-penser (e-think)

We are now more than 200,000 on this channel,

it’s totally insane! I still remember the time

when I thought I would only have like 50,000 subscribers. So I thank you all.

And thanks to the tipers,

I won’t say again that you’ve become mad, since

you’re mad every month. You’ve just stayed mad.

It’s good, I think it’s good. Stay true to yourselves.

I’d rather say it now, because otherwise comments will

go crazy:

“The Imitation Game”, the film based on

Alan Turing’s life, is released this week,

and while we’re at it, I highly recommend that you see the

“After Viewing” of The Fossoyeur de Films, with me.

You’ll find the link in the description, and a thumbnail with it somewhere…

now or after, I don’t know yet.

Now, as always,

you can subscribe, share the video if you liked it,

you can put a thumb up, or a thumb down,

you can follow me on Facebook, Twitter and even on Google+!

I know it’s not attractive but it also works, at least technically.

We’re 7 there now, I think.

Of course and as always, stay curious

and take some time to e-penser (e-think).


Close Menu