Alan Turing: Crash Course Computer Science #15

0:02 Hi, I'm Kerry Ann and welcome to Crash Course computer science.

0:06 Over the past few episodes,

0:07 we've been building up our understanding of computer science

0:09 fundamentals, such as functions, algorithms and data structures.

0:13 Today, we're going to take a step back and

0:15 look at the person who formulated many of

0:17 the theoretical concepts that underline modern computation.

0:19 The father of computer science and not

0:22 quite Benedict Cumberbatch lookalike Alan Turing.

0:24 [Crash Course intro playing]

0:33 Alan Mathison Turing was born in London in 1912

0:36 and showed an incredible aptitude for maths

0:38 and science throughout his early education.

0:40 His first brush of what we now call computer science came in

0:43 1935 while he was a master's student at King's College in Cambridge.

0:46 He set out to solve a problem posed by

0:49 German Mathematician David Hilbert known as the Entscheidungsproblem

0:51 or decision problem, which asked the following:

0:54 is there an algorithm that takes as input a statement written in formal logic,

0:58 and produces a "yes" or "no" answer that's always accurate?

1:01 If such an algorithm existed,

1:02 we could use it to answer questions like,

1:04 "Is there a number bigger than all numbers?"

1:06 No, there's not.

1:06 We know the answer to that one,

1:08 but there are many other questions in mathematics

1:09 that we'd like to know the answer to.

1:11 So if this algorithm existed, we'd want to know it.

1:14 The American mathematician Alonzo Church first presented

1:17 a solution to this problem in 1935.

1:19 He developed a system of mathematical expressions called Lambda Calculus

1:23 and demonstrated that no such universal algorithm could exist.

1:26 Although Lambda Calculus was capable of representing any computation,

1:30 the mathematical technique was difficult to apply and understand.

1:33 At pretty much the same time on the other side of the Atlantic,

1:35 Alan Turing came up with his own approach to solve the decision problem.

1:38 He proposed a hypothetical computing machine,

1:40 which we now call a Turing Machine.

1:43 Turing Machines provided a simple, yet powerful

1:45 mathematical model of computation.

1:47 Although using totally different mathematics,

1:49 they were functionally equivalent to lambda calculus

1:52 in terms of their computational power.

1:54 However their relative simplicity made them much more

1:56 popular in the burgeoning field of computer science.

1:58 In fact, they're simple enough that I'm going to explain it right now.

2:02 A Turing Machine is a theoretical

2:03 computing device equipped with an infinitely

2:06 long memory tape which stores symbols

2:08 and a device called a read/write head which can read and write, or

2:10 modify, symbols on that tape.

2:12 There's also a state variable in which we can hold a piece of information

2:15 about the current state of the machine.

2:17 And a set of rules that describes what the machine does.

2:20 Given a state and the current symbol the head is reading,

2:22 the rule can be to write a symbol on the tape change the state

2:25 of the machine move the read/write head to the left or right by one spot or any

2:29 combination of these actions.

2:31 To make this concrete let's work through a simple example:

2:34 a Turing Machine that reads a string of ones ending in a zero and

2:37 computes whether there is an even number of ones.

2:40 If that's true The machine will write a one to the tape and if it's false,

2:43 it'll write a zero.

2:44 First We need to define our Turing machine rules.

2:47 If the state is even and the current symbol of the tape is one,

2:50 then we update the machine state to odd and move the head to the right.

2:54 On the other hand if the state is even and

2:56 The current symbol is zero,

2:57 which means we've reached the end of the string of ones,

2:59 then we write one to the tape and change

3:01 the state to halt, as in we're finished and the Turing machine has completed the

3:05 computation.

3:05 We also need rules for when the Turing machine is in an odd state,

3:08 one rule for the symbol on the tape is a zero and another for when it is one.

3:12 Lastly we need to define a

3:14 Starting state, which we'll set to be even.

3:16 Now we've defined the rules in the starting state of our Turing machine,

3:19 which is comparable to a computer program, we can run it on some example input.

3:23 Let's say we store 1 1 0 onto tape.

3:25 That's two ones which means there is an even number of ones,

3:28 and if that's news to you,

3:29 We should probably get working on crash course Math.

3:31 Notice that our rules only ever move their head to

3:33 the right so the rest of the tape is irrelevant.

3:36 We'll leave it blank for simplicity.

3:37 Our Turing machine is all ready to go so let's start it.

3:40 Our state is even and the first

3:42 number we see is a one.

3:43 That matches our topmost rule

3:45 and so we execute the effect,

3:46 which is to update the state to odd and move

3:48 the read/write head to the right by one spot.

3:50 Okay, now we see another one on the tape

3:52 But this time our state is odd

3:54 and so we execute our third rule which sets the state

3:56 back to even and moves the head to the right.

3:59 Now we see a 0 and our current state is even so we execute our second rule

4:03 which is to write a 1 to the tape signifying that yes, it's true,

4:06 there is an even number of ones, and finally the machine halts.

