1 00:00:00,000 --> 00:00:04,599 Think of the least natural number that cannot 2 00:00:04,599 --> 00:00:07,120 be described in fewer than 20 words. Oh, this 3 00:00:07,120 --> 00:00:09,939 is such a good one. Right? Seriously, take a 4 00:00:09,939 --> 00:00:13,199 second right now. Just try to imagine that exact 5 00:00:13,199 --> 00:00:15,339 number in your head. It's impossible to actually 6 00:00:15,339 --> 00:00:18,359 picture. It is. Because whatever it is, it must 7 00:00:18,359 --> 00:00:21,000 be absolutely massive, right? You'd think you 8 00:00:21,000 --> 00:00:23,339 would need a whole paragraph or maybe like a 9 00:00:23,339 --> 00:00:25,500 complex mathematical formula translated into 10 00:00:25,500 --> 00:00:28,640 English just to pin it down. Yeah, a huge description. 11 00:00:28,829 --> 00:00:32,729 But here is the paradox. The very sentence I 12 00:00:32,729 --> 00:00:35,009 just said to you, which is the least natural 13 00:00:35,009 --> 00:00:36,630 number that cannot be described in fewer than 14 00:00:36,630 --> 00:00:40,049 20 words, that sentence describes that exact 15 00:00:40,049 --> 00:00:43,170 number. It does. And it does it in only 13 words. 16 00:00:44,060 --> 00:00:47,060 It is a beautiful, deeply unsettling contradiction. 17 00:00:47,600 --> 00:00:49,520 It really breaks your brain a little bit. It 18 00:00:49,520 --> 00:00:52,079 does. In mathematics and logic, it's known as 19 00:00:52,079 --> 00:00:54,780 the Richard Berry paradox. And the moment you 20 00:00:54,780 --> 00:00:56,960 really let it sink in, it immediately breaks 21 00:00:56,960 --> 00:00:58,899 our intuitive understanding of what it actually 22 00:00:58,899 --> 00:01:02,340 means to describe something. Exactly. It feels 23 00:01:02,340 --> 00:01:04,200 like a glitch in the matrix of language, you 24 00:01:04,200 --> 00:01:06,640 know? You're using a short description to pinpoint 25 00:01:06,640 --> 00:01:09,219 a number that by its very definition requires 26 00:01:09,219 --> 00:01:12,140 a long description. It makes your brain hurt 27 00:01:12,140 --> 00:01:14,420 in the absolute best way possible. It really 28 00:01:14,420 --> 00:01:16,840 does. And it is the absolute perfect hook for 29 00:01:16,840 --> 00:01:20,040 what we are doing today. So welcome to this custom 30 00:01:20,040 --> 00:01:22,560 tailored deep dive. So glad to be here. Today, 31 00:01:22,719 --> 00:01:25,040 we are taking a journey into the absolute limits 32 00:01:25,040 --> 00:01:28,019 of knowledge, computation, and well, information 33 00:01:28,019 --> 00:01:31,140 itself. It's a big one today. It is. Our mission, 34 00:01:31,239 --> 00:01:34,760 we are going to extract the absolute core of 35 00:01:34,760 --> 00:01:37,950 algorithmic information theory. And we are using 36 00:01:37,950 --> 00:01:40,329 a truly foundational text as our guide for this 37 00:01:40,329 --> 00:01:43,069 deep dive. It's called An Introduction to Komogorov 38 00:01:43,069 --> 00:01:45,810 Complexity and Its Applications by Ming Li and 39 00:01:45,810 --> 00:01:47,930 Paul Vitanghi. A total classic in the field. 40 00:01:48,090 --> 00:01:50,769 Yeah. And we really want to demystify what it 41 00:01:50,769 --> 00:01:53,189 actually means for an object to be complex or 42 00:01:53,189 --> 00:01:56,329 random or compressible without losing the rigor 43 00:01:56,329 --> 00:01:59,530 of the actual science. And to set the baseline 44 00:01:59,530 --> 00:02:02,569 for this, we really need to distinguish what 45 00:02:02,569 --> 00:02:05,329 we are talking about today from classical information 46 00:02:05,329 --> 00:02:07,480 theory. Right. Because they aren't the same thing. 47 00:02:07,659 --> 00:02:11,300 Not at all. Yep. If you look at Claude Shannon's 48 00:02:11,300 --> 00:02:13,379 foundational work on information theory back 49 00:02:13,379 --> 00:02:16,800 in the 1940s, I mean, his framework revolutionized 50 00:02:16,800 --> 00:02:20,960 telecommunications. But Shannon was it was primarily 51 00:02:20,960 --> 00:02:23,840 he was primarily concerned with the source of 52 00:02:23,840 --> 00:02:26,400 messages. The source. Right. Exactly. Not the 53 00:02:26,400 --> 00:02:28,699 message itself. Exactly. Not the messages themselves. 54 00:02:29,240 --> 00:02:31,039 Shannon's theory treats a communication channel 55 00:02:31,039 --> 00:02:34,939 a bit like a municipal water pipe. Okay, a water 56 00:02:34,939 --> 00:02:37,639 pipe. Yeah, it basically asks, how much physical 57 00:02:37,639 --> 00:02:40,560 capacity do we need to transmit a message from 58 00:02:40,560 --> 00:02:43,800 a random source, given the statistical probabilities 59 00:02:43,800 --> 00:02:46,699 of all the possible messages that source might 60 00:02:46,699 --> 00:02:49,479 spit out? So it's about the pipe, not the water? 61 00:02:49,759 --> 00:02:52,240 Right. It doesn't actually look at the water 62 00:02:52,240 --> 00:02:54,659 flowing through the pipe at all. Okay, so if 63 00:02:54,659 --> 00:02:57,599 I'm understanding Shannon's perspective, he doesn't 64 00:02:57,599 --> 00:02:59,840 care if the text message I'm sending says, like, 65 00:02:59,879 --> 00:03:03,099 I love you, or if it's the formula for a cure 66 00:03:03,099 --> 00:03:05,740 for a disease, or if it's literally just random 67 00:03:05,740 --> 00:03:08,639 keyboard mashing. He does not care. As long as 68 00:03:08,639 --> 00:03:10,860 those specific strings of characters have the 69 00:03:10,860 --> 00:03:14,120 exact same statistical probability of being generated 70 00:03:14,120 --> 00:03:17,099 by the user, Shannon's math treats them as having 71 00:03:17,099 --> 00:03:19,960 the exact same amount of information. Precisely. 72 00:03:20,340 --> 00:03:22,699 Shannon's entropy measures the uncertainty or 73 00:03:22,699 --> 00:03:26,639 the surprise in a probabilistic ensemble. The 74 00:03:26,639 --> 00:03:28,460 average behavior. Exactly. It's about the average 75 00:03:28,460 --> 00:03:31,310 behavior of a system. But Kolmogorov complexity, 76 00:03:31,590 --> 00:03:33,509 which was developed completely independently 77 00:03:33,509 --> 00:03:36,370 by Andrei Kolmogorov in Russia, Ray Solomonov 78 00:03:36,370 --> 00:03:38,330 in the US, and Gregory Chaitin in Argentina. 79 00:03:38,830 --> 00:03:40,889 All in the 1960s, right? Yeah, all around the 80 00:03:40,889 --> 00:03:43,650 same time. It flips this paradigm entirely on 81 00:03:43,650 --> 00:03:45,810 its head. It just ignores the source completely. 82 00:03:46,169 --> 00:03:47,990 It just looks at the object. It looks at the 83 00:03:47,990 --> 00:03:50,090 individual object itself. It asks a profoundly 84 00:03:50,090 --> 00:03:52,490 different question, which is how many bits of 85 00:03:52,490 --> 00:03:55,650 information are actually intrinsically mathematically 86 00:03:55,650 --> 00:03:58,719 inside this specific object? Regardless of how 87 00:03:58,719 --> 00:04:00,939 it was made? Regardless of how or where it was 88 00:04:00,939 --> 00:04:03,659 generated. Okay. That is a huge shift. Because 89 00:04:03,659 --> 00:04:06,919 moving from an ensemble of probabilities to the 90 00:04:06,919 --> 00:04:09,419 actual physical generation of a single object, 91 00:04:09,639 --> 00:04:11,699 I mean, that changes everything about how we 92 00:04:11,699 --> 00:04:13,800 view data. That changes the entire foundation. 93 00:04:14,500 --> 00:04:17,019 Let's make this concrete for you listening. In 94 00:04:17,019 --> 00:04:19,300 Lee and Vittani's book, there is a fantastic 95 00:04:19,300 --> 00:04:21,660 simple example that highlights this perfectly. 96 00:04:22,079 --> 00:04:25,160 Oh, the string of ones? Yes. Imagine a string 97 00:04:25,160 --> 00:04:28,079 of 10 ,000 ones, just the number one repeated 98 00:04:28,079 --> 00:04:31,879 10 ,000 times in a row. Now contrast that with 99 00:04:31,879 --> 00:04:35,379 the first 10 ,000 digits of pi. Right. So under 100 00:04:35,379 --> 00:04:38,279 classical probability theory, if you assume you 101 00:04:38,279 --> 00:04:41,139 have a truly random source that is generating 102 00:04:41,139 --> 00:04:45,379 sequences of 10 ,000 digits, every single specific 103 00:04:45,379 --> 00:04:48,680 sequence has the exact same microscopic probability 104 00:04:48,680 --> 00:04:51,399 of occurring. So the string of ones. The string 105 00:04:51,399 --> 00:04:54,540 of 10 ,000 ones. has the exact same probability 106 00:04:54,540 --> 00:04:57,220 of being generated by pure chance as the first 107 00:04:57,220 --> 00:04:59,819 10 ,000 digits of pi. Which is crazy to think 108 00:04:59,819 --> 00:05:02,139 about. And both of those have the exact same 109 00:05:02,139 --> 00:05:04,839 probability of occurring as a completely chaotic 110 00:05:04,839 --> 00:05:07,660 jumbled string of meaningless numbers. But our 111 00:05:07,660 --> 00:05:09,399 human intuition screams that these three things 112 00:05:09,399 --> 00:05:11,439 are not the same. Right. They don't have the 113 00:05:11,439 --> 00:05:13,360 same amount of information in them. I mean, they 114 00:05:13,360 --> 00:05:16,600 just don't. They don't. And algorithmic complexity 115 00:05:16,600 --> 00:05:19,040 gives us the strict mathematical language to 116 00:05:19,040 --> 00:05:22,040 prove our intuition right. How so? Well, the 117 00:05:22,040 --> 00:05:24,889 string of 10 ,000 ones is not fundamentally complex 118 00:05:24,889 --> 00:05:27,709 because it can be generated by a very short, 119 00:05:27,829 --> 00:05:30,310 very simple computer program. Oh, right, like 120 00:05:30,310 --> 00:05:33,889 a loop. Exactly. You just write a tiny for loop 121 00:05:33,889 --> 00:05:36,470 in code that says essentially print the number 122 00:05:36,470 --> 00:05:39,610 one 10 ,000 times. So the output is long, but 123 00:05:39,610 --> 00:05:42,230 the actual description is tiny. The description 124 00:05:42,230 --> 00:05:45,350 of the output is incredibly short. And the digits 125 00:05:45,350 --> 00:05:48,370 of pi? I mean, to the naked eye, pi looks like 126 00:05:48,370 --> 00:05:50,709 random static. It never repeats. It has no obvious 127 00:05:50,709 --> 00:05:54,370 pattern. It looks irregular, yes. But pi is deeply, 128 00:05:54,529 --> 00:05:56,850 fundamentally structured. There are relatively 129 00:05:56,850 --> 00:05:59,430 short, incredibly elegant mathematical algorithms 130 00:05:59,430 --> 00:06:01,829 that can calculate the digits of pi out to infinity. 131 00:06:02,230 --> 00:06:04,889 Oh, sure. So the first 10 ,000 digits of pi can 132 00:06:04,889 --> 00:06:06,970 also be generated by a very short computer program. 133 00:06:07,189 --> 00:06:10,629 Oh, okay. Therefore, both a string of ones and 134 00:06:10,629 --> 00:06:13,370 the incredibly irregular -looking digits of pi 135 00:06:13,370 --> 00:06:16,050 actually contain very little algorithmic information. 136 00:06:16,410 --> 00:06:18,670 They are highly compressible. OK, let's unpack 137 00:06:18,670 --> 00:06:22,189 this. If I'm turning my head around this, is 138 00:06:22,189 --> 00:06:24,930 Kolmogorov complexity basically just asking, 139 00:06:25,389 --> 00:06:28,069 how small can I squish this file using a zip 140 00:06:28,069 --> 00:06:30,430 program on my laptop? That's a great way to think 141 00:06:30,430 --> 00:06:32,569 about it. Is it basically just data compression? 142 00:06:33,069 --> 00:06:35,790 Conceptually, yes. That is a fantastic starting 143 00:06:35,790 --> 00:06:38,209 point. You have the exact right intuition. But 144 00:06:38,209 --> 00:06:41,029 we need to define the mechanics much more rigorously 145 00:06:41,029 --> 00:06:43,509 than a commercial zip program. OK, because my 146 00:06:43,509 --> 00:06:46,370 laptop's zip program isn't doing pure math. Right. 147 00:06:47,110 --> 00:06:49,009 Real -world zip programs, like the ones you use 148 00:06:49,009 --> 00:06:51,790 on your computer, use specific, clever engineering 149 00:06:51,790 --> 00:06:54,550 algorithms like LimpelZiv. Right. And they scan 150 00:06:54,550 --> 00:06:56,410 a file looking for repeated patterns of bytes 151 00:06:56,410 --> 00:06:59,189 and replace them with shorter references. But 152 00:06:59,189 --> 00:07:01,829 plain Kolmogorov complexity, which mathematicians 153 00:07:01,829 --> 00:07:05,370 denote as C of X, Where X is the string of data? 154 00:07:05,610 --> 00:07:08,829 Exactly. C of X is much more absolute. It is 155 00:07:08,829 --> 00:07:11,129 defined as the length in bits of the absolute 156 00:07:11,129 --> 00:07:14,129 shortest halting program that produces the string 157 00:07:14,129 --> 00:07:17,589 X when run on a fixed optimal universal Turing 158 00:07:17,589 --> 00:07:20,550 machine. OK, a universal Turing machine. Let's 159 00:07:20,550 --> 00:07:22,129 break that down for the listener, because this 160 00:07:22,129 --> 00:07:24,689 goes back to Alan Turing in the 1930s. He does. 161 00:07:25,290 --> 00:07:27,850 A Turing machine is basically the theoretical 162 00:07:27,850 --> 00:07:31,139 mathematical model of a computer. It's an imaginary 163 00:07:31,139 --> 00:07:33,639 machine with an infinitely long tape of memory 164 00:07:33,639 --> 00:07:36,259 that can read, write, and erase symbols based 165 00:07:36,259 --> 00:07:39,379 on a set of rules. That's it? And a universal 166 00:07:39,379 --> 00:07:41,920 Turing machine is one that can simulate any other 167 00:07:41,920 --> 00:07:44,079 Turing machine, right? That's exactly it. It 168 00:07:44,079 --> 00:07:46,540 is the theoretical ancestor of every computer 169 00:07:46,540 --> 00:07:50,189 on Earth today. OK. You feed this optimal universal 170 00:07:50,189 --> 00:07:52,910 Turing machine a program, a sequence of binary 171 00:07:52,910 --> 00:07:56,230 bits, zeros and ones, and it runs. And if it 172 00:07:56,230 --> 00:07:59,060 stops... If it eventually halts, meaning it stops 173 00:07:59,060 --> 00:08:01,699 computing, and it spits out your exact string 174 00:08:01,699 --> 00:08:04,819 x, then that program is considered a valid description 175 00:08:04,819 --> 00:08:08,639 of x. Got it. The plain Kolmogorov complexity, 176 00:08:08,819 --> 00:08:12,300 c of x, is the length in bits of the absolute 177 00:08:12,300 --> 00:08:14,240 shortest program that could possibly do that. 178 00:08:14,500 --> 00:08:17,459 OK, but I have a major question here. I dabble 179 00:08:17,459 --> 00:08:20,639 a bit in coding. OK. If I write a program to 180 00:08:20,639 --> 00:08:23,120 do something in Python, it might take me 100 181 00:08:23,120 --> 00:08:25,720 characters. If I write that exact same program 182 00:08:25,720 --> 00:08:28,959 in an older language like C++ or in like raw 183 00:08:28,959 --> 00:08:31,300 assembly language, it's going to take a completely 184 00:08:31,300 --> 00:08:32,799 different number of characters. It definitely 185 00:08:32,799 --> 00:08:35,299 will. So doesn't the length of the shortest program 186 00:08:35,299 --> 00:08:37,759 completely depend on what programming language 187 00:08:37,759 --> 00:08:40,580 we use or which specific Turing machine we choose 188 00:08:40,580 --> 00:08:43,700 as our reference? That is the big question. Right. 189 00:08:43,799 --> 00:08:45,860 Because if the length changes based on the language, 190 00:08:46,000 --> 00:08:48,899 how can this complexity measure be an objective 191 00:08:48,899 --> 00:08:51,330 fundamental property of the object itself? That 192 00:08:51,330 --> 00:08:53,570 is the exact problem that could have killed this 193 00:08:53,570 --> 00:08:55,769 entire field of mathematics before it even started. 194 00:08:56,169 --> 00:08:58,190 I mean, it seems like a fatal flaw. It does. 195 00:08:58,509 --> 00:09:00,950 But the solution to that problem is the brilliant 196 00:09:00,950 --> 00:09:03,169 insight that made algorithmic information theory 197 00:09:03,169 --> 00:09:05,929 possible. It is a foundational theorem called 198 00:09:05,929 --> 00:09:08,870 the invariance theorem. The invariance theorem. 199 00:09:09,129 --> 00:09:11,850 Right. And what the invariance theorem proves 200 00:09:11,850 --> 00:09:14,750 is that the complexity of an object is objective 201 00:09:14,750 --> 00:09:17,409 and independent of the specific programming language 202 00:09:17,409 --> 00:09:20,289 or the specific reference machine, up to a fixed 203 00:09:20,379 --> 00:09:24,000 additive constant. Wait, up to a fixed additive 204 00:09:24,000 --> 00:09:26,840 constant. What does that actually mean in plain 205 00:09:26,840 --> 00:09:29,799 English? Let's break it down. Are you saying 206 00:09:29,799 --> 00:09:31,600 the difference in the length of the shortest 207 00:09:31,600 --> 00:09:34,639 program between machine A and machine B is never 208 00:09:34,639 --> 00:09:37,700 more than some specific number of bits, regardless 209 00:09:37,700 --> 00:09:40,139 of what string we are trying to describe? Yes, 210 00:09:40,279 --> 00:09:42,519 that is exactly it. Let's look at the mechanics 211 00:09:42,519 --> 00:09:45,200 of it. Think of that constant as the length of 212 00:09:45,200 --> 00:09:47,799 the compiler or the translation program. Okay. 213 00:09:48,039 --> 00:09:50,360 Let's say you have the absolute shortest program 214 00:09:50,360 --> 00:09:53,059 written for Machine B, but you only have Machine 215 00:09:53,059 --> 00:09:55,299 A to run it on. Right. I'm stuck with Machine 216 00:09:55,299 --> 00:09:58,139 A. Well, if Machine A is a universal computer, 217 00:09:58,259 --> 00:10:00,799 it can simulate Machine B. You just take your 218 00:10:00,799 --> 00:10:03,080 shortest program for Machine B, you attach a 219 00:10:03,080 --> 00:10:05,200 set of instructions that tells Machine A how 220 00:10:05,200 --> 00:10:07,379 to simulate Machine B, and you run the whole 221 00:10:07,379 --> 00:10:11,419 package. Ah, I see. So the only extra bits you 222 00:10:11,419 --> 00:10:14,059 have to add to the program is the translation 223 00:10:14,059 --> 00:10:18,480 manual. Exactly. And here's the magic. That translation 224 00:10:18,480 --> 00:10:21,720 manual is a fixed size. The overhead is constant. 225 00:10:22,100 --> 00:10:24,259 Wow. It doesn't matter if the string you're trying 226 00:10:24,259 --> 00:10:26,600 to output is a thousand bits long, or a billion 227 00:10:26,600 --> 00:10:29,700 bits long, or a trillion bits long. The instructions 228 00:10:29,700 --> 00:10:31,639 on how to translate between the two machines 229 00:10:31,639 --> 00:10:35,159 stay exactly the same size. Oh, that's brilliant. 230 00:10:35,700 --> 00:10:38,259 The theorem does not give us exact machine independence 231 00:10:38,259 --> 00:10:40,820 for every single short string in the real physical 232 00:10:40,820 --> 00:10:43,940 world. For short, highly compressible strings, 233 00:10:44,720 --> 00:10:47,299 that additive constant, the overhead of the translation 234 00:10:47,299 --> 00:10:50,360 program, is not negligible at all. Right, because 235 00:10:50,360 --> 00:10:53,120 if my target string is only 50 bits long, but 236 00:10:53,120 --> 00:10:55,419 the translation manual to simulate the machine 237 00:10:55,419 --> 00:10:58,779 takes like 500 bits. It swamps it. The translation 238 00:10:58,779 --> 00:11:00,840 manual completely dominates the size of the program. 239 00:11:01,200 --> 00:11:03,899 Precisely. For small data sets, your choice of 240 00:11:03,899 --> 00:11:06,259 language heavily influences the measured complexity. 241 00:11:06,399 --> 00:11:09,409 That makes sense. Now... The natural next step 242 00:11:09,409 --> 00:11:12,830 for anyone listening is to ask, how do we actually 243 00:11:12,830 --> 00:11:15,509 find it? The golden question. Say I have a one 244 00:11:15,509 --> 00:11:17,909 megabyte file on my desktop. I want to know its 245 00:11:17,909 --> 00:11:20,990 exact Kolmogorov complexity. I want to find the 246 00:11:20,990 --> 00:11:23,009 absolute shortest program that generates it. 247 00:11:23,529 --> 00:11:25,750 But as we move deeper into Lee and Vittani's 248 00:11:25,750 --> 00:11:28,850 text, we hit a fundamental unbreakable wall in 249 00:11:28,850 --> 00:11:32,490 computer science. We do. We hit the wall of uncomputability. 250 00:11:33,110 --> 00:11:35,679 Uncomputability. The plain Kolmogorov complexity 251 00:11:35,679 --> 00:11:39,519 C of X is fundamentally uncomputable. There is 252 00:11:39,519 --> 00:11:42,139 no algorithm, no computer program that currently 253 00:11:42,139 --> 00:11:45,120 exists, and no computer program that could ever 254 00:11:45,120 --> 00:11:48,600 conceivably exist. They can take any arbitrary 255 00:11:48,600 --> 00:11:52,600 string as input and always output its exact Kolmogorov 256 00:11:52,600 --> 00:11:55,039 complexity. See, I always love playing the naive 257 00:11:55,039 --> 00:11:57,679 optimist here. I know you do. Why not? I mean, 258 00:11:57,860 --> 00:12:00,399 computers are unbelievably fast nowadays. We 259 00:12:00,399 --> 00:12:03,070 have quantum computers on the horizon. If I want 260 00:12:03,070 --> 00:12:05,850 to find the absolute shortest program for a specific 261 00:12:05,850 --> 00:12:08,690 string, why don't I just use brute force? Brute 262 00:12:08,690 --> 00:12:12,250 force. Okay. How? Well, I could write a master 263 00:12:12,250 --> 00:12:14,590 program that starts by generating all possible 264 00:12:14,590 --> 00:12:17,909 one -bit programs. It runs them. If none of them 265 00:12:17,909 --> 00:12:19,669 spit out my string, it generates all possible 266 00:12:19,669 --> 00:12:21,950 two -bit programs. Then all three -bit programs. 267 00:12:21,950 --> 00:12:23,809 Right. And I don't just run them one by one. 268 00:12:23,850 --> 00:12:26,289 I run them all at the exact same time. You're 269 00:12:26,289 --> 00:12:28,149 touching on a concept computer scientists call 270 00:12:28,149 --> 00:12:31,250 dovetailing. Dovetailing. Right. So I run program 271 00:12:31,250 --> 00:12:33,389 one for one step. Then I run program one and 272 00:12:33,389 --> 00:12:35,690 program two for one step. I just keep expanding 273 00:12:35,690 --> 00:12:38,090 the pool, running millions of tiny programs in 274 00:12:38,090 --> 00:12:40,909 parallel. And I just sit back and watch. The 275 00:12:40,909 --> 00:12:43,230 exact moment one of these tiny programs spits 276 00:12:43,230 --> 00:12:45,710 out my target string and halts, I stop the experiment. 277 00:12:46,389 --> 00:12:48,629 The first one to spit it out must be the shortest 278 00:12:48,629 --> 00:12:50,509 program because I started from the smallest and 279 00:12:50,509 --> 00:12:52,970 worked my way up. Boom. Boom. I just computed 280 00:12:52,970 --> 00:12:55,529 the uncomputable. Why wouldn't that work? It 281 00:12:55,529 --> 00:12:58,129 sounds like an absolutely perfect foolproof plan. 282 00:12:58,330 --> 00:13:01,009 Thank you. And if computers were just magic boxes, 283 00:13:01,009 --> 00:13:03,919 it would work. But your plan crashes headfirst 284 00:13:03,919 --> 00:13:06,159 into a structural limit of logic, which is the 285 00:13:06,159 --> 00:13:09,340 halting problem. Ah, Turing again. Turing again. 286 00:13:09,860 --> 00:13:12,080 Alan Turing proved back in 1936 that there is 287 00:13:12,080 --> 00:13:14,460 no general algorithm that can determine whether 288 00:13:14,460 --> 00:13:16,720 an arbitrary computer program will eventually 289 00:13:16,720 --> 00:13:19,379 halt and give an answer, or if it will run forever 290 00:13:19,379 --> 00:13:21,500 in an infinite loop. Right, an infinite loop. 291 00:13:21,740 --> 00:13:23,980 Like when an old computer freezes and the hourglass 292 00:13:23,980 --> 00:13:26,139 just sits there spinning forever because the 293 00:13:26,139 --> 00:13:28,799 code is stuck in a cycle. Exactly. So let's look 294 00:13:28,799 --> 00:13:31,399 at the mechanics of your brute force dovetailing 295 00:13:31,399 --> 00:13:34,799 process. You're running millions of tiny programs 296 00:13:34,799 --> 00:13:38,039 simultaneously. Yep. Let's say one of them finally 297 00:13:38,039 --> 00:13:40,700 spits out your target string. You look at that 298 00:13:40,700 --> 00:13:44,720 program and it is exactly 50 bits long. Fantastic. 299 00:13:45,399 --> 00:13:48,279 You now know that 50 bits is an upper bound for 300 00:13:48,279 --> 00:13:51,389 the complexity of your string. Okay. You have 301 00:13:51,389 --> 00:13:53,429 mathematically proven that the complexity is 302 00:13:53,429 --> 00:13:56,490 at most 50 bits. Right, but I don't know if it's 303 00:13:56,490 --> 00:14:00,039 the absolute minimum. Exactly. Can you be absolutely 304 00:14:00,039 --> 00:14:03,379 certain it's the shortest? What if, in your massive 305 00:14:03,379 --> 00:14:06,039 parallel simulation, there is a 40 -bit program 306 00:14:06,039 --> 00:14:08,539 that is still running? Oh. It hasn't produced 307 00:14:08,539 --> 00:14:11,620 any output yet. It's just churning away. Is it 308 00:14:11,620 --> 00:14:13,799 executing a massively complex, time -consuming 309 00:14:13,799 --> 00:14:16,700 calculation that will eventually, after a billion 310 00:14:16,700 --> 00:14:19,559 years, print your string? Or is it just stuck 311 00:14:19,559 --> 00:14:22,879 in a useless infinite loop? Oh, wow. You can 312 00:14:22,879 --> 00:14:24,980 establish upper bounds from above every time 313 00:14:24,980 --> 00:14:27,200 a shorter program happens to output your string. 314 00:14:27,279 --> 00:14:30,220 Your ceiling drops. Right, I know it's at least 315 00:14:30,220 --> 00:14:33,000 that small. But there is no general, computable 316 00:14:33,000 --> 00:14:36,179 certificate that can prove you have hit the absolute 317 00:14:36,179 --> 00:14:39,759 floor. That is wild. It is not a matter of having 318 00:14:39,759 --> 00:14:42,399 slow computers, and it's not something that a 319 00:14:42,399 --> 00:14:45,399 quantum computer can fix. It is a structural, 320 00:14:45,820 --> 00:14:48,899 inescapable limit of logic itself. That is profound. 321 00:14:49,340 --> 00:14:51,240 And it brings us straight into the shadow of 322 00:14:51,240 --> 00:14:54,740 Kurt Goodall. Oh yes. Godel's incompleteness 323 00:14:54,740 --> 00:14:57,139 theorem is easily one of the most famous, most 324 00:14:57,139 --> 00:14:59,220 earth -shattering results in the history of mathematics. 325 00:14:59,980 --> 00:15:02,700 In the 1930s, he essentially proved that in any 326 00:15:02,700 --> 00:15:05,320 sufficiently powerful logical system, there are 327 00:15:05,320 --> 00:15:07,399 true statements that simply cannot be proven 328 00:15:07,399 --> 00:15:10,659 true within that system. Right. Math is fundamentally 329 00:15:10,659 --> 00:15:13,500 incomplete. So how does algorithmic information 330 00:15:13,500 --> 00:15:15,809 theory connect to Godel? It connects beautifully. 331 00:15:16,610 --> 00:15:18,429 Algorithmic information theory actually gives 332 00:15:18,429 --> 00:15:21,750 us a fascinating alternative way to prove Gödel's 333 00:15:21,750 --> 00:15:24,490 incompleteness theorem, and it does it via the 334 00:15:24,490 --> 00:15:27,409 concept of incompressibility. Okay, let's walk 335 00:15:27,409 --> 00:15:30,159 through that. Let's look at the mechanics of 336 00:15:30,159 --> 00:15:33,000 the proof provided in the text. Imagine a sound, 337 00:15:33,220 --> 00:15:35,919 effectively axiomatized formal mathematical system. 338 00:15:36,049 --> 00:15:39,649 By formal system, we mean a rigorous set of mathematical 339 00:15:39,649 --> 00:15:43,090 axioms and the strict rules for how you can deduce 340 00:15:43,090 --> 00:15:46,029 new truths from those axioms, like the fundamental 341 00:15:46,029 --> 00:15:48,730 rules of geometry or algebra. Exactly. Now, that 342 00:15:48,730 --> 00:15:50,669 formal system itself can be described by a computer 343 00:15:50,669 --> 00:15:53,409 program. Because it's just rules. Right. It has 344 00:15:53,409 --> 00:15:56,470 its own Kolmogorov complexity. Let's say the 345 00:15:56,470 --> 00:15:58,690 absolute shortest program to describe the complete 346 00:15:58,690 --> 00:16:01,090 rulebook of this formal system is F bits long. 347 00:16:01,299 --> 00:16:03,700 Okay, I am tracking with you. We have a mathematical 348 00:16:03,700 --> 00:16:06,379 rulebook, and it takes exactly f bits to describe 349 00:16:06,379 --> 00:16:09,779 it to a computer. Good. Now, suppose you want 350 00:16:09,779 --> 00:16:12,639 to use this formal f -bit system to prove a specific 351 00:16:12,639 --> 00:16:15,639 fact. You want to prove that a massive, specific 352 00:16:15,639 --> 00:16:18,159 string of data, which we will call string x, 353 00:16:18,580 --> 00:16:20,980 is mathematically incompressible. Meaning you 354 00:16:20,980 --> 00:16:24,139 want to prove that the true Kolmogorov complexity 355 00:16:24,139 --> 00:16:26,980 of string x is greater than some massive number 356 00:16:26,980 --> 00:16:30,720 n. Exactly. So, I want my rulebook to prove that 357 00:16:30,720 --> 00:16:33,220 string x cannot be compressed to anything smaller 358 00:16:33,220 --> 00:16:36,820 than n bits. And let's assume n is vastly, vastly 359 00:16:36,820 --> 00:16:39,480 larger than f, which is the size of my rulebook. 360 00:16:40,000 --> 00:16:42,879 Right. What Lee and Vittani demonstrate is that 361 00:16:42,879 --> 00:16:45,120 this formal system is structurally incapable 362 00:16:45,120 --> 00:16:48,360 of doing that. It can't do it. It can't. Okay, 363 00:16:48,360 --> 00:16:51,360 wait. Walk me through exactly why that is. Why 364 00:16:51,360 --> 00:16:53,899 can't a simple rulebook prove that a really long 365 00:16:53,899 --> 00:16:56,000 string is incompressible? We do it by a proof 366 00:16:56,000 --> 00:16:59,379 by contradiction. Okay, I love these. Let's assume 367 00:16:59,379 --> 00:17:02,419 your formal system, which is only f -bits complex, 368 00:17:03,120 --> 00:17:06,519 could somehow prove that string x is incompressible 369 00:17:06,519 --> 00:17:09,619 and has a complexity greater than n. Let's assume 370 00:17:09,619 --> 00:17:13,099 it works. If that were possible, you and I could 371 00:17:13,099 --> 00:17:16,059 write a clever little search program. This search 372 00:17:16,059 --> 00:17:18,799 program simply uses the formal system to generate 373 00:17:18,799 --> 00:17:21,480 every single possible valid mathematical proof, 374 00:17:21,839 --> 00:17:24,890 one by one. Just grinding through every possible 375 00:17:24,890 --> 00:17:28,710 logical deduction the rulebook allows. Yes. And 376 00:17:28,710 --> 00:17:31,170 we program it to scan those proofs. The program 377 00:17:31,170 --> 00:17:33,650 just waits until it finally generates a valid 378 00:17:33,650 --> 00:17:36,289 proof for the statement, this specific string 379 00:17:36,289 --> 00:17:40,420 x has a complexity greater than n. Right. The 380 00:17:40,420 --> 00:17:42,920 exact moment it finds that proof, the program 381 00:17:42,920 --> 00:17:45,220 is instructed to print string x to the screen 382 00:17:45,220 --> 00:17:49,019 and halt. Okay, I see the setup. But let's look 383 00:17:49,019 --> 00:17:51,319 at the size of the search program we just wrote. 384 00:17:51,440 --> 00:17:53,539 Let's look at it. To write it, we needed the 385 00:17:53,539 --> 00:17:56,099 formal system itself, which we set as F bits. 386 00:17:56,779 --> 00:17:59,559 We needed to encode the target number n, which 387 00:17:59,559 --> 00:18:02,160 takes a very small number of bits, maybe just 388 00:18:02,160 --> 00:18:05,220 the logarithm of n. And we need a few bits for 389 00:18:05,220 --> 00:18:08,779 the basic search and print script. So the total 390 00:18:08,779 --> 00:18:11,019 size of our search program is roughly F bits. 391 00:18:11,859 --> 00:18:15,259 Exactly. Now look at what your roughly F bit 392 00:18:15,259 --> 00:18:18,900 program just achieved. It just ran, and it printed 393 00:18:18,900 --> 00:18:22,279 string x. Oh. Oh, I see it. Tell me what you 394 00:18:22,279 --> 00:18:26,660 see. A program that is roughly f bits long just 395 00:18:26,660 --> 00:18:30,220 perfectly generated string x. But the formal 396 00:18:30,220 --> 00:18:32,940 system just proved that string x has a complexity 397 00:18:32,940 --> 00:18:37,440 greater than n. And we explicitly set this up 398 00:18:37,440 --> 00:18:41,140 so that n is vastly larger than f. That is the 399 00:18:41,140 --> 00:18:44,299 massive fatal contradiction. Oh wow. You just 400 00:18:44,299 --> 00:18:46,680 used a tiny program to generate a string, while 401 00:18:46,680 --> 00:18:49,420 simultaneously using that exact same tiny program 402 00:18:49,420 --> 00:18:52,400 to mathematically prove that no tiny program 403 00:18:52,400 --> 00:18:54,500 could possibly generate it. It's the Richard 404 00:18:54,500 --> 00:18:57,339 Berry paradox. It is the Richard Berry paradox 405 00:18:57,339 --> 00:19:00,640 manifesting in pure computer logic. It's the 406 00:19:00,640 --> 00:19:03,700 exact same glitch. The only way out of the contradiction 407 00:19:03,700 --> 00:19:05,960 is to accept that the initial assumption was 408 00:19:05,960 --> 00:19:08,549 wrong. A sound formal system can never prove 409 00:19:08,549 --> 00:19:11,589 that a string's complexity is substantially larger 410 00:19:11,589 --> 00:19:14,009 than the complexity of the formal system itself. 411 00:19:14,430 --> 00:19:17,990 Precisely. That is genuinely mind -bending. But 412 00:19:17,990 --> 00:19:20,009 I want to make sure I'm not taking this too far 413 00:19:20,009 --> 00:19:22,710 into science fiction. This doesn't mean that 414 00:19:22,710 --> 00:19:26,509 logic itself is broken, right? No. And it's vital 415 00:19:26,509 --> 00:19:29,390 we don't misinterpret this. This theorem precisely 416 00:19:29,390 --> 00:19:32,470 defines the limits of what a specific, formal, 417 00:19:32,829 --> 00:19:35,839 axiomatic system can prove. Okay. It does not 418 00:19:35,839 --> 00:19:38,440 mean that all true math is simpler than its axioms. 419 00:19:38,799 --> 00:19:41,339 And it certainly doesn't mean that ordinary language 420 00:19:41,339 --> 00:19:43,900 destroys logic just because natural language 421 00:19:43,900 --> 00:19:46,279 paradoxes like the Richard Berry paradox inspired 422 00:19:46,279 --> 00:19:50,359 the math. That's a relief. It simply puts a firm, 423 00:19:50,660 --> 00:19:52,960 quantifiable mathematical ceiling on the proving 424 00:19:52,960 --> 00:19:55,539 power of any mechanical system when it comes 425 00:19:55,539 --> 00:19:58,000 to algorithmic complexity. That makes sense. 426 00:19:58,200 --> 00:20:00,700 It's a precise boundary, not a dissolution of 427 00:20:00,700 --> 00:20:03,539 logic. And this exploration of complexity brings 428 00:20:03,539 --> 00:20:05,960 us to a really profound redefinition of a word 429 00:20:05,960 --> 00:20:09,960 we use every single day. Randomness. Yes. Randomness. 430 00:20:10,420 --> 00:20:12,579 We throw the word random around constantly. We 431 00:20:12,579 --> 00:20:15,079 say a song on shuffle is random or a dice roll 432 00:20:15,079 --> 00:20:17,640 is random, but algorithmic information theory 433 00:20:17,640 --> 00:20:20,539 redefines randomness mathematically. Under this 434 00:20:20,539 --> 00:20:23,259 framework, a string of data is random if and 435 00:20:23,259 --> 00:20:26,170 only if it is incompressible. Yes. If a string 436 00:20:26,170 --> 00:20:28,829 is mathematically random, it means its absolute 437 00:20:28,829 --> 00:20:31,009 shortest program is basically just the literal 438 00:20:31,009 --> 00:20:33,890 string itself, packaged with a basic print command. 439 00:20:34,289 --> 00:20:35,829 There's no trick to it. There are absolutely 440 00:20:35,829 --> 00:20:38,710 no hidden patterns, no fractal structures, no 441 00:20:38,710 --> 00:20:41,490 shortcuts for an algorithm to exploit. But wait, 442 00:20:41,650 --> 00:20:44,589 if I take a perfectly fair coin and I flip it 443 00:20:44,589 --> 00:20:47,390 a hundred times in a row, it is entirely possible, 444 00:20:47,630 --> 00:20:50,009 though highly improbable, that I could flip a 445 00:20:50,009 --> 00:20:52,910 hundred heads in a row. It is. Are you saying 446 00:20:52,910 --> 00:20:55,420 that outcome isn't random? This is a crucial 447 00:20:55,420 --> 00:20:57,940 distinction that Lee and Vitanya make, and it 448 00:20:57,940 --> 00:21:00,599 separates the process from the outcome. Process 449 00:21:00,599 --> 00:21:03,160 versus outcome. Right. A fair coin flip is a 450 00:21:03,160 --> 00:21:06,359 random process. It can absolutely produce 100 451 00:21:06,359 --> 00:21:10,059 heads in a row. But that specific outcome, the 452 00:21:10,059 --> 00:21:12,400 string of 100 heads, is highly compressible. 453 00:21:12,819 --> 00:21:16,039 Because it's just heads times 100. Exactly. You 454 00:21:16,039 --> 00:21:18,740 can describe it in a few bits. Print heads 100 455 00:21:18,740 --> 00:21:22,599 times. Therefore, the outcome itself is not algorithmically 456 00:21:22,599 --> 00:21:26,230 random. I love that distinction. A random process 457 00:21:26,230 --> 00:21:28,829 doesn't guarantee an incompressible outcome. 458 00:21:29,309 --> 00:21:31,509 We have to separate how a thing was made from 459 00:21:31,509 --> 00:21:34,250 what the thing actually is. Exactly. Now up to 460 00:21:34,250 --> 00:21:36,869 this point, we've established plane complexity, 461 00:21:37,210 --> 00:21:40,670 C of X, the absolute shortest program. Right. 462 00:21:40,950 --> 00:21:43,829 But as we dive deeper into the text, a subtle 463 00:21:43,829 --> 00:21:46,289 but massive technical problem arises when we 464 00:21:46,289 --> 00:21:48,509 try to actually use these programs mathematically, 465 00:21:48,990 --> 00:21:50,869 particularly when we want to stitch multiple 466 00:21:50,869 --> 00:21:53,430 programs together. The problem of concatenation. 467 00:21:53,910 --> 00:21:56,009 I was reading this section and it reminded me 468 00:21:56,009 --> 00:21:57,829 of trying to read an entire sentence where someone 469 00:21:57,829 --> 00:22:00,309 forgot to use the space bar. That is the perfect 470 00:22:00,309 --> 00:22:03,549 analogy. Let's break down the mechanics. In plain 471 00:22:03,549 --> 00:22:06,490 complexity, we feed a binary program to a Turing 472 00:22:06,490 --> 00:22:09,690 machine. But how does the machine know when to 473 00:22:09,690 --> 00:22:12,210 stop reading the input? Because there's no space 474 00:22:12,210 --> 00:22:16,180 bar. Right. We usually implicitly assume the 475 00:22:16,180 --> 00:22:18,119 machine knows the length of the program because 476 00:22:18,119 --> 00:22:20,900 it's stored in a separate file or the operating 477 00:22:20,900 --> 00:22:23,630 system has a special and a file marker. Right. 478 00:22:24,049 --> 00:22:26,410 But if I just hand you a continuous stream of 479 00:22:26,410 --> 00:22:29,670 binary, like 101110, and I say, here are some 480 00:22:29,670 --> 00:22:32,289 programs, you have no idea what you're looking 481 00:22:32,289 --> 00:22:34,990 at. Completely blind. Is that one single program 482 00:22:34,990 --> 00:22:38,150 that is six bits long? Is it two programs, 101 483 00:22:38,150 --> 00:22:41,630 and 110, stitched together? Is it three two -bit 484 00:22:41,630 --> 00:22:44,089 programs? Without spaces, without punctuation, 485 00:22:44,190 --> 00:22:47,250 the machine is completely lost. To solve this, 486 00:22:47,549 --> 00:22:50,289 the book introduces a new refined measure called 487 00:22:50,440 --> 00:22:53,599 Prefix complexity. Prefix complexity. Denoted 488 00:22:53,599 --> 00:22:57,180 as K of X. This version of complexity requires 489 00:22:57,180 --> 00:23:00,400 all valid programs to be prefix free. Prefix 490 00:23:00,400 --> 00:23:02,539 free. Let me see if I have a good analogy for 491 00:23:02,539 --> 00:23:05,339 this. It's like telephone numbers, right? Go 492 00:23:05,339 --> 00:23:08,480 on. In the US, 911 is a valid emergency number. 493 00:23:08,940 --> 00:23:11,200 Because it's a valid number, the phone company 494 00:23:11,200 --> 00:23:15,200 can't also assign 9114 as a completely different 495 00:23:15,200 --> 00:23:18,029 person's phone number. Right. If they did, The 496 00:23:18,029 --> 00:23:19,730 system wouldn't know if you were done dialing 497 00:23:19,730 --> 00:23:21,470 after the first three digits or if you were still 498 00:23:21,470 --> 00:23:24,890 typing. No valid number can be the starting sequence, 499 00:23:25,190 --> 00:23:28,549 the prefix, of another valid number. That is 500 00:23:28,549 --> 00:23:31,609 a brilliant analogy. Prefix -free codes are self 501 00:23:31,609 --> 00:23:33,910 -delimiting. The program essentially contains 502 00:23:33,910 --> 00:23:36,329 its own punctuation. So it tells the machine 503 00:23:36,329 --> 00:23:39,069 when to stop. Usually it does this by encoding 504 00:23:39,069 --> 00:23:41,309 the total length of the program at the very beginning 505 00:23:41,309 --> 00:23:43,890 of the string, using a clever format that the 506 00:23:43,890 --> 00:23:47,240 machine can decode on the fly. Okay, I get how 507 00:23:47,240 --> 00:23:50,500 it works mechanically, but I have to ask, why 508 00:23:50,500 --> 00:23:53,380 go through the trouble? Adding this self -delimiting 509 00:23:53,380 --> 00:23:56,279 punctuation adds extra bits to the program. It 510 00:23:56,279 --> 00:23:58,400 does. It makes the shortest program slightly 511 00:23:58,400 --> 00:24:01,299 longer. Think about the fundamental rule of probability. 512 00:24:01,920 --> 00:24:04,759 The probabilities of all possible mutually exclusive 513 00:24:04,759 --> 00:24:09,079 events must sum to exactly one, or 100%. Right. 514 00:24:09,640 --> 00:24:12,319 Think of total probability as a pie chart. The 515 00:24:12,319 --> 00:24:15,930 whole pie is 100%. If you assign probabilities 516 00:24:15,930 --> 00:24:18,630 to binary strings, and your code allows a program 517 00:24:18,630 --> 00:24:22,369 like zero to be valid, but also allows zero one 518 00:24:22,369 --> 00:24:25,710 to be valid, you are double counting. Like overlapping 519 00:24:25,710 --> 00:24:28,589 pie slices. Exactly. The event where the machine 520 00:24:28,589 --> 00:24:31,609 reads zero overlaps with the event where it reads 521 00:24:31,609 --> 00:24:34,430 zero one. You are assigning overlapping pieces 522 00:24:34,430 --> 00:24:36,849 of the pie chart. In probability theory, the 523 00:24:36,849 --> 00:24:39,630 requirement that valid code words must satisfy 524 00:24:39,630 --> 00:24:42,309 this mathematical constraint is known as Kraft's 525 00:24:42,309 --> 00:24:45,970 inequality. Kraft's? Inequality. Prefix -free 526 00:24:45,970 --> 00:24:48,089 codes ensure that every single valid program 527 00:24:48,089 --> 00:24:50,509 gets its own distinct non -overlapping slice 528 00:24:50,509 --> 00:24:53,430 of the probability pie. The sum will always be 529 00:24:53,430 --> 00:24:57,869 less than or equal to 1. Wow. So prefix complexity, 530 00:24:58,250 --> 00:25:01,609 k of x, isn't a hack. It is the vital mathematical 531 00:25:01,609 --> 00:25:04,250 bridge that allows algorithmic information theory 532 00:25:04,250 --> 00:25:07,150 to merge flawlessly with probability. And once 533 00:25:07,150 --> 00:25:09,450 we cross that bridge into prefix complexity, 534 00:25:09,630 --> 00:25:12,130 the math and the textbook yield some incredibly 535 00:25:12,130 --> 00:25:14,829 elegant theorems. One of them that really caught 536 00:25:14,829 --> 00:25:17,829 my eye is the symmetry of algorithmic information. 537 00:25:18,049 --> 00:25:20,390 Yes. In classical Shannon information theory, 538 00:25:20,910 --> 00:25:23,029 the mutual information between two variables 539 00:25:23,029 --> 00:25:26,710 is symmetric. The information x has about y is 540 00:25:26,710 --> 00:25:29,470 the same as y has about x. And the algorithmic 541 00:25:29,470 --> 00:25:31,730 equivalent is the same. It's equally beautiful. 542 00:25:32,299 --> 00:25:34,819 It states that the algorithmic information contained 543 00:25:34,819 --> 00:25:38,220 in object x about object y is roughly equal to 544 00:25:38,220 --> 00:25:42,099 the information contained in y about x. Formulaically, 545 00:25:42,380 --> 00:25:46,200 the text writes this as k of x comma y, which 546 00:25:46,200 --> 00:25:48,700 is the complexity of computing both x and y together, 547 00:25:49,240 --> 00:25:52,819 is approximately equal to k of x plus k of y 548 00:25:52,819 --> 00:25:55,759 given x. Let's translate that math into a mechanism. 549 00:25:56,319 --> 00:25:58,539 It means the length of the shortest prefix program 550 00:25:58,539 --> 00:26:02,019 needed to compute both x and y is basically equal 551 00:26:02,019 --> 00:26:03,839 to the length of the shortest program to compute 552 00:26:03,839 --> 00:26:06,890 x from scratch, plus the length of the shortest 553 00:26:06,890 --> 00:26:09,309 program to compute y if the computer already 554 00:26:09,309 --> 00:26:12,250 has x sitting in its memory. That is so clean. 555 00:26:12,690 --> 00:26:14,890 It proves that algorithmic information acts almost 556 00:26:14,890 --> 00:26:17,410 like a physical, tangible quantity. It can be 557 00:26:17,410 --> 00:26:20,430 partitioned, shifted, and combined symmetrically. 558 00:26:21,049 --> 00:26:23,650 Makes perfect sense. But right after that, the 559 00:26:23,650 --> 00:26:25,910 text takes us into a real psychological mind 560 00:26:25,910 --> 00:26:28,890 -bender, which is the complexity of complexity. 561 00:26:28,910 --> 00:26:32,670 Oh yes. The mathematical term is k of k of x 562 00:26:32,670 --> 00:26:36,009 given x. Let me try to explain what this represents. 563 00:26:36,210 --> 00:26:38,789 This is the length of the shortest program needed 564 00:26:38,789 --> 00:26:41,609 to compute the exact complexity of an object 565 00:26:41,609 --> 00:26:44,950 x, assuming the computer is already given the 566 00:26:44,950 --> 00:26:48,390 object x itself for free. That is correct. Now 567 00:26:48,390 --> 00:26:50,660 intuitively, I would look at that and think, 568 00:26:50,779 --> 00:26:52,579 well, I have the object X right in front of me. 569 00:26:52,660 --> 00:26:55,019 The computer holds it in memory. Therefore, I 570 00:26:55,019 --> 00:26:57,019 know everything there is to know about it. Finding 571 00:26:57,019 --> 00:26:59,599 its complexity should be trivial. That is the 572 00:26:59,599 --> 00:27:01,920 natural human intuition, but it is mathematically 573 00:27:01,920 --> 00:27:05,220 false. It is surprisingly non -trivial. Really? 574 00:27:05,740 --> 00:27:08,240 Think about it like staring at a massively messy 575 00:27:08,240 --> 00:27:10,759 chaotic desk in your office. You have all the 576 00:27:10,759 --> 00:27:12,640 objects right in front of you. You can see the 577 00:27:12,640 --> 00:27:15,009 papers, the pens, the books. Sure. But knowing 578 00:27:15,009 --> 00:27:17,529 how to perfectly organize that desk into the 579 00:27:17,529 --> 00:27:20,230 absolute most efficient arrangement is a completely 580 00:27:20,230 --> 00:27:23,750 separate, exhausting mental task. Having the 581 00:27:23,750 --> 00:27:26,869 raw data does not mean you possess the optimal 582 00:27:26,869 --> 00:27:29,630 description of the data. Wow. The desk analogy 583 00:27:29,630 --> 00:27:31,269 is perfect. Just because I have the file doesn't 584 00:27:31,269 --> 00:27:34,089 mean I have the zip algorithm perfectly tuned 585 00:27:34,089 --> 00:27:36,690 for it. Exactly. The complexity value itself 586 00:27:36,690 --> 00:27:39,380 holds its own algorithmic information. as we 587 00:27:39,380 --> 00:27:41,859 discussed earlier with the halting problem. Finding 588 00:27:41,859 --> 00:27:44,599 the shortest program is fundamentally uncomputable. 589 00:27:44,980 --> 00:27:48,319 Right. Okay, so we've built a massive foundation. 590 00:27:48,500 --> 00:27:51,279 We understand plane complexity, we understand 591 00:27:51,279 --> 00:27:54,000 the uncomputable limits of logic, and we understand 592 00:27:54,000 --> 00:27:56,579 why prefix codes are the necessary punctuation 593 00:27:56,579 --> 00:27:58,619 to make the math work. The necessary punctuation, 594 00:27:58,779 --> 00:28:02,920 yes. Now we transition into algorithmic probability. 595 00:28:03,079 --> 00:28:05,240 This is where Lee and Vitani build a bridge from 596 00:28:05,240 --> 00:28:07,519 computer science directly into deep philosophy. 597 00:28:07,980 --> 00:28:09,859 This is perhaps my favorite part of the theory. 598 00:28:10,880 --> 00:28:14,460 What we see here is mathematics formalizing a 599 00:28:14,460 --> 00:28:16,619 concept that philosophers have debated for centuries, 600 00:28:16,799 --> 00:28:19,700 which is Occam's razor. The philosophical maxim 601 00:28:19,700 --> 00:28:23,200 that basically says when you are faced with competing 602 00:28:23,200 --> 00:28:26,779 hypotheses or explanations, the simplest explanation 603 00:28:26,779 --> 00:28:29,940 is the most likely to be true. Precisely. But 604 00:28:29,940 --> 00:28:32,799 philosophically, Occam's razor is vague. what 605 00:28:32,799 --> 00:28:36,200 exactly defines simple and what exactly defines 606 00:28:36,200 --> 00:28:39,359 likely. Right. Ray Solomonoff formalized this 607 00:28:39,359 --> 00:28:42,119 mathematically with his universal prior distribution. 608 00:28:42,680 --> 00:28:45,420 How exactly does he formalize it? A specific 609 00:28:45,420 --> 00:28:48,000 1 -bit program has a 1 in 2 chance of being randomly 610 00:28:48,000 --> 00:28:50,559 activated. A 2 -bit program has a 1 in 4 chance. 611 00:28:50,660 --> 00:28:53,619 A 3 -bit program has a 1 in 8 chance. So it drops 612 00:28:53,619 --> 00:28:56,319 exponentially. The discrete universal a priori 613 00:28:56,319 --> 00:28:58,720 semi -measure, which mathematicians denote as 614 00:28:58,720 --> 00:29:01,839 M of X, is found by summing up the probabilities 615 00:29:01,839 --> 00:29:04,579 of all the different random prefix -free programs 616 00:29:04,579 --> 00:29:07,220 that eventually halt and output the specific 617 00:29:07,220 --> 00:29:10,140 string x. So because short programs require fewer 618 00:29:10,140 --> 00:29:13,380 specific consecutive coin tosses to be activated, 619 00:29:14,000 --> 00:29:17,000 they are exponentially more likely to occur by 620 00:29:17,000 --> 00:29:19,819 chance than long complicated programs. Exactly. 621 00:29:20,480 --> 00:29:23,019 The formula sums the weights calculated as 2 622 00:29:23,019 --> 00:29:24,980 to the power of negative length of the program 623 00:29:24,980 --> 00:29:28,799 of all halting prefix programs that output x. 624 00:29:28,990 --> 00:29:32,309 And wait, you called it a semi -measure. It is 625 00:29:32,309 --> 00:29:35,009 critically called a semi -measure because not 626 00:29:35,009 --> 00:29:37,470 all random sequences of coin tosses will result 627 00:29:37,470 --> 00:29:40,250 in a program that halts. Right, the halting problem 628 00:29:40,250 --> 00:29:43,490 again. Yeah. So the total sum of the probabilities 629 00:29:43,490 --> 00:29:46,589 of all halting outcomes is strictly less than 630 00:29:46,589 --> 00:29:49,250 one. And the crowning mathematical achievement 631 00:29:49,250 --> 00:29:51,269 of this section is something called the coding 632 00:29:51,269 --> 00:29:54,450 theorem. What does that theorem tell us? Let's 633 00:29:54,450 --> 00:29:57,490 translate that. In plain English. The probability 634 00:29:57,490 --> 00:30:00,109 of an object emerging from a random computational 635 00:30:00,109 --> 00:30:04,329 process is almost entirely dictated by its Kolmogorov 636 00:30:04,329 --> 00:30:07,450 complexity. The shorter the absolute shortest 637 00:30:07,450 --> 00:30:10,869 program for an object is, the exponentially more 638 00:30:10,869 --> 00:30:13,829 likely that object is to be generated. Wow. Wait, 639 00:30:13,890 --> 00:30:16,069 hold on. Let me stop you there because this sounds 640 00:30:16,069 --> 00:30:19,549 massive. Are we saying that Occam's razor is 641 00:30:19,549 --> 00:30:22,680 now a proven mathematical law of the physical 642 00:30:22,680 --> 00:30:26,140 universe? Like, the simplest explanation is objectively, 643 00:30:26,640 --> 00:30:28,680 physically the right one in nature. Because that 644 00:30:28,680 --> 00:30:32,779 feels like an incredibly bold claim for a computer 645 00:30:32,779 --> 00:30:35,400 science textbook. That is a very dangerous trap 646 00:30:35,400 --> 00:30:36,920 to fall into, and I'm really glad you brought 647 00:30:36,920 --> 00:30:39,619 it up. We have to dial that back. Okay, good. 648 00:30:39,920 --> 00:30:43,460 It is crucial we don't overstate this. Solomonoff's 649 00:30:43,460 --> 00:30:46,460 universal prior is a formalized theoretical mixture. 650 00:30:47,059 --> 00:30:49,519 It has incredibly powerful mathematical convergence 651 00:30:49,519 --> 00:30:51,960 results if we assume the data we are observing 652 00:30:51,960 --> 00:30:55,259 is generated by some computable probability measure. 653 00:30:55,500 --> 00:30:58,180 Exactly. But it does not definitively prove that 654 00:30:58,180 --> 00:31:00,640 the physical universe is actively generated by 655 00:31:00,640 --> 00:31:03,599 the absolute simplest program. Right. Furthermore, 656 00:31:03,839 --> 00:31:05,920 the probabilities given by the universal prior 657 00:31:05,920 --> 00:31:09,180 m of x are not exact literal numerical frequencies 658 00:31:09,180 --> 00:31:11,460 that you can go out and observe in a laboratory. 659 00:31:11,710 --> 00:31:13,990 So I can't just measure it with a stopwatch? 660 00:31:14,390 --> 00:31:17,470 No. The coding theorem holds true up to an additive 661 00:31:17,470 --> 00:31:20,930 constant in the exponent, which means the probabilities 662 00:31:20,930 --> 00:31:23,750 agree only up to a multiplicative constant factor. 663 00:31:24,230 --> 00:31:26,869 Okay, that brings us down to Earth a bit. So 664 00:31:26,869 --> 00:31:30,410 if Solomonoff gives us this beautiful, yet highly 665 00:31:30,410 --> 00:31:33,089 theoretical ideal for inductive reasoning, how 666 00:31:33,089 --> 00:31:35,869 do we actually apply it to the real world? That's 667 00:31:35,869 --> 00:31:38,460 the next big step. Because in the real world 668 00:31:38,460 --> 00:31:41,039 of statistics, data science, and machine learning, 669 00:31:41,279 --> 00:31:44,579 we don't have infinite computing power. We can't 670 00:31:44,579 --> 00:31:47,059 wait out the halting problem to find the absolute 671 00:31:47,059 --> 00:31:49,519 shortest program. We need tools that actually 672 00:31:49,519 --> 00:31:52,380 work before the sun burns out. And that is exactly 673 00:31:52,380 --> 00:31:55,740 what the text explores next. To bridge the theoretical 674 00:31:55,740 --> 00:31:58,839 with the highly practical, Leon Vittagni introduced 675 00:31:58,839 --> 00:32:01,180 the Minimum Description Length Principle, or 676 00:32:01,180 --> 00:32:04,079 MDL. MDL. It was pioneered by Yorma Risenin. 677 00:32:04,519 --> 00:32:06,279 If you are building an artificial intelligence, 678 00:32:06,539 --> 00:32:09,460 or if you are a data scientist trying to analyze 679 00:32:09,460 --> 00:32:12,700 a massive data set, MDL tells you exactly how 680 00:32:12,700 --> 00:32:15,700 to choose the best mathematical model. So what 681 00:32:15,700 --> 00:32:19,440 does this all mean? How does it work? MDL states 682 00:32:19,440 --> 00:32:22,039 that the best hypothesis for a given set of data 683 00:32:22,039 --> 00:32:24,099 is the one that minimizes the combined length 684 00:32:24,099 --> 00:32:27,059 of two distinct things. First, the description 685 00:32:27,059 --> 00:32:30,519 length of the model itself. And second, the description 686 00:32:30,519 --> 00:32:34,059 length of the data given that model. Okay, let's 687 00:32:34,059 --> 00:32:36,599 visualize this for the listener. Say I'm a scientist 688 00:32:36,599 --> 00:32:39,259 and I have a scatter plot of a hundred data points 689 00:32:39,259 --> 00:32:42,619 on a graph. They roughly trend upwards. I want 690 00:32:42,619 --> 00:32:44,799 to draw a line through them to predict future 691 00:32:44,799 --> 00:32:48,799 data. The model is the mathematical equation 692 00:32:48,799 --> 00:32:52,390 of the line I draw. Exactly. Now, consider the 693 00:32:52,390 --> 00:32:55,190 two extreme ways you could approach this. Extreme 694 00:32:55,190 --> 00:32:58,609 A, you want zero error. Right. So you would draw 695 00:32:58,609 --> 00:33:01,849 a completely erratic, highly complex 99 degree 696 00:33:01,849 --> 00:33:04,630 polynomial squiggle that weaves around and perfectly 697 00:33:04,630 --> 00:33:06,549 intersects every single one of your 100 data 698 00:33:06,549 --> 00:33:09,210 points. The model fits the data perfectly. But 699 00:33:09,210 --> 00:33:10,950 the description of the model itself is going 700 00:33:10,950 --> 00:33:13,049 to be a nightmare. To write down the equation 701 00:33:13,049 --> 00:33:16,089 for a 99 degree polynomial, I have to write out 702 00:33:16,089 --> 00:33:19,109 100 different parameters, coefficients, and exponents. 703 00:33:19,230 --> 00:33:22,369 The description is huge. Right. It takes way 704 00:33:22,369 --> 00:33:24,970 too many bits to describe the model. Now consider 705 00:33:24,970 --> 00:33:27,849 extreme B. You want the simplest model possible. 706 00:33:28,029 --> 00:33:30,730 So you just draw a flat horizontal line right 707 00:33:30,730 --> 00:33:33,009 through the middle of the graph. The description 708 00:33:33,009 --> 00:33:37,089 of that model is tiny. Y equals five. Just a 709 00:33:37,089 --> 00:33:39,529 few bits. But the residual error for that flat 710 00:33:39,529 --> 00:33:42,049 line is massive. Most of my data points are nowhere 711 00:33:42,049 --> 00:33:44,809 near that line, so to accurately describe my 712 00:33:44,809 --> 00:33:46,970 data, I have to spend a ton of bits describing 713 00:33:46,970 --> 00:33:49,569 exactly how far off every single point is from 714 00:33:49,569 --> 00:33:52,589 the model. This is underfitting. I missed the 715 00:33:52,589 --> 00:33:55,980 upward trend entirely. Exactly. MDL mathematically 716 00:33:55,980 --> 00:33:59,079 forces you to balance those two extremes. It 717 00:33:59,079 --> 00:34:01,160 asks you to calculate the length of the model's 718 00:34:01,160 --> 00:34:04,039 equation plus the length of the residual errors 719 00:34:04,039 --> 00:34:06,819 and minimize the sum of both. Finding the sweet 720 00:34:06,819 --> 00:34:10,369 spot. When you do that, it finds the sweet spot. 721 00:34:10,869 --> 00:34:14,329 Maybe a simple, elegant quadratic curve that 722 00:34:14,329 --> 00:34:16,809 captures the genuine structure of the data without 723 00:34:16,809 --> 00:34:20,650 memorizing the noise. MDL is essentially the 724 00:34:20,650 --> 00:34:23,750 practical, computable incarnation of Kolmogorov 725 00:34:23,750 --> 00:34:26,769 complexity for modern statistics. I love that. 726 00:34:27,070 --> 00:34:30,260 It's Occam's razor with a calculator. But I want 727 00:34:30,260 --> 00:34:32,400 to inject a little skepticism here. Please do. 728 00:34:33,000 --> 00:34:35,920 It's tempting to think that if I run MDL on my 729 00:34:35,920 --> 00:34:39,179 data, it magically hands me the ultimate objective 730 00:34:39,179 --> 00:34:42,420 scientific truth of the universe. Like, MDL shows 731 00:34:42,420 --> 00:34:45,380 the quadratic curve, therefore gravity is a quadratic 732 00:34:45,380 --> 00:34:47,920 curve. That is a very common misconception. and 733 00:34:47,920 --> 00:34:51,639 we must explicitly correct it. MDL is absolutely 734 00:34:51,639 --> 00:34:53,840 not an oracle for objective scientific truth. 735 00:34:53,940 --> 00:34:56,239 It's not magic. Whether a straight line, a quadratic 736 00:34:56,239 --> 00:35:00,079 curve, or a polynomial model wins under the MDL 737 00:35:00,079 --> 00:35:02,679 principle depends entirely on the actual data 738 00:35:02,679 --> 00:35:05,380 provided, the precision of the parameters you 739 00:35:05,380 --> 00:35:08,420 allow, and crucially, the specific coding choices 740 00:35:08,420 --> 00:35:10,719 made by the human designing the system. Right, 741 00:35:10,719 --> 00:35:12,820 because how you encode the data changes the length. 742 00:35:13,300 --> 00:35:15,360 How you choose to encode the data changes the 743 00:35:15,360 --> 00:35:18,530 description length. MDL is a profoundly powerful 744 00:35:18,530 --> 00:35:21,130 heuristic for finding structure, but it is entirely 745 00:35:21,130 --> 00:35:23,610 bounded by the subjective framework you set up. 746 00:35:24,070 --> 00:35:26,829 That is a great perspective. We are moving from 747 00:35:26,829 --> 00:35:29,409 the abstract limits of logic into tools we can 748 00:35:29,409 --> 00:35:32,369 actually use. And speaking of tools, this transitions 749 00:35:32,369 --> 00:35:34,610 us into one of my absolutely favorite parts of 750 00:35:34,610 --> 00:35:36,710 this deep dive. The incompressibility method. 751 00:35:36,829 --> 00:35:39,530 Yes. We've seen how to use complexity to evaluate 752 00:35:39,530 --> 00:35:42,389 data and machine learning models, but Lee and 753 00:35:42,389 --> 00:35:44,690 Vitanya show us that we can also use it to prove 754 00:35:44,690 --> 00:35:48,639 deep abstract mathematical truths. Yes, through 755 00:35:48,639 --> 00:35:50,699 something called the incompressibility method. 756 00:35:51,320 --> 00:35:53,420 It is a mathematical proof technique that is 757 00:35:53,420 --> 00:35:56,760 as logically elegant as it is powerful. Since 758 00:35:56,760 --> 00:35:59,539 we know mathematically, via probability, that 759 00:35:59,539 --> 00:36:02,000 the vast majority of strings of any given length 760 00:36:02,000 --> 00:36:04,340 are fundamentally incompressible, meaning they 761 00:36:04,340 --> 00:36:06,679 are random with no hidden patterns to exploit, 762 00:36:07,440 --> 00:36:10,079 we can prove broad mathematical theorems by simply 763 00:36:10,079 --> 00:36:12,769 selecting one of these guaranteed incompressible 764 00:36:12,769 --> 00:36:16,030 strings, assuming it is our input and showing 765 00:36:16,030 --> 00:36:18,610 what must logically happen to it. Because if 766 00:36:18,610 --> 00:36:21,230 a mathematical property holds true for a random 767 00:36:21,230 --> 00:36:23,650 incompressible string, it usually represents 768 00:36:23,650 --> 00:36:26,070 the average or typical case for all strings. 769 00:36:27,090 --> 00:36:29,150 Let's look at a specific example the book highlights. 770 00:36:29,429 --> 00:36:31,610 One of them is about prime numbers developed 771 00:36:31,610 --> 00:36:34,670 by Gregory Chaitin. Yes, the distribution of 772 00:36:34,670 --> 00:36:37,769 prime numbers is a central historical topic in 773 00:36:37,769 --> 00:36:40,860 number theory. Mathematicians have spent centuries 774 00:36:40,860 --> 00:36:43,519 trying to pin down exactly how frequent prime 775 00:36:43,519 --> 00:36:46,940 numbers are. Chaitin used algorithmic complexity, 776 00:36:47,519 --> 00:36:50,320 specifically prefix codes and the existence of 777 00:36:50,320 --> 00:36:53,179 incompressible strings, to prove bounds on the 778 00:36:53,179 --> 00:36:56,099 distribution of primes. The logic is brilliant. 779 00:36:56,699 --> 00:36:59,440 Walk me through it. We know from basic math that 780 00:36:59,440 --> 00:37:02,659 any integer can be uniquely factored into a specific 781 00:37:02,659 --> 00:37:05,260 set of prime numbers. You can describe an integer 782 00:37:05,260 --> 00:37:08,179 entirely by listing the exponents of its prime 783 00:37:08,179 --> 00:37:11,320 factors. Right, so the number 12 is 2 squared 784 00:37:11,320 --> 00:37:15,659 times 3 to the first power. Exactly. Now, Chaitin 785 00:37:15,659 --> 00:37:19,079 says, let's take a massive, highly incompressible 786 00:37:19,079 --> 00:37:22,159 random integer. Because we know it is incompressible, 787 00:37:22,559 --> 00:37:25,320 its shortest description must be long. It must 788 00:37:25,320 --> 00:37:27,539 be close to the length of the number itself. 789 00:37:28,159 --> 00:37:31,960 Okay. Now, if we carefully encode the prime factorization 790 00:37:31,960 --> 00:37:34,440 of that massive number using prefix -free codes, 791 00:37:34,980 --> 00:37:38,159 we create a mathematical inequality. Because 792 00:37:38,159 --> 00:37:40,699 the length of the compressed prime factorization 793 00:37:40,699 --> 00:37:44,280 cannot be smaller than the true Kolmogorov complexity 794 00:37:44,280 --> 00:37:46,420 of the number. If it was, the number wouldn't 795 00:37:46,420 --> 00:37:50,320 be incompressible. Exactly. You have a vice grip 796 00:37:50,320 --> 00:37:53,579 of logic. When you run the algebra on that strict 797 00:37:53,579 --> 00:37:57,039 inequality, isolating the variables, it naturally, 798 00:37:57,360 --> 00:38:00,239 inescapably spits out the mathematical fact that 799 00:38:00,239 --> 00:38:03,480 the number of primes must grow at a certain minimum 800 00:38:03,480 --> 00:38:07,139 rate. That is so cool. It provides a completely 801 00:38:07,139 --> 00:38:09,920 distinct algorithmic proof of limits related 802 00:38:09,920 --> 00:38:12,599 to Hadamard and de la Valle -Poussin's famous 803 00:38:12,599 --> 00:38:15,719 prime number theorem, which traditionally required 804 00:38:15,719 --> 00:38:18,179 incredibly dense, complex analysis to prove. 805 00:38:18,380 --> 00:38:21,300 It's like using logic as a physical constraint. 806 00:38:21,840 --> 00:38:24,500 Like, this string literally cannot be squished. 807 00:38:24,679 --> 00:38:26,760 Therefore, the mathematical properties that make 808 00:38:26,760 --> 00:38:29,840 up its squished version must have certain physical 809 00:38:29,840 --> 00:38:32,340 limits. That's a great way to say it. The book 810 00:38:32,340 --> 00:38:34,780 also applies this to computer science, specifically 811 00:38:34,780 --> 00:38:38,460 the analysis of sorting algorithms. This is a 812 00:38:38,460 --> 00:38:41,000 highly practical application for software engineers. 813 00:38:41,880 --> 00:38:43,760 Computer scientists constantly want to know the 814 00:38:43,760 --> 00:38:46,659 average case runtime of sorting algorithms like 815 00:38:46,659 --> 00:38:49,619 heap sort or shell sort. Right. Traditionally, 816 00:38:50,079 --> 00:38:52,079 to find the average case, you have to do massive 817 00:38:52,079 --> 00:38:55,800 agonizing probabilistic calculations over every 818 00:38:55,800 --> 00:38:58,219 single possible permutation of an array of numbers. 819 00:38:58,559 --> 00:39:01,579 Which sounds like an absolute nightmare of factorials 820 00:39:01,579 --> 00:39:04,119 and expected value equations. It is a nightmare. 821 00:39:04,420 --> 00:39:06,820 But with the incompressibility method, you completely 822 00:39:06,820 --> 00:39:09,840 bypass the probability. You simply assume your 823 00:39:09,840 --> 00:39:12,599 input array is an incompressible sequence. Okay. 824 00:39:12,880 --> 00:39:15,059 You then track how the sorting algorithm handles 825 00:39:15,059 --> 00:39:18,500 this specific patternless input. Because the 826 00:39:18,500 --> 00:39:20,599 algorithm has absolutely no patterns to exploit 827 00:39:20,599 --> 00:39:23,320 to make the sorting faster, the number of operations 828 00:39:23,320 --> 00:39:25,840 it takes on the incompressible string represents 829 00:39:25,840 --> 00:39:29,230 a rock -solid bound on the average case. Why? 830 00:39:29,929 --> 00:39:32,329 Because the overwhelming majority of all possible 831 00:39:32,329 --> 00:39:35,309 input arrays are incompressible. It's such a 832 00:39:35,309 --> 00:39:38,380 beautiful shortcut. We must clarify that these 833 00:39:38,380 --> 00:39:41,039 proofs rely purely on the mathematical existence 834 00:39:41,039 --> 00:39:43,900 and the counting of these incompressible strings. 835 00:39:44,940 --> 00:39:47,739 You never actually have to compute the uncomputable 836 00:39:47,739 --> 00:39:50,039 shortest program to make the proof work. You 837 00:39:50,039 --> 00:39:52,320 never have to isolate the string in a computer 838 00:39:52,320 --> 00:39:55,219 memory. You just invoke the theorem that such 839 00:39:55,219 --> 00:39:57,940 strings logically must exist and the algebraic 840 00:39:57,940 --> 00:39:59,800 constraints naturally follow. You don't need 841 00:39:59,800 --> 00:40:01,280 to hold the thing in your hand to know its weight. 842 00:40:01,440 --> 00:40:05,139 I love it. OK, so. Moving deeper, in all these 843 00:40:05,139 --> 00:40:07,639 proofs, we basically assumed that the universal 844 00:40:07,639 --> 00:40:10,039 Turing machine had until the end of time to run. 845 00:40:10,260 --> 00:40:12,139 We did. We didn't care if the shortest program 846 00:40:12,139 --> 00:40:14,599 took a billion years of processing power to decompress 847 00:40:14,599 --> 00:40:17,719 into our target string. But in the real physical 848 00:40:17,719 --> 00:40:21,579 world, time and memory are strictly limited resources. 849 00:40:21,780 --> 00:40:23,980 Very limited. A zip file is completely useless 850 00:40:23,980 --> 00:40:26,900 to me if it takes 10 ,000 years to open. Does 851 00:40:26,900 --> 00:40:28,940 the math break down if we introduce a ticking 852 00:40:28,940 --> 00:40:31,800 clock? It doesn't break down, but the landscape 853 00:40:31,800 --> 00:40:34,530 changes completely. This introduces the concept 854 00:40:34,530 --> 00:40:37,349 of resource -bounded complexity, which is mathematically 855 00:40:37,349 --> 00:40:42,469 denoted as C superscript T comma S of X. Okay. 856 00:40:42,909 --> 00:40:45,429 The T stands for a strict time limit, and the 857 00:40:45,429 --> 00:40:48,909 S stands for a space or memory limit. We are 858 00:40:48,909 --> 00:40:50,949 no longer asking for just the absolute shortest 859 00:40:50,949 --> 00:40:53,550 program. We are now asking for the length of 860 00:40:53,550 --> 00:40:55,909 the shortest program that produces the string 861 00:40:55,909 --> 00:40:58,530 and finishes the computation within a specific 862 00:40:58,530 --> 00:41:01,809 time and space budget. And this constraint forces 863 00:41:01,809 --> 00:41:05,000 compromises. Here's where it gets really interesting. 864 00:41:05,719 --> 00:41:08,659 The text defines a specific concept called logical 865 00:41:08,659 --> 00:41:11,059 depth, introduced by the physicist Charles Bennett. 866 00:41:11,579 --> 00:41:13,900 When I read this, it felt like a profound shift 867 00:41:13,900 --> 00:41:16,159 in how we think about the value of information. 868 00:41:16,539 --> 00:41:19,420 It is a paradigm shift. Logical depth is a measure 869 00:41:19,420 --> 00:41:22,280 of the significance or the evolutionary history 870 00:41:22,280 --> 00:41:25,119 required to produce a string of data. So it's 871 00:41:25,119 --> 00:41:28,300 not just bits. So wait, is depth just a fancy 872 00:41:28,300 --> 00:41:31,110 word for how long a program takes to run? We 873 00:41:31,110 --> 00:41:33,349 must be very precise here, because it is more 874 00:41:33,349 --> 00:41:36,130 nuanced than just a stopwatch. Let's look at 875 00:41:36,130 --> 00:41:38,489 three distinct examples to separate complexity 876 00:41:38,489 --> 00:41:42,369 from depth. OK, let's do it. First, imagine a 877 00:41:42,369 --> 00:41:44,889 string of a million zeros. Its shortest program 878 00:41:44,889 --> 00:41:48,070 is tiny. Print zero a million times, and it runs 879 00:41:48,070 --> 00:41:50,869 incredibly fast. It is algorithmically simple, 880 00:41:50,869 --> 00:41:54,289 and it is logically shallow. Easy to compress, 881 00:41:54,449 --> 00:41:56,889 easy to decompress. Exactly. Nothing interesting 882 00:41:56,889 --> 00:42:00,360 happening. Exactly. Second, Consider a completely 883 00:42:00,360 --> 00:42:02,679 random, mathematically incompressible string 884 00:42:02,679 --> 00:42:05,599 of a million bits. Its shortest program is a 885 00:42:05,599 --> 00:42:07,820 million bits long. It's basically just the literal 886 00:42:07,820 --> 00:42:09,920 string itself packaged with a print command. 887 00:42:10,420 --> 00:42:13,280 Right. But think about how it runs. It also runs 888 00:42:13,280 --> 00:42:15,780 incredibly fast. It just dumps itself onto the 889 00:42:15,780 --> 00:42:18,880 screen. Therefore, a completely random, highly 890 00:42:18,880 --> 00:42:21,440 complex string is actually incredibly shallow. 891 00:42:21,739 --> 00:42:24,460 There's no hidden structure taking time to unpack. 892 00:42:24,940 --> 00:42:28,619 Wait, random static is shallow? That feels... 893 00:42:28,380 --> 00:42:30,440 Completely counterintuitive at first glance. 894 00:42:30,800 --> 00:42:32,960 It is shallow because there is no computational 895 00:42:32,960 --> 00:42:35,619 history required to make it. It is just raw, 896 00:42:36,059 --> 00:42:39,699 unprocessed noise. Ah, I see. But now consider 897 00:42:39,699 --> 00:42:42,500 a third example. The genome inside a biological 898 00:42:42,500 --> 00:42:46,500 cell is another phenomenal example. The raw information 899 00:42:46,500 --> 00:42:49,320 in a strand of DNA might be somewhat compressible, 900 00:42:49,599 --> 00:42:52,420 but the specific functional structure it represents 901 00:42:52,420 --> 00:42:55,400 took billions of years of evolutionary computation 902 00:42:55,400 --> 00:42:58,449 by nature to arrive at. Now, speaking of the 903 00:42:58,449 --> 00:43:00,889 physical limits of computation in biology, section 904 00:43:00,889 --> 00:43:04,030 8 of the book takes chlamograph complexity entirely 905 00:43:04,030 --> 00:43:06,610 out of the abstract realm of mathematics and 906 00:43:06,610 --> 00:43:08,909 applies it directly to the physical universe. 907 00:43:09,289 --> 00:43:12,010 Physics, biology, thermodynamics. This is where 908 00:43:12,010 --> 00:43:14,030 algorithmic information theory meets physical 909 00:43:14,030 --> 00:43:17,070 reality. The book discusses the thermodynamics 910 00:43:17,070 --> 00:43:19,869 of computation. Yes, this part was wild. For 911 00:43:19,869 --> 00:43:22,289 a very long time, physicists wondered if the 912 00:43:22,289 --> 00:43:25,409 abstract act of computing fundamentally required 913 00:43:25,409 --> 00:43:28,400 energy. Rolf Landauer proved something remarkable 914 00:43:28,400 --> 00:43:31,539 known as Landauer's Principle. Landauer's Principle. 915 00:43:31,920 --> 00:43:34,400 He demonstrated that doing a basic logical operation, 916 00:43:34,599 --> 00:43:36,480 like adding two numbers or moving data around, 917 00:43:37,059 --> 00:43:39,440 doesn't necessarily dissipate heat into the environment. 918 00:43:40,400 --> 00:43:43,019 But erasing a bit of information fundamentally, 919 00:43:43,280 --> 00:43:46,380 inevitably dissipates heat. Wait, why? Why does 920 00:43:46,380 --> 00:43:48,380 deleting a file create physical heat in the real 921 00:43:48,380 --> 00:43:50,840 world? It comes down to the laws of thermodynamics, 922 00:43:51,460 --> 00:43:54,090 specifically entropy. When you erase a bit of 923 00:43:54,090 --> 00:43:56,570 data in a computer, you are taking a physical 924 00:43:56,570 --> 00:43:59,130 system that could be in one of two possible states, 925 00:43:59,230 --> 00:44:02,130 a zero or a one, and you are forcibly resetting 926 00:44:02,130 --> 00:44:05,769 it into a single known state, usually zero. Okay. 927 00:44:06,150 --> 00:44:08,869 By doing that, you have physically reduced the 928 00:44:08,869 --> 00:44:12,070 entropy, the disorder, of the computer's memory. 929 00:44:12,889 --> 00:44:16,010 So that lost entropy in the memory must be expelled 930 00:44:16,010 --> 00:44:19,190 out into the environment as physical heat. Information 931 00:44:19,190 --> 00:44:23,179 is physical. That is mind -blowing. So if erasing 932 00:44:23,179 --> 00:44:26,039 data is what specifically causes heat, could 933 00:44:26,039 --> 00:44:28,159 we theoretically build a computer that never 934 00:44:28,159 --> 00:44:31,239 erases any data? Theoretically, yes. This is 935 00:44:31,239 --> 00:44:34,360 the concept of reversible computing. Reversible 936 00:44:34,360 --> 00:44:36,820 computing. If you build a computer entirely out 937 00:44:36,820 --> 00:44:39,500 of reversible logic gates, where you can always 938 00:44:39,500 --> 00:44:42,300 run the computation completely backwards to deduce 939 00:44:42,300 --> 00:44:44,880 the exact input from the output, you never actually 940 00:44:44,880 --> 00:44:48,150 lose or erase any information. Charles Bennett 941 00:44:48,150 --> 00:44:50,329 mathematically showed that you can simulate any 942 00:44:50,329 --> 00:44:52,889 standard touring machine with a reversible touring 943 00:44:52,889 --> 00:44:55,449 machine. Okay, I have to stop you. I'm gonna 944 00:44:55,449 --> 00:44:57,789 drop out of podcasting, go to Silicon Valley, 945 00:44:57,869 --> 00:45:00,190 and invent a zero heat laptop based on reversible 946 00:45:00,190 --> 00:45:02,409 computing. I'll never need a cooling fan again. 947 00:45:02,690 --> 00:45:04,929 I would strongly advise against quitting your 948 00:45:04,929 --> 00:45:07,590 day job just yet. We have to ground this in reality. 949 00:45:07,690 --> 00:45:11,250 Let me dream. Reversible computing dictates the 950 00:45:11,250 --> 00:45:14,269 fundamental theoretical thermodynamic floor of 951 00:45:14,269 --> 00:45:17,940 logic. It is an idealized limit. It does not 952 00:45:17,940 --> 00:45:20,980 mean your reversible laptop will literally generate 953 00:45:20,980 --> 00:45:25,139 zero heat. Why not? In the physical world, friction 954 00:45:25,139 --> 00:45:29,059 exists, electrical resistance in the wires exists, 955 00:45:29,360 --> 00:45:32,219 quantum fluctuations exist. Landauer's limit 956 00:45:32,219 --> 00:45:34,980 is the absolute theoretical minimum of the logic 957 00:45:34,980 --> 00:45:38,519 itself, not the engineering reality of a physical 958 00:45:38,519 --> 00:45:41,199 silicon ship running on a desk. You will still 959 00:45:41,199 --> 00:45:43,679 need a cooling fan. Fair enough. I'll keep the 960 00:45:43,679 --> 00:45:48,659 day job. Still, it is astonishing that abstract 961 00:45:48,659 --> 00:45:50,880 information theory dictates physical heat limits. 962 00:45:51,519 --> 00:45:53,739 But physics isn't the only real -world application. 963 00:45:54,079 --> 00:45:56,460 The book moves into a concept that I found completely 964 00:45:56,460 --> 00:45:59,260 fascinating. Measuring the absolute distance 965 00:45:59,260 --> 00:46:02,519 between two objects. Like how similar are two 966 00:46:02,519 --> 00:46:05,179 genomes or two pieces of music? To answer this 967 00:46:05,179 --> 00:46:07,519 mathematically, the authors introduce a concept 968 00:46:07,519 --> 00:46:10,739 called information distance. How do we objectively 969 00:46:10,739 --> 00:46:13,199 measure the absolute distance between object 970 00:46:13,199 --> 00:46:17,150 A and object B? How do they do it? Mathematically, 971 00:46:17,650 --> 00:46:19,989 it is defined as the length of the absolute shortest 972 00:46:19,989 --> 00:46:23,289 program that can translate object A into object 973 00:46:23,289 --> 00:46:26,869 B, and simultaneously translate object B back 974 00:46:26,869 --> 00:46:29,349 into object A. So if A and B are very similar, 975 00:46:29,469 --> 00:46:31,349 like two slightly different versions of the same 976 00:46:31,349 --> 00:46:33,869 essay, the program to translate between them 977 00:46:33,869 --> 00:46:36,230 is very short. It just says, change this one 978 00:46:36,230 --> 00:46:38,570 word. Right. If they are completely different, 979 00:46:38,750 --> 00:46:41,190 the translation program is massive. But we have 980 00:46:41,190 --> 00:46:44,059 a major problem here. As we learned exhaustively 981 00:46:44,059 --> 00:46:46,780 in section two, finding the shortest program, 982 00:46:47,000 --> 00:46:49,940 comagore of complexity, is fundamentally uncomputable. 983 00:46:50,000 --> 00:46:53,000 We can't find it. Which is exactly why the authors 984 00:46:53,000 --> 00:46:55,780 created a brilliant computable approximation, 985 00:46:56,780 --> 00:46:59,699 the normalized compression distance, or NCD. 986 00:46:59,840 --> 00:47:03,079 NCD. Since we can't find the true uncomputable 987 00:47:03,079 --> 00:47:05,480 algorithmic distance, we approximate it using 988 00:47:05,480 --> 00:47:09,019 the best tools we have, real world file compressors. 989 00:47:09,360 --> 00:47:11,820 Wait, are you telling me I can literally just 990 00:47:11,820 --> 00:47:14,659 use an everyday zip program on my computer to 991 00:47:14,659 --> 00:47:16,539 reconstruct the evolutionary tree of mammals 992 00:47:16,539 --> 00:47:20,250 by just zipping their DNA files together? Conceptually, 993 00:47:20,309 --> 00:47:23,039 yes. If we connect this to the bigger picture, 994 00:47:23,360 --> 00:47:27,679 that is exactly what the NCD does. NCD uses standard 995 00:47:27,679 --> 00:47:31,400 off -the -shelf compressors like gzip or bzip2 996 00:47:31,400 --> 00:47:34,260 to find the mathematical distance between file 997 00:47:34,260 --> 00:47:38,199 A and file B. You compress file A. You compress 998 00:47:38,199 --> 00:47:41,920 file B. Then you paste file A and file B together 999 00:47:41,920 --> 00:47:44,940 into one combined file, and you compress that 1000 00:47:44,940 --> 00:47:47,440 combined file. And I see the mechanics of this. 1001 00:47:47,760 --> 00:47:50,719 If file A and file B are very similar, the zip 1002 00:47:50,719 --> 00:47:52,739 program's algorithm will see all the repeated 1003 00:47:52,739 --> 00:47:55,119 patterns across both files, and it will compress 1004 00:47:55,119 --> 00:47:57,739 the combined file really well. It will be much 1005 00:47:57,739 --> 00:47:59,760 smaller than the two separate files. Exactly. 1006 00:48:00,000 --> 00:48:01,619 But if they are completely different, like a 1007 00:48:01,619 --> 00:48:03,719 Shakespeare play and a random image, the combined 1008 00:48:03,719 --> 00:48:05,719 compressed file will just be the size of the 1009 00:48:05,719 --> 00:48:07,880 two individual compressed files added together 1010 00:48:07,880 --> 00:48:09,739 because there are no shared patterns to exploit. 1011 00:48:09,980 --> 00:48:13,059 Exactly. You take those three file sizes, you 1012 00:48:13,059 --> 00:48:15,820 run them through the NCD algebraic formula. The 1013 00:48:15,820 --> 00:48:17,480 authors of the book, along with other researchers, 1014 00:48:17,619 --> 00:48:20,539 have used this exact method to successfully cluster 1015 00:48:20,539 --> 00:48:23,440 different genres of music to group human languages 1016 00:48:23,440 --> 00:48:26,179 by their linguistic roots. That is genuinely 1017 00:48:26,179 --> 00:48:28,579 incredible. It feels like a magic trick, but... 1018 00:48:28,559 --> 00:48:30,980 Let me put my skeptic hat back on for a second. 1019 00:48:31,539 --> 00:48:33,900 If WinZip can build an evolutionary tree, our 1020 00:48:33,900 --> 00:48:36,599 evolutionary biologists out of a job, this can't 1021 00:48:36,599 --> 00:48:39,940 be a 100 % flawless metric. It is absolutely 1022 00:48:39,940 --> 00:48:43,260 not flawless, and biologists are safe. NCD is 1023 00:48:43,260 --> 00:48:46,199 a heuristic. It relies entirely on the specific 1024 00:48:46,199 --> 00:48:49,599 algorithms, like Limpel -Ziv, of the zip program 1025 00:48:49,599 --> 00:48:53,320 used. Right. It does not calculate exact Kolmogorov 1026 00:48:53,320 --> 00:48:55,820 complexity, and therefore It doesn't guarantee 1027 00:48:55,820 --> 00:48:59,119 a perfectly correct biological tree or a flawless 1028 00:48:59,119 --> 00:49:02,780 music clustering. It misses deep logical structures 1029 00:49:02,780 --> 00:49:05,679 that simple zip algorithms can't see. Because 1030 00:49:05,679 --> 00:49:08,260 it's just an approximation. It is a profoundly 1031 00:49:08,260 --> 00:49:11,000 useful approximation, but it is firmly bounded 1032 00:49:11,000 --> 00:49:13,659 by the mathematical limits of the specific compression 1033 00:49:13,659 --> 00:49:17,000 software you happen to be using. What an unbelievable 1034 00:49:17,000 --> 00:49:19,099 journey this has been. Let's do a quick recap 1035 00:49:19,099 --> 00:49:21,420 to anchor all of this. We started with plane 1036 00:49:21,420 --> 00:49:24,929 complexity, the theoretical absolute shortest 1037 00:49:24,929 --> 00:49:28,449 program to describe an object. Right. We adapted 1038 00:49:28,449 --> 00:49:30,969 by introducing prefix -free codes to build a 1039 00:49:30,969 --> 00:49:33,710 bridge to probability, which led us to Solomonoff's 1040 00:49:33,710 --> 00:49:36,650 universal prior and the highly practical minimum 1041 00:49:36,650 --> 00:49:39,510 description length principle. And the incompressibility 1042 00:49:39,510 --> 00:49:43,289 method. Yes, where we saw how assuming an incompressible 1043 00:49:43,289 --> 00:49:45,869 string can mathematically prove deep theorems 1044 00:49:45,869 --> 00:49:49,070 without calculating probabilities. We added real 1045 00:49:49,070 --> 00:49:51,269 -world time and space limits to explore the beautiful 1046 00:49:51,269 --> 00:49:54,980 concept of logical depths. It is a truly remarkable 1047 00:49:54,980 --> 00:49:57,480 progression. To watch a field grow from abstract 1048 00:49:57,480 --> 00:49:59,980 theoretical limits of touring machines all the 1049 00:49:59,980 --> 00:50:02,920 way to concrete physical applications of biology 1050 00:50:02,920 --> 00:50:05,820 and thermodynamics is a testament to the power 1051 00:50:05,820 --> 00:50:07,579 of mathematics. It really is.