WEBVTT 1 00:00:01.000 --> 00:00:02.980 This series is going to cover computation. 2 00:00:02.980 --> 00:00:05.810 And I think we should begin by just laying out the topics 3 00:00:05.810 --> 00:00:07.440 that we're going to mention along the way, 4 00:00:07.440 --> 00:00:09.440 so we have a sense of where we're going. 5 00:00:09.440 --> 00:00:10.770 The first of those topics 6 00:00:10.770 --> 00:00:13.920 is the radical simplicity of computation. 7 00:00:13.920 --> 00:00:16.580 It turns out that all of the complexity of our computers 8 00:00:16.580 --> 00:00:17.610 and programming languages 9 00:00:17.610 --> 00:00:21.010 and operating systems is complexity that we have added. 10 00:00:21.010 --> 00:00:23.850 It is not fundamental to computation. 11 00:00:23.850 --> 00:00:25.580 And to see that we're going to look both 12 00:00:25.580 --> 00:00:28.970 at the Turing machine and add the Lambda calculus, 13 00:00:28.970 --> 00:00:32.180 which are the two most well-known models of computation 14 00:00:32.180 --> 00:00:35.460 or at least the two most well-known abstract models. 15 00:00:35.460 --> 00:00:36.860 Both of these are normally taught 16 00:00:36.860 --> 00:00:39.870 with a very mathematical kind of terminology and notation, 17 00:00:39.870 --> 00:00:41.720 a lot of Greek letters and so on, 18 00:00:41.720 --> 00:00:43.500 but we're just going to use Python code 19 00:00:43.500 --> 00:00:44.690 because Python is a language 20 00:00:44.690 --> 00:00:47.180 that any programmer can understand pretty easily. 21 00:00:47.180 --> 00:00:48.640 And that will allow us to get 22 00:00:48.640 --> 00:00:50.750 at least a high level understanding 23 00:00:50.750 --> 00:00:53.150 of what's going on inside of these systems. 24 00:00:53.150 --> 00:00:55.300 The next topic that we're going to talk about is, 25 00:00:55.300 --> 00:00:57.110 the limits of computation. 26 00:00:57.110 --> 00:00:59.000 Specifically the halting problem 27 00:00:59.000 --> 00:01:01.630 which is an example of an undecidable problem 28 00:01:01.630 --> 00:01:03.110 in computer science. 29 00:01:03.110 --> 00:01:05.280 The halting problem to state it really quickly, 30 00:01:05.280 --> 00:01:06.870 is the problem of writing a function. 31 00:01:06.870 --> 00:01:07.990 Let's call it, halts 32 00:01:07.990 --> 00:01:10.510 that takes another function, let's call it f 33 00:01:10.510 --> 00:01:13.800 and decides whether f will terminate or not. 34 00:01:13.800 --> 00:01:15.330 If f will terminate eventually, 35 00:01:15.330 --> 00:01:16.900 then halts should turn true. 36 00:01:16.900 --> 00:01:19.240 If f we'll for example, loop forever, 37 00:01:19.240 --> 00:01:21.290 then halts should turn false. 38 00:01:21.290 --> 00:01:23.690 And it's easy to state that problem as I just did, 39 00:01:23.690 --> 00:01:25.720 but you cannot write this function. 40 00:01:25.720 --> 00:01:28.070 No programming language can express this function. 41 00:01:28.070 --> 00:01:31.400 No computational system can express this function. 42 00:01:31.400 --> 00:01:33.290 That's a highly non-obvious result, 43 00:01:33.290 --> 00:01:35.360 but there are rigorous mathematical proofs of this 44 00:01:35.360 --> 00:01:37.500 going back to the 1930s 45 00:01:37.500 --> 00:01:39.380 and they have held up for 80 years 46 00:01:39.380 --> 00:01:41.950 both in theory and in practice. 47 00:01:41.950 --> 00:01:43.520 So we'll see why that's true, 48 00:01:43.520 --> 00:01:46.190 or at least a high level sketch of why that's true 49 00:01:46.190 --> 00:01:47.960 and some of the implications of it 50 00:01:47.960 --> 00:01:50.010 for the rest of computation. 51 00:01:50.010 --> 00:01:53.100 We're also going to see the structure of computation 52 00:01:53.100 --> 00:01:55.620 specifically the idea of touring equivalents 53 00:01:55.620 --> 00:01:57.550 which tells us that the Turing machine 54 00:01:57.550 --> 00:01:58.610 and the Lambda calculus 55 00:01:58.610 --> 00:02:01.420 are both capable of answering the same questions. 56 00:02:01.420 --> 00:02:03.360 Any question that one of them can answer 57 00:02:03.360 --> 00:02:04.590 the other can answer. 58 00:02:04.590 --> 00:02:06.380 And it turns out that this is true 59 00:02:06.380 --> 00:02:08.780 of our real world computers as well 60 00:02:08.780 --> 00:02:11.200 including the laptop that I'm recording the song. 61 00:02:11.200 --> 00:02:13.200 If my laptop can answer a question, 62 00:02:13.200 --> 00:02:14.870 then so can a Turing machine. 63 00:02:14.870 --> 00:02:17.160 And this is extremely surprising 64 00:02:17.160 --> 00:02:19.670 given how simple Turing machines are. 65 00:02:19.670 --> 00:02:21.070 In fact, when we first look at them 66 00:02:21.070 --> 00:02:22.430 you're not going to believe 67 00:02:22.430 --> 00:02:25.380 that they are an actual general purpose computing system 68 00:02:25.380 --> 00:02:27.520 but it turns out that in fact they are 69 00:02:27.520 --> 00:02:28.860 because of turning equivalents 70 00:02:28.860 --> 00:02:31.960 which once again has rigorous mathematical proofs 71 00:02:31.960 --> 00:02:34.070 going back to the 1980s. 72 00:02:34.070 --> 00:02:35.000 Excuse me. 73 00:02:35.000 --> 00:02:37.780 80 years ago to the 1930s. 74 00:02:37.780 --> 00:02:39.460 A related idea that we'll talk about 75 00:02:39.460 --> 00:02:42.640 is the Chomsky Hierarchy of computational systems. 76 00:02:42.640 --> 00:02:45.410 And it turns out that this Turing equivalent type of system 77 00:02:45.410 --> 00:02:48.550 is only the most powerful type of computation. 78 00:02:48.550 --> 00:02:50.730 There are four levels in this hierarchy 79 00:02:50.730 --> 00:02:52.590 and they begin with the weakest 80 00:02:52.590 --> 00:02:56.060 which is equivalent to what we call, regular expressions. 81 00:02:56.060 --> 00:02:57.590 The next level is what you would need 82 00:02:57.590 --> 00:03:00.050 if you wanted to recognize Python code. 83 00:03:00.050 --> 00:03:02.160 Meaning you want to decide whether a string 84 00:03:02.160 --> 00:03:05.240 is valid Python or is not valid Python. 85 00:03:05.240 --> 00:03:06.610 The next level is what you would need 86 00:03:06.610 --> 00:03:09.700 if you wanted to recognize a C++ code. 87 00:03:09.700 --> 00:03:11.760 And this distinction is very important. 88 00:03:11.760 --> 00:03:14.410 And in fact Python was intentionally designed 89 00:03:14.410 --> 00:03:16.410 to require less complexity 90 00:03:16.410 --> 00:03:19.040 in the computational system that recognizes it. 91 00:03:19.040 --> 00:03:21.530 Most programming languages have this level of complexity 92 00:03:21.530 --> 00:03:24.070 including for example, a JavaScript. 93 00:03:24.070 --> 00:03:25.190 And one of the reasons 94 00:03:25.190 --> 00:03:27.010 that Python is so easy to learn and read, 95 00:03:27.010 --> 00:03:28.900 is that it intentionally was designed 96 00:03:28.900 --> 00:03:31.530 to require less complexity. 97 00:03:31.530 --> 00:03:33.640 Finally, the last level in this hierarchy 98 00:03:33.640 --> 00:03:35.040 is the Turing equivalent level, 99 00:03:35.040 --> 00:03:37.920 which contains Turing machines, the Lambda calculus, 100 00:03:37.920 --> 00:03:40.000 my laptop, and so on. 101 00:03:40.000 --> 00:03:42.410 And this hierarchy is first of all amazing, 102 00:03:42.410 --> 00:03:45.230 just that it relates these things that seem unrelated 103 00:03:45.230 --> 00:03:46.750 if you haven't learned this yet, 104 00:03:46.750 --> 00:03:49.090 but that's not even the most amazing thing about it. 105 00:03:49.090 --> 00:03:51.400 The most amazing thing is that Noam Chomsky 106 00:03:51.400 --> 00:03:54.090 created this hierarchy when he was studying linguistics. 107 00:03:54.090 --> 00:03:56.910 He was studying natural languages like English, 108 00:03:56.910 --> 00:04:00.160 and he established different levels of linguistic complexity 109 00:04:00.160 --> 00:04:01.910 which computer scientists then took 110 00:04:01.910 --> 00:04:03.620 and used for all kinds of things, 111 00:04:03.620 --> 00:04:05.740 including programming languages, 112 00:04:05.740 --> 00:04:08.580 but also categorizing finite state machines, 113 00:04:08.580 --> 00:04:10.420 which fall into these different categories 114 00:04:10.420 --> 00:04:11.430 in different ways 115 00:04:11.430 --> 00:04:15.600 and we'll see all of these things in more detail as we go. 116 00:04:15.600 --> 00:04:18.350 That's all I want to say about this introduction. 117 00:04:18.350 --> 00:04:20.210 Next time we're going to pick up Turing machines, 118 00:04:20.210 --> 00:04:21.630 we're going to write that simulator, 119 00:04:21.630 --> 00:04:23.160 it's gonna be about 10 lines of code 120 00:04:23.160 --> 00:04:24.670 and take about 10 minutes. 121 00:04:24.670 --> 00:04:26.760 So it will be quite easy to write. 122 00:04:26.760 --> 00:04:29.623 So I will see you next time for Turing machines.