4:10 That's how turing machines work pretty simple right so you

4:13 might be wondering why there's such a big deal

4:15 Well cheering shows that this simple hypothetical machine can

4:18 perform any computation if given enough time and memory

4:21 It's a general-purpose computer our program was a simple example

4:25 But with enough Rules states and tape you could build anything- a web browser,

4:29 world of warcraft- whatever!

4:30 Of course it would be

4:31 ridiculously inefficient, but it is theoretically possible.

4:34 And that's why, as a model of computing, it's such a powerful idea.

4:37 In fact in terms of what it can and cannot compute

4:40 there's no computer more powerful than a turing machine.

4:43 A computer that is as powerful is called Turing complete

4:46 Every modern computing system your laptop your smartphone and even the

4:50 little computer inside your microwave and thermostat are all Turing Complete.

4:54 To answer Hilbert's decision problem,

4:55 Turing applied these new Turing machines to an intriguing

4:58 computational puzzle: the halting problem.

5:00 Put simply this asks

5:01 "Is there an algorithm that can determine,

5:03 given a description of a turing machine and the input from its tape,

5:07 whether the Machine will run forever or halt?" For example we know

5:10 our Turing machine will halt when given the input 1 1 0

5:13 Because we literally walk through the example until it halted,

5:16 but what about a more complex problem?

5:18 Is there a way to figure out if the program will halt without

5:21 executing it?

5:21 Some programs might take years to run

5:23 so it would be useful to know before we run it and wait

5:26 and wait and wait and then start getting worried and wonder and

5:29 Then decades later when you're old and gray control-alt-delete so much sadness

5:34 Unfortunately turing came up with a proof that

5:36 shows the halting problem was in fact unsolvable,

5:38 through a clever logical contradiction.

5:40 Let's Follow his reasoning.

5:41 Imagine we have a hypothetical Turing machine that takes a description of

5:44 a program and some input for his tape and always outputs either

5:48 Yes, it halts or no, it doesn't and I'm going to give this machine a fun name

5:52 H for Holtz.

5:52 Don't worry about how it works.

5:54 Let's just assume such a machine exists

5:56 We're talking theory here.

5:57 Turing reasoned if there existed a program

5:59 Whose halting behavior was not decidable by age

6:01 it would mean the halting problem is

6:03 Unsolvable to find one Turing designed another Turing

6:05 machine that built on top of H.

6:07 If H says the program holds

6:09 Then we'll make our new machine loop forever.

6:12 If the answer is no

6:13 It doesn't halt, we'll have the new machine output a no and halt.

6:17 In essence We're building a machine that does the opposite of what H says:

6:20 halt if the program doesn't halt and run forever if the program halts

6:23 For this argument we'll also need to add a

6:25 splitter to the front of our new machine

6:27 So that it accepts only one input and passes

6:29 that as both the program and input into H.

6:32 Let's call this new machine "Bizzaro"

6:34 So far this seems like a plausible machine, right?

6:37 Now it's going to get pretty complicated

6:38 But bear with me for a second.

6:40 Look what happens when you pass Bizzaro a description of itself as the input

6:43 This means we're asking H what Bizzaro will do when asked to evaluate itself

6:47 But if H says Bizzaro halts then Bizzaro

6:50 enters its infinite loop and thus doesn't halt

6:53 And if H says Bizarro doesn't halt then Bizzaro outputs a no and halts

6:57 so H can't possibly decide the halting

6:59 problem correctly because there is no answer.

7:01 It's a paradox and this paradox means

7:03 That the halting problem cannot be solved with Turing machines.

7:07 Remember Turing proved that Turing machines could implement any computation

7:10 So this solution to the halting problem proves that

7:13 not all problems can be solved by computation.

7:15 Wow, that's some heavy stuff

7:16 I might have to watch that again myself.

7:19 Long story short Church

7:20 and Turing showed there were limits to the ability of computers no matter

7:23 how much time or memory you have there are just some problems

7:26 that cannot be solved ever.

7:36 At this point in

7:37 1936 Turing was only 24 years old and really only just beginning his career.

7:42 From 1936 through 1938 he completed a PhD at Princeton University

7:46 under the guidance of Church then after graduating he returned to Cambridge.

7:51 Shortly after in 1939 Britain became embroiled in World War

7:53 II Turing's genius was quickly applied to the war effort.

7:56 In fact a year before the war

7:58 Started he was already working part-time at

8:00 the uk's government code and Cypher school

8:02 Which was the British code breaking group based out of Bletchley Park.

8:05 One of his main efforts was figuring out how to decrypt German communications

8:09 Especially those that use the enigma machine.

8:11 In short these machines scrambled text.

8:13 Like you'd type the letters

8:15 H-E-L-L-O and the letters XWDBJ

8:18 Would come out.

8:19 This process is called encryption

8:20 The scrambling wasn't random.

8:22 The behavior was defined by a series of re-orderable

8:24 rotors on the top of the enigma machine

8:26 Each with 26 possible rotational positions.

8:28 There was also a plug board at the front of

8:30 the machine that allowed pairs of letters to be swapped

8:33 In total there were billions of possible settings.

8:35 If you had your own enigma machine and you

8:38 knew the correct rotor and plug board settings

8:40 You could type in XWDBJ

8:42 and hello would come out.

8:44 In other words, you decrypted the message

8:46 Of course the German military wasn't sharing

8:48 their enigma settings on Social Media

8:50 So the allies had to break the code

8:52 with billions of Rotor and plug board combinations

8:54 There was no way to check them all by hand

8:56 Fortunately for Turing,

8:57 enigma machines and the people who operated them were not perfect

9:00 Like one key flaw was that a letter would never be encoded

9:03 as itself as in an h was never encrypted as an h

9:06 Turing, building on earlier work by Polish code breakers,

9:09 designed a special-Purpose

9:10 electromechanical Computer called the Bombe that took advantage of this flaw.

9:14 It tried lots and lots of combinations of enigma settings

9:17 for a given encrypted message if the Bombe found a

9:19 setting that led to a letter being encoded as itself

9:22 Which we know the real Enigma machine couldn't do,

9:25 that combination was discarded then the machine

9:27 moved on to try another combination

9:29 So Bombes were used to greatly narrow the number of Possible enigma settings

9:32 This allowed human code breakers to hone

9:34 their efforts on the most probable solutions

9:36 Looking for things like common german words in fragments of decoded text

9:40 Periodically the Germans would suspect someone

9:42 was decoding their communications and upgrade

9:43 the enigma machine like they'd add another rotor creating many more combinations

9:48 they even built entirely new encryption machines.

9:50 Throughout the war Turing and his colleagues at bletchley

9:53 park worked tirelessly to defeat these mechanisms and

9:56 overall the intelligence gained from Decrypted German communications

9:59 Gave the allies an Edge in many theatres with

10:02 some historians arguing it shortened the war by years

10:04 after the war turing returned to Academia and

10:07 Contributed to many early electronic computing efforts like the Manchester

10:10 Mark 1 which was an early and influential stored-Program computer

10:14 But his most famous post-war contribution was to artificial intelligence,

10:17 a field so new that it didn't even get that name until 1956

10:21 It's a huge topic

10:22 So we'll get to it again in future episodes

10:25 In 1950 Turing could envision a future where computers were

10:28 powerful enough to exhibit intelligence equivalent to or at least

10:32 indistinguishable from that of a human

10:33 Turing postulated that a computer would deserve to be called intelligent

10:37 If it could deceive a human into believing that it was human.

10:40 This became the basis of a simple test now called the turing test

10:43 Imagine that you are having a conversation with two

10:45 different people not by voice or in person

10:47 But by sending typed notes back and forth.

10:49 You can ask any questions you want and you get replies

10:52 But one of those two people is actually a computer.

10:55 If you can't tell which one is human and which one is a computer then

10:58 the computer passes the test

11:00 There's a modern version of this test called a completely automated public

11:03 turing test to tell computers and humans apart or captcha for short

11:07 These are frequently used on the internet to prevent automated

11:10 systems from doing things like posting spam on Websites.

11:13 I'll admit sometimes I can't read what those squiggly things say.

11:16 Does that mean I'm a computer?

11:18 Normally in this series

11:19 We don't delve into the personal lives of these historical figures

11:22 But in Turing's case his name has been inextricably

11:25 tied to tragedy so his story is worth mentioning

11:28 Turing was gay in a time when homosexuality was illegal

11:31 in the united Kingdom and much of the world.

11:33 An investigation into a 1952 Burglary

11:36 at his home revealed his sexual orientation to

11:38 the authorities who charged him with gross indecency.

11:40 Turing was convicted and given a choice between

11:43 Imprisonment or probation with hormonal treatments to suppress his sexuality

11:47 He chose the latter in part to continue his academic work,

11:50 but it altered his mood and personality

11:53 Although the exact circumstances will never be known,

11:56 it's most widely accepted that Alan Turing took his own life by poison in 1954

12:01 He was only 41.

12:02 Many things have been named in recognition

12:04 of Turing's contributions to theoretical computer science

12:07 But perhaps the most prestigious among them is the turing

12:10 award the highest distinction in the field of computer science

12:13 Equivalent to a nobel prize in Physics, chemistry or other sciences.

12:17 Despite a life cut short

12:18 Alan inspired th e first generation of computer scientists and laid key

12:22 groundwork that enabled a digital era we get to enjoy today

12:25 I'll see you next week.

12:27 Crash course computer science is produced in association

12:30 with PBS digital studios at their channel

12:32 You can check out our pla ylist to show like gross science

12:35 ACS reactions and the art assignment.

12:37 this episode was filmed at the Chad and stacey Emigholz studio in Indianapolis,

12:41 Indiana And it was made with the help of all these

12:44 nice people and a wonderful graphics team thought cafe

12:46 Thanks for watching and try turning it off and then back [on] again