1
00:00:00,000 --> 00:00:01,840
I want to start off by asking you a deceptively

2
00:00:01,840 --> 00:00:04,980
simple question. What actually is a computer?

3
00:00:05,459 --> 00:00:07,480
That is a big question to just throw out there

4
00:00:07,480 --> 00:00:10,080
right at the start. Right, but I mean... Before

5
00:00:10,080 --> 00:00:12,679
you picture the smartphone in your pocket or,

6
00:00:12,699 --> 00:00:14,800
you know, the laptop sitting on your desk or

7
00:00:14,800 --> 00:00:17,179
even those massive server farms out in the desert

8
00:00:17,179 --> 00:00:19,579
that powered the Internet. I want you to completely

9
00:00:19,579 --> 00:00:22,460
erase all of that from your mind. Oh, wow. OK,

10
00:00:22,539 --> 00:00:26,140
so no hardware at all. Exactly. No hardware today.

11
00:00:26,219 --> 00:00:30,000
No silicon, no microchips, no touchscreens, no

12
00:00:30,000 --> 00:00:33,060
batteries. Imagine a universe where electricity

13
00:00:33,060 --> 00:00:35,600
was never even discovered. Right. Could computation

14
00:00:35,600 --> 00:00:38,700
still exist? Because today we are talking about

15
00:00:38,700 --> 00:00:41,719
the pure mathematical essence of computation

16
00:00:41,719 --> 00:00:44,520
itself. We're looking at a concept that predates

17
00:00:44,520 --> 00:00:48,619
modern electronics by like decades. Yeah. It's

18
00:00:48,619 --> 00:00:51,159
the unadulterated logic of what it actually means

19
00:00:51,159 --> 00:00:54,020
to solve a problem. It's a really profound shift

20
00:00:54,020 --> 00:00:55,840
in perspective. And honestly, it's a shift that

21
00:00:55,840 --> 00:00:58,100
most people who use computers every single day,

22
00:00:58,179 --> 00:01:00,759
they never make it. Because when you strip away

23
00:01:00,759 --> 00:01:03,240
all the engineering, the electricity, the cooling

24
00:01:03,240 --> 00:01:06,319
fans, the physical components, you are left with

25
00:01:06,319 --> 00:01:09,680
nothing. You're left with pure mathematics. Just

26
00:01:09,680 --> 00:01:12,260
the math. Just the math. You are left with abstract

27
00:01:12,260 --> 00:01:16,099
theoretical machines. And what is so deeply fascinating

28
00:01:16,099 --> 00:01:18,799
about this is that by studying these imaginary,

29
00:01:19,079 --> 00:01:22,459
perfectly abstract machines, we can actually

30
00:01:22,459 --> 00:01:26,480
discover the absolute. unbreakable laws of logic.

31
00:01:26,719 --> 00:01:29,099
Yeah. And we find boundaries that apply to literally

32
00:01:29,099 --> 00:01:31,640
any computer that could ever possibly exist in

33
00:01:31,640 --> 00:01:34,219
our universe. Right. No matter how advanced the

34
00:01:34,219 --> 00:01:36,400
technology becomes, like even if you build a

35
00:01:36,400 --> 00:01:39,120
computer out of light or quantum fields or biological

36
00:01:39,120 --> 00:01:41,760
neurons, it cannot break the laws we're going

37
00:01:41,760 --> 00:01:43,780
to talk about today. That is the perfect setup.

38
00:01:43,900 --> 00:01:46,200
Our goal for this deep dive is to essentially

39
00:01:46,200 --> 00:01:48,920
map the entire theoretical DNA of computation.

40
00:01:49,400 --> 00:01:51,099
We're going to use the foundational concepts

41
00:01:51,099 --> 00:01:53,500
laid out in Michael Sipster's legendary text.

42
00:01:53,959 --> 00:01:57,000
to the theory of computation as our guide. Which

43
00:01:57,000 --> 00:01:59,120
is pretty much the Bible for this stuff. It really

44
00:01:59,120 --> 00:02:01,239
is. But we aren't just going to read definitions

45
00:02:01,239 --> 00:02:03,500
at you. We want to understand the why and the

46
00:02:03,500 --> 00:02:06,120
how behind the digital world. So we're going

47
00:02:06,120 --> 00:02:08,900
to start with the absolute simplest imaginable

48
00:02:08,900 --> 00:02:11,659
machines and then give them slightly more power

49
00:02:11,659 --> 00:02:14,539
step by step. Right. And just watch how reality

50
00:02:14,539 --> 00:02:18,039
warps as we approach the absolute limits of what

51
00:02:18,039 --> 00:02:20,879
can be known and... Well, what can be solved

52
00:02:20,879 --> 00:02:23,180
in the finite time we have in this universe.

53
00:02:23,300 --> 00:02:25,460
Exactly. And the blueprint for this is going

54
00:02:25,460 --> 00:02:28,680
to be three parts. First, automata, which are

55
00:02:28,680 --> 00:02:31,259
the simple mathematical models of machines. Then

56
00:02:31,259 --> 00:02:34,439
computability, which is the absolute limits of

57
00:02:34,439 --> 00:02:37,460
what those machines can solve. And finally, complexity.

58
00:02:38,169 --> 00:02:40,009
Right, which is what those machines can solve

59
00:02:40,009 --> 00:02:42,370
practically when they're constrained by time

60
00:02:42,370 --> 00:02:44,550
and memory. So I think the best place to start

61
00:02:44,550 --> 00:02:46,330
that journey is at the very bottom. Let's do

62
00:02:46,330 --> 00:02:48,229
it. Before we can talk about artificial intelligence

63
00:02:48,229 --> 00:02:50,849
or global networks, we have to define what a

64
00:02:50,849 --> 00:02:53,469
machine is in the language of mathematics. We

65
00:02:53,469 --> 00:02:55,389
have to build a theoretical model that takes

66
00:02:55,389 --> 00:02:58,310
an input, processes it, and gives an output.

67
00:02:58,629 --> 00:03:01,270
Right. And if we strip a machine down to its

68
00:03:01,270 --> 00:03:04,229
most basic fundamental parts, we get something

69
00:03:04,229 --> 00:03:07,860
called a deterministic finite automaton. A DFA.

70
00:03:08,020 --> 00:03:11,139
Yes. Now, the math books define this with a bunch

71
00:03:11,139 --> 00:03:13,460
of formal notation sets of states, transition

72
00:03:13,460 --> 00:03:16,620
functions, alphabets. But I want to anchor this

73
00:03:16,620 --> 00:03:18,520
in the real world. I want to make this something

74
00:03:18,520 --> 00:03:21,039
you can actually touch. I think that's essential.

75
00:03:21,199 --> 00:03:24,439
The mathematical definition is it's rigorous

76
00:03:24,439 --> 00:03:27,099
so that we can write proofs about it. The intuition

77
00:03:27,099 --> 00:03:30,659
is quite physical. Yeah. At its core, a DFA is

78
00:03:30,659 --> 00:03:33,460
simply a system that can be in one of a limited

79
00:03:33,460 --> 00:03:36,759
number of specific conditions or states. It reads

80
00:03:36,759 --> 00:03:39,259
an input, maybe a string of characters like zeros

81
00:03:39,259 --> 00:03:41,560
and ones, and it does it one symbol at a time.

82
00:03:41,659 --> 00:03:44,120
And every time it reads a symbol, it consults

83
00:03:44,120 --> 00:03:46,659
a perfectly strict set of rules to decide which

84
00:03:46,659 --> 00:03:49,719
state to jump to next. It is deterministic because

85
00:03:49,719 --> 00:03:52,479
there is zero guesswork. If it's in state A and

86
00:03:52,479 --> 00:03:55,280
it reads a one, the rule book might say it absolutely

87
00:03:55,280 --> 00:03:58,479
must go to state B. So my go -to analogy for

88
00:03:58,479 --> 00:04:00,740
a DFA has always been an old school mechanical

89
00:04:00,740 --> 00:04:03,020
turnstile. Well, that's a classic one. Right.

90
00:04:03,360 --> 00:04:06,099
The kind you see at a subway station, let's really

91
00:04:06,099 --> 00:04:08,620
look at how that turnstile works. It essentially

92
00:04:08,620 --> 00:04:12,039
has two states, locked and unlocked. Makes sense.

93
00:04:12,259 --> 00:04:15,719
And its alphabet, the inputs it accepts are physical

94
00:04:15,719 --> 00:04:19,399
objects. So a token or a physical push against

95
00:04:19,399 --> 00:04:21,339
the bar. Let's trace the logic on that. Okay,

96
00:04:21,379 --> 00:04:24,180
so the start state is locked. If you push on

97
00:04:24,180 --> 00:04:26,639
the bar while it's in the locked state, the transition

98
00:04:26,639 --> 00:04:29,600
rule says stay locked. Nothing happens. Exactly,

99
00:04:29,720 --> 00:04:31,899
nothing happens. But if you drop a token into

100
00:04:31,899 --> 00:04:34,829
the slot. The token is your new input. The rulebook

101
00:04:34,829 --> 00:04:38,910
says if in locked state an input is token, transition

102
00:04:38,910 --> 00:04:41,689
to unlocked state. Right. Now the machine is

103
00:04:41,689 --> 00:04:44,300
in a new state. If you then push the bar, the

104
00:04:44,300 --> 00:04:46,800
rulebook says, if an unlocked state and input

105
00:04:46,800 --> 00:04:49,420
is pushed, allow the rotation and transition

106
00:04:49,420 --> 00:04:52,339
back to locked. That is a perfect, complete mechanical

107
00:04:52,339 --> 00:04:55,579
representation of a finite automaton. And you'll

108
00:04:55,579 --> 00:04:58,439
notice a massive glaring limitation in the turnstile's

109
00:04:58,439 --> 00:05:00,459
design. Oh, absolutely. It has zero memory of

110
00:05:00,459 --> 00:05:02,180
its past history, other than the fact that it

111
00:05:02,180 --> 00:05:05,019
is in its current state. Exactly. The turnstile

112
00:05:05,019 --> 00:05:07,500
doesn't remember if a thousand people just walked

113
00:05:07,500 --> 00:05:10,339
through or if the station just opened. Right.

114
00:05:10,800 --> 00:05:12,459
If it is in the unlocked state, it doesn't know

115
00:05:12,459 --> 00:05:14,620
if you put in the token three seconds ago or

116
00:05:14,620 --> 00:05:16,699
if someone put a token in yesterday and just

117
00:05:16,699 --> 00:05:19,639
walked away. It only knows the now. And because

118
00:05:19,639 --> 00:05:23,120
of that extreme limitation, DFAs... can only

119
00:05:23,120 --> 00:05:26,480
recognize a very specific, very simple class

120
00:05:26,480 --> 00:05:28,779
of patterns. Which we call regular languages.

121
00:05:29,040 --> 00:05:33,579
Exactly. A DFA is fantastic at, say, scanning

122
00:05:33,579 --> 00:05:36,000
a long document and finding every instance of

123
00:05:36,000 --> 00:05:38,759
a specific word or validating that an email address

124
00:05:38,759 --> 00:05:41,339
has an ad symbol and a dot com at the end. Right.

125
00:05:41,399 --> 00:05:43,019
It just moves from state to state as it reads

126
00:05:43,019 --> 00:05:46,500
the letters. Yeah. But almost immediately, when

127
00:05:46,500 --> 00:05:48,740
computer scientists were mapping this out, they

128
00:05:48,740 --> 00:05:50,939
introduced a concept that feels like it completely

129
00:05:50,939 --> 00:05:53,930
breaks the rules. Non -determinism. We call this

130
00:05:53,930 --> 00:05:57,129
the non -deterministic finite automaton or NFA.

131
00:05:57,230 --> 00:05:59,470
I remember when I first encountered the concept

132
00:05:59,470 --> 00:06:01,370
of an NFA, it felt like someone was sneaking

133
00:06:01,370 --> 00:06:03,589
magic into the math. It really does. Because

134
00:06:03,589 --> 00:06:05,529
in a standard deterministic machine, there is

135
00:06:05,529 --> 00:06:08,029
exactly one path forward. You read a one, you

136
00:06:08,029 --> 00:06:12,069
go to state B. End of story. But an NFA doesn't

137
00:06:12,069 --> 00:06:14,610
play by those rules. It can have multiple conflicting

138
00:06:14,610 --> 00:06:17,490
rules for the same input. It can be in state

139
00:06:17,490 --> 00:06:20,860
A, read a one, and the rule book says. You can

140
00:06:20,860 --> 00:06:23,319
go to state B or R. You can go to state C. It

141
00:06:23,319 --> 00:06:25,319
can even transition between states without reading

142
00:06:25,319 --> 00:06:27,860
any input at all. Yeah. It just spontaneously

143
00:06:27,860 --> 00:06:30,399
jumps from one condition to another. Right. So

144
00:06:30,399 --> 00:06:33,240
effectively, the machine has a choice to make.

145
00:06:33,420 --> 00:06:36,220
Yeah. But machines don't have free will. So how

146
00:06:36,220 --> 00:06:38,540
does it choose? Well, the way it's often explained

147
00:06:38,540 --> 00:06:41,279
is that the machine branches into parallel realities.

148
00:06:41,439 --> 00:06:43,920
It just splits. Okay. In one universe, it went

149
00:06:43,920 --> 00:06:46,420
to state B. In another universe, it went to state

150
00:06:46,420 --> 00:06:49,279
C. It investigates both paths simultaneously.

151
00:06:50,250 --> 00:06:53,069
And as long as just one of those parallel universes

152
00:06:53,069 --> 00:06:56,029
eventually reaches and accepts state, the machine

153
00:06:56,029 --> 00:06:58,629
as a whole accepts the input. That parallel universe

154
00:06:58,629 --> 00:07:01,430
visualization is incredibly helpful for human

155
00:07:01,430 --> 00:07:04,189
comprehension, but it also creates a massive

156
00:07:04,189 --> 00:07:07,430
intuitive trap. Oh, a huge one. Almost everyone

157
00:07:07,430 --> 00:07:09,829
who hears that description assumes that an NFA

158
00:07:09,829 --> 00:07:12,879
must be vastly more powerful than a DFA. I definitely

159
00:07:12,879 --> 00:07:14,600
fell into that trap. I mean, it seems obvious.

160
00:07:14,779 --> 00:07:17,740
If I have a machine that can only try one path

161
00:07:17,740 --> 00:07:20,259
at a time, like a mouse in a maze hitting dead

162
00:07:20,259 --> 00:07:23,379
ends, versus a magical liquid machine that floods

163
00:07:23,379 --> 00:07:26,139
the entire maze and explores every path instantly,

164
00:07:26,540 --> 00:07:29,319
surely the magical parallel machine can solve

165
00:07:29,319 --> 00:07:31,540
harder problems, right? It seems like it absolutely

166
00:07:31,540 --> 00:07:34,600
should. But here is where we hit our first truly

167
00:07:34,600 --> 00:07:36,699
counterintuitive mathematical truth of the deep

168
00:07:36,699 --> 00:07:39,300
dive. Okay. There is a rigorous mathematical

169
00:07:39,300 --> 00:07:44,560
proof. that NFAs and DFAs are perfectly equivalent

170
00:07:44,560 --> 00:07:46,740
in their computational power. That still blows

171
00:07:46,740 --> 00:07:49,100
my mind. The magical parallel universe machine

172
00:07:49,100 --> 00:07:52,199
is exactly as capable as the dumb mechanical

173
00:07:52,199 --> 00:07:55,199
turnstile. How is that even possible? To understand

174
00:07:55,199 --> 00:07:57,060
the how, you have to look at the conversion process.

175
00:07:57,420 --> 00:07:59,720
The proof actually gives you an algorithm to

176
00:07:59,720 --> 00:08:02,660
take any NFA and rebuild it as a DFA. Really?

177
00:08:02,779 --> 00:08:04,959
Yeah. Think about the parallel universes. If

178
00:08:04,959 --> 00:08:07,839
your NFA has, say, three states, A, B, and C,

179
00:08:07,879 --> 00:08:10,160
and it splits, maybe at a certain point in time

180
00:08:10,160 --> 00:08:12,459
it exists in both state A and state B simultaneously.

181
00:08:12,560 --> 00:08:14,899
Okay, I'm with you. Well, what if we build a

182
00:08:14,899 --> 00:08:17,779
new deterministic machine where the states themselves

183
00:08:17,779 --> 00:08:20,560
represent combinations of the old states? Wait,

184
00:08:20,579 --> 00:08:22,959
what do you mean? We create a single new state,

185
00:08:23,100 --> 00:08:26,500
and we label it state AB. This new state simply

186
00:08:26,500 --> 00:08:29,500
means the condition of currently being in both

187
00:08:29,500 --> 00:08:33,990
A and B in the NFA. Oh. I see. So the deterministic

188
00:08:33,990 --> 00:08:36,129
machine isn't trying to be magical. It's just

189
00:08:36,129 --> 00:08:38,909
keeping a master ledger of everywhere the magical

190
00:08:38,909 --> 00:08:41,370
machine would be at that exact moment. Precisely.

191
00:08:41,450 --> 00:08:44,789
If the original NFA had 10 states, it could potentially

192
00:08:44,789 --> 00:08:47,330
be in any combination of those 10 states at once.

193
00:08:47,409 --> 00:08:50,710
Right. So our new DFA just needs a unique state

194
00:08:50,710 --> 00:08:53,610
for every possible combination. The catch is

195
00:08:53,610 --> 00:08:55,769
that there are two to the power of 10 possible

196
00:08:55,769 --> 00:08:59,149
combinations. So an NFA with 10 states might

197
00:08:59,149 --> 00:09:02,250
require a DFA with 1 ,024 states to simulate

198
00:09:02,250 --> 00:09:04,649
it. So the turnstile gets massively more complicated.

199
00:09:04,669 --> 00:09:06,990
It has an explosion of gears and levers. Yes,

200
00:09:06,990 --> 00:09:09,090
it might have exponentially more states, but

201
00:09:09,090 --> 00:09:11,389
the fundamental capability hasn't changed. Every

202
00:09:11,389 --> 00:09:13,929
single pattern, every language that can be recognized

203
00:09:13,929 --> 00:09:16,389
by the parallel processing NFA can be recognized

204
00:09:16,389 --> 00:09:19,669
by the single track DFA. That's wild. Non -determinism

205
00:09:19,669 --> 00:09:21,389
doesn't let the machine solve more problems.

206
00:09:21,549 --> 00:09:24,110
It just makes designing the machine vastly easier

207
00:09:24,110 --> 00:09:26,509
for us. Right. It's an elegant shorthand. It's

208
00:09:26,509 --> 00:09:28,870
a tool for the human mind, not extra horsepower

209
00:09:28,870 --> 00:09:32,100
for the math. That makes so much sense. And speaking

210
00:09:32,100 --> 00:09:34,159
of tools for the human mind, this brings us to

211
00:09:34,159 --> 00:09:36,620
another way to describe these exact same simple

212
00:09:36,620 --> 00:09:39,059
patterns, one that programmers use literally

213
00:09:39,059 --> 00:09:42,080
every single day, regular expressions. Oh, yes.

214
00:09:42,519 --> 00:09:45,879
If DFAs are the machines, regular expressions

215
00:09:45,879 --> 00:09:48,440
are the language we use to command them. They

216
00:09:48,440 --> 00:09:50,600
are a mathematical notation for pattern matching.

217
00:09:50,990 --> 00:09:52,990
I have to admit, I kind of love regular expressions.

218
00:09:53,250 --> 00:09:55,289
When you first see them, they look like a cat

219
00:09:55,289 --> 00:09:57,590
walked across a keyboard, just a jumble of brackets,

220
00:09:57,889 --> 00:10:00,309
asterisks, and slashes. It's a very dense syntax.

221
00:10:00,610 --> 00:10:03,110
Very. But they are incredibly elegant. You can

222
00:10:03,110 --> 00:10:05,490
describe any regular language using just three

223
00:10:05,490 --> 00:10:09,490
basic operations. Just three. Union, concatenation,

224
00:10:09,610 --> 00:10:11,889
and the star operation. Let's break those down

225
00:10:11,889 --> 00:10:14,110
because they show how really complex systems

226
00:10:14,110 --> 00:10:16,529
are built from simple foundations. Okay, so union

227
00:10:16,529 --> 00:10:19,740
is essentially the word O -R. You tell the machine,

228
00:10:19,919 --> 00:10:23,080
accept the word cat or R the word dog. Concatenation

229
00:10:23,080 --> 00:10:25,519
is sequence. You tell it, accept cat followed

230
00:10:25,519 --> 00:10:28,120
by dog. And then there is the star operation,

231
00:10:28,379 --> 00:10:30,879
sometimes called the clean star. That's the real

232
00:10:30,879 --> 00:10:33,899
workhorse. It is. The star operation means accept

233
00:10:33,899 --> 00:10:37,500
zero or more repetitions of the preceding thing.

234
00:10:37,860 --> 00:10:41,039
So if I put a star after the word cat, the machine

235
00:10:41,039 --> 00:10:44,019
will accept a blank page or cat or cat cat or

236
00:10:44,019 --> 00:10:46,889
cat cat cat going on to infinity. And the beautiful

237
00:10:46,889 --> 00:10:49,370
theoretical result here is that the class of

238
00:10:49,370 --> 00:10:51,809
regular languages is closed under these operations.

239
00:10:52,450 --> 00:10:54,470
Closed. What does that mean in this context?

240
00:10:54,870 --> 00:10:57,490
It means if you take two perfectly valid regular

241
00:10:57,490 --> 00:11:00,049
expressions and you combine them using a union

242
00:11:00,049 --> 00:11:02,690
or stick them together with concatenation or

243
00:11:02,690 --> 00:11:05,169
throw a star on them, the result is guaranteed

244
00:11:05,169 --> 00:11:07,370
to still be a regular expression. Oh, I see.

245
00:11:07,470 --> 00:11:09,549
You can never accidentally combine two simple

246
00:11:09,549 --> 00:11:12,269
patterns and accidentally create a monster that

247
00:11:12,269 --> 00:11:15,090
requires a more powerful machine. A DFA can always

248
00:11:15,090 --> 00:11:17,860
process it. But, I mean, there is a monster lurking,

249
00:11:17,899 --> 00:11:19,980
isn't there? There's a hard limit to what these

250
00:11:19,980 --> 00:11:22,960
finite automata and regular expressions can actually

251
00:11:22,960 --> 00:11:24,960
do. They are not universal computers. No, they

252
00:11:24,960 --> 00:11:27,220
definitely aren't. And computer scientists prove

253
00:11:27,220 --> 00:11:29,360
this limitation using something called the pumping

254
00:11:29,360 --> 00:11:31,919
lemma. That's right. We need a way to mathematically

255
00:11:31,919 --> 00:11:35,399
prove that a machine cannot do something. We

256
00:11:35,399 --> 00:11:38,139
know DFAs have strictly finite memory. They're

257
00:11:38,139 --> 00:11:41,100
a limited number of states. So how do we break

258
00:11:41,100 --> 00:11:43,299
a machine with finite memory? We force it to

259
00:11:43,299 --> 00:11:45,679
count. Exactly. We force it to count. Let's walk

260
00:11:45,679 --> 00:11:47,600
through the exact mechanism of this because I

261
00:11:47,600 --> 00:11:50,059
think it's brilliant. Let's say I want my machine

262
00:11:50,059 --> 00:11:52,360
to recognize a language of perfectly balanced

263
00:11:52,360 --> 00:11:55,940
strings. The rule is the string must consist

264
00:11:55,940 --> 00:11:59,710
of exactly n zeros. followed by exactly N1s.

265
00:11:59,750 --> 00:12:04,250
So strings like 01 or 0011 or a million zeros

266
00:12:04,250 --> 00:12:07,350
followed by a million ones. Perfectly symmetrical.

267
00:12:07,669 --> 00:12:10,289
Right. To a human, that's trivial. But put yourself

268
00:12:10,289 --> 00:12:12,809
in the shoes of the DFA. It's reading the input

269
00:12:12,809 --> 00:12:15,610
one character at a time from left to right. As

270
00:12:15,610 --> 00:12:17,710
it reads the zeros, it has to remember how many

271
00:12:17,710 --> 00:12:19,570
it has seen so that when the ones start showing

272
00:12:19,570 --> 00:12:21,909
up, it knows exactly when to stop. But the DFA

273
00:12:21,909 --> 00:12:24,110
doesn't have a notepad. It doesn't have a counter.

274
00:12:24,470 --> 00:12:27,029
The only way it can remember a number is by changing

275
00:12:27,029 --> 00:12:30,240
its state. So state 1 means I've seen one zero.

276
00:12:30,519 --> 00:12:33,879
State 2 means I've seen two zeros. And this is

277
00:12:33,879 --> 00:12:36,960
where the traps snap shut. Let's say our DFA

278
00:12:36,960 --> 00:12:39,899
is built with five states. It's a five -state

279
00:12:39,899 --> 00:12:43,440
machine. But I feed it an input that starts with

280
00:12:43,440 --> 00:12:46,120
six zeros. This is a classic application of the

281
00:12:46,120 --> 00:12:48,659
pigeonhole principle. The pigeons. Yeah. If you

282
00:12:48,659 --> 00:12:51,019
have six pigeons but only five pigeonholes to

283
00:12:51,019 --> 00:12:53,559
put them in, at least one hole must contain more

284
00:12:53,559 --> 00:12:56,480
than one pigeon. If the machine reads six zeros

285
00:12:56,480 --> 00:13:00,080
but only has five states, it must, absolutely

286
00:13:00,080 --> 00:13:03,460
must, revisit a state it has already been in.

287
00:13:03,539 --> 00:13:05,559
It creates a loop. The sequence of states just

288
00:13:05,559 --> 00:13:07,539
circles back on itself. Exactly. The machine

289
00:13:07,539 --> 00:13:10,220
gets trapped in a cycle, and the pumping lemma

290
00:13:10,220 --> 00:13:12,820
exploits this loop. It says that for any regular

291
00:13:12,820 --> 00:13:15,100
language, if a string is long enough to trigger

292
00:13:15,100 --> 00:13:17,639
this loop, you can take the section of the input

293
00:13:17,639 --> 00:13:20,289
that caused the loop, and you can pump it. pump

294
00:13:20,289 --> 00:13:22,490
it you can repeat that middle section artificially

295
00:13:22,490 --> 00:13:24,909
you can copy and paste it 10 times or a million

296
00:13:24,909 --> 00:13:27,450
times and the machine will blindly follow the

297
00:13:27,450 --> 00:13:29,870
loop over and over and it will still accept the

298
00:13:29,870 --> 00:13:32,090
final string so if i pump the zeros in my perfectly

299
00:13:32,090 --> 00:13:34,289
balanced string the machine just keeps looping

300
00:13:34,289 --> 00:13:36,009
suddenly i have a string with a million zeros

301
00:13:36,009 --> 00:13:38,970
but only six ones the string is now totally invalid

302
00:13:38,970 --> 00:13:42,179
it breaks our rule of symmetry But the DFA doesn't

303
00:13:42,179 --> 00:13:44,399
know that. The DFA just rode the loop and eventually

304
00:13:44,399 --> 00:13:46,960
stumbled into the accept state anyway. It gave

305
00:13:46,960 --> 00:13:49,379
a false positive. Therefore, we have mathematically

306
00:13:49,379 --> 00:13:53,500
proven that the language of N0s followed by N1s

307
00:13:53,500 --> 00:13:57,220
cannot possibly be a regular language. No DFA,

308
00:13:57,419 --> 00:13:59,759
no matter how many states you give it, can ever

309
00:13:59,759 --> 00:14:02,340
solve it perfectly for all numbers. It requires

310
00:14:02,340 --> 00:14:05,720
infinite counting capability, and DFAs are strictly

311
00:14:05,720 --> 00:14:08,779
finite. This is a massive pivot point. Our turnstile

312
00:14:08,779 --> 00:14:11,480
is officially broken. It's great at finding an

313
00:14:11,480 --> 00:14:14,580
at symbol in an email, but it cannot do basic

314
00:14:14,580 --> 00:14:17,679
arithmetic. It cannot match parentheses. If we

315
00:14:17,679 --> 00:14:19,440
want to do actual computing, we need a way to

316
00:14:19,440 --> 00:14:21,740
give our mathematical machine a real memory bank.

317
00:14:21,980 --> 00:14:24,200
Which brings us to the next level of computational

318
00:14:24,200 --> 00:14:27,480
power. Context -free languages and the machines

319
00:14:27,480 --> 00:14:30,379
that process them push down automata. Let's start

320
00:14:30,379 --> 00:14:32,200
with the language side of things. If regular

321
00:14:32,200 --> 00:14:34,279
languages are defined by regular expressions,

322
00:14:34,679 --> 00:14:36,759
context -free languages are defined by context

323
00:14:36,759 --> 00:14:39,679
-free grammars, or CFGs. This feels less like

324
00:14:39,679 --> 00:14:42,039
a machine reading an input and more like a set

325
00:14:42,039 --> 00:14:44,100
of biological rules for growing a string from

326
00:14:44,100 --> 00:14:46,240
a single seed. That's a really good way to picture

327
00:14:46,240 --> 00:14:49,639
it. A CFG consists of variables, terminals, and

328
00:14:49,639 --> 00:14:52,440
substitution rules. You start with a master variable,

329
00:14:52,600 --> 00:14:55,419
and you apply rules to substitute that variable

330
00:14:55,419 --> 00:14:58,360
with other variables or terminals until all you

331
00:14:58,360 --> 00:15:01,070
have left are terminals. My favorite way to explain

332
00:15:01,070 --> 00:15:03,730
this is to think of the game of Mad Libs or maybe,

333
00:15:03,850 --> 00:15:06,169
you know, the sentence diagramming we all used

334
00:15:06,169 --> 00:15:08,169
to do in elementary school English class. Yeah.

335
00:15:08,509 --> 00:15:10,850
Let's say you start with a big abstract variable

336
00:15:10,850 --> 00:15:13,950
called sentence. The rules of your grammar might

337
00:15:13,950 --> 00:15:16,169
say that sentence can be substituted with a noun

338
00:15:16,169 --> 00:15:18,690
phrase followed by a verb phrase. So you replace

339
00:15:18,690 --> 00:15:20,629
the one variable with two new ones. Exactly.

340
00:15:20,970 --> 00:15:23,610
Then you look at the rule for noun phrase. It

341
00:15:23,610 --> 00:15:26,149
says a noun phrase seamlessly expands into an

342
00:15:26,149 --> 00:15:28,809
adjective and a noun. We keep applying these

343
00:15:28,809 --> 00:15:30,629
substitution rules, drilling down through the

344
00:15:30,629 --> 00:15:33,490
hierarchy. Eventually, the rules say that adjective

345
00:15:33,490 --> 00:15:36,330
becomes the terminal word quick, noun becomes

346
00:15:36,330 --> 00:15:39,789
fox, and verb phrase becomes jumps. You are left

347
00:15:39,789 --> 00:15:42,429
with the terminal string, the quick brown fox

348
00:15:42,429 --> 00:15:45,690
jumps. It's a recursive, hierarchical way of

349
00:15:45,690 --> 00:15:48,610
building structures. And that concept of recursion

350
00:15:48,610 --> 00:15:51,370
rules calling themselves or nesting inside themselves

351
00:15:51,370 --> 00:15:55,649
is exactly why context -free grammars can effortlessly

352
00:15:55,649 --> 00:15:58,590
solve the counting problem that broke the DFA.

353
00:15:58,789 --> 00:16:02,570
Oh, wait, how does it handle the N0s and N1s

354
00:16:02,570 --> 00:16:04,850
problem? You just define a rule that generates

355
00:16:04,850 --> 00:16:06,970
from the inside out. You have a variable, let's

356
00:16:06,970 --> 00:16:10,070
call it A, and the rule for A says A can be replaced

357
00:16:10,070 --> 00:16:12,669
by a 0. followed by the variable A again, followed

358
00:16:12,669 --> 00:16:15,450
by a 1. Oh, wow. So every time you apply the

359
00:16:15,450 --> 00:16:17,950
rule, it spits out a 0 on the left side and a

360
00:16:17,950 --> 00:16:20,330
1 on the right side and puts the variable A back

361
00:16:20,330 --> 00:16:22,090
in the middle to do it again. Exactly. If you

362
00:16:22,090 --> 00:16:24,570
apply the rule three times, you get three 0s

363
00:16:24,570 --> 00:16:26,350
on the left, three 1s on the right. They are

364
00:16:26,350 --> 00:16:28,690
intrinsically linked. They grow together. They

365
00:16:28,690 --> 00:16:31,000
will always be perfectly balanced. That's incredibly

366
00:16:31,000 --> 00:16:33,379
elegant. So that is the grammar, the rulebook.

367
00:16:33,600 --> 00:16:36,899
But what is the machine equivalent? What kind

368
00:16:36,899 --> 00:16:39,259
of theoretical hardware can actually process

369
00:16:39,259 --> 00:16:42,620
this nested grammar and verify if a string belongs

370
00:16:42,620 --> 00:16:45,480
to it? Well, to process a context -free grammar,

371
00:16:45,639 --> 00:16:48,639
you take a standard finite autobana and you give

372
00:16:48,639 --> 00:16:50,720
it a specific type of memory called a stack.

373
00:16:50,919 --> 00:16:53,600
This creates a push -down automaton, or PDA.

374
00:16:53,950 --> 00:16:56,610
A stack. Let's make this tangible. The classic

375
00:16:56,610 --> 00:17:00,149
analogy is a spring -loaded stack of plates at

376
00:17:00,149 --> 00:17:02,769
a cafeteria buffet. It's a pillar of plates.

377
00:17:02,909 --> 00:17:05,250
Right. When a clean plate comes out of the kitchen,

378
00:17:05,390 --> 00:17:08,289
you push it down onto the top of the stack. When

379
00:17:08,289 --> 00:17:10,750
a customer wants a plate, they pop the top one

380
00:17:10,750 --> 00:17:14,630
off. But here is the critical, absolute restriction

381
00:17:14,630 --> 00:17:18,269
of a stack. It operates on a last -in, first

382
00:17:18,269 --> 00:17:21,910
-out basis, or LIFO. You cannot reach into the

383
00:17:21,910 --> 00:17:23,670
middle of the stack and pull out plate number

384
00:17:23,670 --> 00:17:26,109
seven. No, definitely not. You can only ever

385
00:17:26,109 --> 00:17:29,650
see and touch the very top plate. It's an infinite

386
00:17:29,650 --> 00:17:31,750
memory structure, but with radically restricted

387
00:17:31,750 --> 00:17:34,450
access. So let's look at how the PDA uses this

388
00:17:34,450 --> 00:17:36,410
cafeteria stack to solve the counting problem,

389
00:17:36,549 --> 00:17:39,009
matching the zeros and ones. The machine starts

390
00:17:39,009 --> 00:17:40,990
reading the input string from left to right.

391
00:17:41,109 --> 00:17:43,349
As it reads the zeros, it doesn't try to change

392
00:17:43,349 --> 00:17:46,130
states to remember the number. Instead, for every

393
00:17:46,130 --> 00:17:48,490
single zero it reads, it pushes a plate onto

394
00:17:48,490 --> 00:17:50,900
the stack. Go. If it reads 100 zeros, it pushes

395
00:17:50,900 --> 00:17:54,180
100 plates. The stack gets incredibly tall. It

396
00:17:54,180 --> 00:17:56,579
is effectively using the physical height of the

397
00:17:56,579 --> 00:17:59,640
stack as a counter. Right. Then, the moment the

398
00:17:59,640 --> 00:18:02,039
machine reads the first one in the input, the

399
00:18:02,039 --> 00:18:04,519
transition rules tell it to switch modes. Now,

400
00:18:04,539 --> 00:18:06,440
for every one it reads, it pops a plate off the

401
00:18:06,440 --> 00:18:09,059
top of the stack. Read a one, pop a plate. Read

402
00:18:09,059 --> 00:18:11,400
a one, pop a plate. And the acceptance condition

403
00:18:11,400 --> 00:18:14,559
is elegant. If the machine finishes reading the

404
00:18:14,559 --> 00:18:17,470
entire string of input, And at that exact moment,

405
00:18:17,630 --> 00:18:21,309
it pops the very last plate off the stack, leaving

406
00:18:21,309 --> 00:18:23,569
the stack perfectly empty. Then it knows it's

407
00:18:23,569 --> 00:18:25,150
a perfect match. It doesn't know what the number

408
00:18:25,150 --> 00:18:27,150
was. It just knows the pushing and the popping

409
00:18:27,150 --> 00:18:30,250
canceled each other out exactly. Precisely. The

410
00:18:30,250 --> 00:18:33,170
push down automacon has an infinite capacity

411
00:18:33,170 --> 00:18:35,490
to count as long as it only needs to count in

412
00:18:35,490 --> 00:18:38,789
this very specific nested last and first out

413
00:18:38,789 --> 00:18:41,630
way. And just as regular expressions are mathematically

414
00:18:41,630 --> 00:18:44,690
equivalent to finite automata, Sipser's text

415
00:18:44,690 --> 00:18:47,410
details the rigorous proof that context -free

416
00:18:47,410 --> 00:18:49,410
grammars are perfectly equivalent to push -down

417
00:18:49,410 --> 00:18:51,910
automata. So they match up perfectly. Yes. If

418
00:18:51,910 --> 00:18:53,849
you can write a grammar for a language, a PDA

419
00:18:53,849 --> 00:18:56,029
can process it. I want to pause here because

420
00:18:56,029 --> 00:18:58,269
a listener might be thinking, okay, this is a

421
00:18:58,269 --> 00:19:00,250
neat parlor trick with plates and zeros, but

422
00:19:00,250 --> 00:19:03,569
why do I care? The reason this matters, and Sipser

423
00:19:03,569 --> 00:19:05,769
has a great section on deterministic context

424
00:19:05,769 --> 00:19:08,869
-free grammars, is because this pure abstract

425
00:19:08,869 --> 00:19:11,990
theory translates directly to the real -world

426
00:19:11,990 --> 00:19:14,450
software you use every day. It really does. This

427
00:19:14,450 --> 00:19:17,269
is the entire mathematical foundation for compiling

428
00:19:17,269 --> 00:19:19,450
programming languages. It is the bridge between

429
00:19:19,450 --> 00:19:22,349
human thought and machine code. Exactly. When

430
00:19:22,349 --> 00:19:25,230
a software engineer writes code in Python or

431
00:19:25,230 --> 00:19:28,150
C++ brain, they are using nested structures.

432
00:19:28,410 --> 00:19:30,569
You open a parenthesis, you type an equation,

433
00:19:30,769 --> 00:19:32,569
you close the... parentheses, you write an if

434
00:19:32,569 --> 00:19:34,269
statement. And inside that, you write a while

435
00:19:34,269 --> 00:19:36,750
loop. And inside that, another if statement.

436
00:19:36,970 --> 00:19:39,309
Right. Before the computer can run that program,

437
00:19:39,609 --> 00:19:41,690
a compiler has to read it and understand that

438
00:19:41,690 --> 00:19:45,049
hierarchy. It uses a deterministic pushdown automaton

439
00:19:45,049 --> 00:19:48,230
to parse your code. It pushes a marker onto the

440
00:19:48,230 --> 00:19:50,869
stack every time you open a bracket and pops

441
00:19:50,869 --> 00:19:53,009
it when you close one. And if the compiler gets

442
00:19:53,009 --> 00:19:55,390
to the end of your file and the stack isn't empty,

443
00:19:55,589 --> 00:19:58,890
it throws a syntax error. Missing closing bracket.

444
00:19:59,289 --> 00:20:01,430
Exactly. And every piece of software in the world

445
00:20:01,430 --> 00:20:04,450
relies on this abstract stack machine to function.

446
00:20:04,690 --> 00:20:07,809
It's a beautiful example of how exploring the

447
00:20:07,809 --> 00:20:11,990
purely theoretical bounds of logic yields the

448
00:20:11,990 --> 00:20:14,130
practical tools we need to build the digital

449
00:20:14,130 --> 00:20:16,529
age. But I have to push back on the pushdown

450
00:20:16,529 --> 00:20:19,839
automaton. Oh. I am not satisfied. A stack is

451
00:20:19,839 --> 00:20:22,519
great for matching parentheses, but as a general

452
00:20:22,519 --> 00:20:25,380
purpose memory system, it is painfully restricted.

453
00:20:25,819 --> 00:20:28,480
What if I am doing complex math and I write an

454
00:20:28,480 --> 00:20:30,160
intermediate value to my memory and then I go

455
00:20:30,160 --> 00:20:32,359
do a bunch of other calculations? With a stack,

456
00:20:32,400 --> 00:20:34,259
you'd be in trouble. Right. With a stack, I have

457
00:20:34,259 --> 00:20:36,359
to pop off all the new calculations, destroying

458
00:20:36,359 --> 00:20:38,700
them just to reach down and retrieve that intermediate

459
00:20:38,700 --> 00:20:41,240
value. A real computer doesn't work like that.

460
00:20:41,609 --> 00:20:44,769
My laptop has random access memory. It can look

461
00:20:44,769 --> 00:20:46,829
at memory address zero, then jump to address

462
00:20:46,829 --> 00:20:49,430
one million, then back to five. How do we model

463
00:20:49,430 --> 00:20:51,369
a machine that can just write things down and

464
00:20:51,369 --> 00:20:53,609
look at them later? Well, the stack is too rigid.

465
00:20:53,910 --> 00:20:56,289
You are looking for a machine that uses a scratch

466
00:20:56,289 --> 00:21:00,130
pad. And that brings us to the very heart of

467
00:21:00,130 --> 00:21:03,250
the entire field. We are moving beyond the simple

468
00:21:03,250 --> 00:21:06,130
machines of automata and entering the realm of

469
00:21:06,130 --> 00:21:09,710
computability theory. Part two. Yes, we are searching

470
00:21:09,710 --> 00:21:12,569
for the absolute. hard limits of logic itself.

471
00:21:12,950 --> 00:21:16,170
And to do that, we meet the ultimate model of

472
00:21:16,170 --> 00:21:19,269
computation, the Turing machine. The Turing machine,

473
00:21:19,509 --> 00:21:22,690
introduced by the brilliant Alan Turing in 1936.

474
00:21:23,029 --> 00:21:25,970
Long before transistors existed, Turing was trying

475
00:21:25,970 --> 00:21:27,869
to figure out what it actually meant for a human

476
00:21:27,869 --> 00:21:30,990
mathematician to compute something. He visualized

477
00:21:30,990 --> 00:21:33,009
a clerk sitting at a desk with a pencil and an

478
00:21:33,009 --> 00:21:35,339
eraser. How do we distill that human process

479
00:21:35,339 --> 00:21:37,900
into a mathematical model? Turing's genius was

480
00:21:37,900 --> 00:21:40,279
in extreme simplification. He took the finite

481
00:21:40,279 --> 00:21:42,940
state control we saw in the DFA, the little mechanical

482
00:21:42,940 --> 00:21:45,200
box with a set of internal states and transition

483
00:21:45,200 --> 00:21:47,460
rules, but instead of reading a fleeting input

484
00:21:47,460 --> 00:21:49,799
and instead of a restrictive stack, he gave his

485
00:21:49,799 --> 00:21:51,720
machine an infinite tape. Paint a picture of

486
00:21:51,720 --> 00:21:54,119
this tape for us. Imagine a strip of paper tape

487
00:21:54,119 --> 00:21:57,000
divided into individual squares, stretching out

488
00:21:57,000 --> 00:22:00,319
infinitely to the right. The machine has a head,

489
00:22:00,400 --> 00:22:02,380
a scanner, that rests on one of these squares

490
00:22:02,380 --> 00:22:05,329
at a time. The head can read the symbol printed

491
00:22:05,329 --> 00:22:07,730
on the square, and it can write a new symbol

492
00:22:07,730 --> 00:22:10,450
over it, erasing what was there. Okay, so it

493
00:22:10,450 --> 00:22:13,049
can read and write, but how does it move? In

494
00:22:13,049 --> 00:22:15,589
a single step of computation, the machine reads

495
00:22:15,589 --> 00:22:18,170
the symbol under the head. It consults its internal

496
00:22:18,170 --> 00:22:20,930
state rules. Based on those rules, it overwrites

497
00:22:20,930 --> 00:22:23,750
the symbol, it changes its internal state, and

498
00:22:23,750 --> 00:22:25,730
then the head moves exactly one square to the

499
00:22:25,730 --> 00:22:28,049
left or one square to the right. That is it.

500
00:22:28,190 --> 00:22:29,950
That's it? That is the entire architecture of

501
00:22:29,950 --> 00:22:32,359
the Turing machine. Read. right, change state,

502
00:22:32,559 --> 00:22:34,900
move left or right. I have to be honest, when

503
00:22:34,900 --> 00:22:36,759
you describe it like that, it sounds pathetic.

504
00:22:37,079 --> 00:22:38,960
It does sound underwhelming. It sounds almost

505
00:22:38,960 --> 00:22:41,880
too simple to be useful. It's just inching back

506
00:22:41,880 --> 00:22:44,119
and forth along a paper tape, scribbling and

507
00:22:44,119 --> 00:22:47,319
erasing one square at a time. How can this incredibly

508
00:22:47,319 --> 00:22:50,779
primitive caterpillar of a machine possibly represent

509
00:22:50,779 --> 00:22:54,380
my MacBook, which is rendering 3D graphics and

510
00:22:54,380 --> 00:22:57,119
streaming high -definition video? It is hard

511
00:22:57,119 --> 00:22:59,730
to reconcile the simplicity of the model. with

512
00:22:59,730 --> 00:23:02,509
the complexity of modern software. But the power

513
00:23:02,509 --> 00:23:05,589
lies entirely in the unrestricted, random access

514
00:23:05,589 --> 00:23:08,769
to infinite memory. Because the head can move

515
00:23:08,769 --> 00:23:11,190
left and right freely, the machine can write

516
00:23:11,190 --> 00:23:13,910
a piece of data on square number 10, move the

517
00:23:13,910 --> 00:23:15,849
head a million squares to the right to perform

518
00:23:15,849 --> 00:23:18,750
a massive calculation, and then leisurely march

519
00:23:18,750 --> 00:23:21,089
a million squares back to the left to read the

520
00:23:21,089 --> 00:23:23,450
original data on square 10 without destroying

521
00:23:23,450 --> 00:23:25,470
anything in between. So it can use different

522
00:23:25,470 --> 00:23:27,369
parts of the tape for different things. It can

523
00:23:27,369 --> 00:23:30,130
have a section for the input, a section for working

524
00:23:30,130 --> 00:23:32,930
memory, a section for the final answer. Exactly.

525
00:23:33,410 --> 00:23:35,849
Sibster's text walks through how you would actually

526
00:23:35,849 --> 00:23:38,829
program a basic Turing machine to do things like

527
00:23:38,829 --> 00:23:41,410
addition or multiplication. And yes, to your

528
00:23:41,410 --> 00:23:44,289
point, it is mind -numbingly tedious. I can imagine.

529
00:23:44,410 --> 00:23:47,069
To add two numbers, the machine spends most of

530
00:23:47,069 --> 00:23:49,150
its time just zigzagging back and forth across

531
00:23:49,150 --> 00:23:51,509
the tape, carrying ones and shifting symbols

532
00:23:51,509 --> 00:23:54,759
around. It is incredibly inefficient. But we

533
00:23:54,759 --> 00:23:56,960
aren't talking about speed yet. We are talking

534
00:23:56,960 --> 00:23:59,380
about capability. The astonishing mathematical

535
00:23:59,380 --> 00:24:02,720
fact is that this simple zigzagging tape machine

536
00:24:02,720 --> 00:24:06,480
is unequivocally capable of executing any algorithm

537
00:24:06,480 --> 00:24:09,240
that your MacBook can execute. And computer scientists

538
00:24:09,240 --> 00:24:11,420
really tried to prove that wrong. They tried

539
00:24:11,420 --> 00:24:14,240
to build more powerful theoretical models. Sipser

540
00:24:14,240 --> 00:24:16,380
introduces a whole section on Turing machine

541
00:24:16,380 --> 00:24:19,059
variants. People looked at Turing's single tape

542
00:24:19,059 --> 00:24:22,529
and said, What if we give the machine multiple

543
00:24:22,529 --> 00:24:25,150
tapes, like three different infinite tapes with

544
00:24:25,150 --> 00:24:27,410
three independent read -write heads moving at

545
00:24:27,410 --> 00:24:30,069
the same time? Wouldn't that parallel processing

546
00:24:30,069 --> 00:24:32,630
be fundamentally more powerful? It is a very

547
00:24:32,630 --> 00:24:35,230
logical question. But the incredible conclusion

548
00:24:35,230 --> 00:24:37,789
is that none of these structural upgrades add

549
00:24:37,789 --> 00:24:40,869
any actual computational power over the basic

550
00:24:40,869 --> 00:24:43,250
single -tape model. Wait, how is that possible?

551
00:24:43,450 --> 00:24:45,450
How can a one -tape machine do everything a three

552
00:24:45,450 --> 00:24:48,349
-tape machine can do? Through simulation. We

553
00:24:48,349 --> 00:24:51,069
can prove that a standard Turing machine can

554
00:24:51,069 --> 00:24:54,150
perfectly simulate a multi -tape machine just

555
00:24:54,150 --> 00:24:56,690
by formatting its single tape cleverly. How does

556
00:24:56,690 --> 00:24:58,210
it do that? Let's walk through the mechanics.

557
00:24:58,569 --> 00:25:00,869
Imagine you take this single infinite tape and

558
00:25:00,869 --> 00:25:03,490
divide it into tracks. You use symbols that represent

559
00:25:03,490 --> 00:25:06,589
columns. So instead of writing a 0 or a 1, you

560
00:25:06,589 --> 00:25:08,869
write a complex symbol that essentially says

561
00:25:08,869 --> 00:25:12,309
on simulated tape 1 there is a 0, on simulated

562
00:25:12,309 --> 00:25:14,970
tape 2 there is a 1, and on simulated tape 3

563
00:25:14,970 --> 00:25:17,890
there is a blank. and you use special markers

564
00:25:17,890 --> 00:25:20,069
to keep track of where the simulated heads are

565
00:25:20,069 --> 00:25:22,390
supposed to be. Oh, I see. So for every single

566
00:25:22,390 --> 00:25:24,829
step the multi -tape machine takes, the single

567
00:25:24,829 --> 00:25:27,190
tape machine has to scan all the way across its

568
00:25:27,190 --> 00:25:29,529
tape to find the virtual heads, figure out what

569
00:25:29,529 --> 00:25:31,410
they are looking at, update its internal state,

570
00:25:31,529 --> 00:25:33,950
and then sweep all the way back across the tape

571
00:25:33,950 --> 00:25:36,589
to update the virtual symbols. Yes. It might

572
00:25:36,589 --> 00:25:39,170
take the single tape machine 10 ,000 steps to

573
00:25:39,170 --> 00:25:41,009
simulate a single step of the multi -tape machine.

574
00:25:41,170 --> 00:25:44,289
It is massively slower. But eventually it arrives

575
00:25:44,289 --> 00:25:46,619
at the exact same answer. The fundamental set

576
00:25:46,619 --> 00:25:49,259
of problems it can solve is identical. What about

577
00:25:49,259 --> 00:25:51,859
non -determinism? We saw that giving the finite

578
00:25:51,859 --> 00:25:54,579
automaton parallel universes didn't increase

579
00:25:54,579 --> 00:25:57,819
its power. Does giving a Turing machine parallel

580
00:25:57,819 --> 00:26:00,940
universes increase its power? Once again, the

581
00:26:00,940 --> 00:26:04,220
answer is no. If you have a magical non -deterministic

582
00:26:04,220 --> 00:26:06,859
Turing machine that can instantly guess the correct

583
00:26:06,859 --> 00:26:10,200
path through a labyrinth of calculations, you

584
00:26:10,200 --> 00:26:12,680
can simulate it with a standard deterministic

585
00:26:12,680 --> 00:26:15,460
Turing machine. Okay. The standard machine just

586
00:26:15,460 --> 00:26:18,180
systematically tries every single possible guess,

587
00:26:18,319 --> 00:26:21,440
one by one. It explores the first path. If it

588
00:26:21,440 --> 00:26:24,180
hits a dead end, it rewinds the tape, resets,

589
00:26:24,220 --> 00:26:27,119
and tries the second path. It uses the tape to

590
00:26:27,119 --> 00:26:30,019
keep a meticulous journal of which paths it has

591
00:26:30,019 --> 00:26:32,220
already checked. It's the ultimate brute force

592
00:26:32,220 --> 00:26:34,420
attack. Exactly. It might take until the end

593
00:26:34,420 --> 00:26:36,460
of the universe to finish the calculation, but

594
00:26:36,460 --> 00:26:38,539
mathematically, the deterministic machine will

595
00:26:38,539 --> 00:26:41,019
eventually find the same answer as the non -deterministic

596
00:26:41,019 --> 00:26:43,420
one. They're equivalent in their absolute capability.

597
00:26:44,039 --> 00:26:47,279
This is a staggering realization. No matter how

598
00:26:47,279 --> 00:26:49,200
many bells and whistles you add, no matter how

599
00:26:49,200 --> 00:26:52,200
much you complicate the architecture, you never

600
00:26:52,200 --> 00:26:54,440
surpass the fundamental problem -solving power

601
00:26:54,440 --> 00:26:58,299
of Turing's basic paper tape machine. It is a

602
00:26:58,299 --> 00:27:01,140
ceiling we cannot punch through. And this realization

603
00:27:01,140 --> 00:27:03,759
crystallizes into something called the Church

604
00:27:03,759 --> 00:27:06,519
-Turing thesis. Yes. Now, this is an interesting

605
00:27:06,519 --> 00:27:08,700
moment in the textbook because Sipser points

606
00:27:08,700 --> 00:27:11,079
out that the Church -Turing thesis isn't a mathematical

607
00:27:11,079 --> 00:27:14,099
proof, is it? It's something else. It is a philosophical

608
00:27:14,099 --> 00:27:17,180
bridge. It connects the informal intuitive world

609
00:27:17,180 --> 00:27:19,819
of human thought to the rigorous formal world

610
00:27:19,819 --> 00:27:22,440
of mathematics. The Church -Turing thesis states

611
00:27:22,440 --> 00:27:25,500
that our intuitive notion of an algorithm Any

612
00:27:25,500 --> 00:27:28,119
systematic step -by -step procedure that a human

613
00:27:28,119 --> 00:27:30,119
could theoretically carry out with a pencil and

614
00:27:30,119 --> 00:27:33,519
paper is perfectly, completely, and exactly captured

615
00:27:33,519 --> 00:27:35,539
by the Turing machine model. If a process can

616
00:27:35,539 --> 00:27:38,039
be described as an algorithm, a Turing machine

617
00:27:38,039 --> 00:27:41,019
can execute it. And conversely, if a Turing machine

618
00:27:41,019 --> 00:27:44,200
cannot compute it, no algorithm exists that can.

619
00:27:44,440 --> 00:27:46,759
Right. And to understand why this thesis was

620
00:27:46,759 --> 00:27:48,839
so earth -shattering, you have to look at the

621
00:27:48,839 --> 00:27:51,380
historical context of mathematics in the early

622
00:27:51,380 --> 00:27:54,420
20th century. At that time, there was a deep

623
00:27:54,420 --> 00:27:56,680
-seated belief that mathematics was omnipotent.

624
00:27:56,880 --> 00:27:59,799
In the year 1900, the preeminent mathematician

625
00:27:59,799 --> 00:28:02,740
David Hilbert gave a legendary speech where he

626
00:28:02,740 --> 00:28:06,440
outlined 23 massive unsolved mathematical problems.

627
00:28:06,599 --> 00:28:08,900
He essentially laid out the agenda for the next

628
00:28:08,900 --> 00:28:11,299
century of math. And one of those problems, Hilbert's

629
00:28:11,299 --> 00:28:13,660
10th problem, dealt with algorithms, right? Yes.

630
00:28:13,660 --> 00:28:15,559
Hilbert's 10th problem asked the mathematical

631
00:28:15,559 --> 00:28:18,559
community to find a general algorithm that could

632
00:28:18,559 --> 00:28:20,940
determine whether any given polynomial equation

633
00:28:20,940 --> 00:28:24,099
with integer coefficients has any integer roots.

634
00:28:24,420 --> 00:28:26,619
So he wasn't asking them to solve a specific

635
00:28:26,619 --> 00:28:29,039
equation. He was asking them to invent a universal

636
00:28:29,039 --> 00:28:31,019
machine, a universal process that could look

637
00:28:31,019 --> 00:28:32,859
at an equation and just say, yes, this is solvable

638
00:28:32,859 --> 00:28:36,140
or no, this is impossible. Exactly. And the crucial

639
00:28:36,140 --> 00:28:38,859
thing is Hilbert assumed such an algorithm existed.

640
00:28:39,579 --> 00:28:41,700
He just assumed someone needed to be clever enough

641
00:28:41,700 --> 00:28:44,880
to find it. But for decades, some of the greatest

642
00:28:44,880 --> 00:28:47,339
minds in the world worked on it. And they failed.

643
00:28:47,480 --> 00:28:50,200
They couldn't find the algorithm. But more importantly,

644
00:28:50,380 --> 00:28:52,640
they couldn't prove that the algorithm didn't

645
00:28:52,640 --> 00:28:54,819
exist. Wait, why couldn't they just prove it

646
00:28:54,819 --> 00:28:56,960
was impossible? Because they didn't have a definition

647
00:28:56,960 --> 00:28:59,859
of what an algorithm was. How do you prove that

648
00:28:59,859 --> 00:29:02,140
no algorithm in the universe can solve a problem

649
00:29:02,140 --> 00:29:04,559
if you don't have a mathematical boundary defining

650
00:29:04,559 --> 00:29:07,920
all possible algorithms? Oh. You can't prove

651
00:29:07,920 --> 00:29:10,480
a negative about a vague concept. You can't say

652
00:29:10,480 --> 00:29:13,839
no process can do this if you can't define process.

653
00:29:14,220 --> 00:29:16,640
Exactly. That is the vacuum that Turing filled

654
00:29:16,640 --> 00:29:20,619
in 1936. The church Turing thesis provided that

655
00:29:20,619 --> 00:29:23,140
boundary. Once the mathematical community accepted

656
00:29:23,140 --> 00:29:25,960
that algorithm equals Turing machine, they finally

657
00:29:25,960 --> 00:29:28,440
had a target. They now proved that a problem

658
00:29:28,440 --> 00:29:31,480
was unsolvable by proving that no Turing machine

659
00:29:31,480 --> 00:29:35,269
could solve it. And did they? They did. Decades

660
00:29:35,269 --> 00:29:38,829
later, in 1970, a mathematician named Yuri Matyasovich

661
00:29:38,829 --> 00:29:41,750
used this exact foundation to finally answer

662
00:29:41,750 --> 00:29:44,549
Hilbert's 10th problem. He proved mathematically

663
00:29:44,549 --> 00:29:47,210
that no Turing machine can universally solve

664
00:29:47,210 --> 00:29:50,250
polynomial roots. Therefore, by the Church -Turing

665
00:29:50,250 --> 00:29:53,569
thesis, no algorithm exists. Hilbert was wrong.

666
00:29:53,910 --> 00:29:56,589
Some mathematical problems simply cannot be solved

667
00:29:56,589 --> 00:29:59,150
by algorithms. They are entirely beyond the reach

668
00:29:59,150 --> 00:30:01,779
of computation. That is a chilling thought. We

669
00:30:01,779 --> 00:30:03,859
build these massive supercomputers, assuming

670
00:30:03,859 --> 00:30:05,319
they can figure anything out if we just give

671
00:30:05,319 --> 00:30:07,279
them enough time. But there are fundamental laws

672
00:30:07,279 --> 00:30:10,039
of logic that say, no, you cannot know the answer

673
00:30:10,039 --> 00:30:12,900
to this. Which perfectly sets the stage for the

674
00:30:12,900 --> 00:30:15,700
most famous undecidable problem in history. We

675
00:30:15,700 --> 00:30:18,119
are looking at the great divide. Decidable problems

676
00:30:18,119 --> 00:30:20,099
versus undecidable problems. We should define

677
00:30:20,099 --> 00:30:22,509
those terms clearly. A problem is decidable if

678
00:30:22,509 --> 00:30:24,230
there exists a Turing machine that can evaluate

679
00:30:24,230 --> 00:30:26,930
any input for that problem and guaranteed eventually

680
00:30:26,930 --> 00:30:30,109
halt in an accept state or a reject state. It

681
00:30:30,109 --> 00:30:32,109
must always give an answer. It must always halt.

682
00:30:32,230 --> 00:30:34,849
It cannot run forever. Now, a lot of things are

683
00:30:34,849 --> 00:30:37,650
decidable. Adding numbers is decidable. Checking

684
00:30:37,650 --> 00:30:40,349
if a string has matched parentheses is decidable.

685
00:30:40,609 --> 00:30:43,690
But then we encounter the monster, the halting

686
00:30:43,690 --> 00:30:46,069
problem. In the notation of Sipser's text, it's

687
00:30:46,069 --> 00:30:49,430
often denoted as ATM. The problem asks a very

688
00:30:49,430 --> 00:30:52,750
simple question about programs themselves. Can

689
00:30:52,750 --> 00:30:55,789
we write a universal debugging algorithm? Can

690
00:30:55,789 --> 00:30:57,990
we build a Turing machine that takes two things

691
00:30:57,990 --> 00:31:00,859
as input? The source code of any other program,

692
00:31:01,019 --> 00:31:03,759
and an input for that program. And our debugger

693
00:31:03,759 --> 00:31:05,619
machine will analyze the code and tell us with

694
00:31:05,619 --> 00:31:08,440
absolute certainty, yes, this program will eventually

695
00:31:08,440 --> 00:31:11,240
halt and finish its job, or... No, this program

696
00:31:11,240 --> 00:31:13,319
has a bug and we'll get stuck in an infinite

697
00:31:13,319 --> 00:31:15,680
loop and run forever. Now, let me push back here

698
00:31:15,680 --> 00:31:17,160
on behalf of the listener, because the first

699
00:31:17,160 --> 00:31:18,740
time I heard the halting problem, I thought it

700
00:31:18,740 --> 00:31:20,599
was a trick question. It sounds like one. Right.

701
00:31:21,099 --> 00:31:23,779
Why is this hard? We just built the Turing machine

702
00:31:23,779 --> 00:31:26,700
model. We know Turing machines can simulate other

703
00:31:26,700 --> 00:31:29,339
Turing machines. So why can't I just build a

704
00:31:29,339 --> 00:31:32,079
simulator? My debugger takes the source code,

705
00:31:32,319 --> 00:31:34,839
boots up a virtual environment, runs the program,

706
00:31:35,059 --> 00:31:37,400
and I just sit back and watch what it does. If

707
00:31:37,400 --> 00:31:40,519
the simulated program halts. and prints an answer,

708
00:31:40,740 --> 00:31:44,700
my debugger says, yes, it halts. Problem solved,

709
00:31:44,859 --> 00:31:46,980
right? It sounds perfectly logical until you

710
00:31:46,980 --> 00:31:49,799
encounter the fatal flaw in simulation. Simulation

711
00:31:49,799 --> 00:31:51,900
works wonderfully if the target program actually

712
00:31:51,900 --> 00:31:54,299
halts. But what happens if the target program

713
00:31:54,299 --> 00:31:56,420
you are simulating contains an infinite loop?

714
00:31:56,539 --> 00:31:58,319
Well, my simulator is running the Toad, so my

715
00:31:58,319 --> 00:32:00,500
simulator also gets stuck in the loop. Exactly.

716
00:32:00,720 --> 00:32:02,880
Your simulator will run forever. You will sit

717
00:32:02,880 --> 00:32:04,839
there watching the screen until the end of time.

718
00:32:04,980 --> 00:32:07,539
And the critical issue is... You will never,

719
00:32:07,559 --> 00:32:10,119
ever know if the program is genuinely stuck in

720
00:32:10,119 --> 00:32:13,400
an infinite loop or if it is just a very complex

721
00:32:13,400 --> 00:32:15,660
calculation that needs one more minute to finish.

722
00:32:15,819 --> 00:32:17,839
Maybe it needs a trillion years to finish. Because

723
00:32:17,839 --> 00:32:20,200
I can't see the future, I can never confidently

724
00:32:20,200 --> 00:32:22,819
press the stop button and declare it's an infinite

725
00:32:22,819 --> 00:32:25,700
loop. I just have to keep waiting. Right. A true

726
00:32:25,700 --> 00:32:27,960
decider must always halt and give an answer.

727
00:32:28,500 --> 00:32:31,440
A simulator cannot guarantee it will ever halt.

728
00:32:31,829 --> 00:32:34,630
Therefore, simulation fails to solve the halting

729
00:32:34,630 --> 00:32:37,490
problem. Okay, so we can't do it by blindly simulating

730
00:32:37,490 --> 00:32:39,369
the code, but surely there is some other way.

731
00:32:39,509 --> 00:32:42,009
What if we don't run the code? What if we build

732
00:32:42,009 --> 00:32:44,930
a super advanced static analysis tool? It doesn't

733
00:32:44,930 --> 00:32:47,089
run the program. It just reads the source code,

734
00:32:47,309 --> 00:32:49,829
analyzes the logic loops, looks at the variables,

735
00:32:49,950 --> 00:32:52,430
and mathematically deduces whether it halts.

736
00:32:52,990 --> 00:32:56,630
AI tools do code analysis all the time now. How

737
00:32:56,630 --> 00:32:59,089
can we definitively prove that no such analytical

738
00:32:59,089 --> 00:33:02,720
tool could ever possibly exist? This is the pinnacle

739
00:33:02,720 --> 00:33:04,660
of the computability section, and it involves

740
00:33:04,660 --> 00:33:06,740
one of the most beautiful, elegant proofs in

741
00:33:06,740 --> 00:33:10,079
all of mathematics. It's called Cantor's diagonalization

742
00:33:10,079 --> 00:33:12,519
method. George Cantor originally developed this

743
00:33:12,519 --> 00:33:15,019
technique in the late 1800s to prove that some

744
00:33:15,019 --> 00:33:17,519
infinities are literally bigger than other infinities.

745
00:33:17,839 --> 00:33:20,480
Alan Turing adapted Cantor's brilliance and applied

746
00:33:20,480 --> 00:33:22,859
it to computer programs. This is a dense proof,

747
00:33:22,960 --> 00:33:25,099
so let's take it very slow. Let's try to visualize

748
00:33:25,099 --> 00:33:28,359
the math. Imagine a massive, infinite grid. A

749
00:33:28,359 --> 00:33:31,660
giant spreadsheet. Every single row in this spreadsheet

750
00:33:31,660 --> 00:33:34,220
represents a different possible Turing machine.

751
00:33:34,599 --> 00:33:37,420
Because programs are just strings of binary code,

752
00:33:37,680 --> 00:33:40,039
we can list them in alphabetical order. So row

753
00:33:40,039 --> 00:33:43,000
1 is program 1, row 2 is program 2, going down

754
00:33:43,000 --> 00:33:45,240
forever. This is every program that has ever

755
00:33:45,240 --> 00:33:47,569
been written or ever could be written. Okay,

756
00:33:47,589 --> 00:33:50,529
an infinitely deep spreadsheet of programs. Now,

757
00:33:50,529 --> 00:33:52,970
the columns across the top represent every possible

758
00:33:52,970 --> 00:33:55,250
input string you could ever feed into a program.

759
00:33:55,450 --> 00:33:58,630
Input 1, input 2, input 3, stretching infinitely

760
00:33:58,630 --> 00:34:01,450
to the right. So every cell in this grid represents

761
00:34:01,450 --> 00:34:03,789
a specific interaction, program X running on

762
00:34:03,789 --> 00:34:06,009
input Y. Exactly. Now, let's fill in the cells.

763
00:34:06,170 --> 00:34:09,090
For each cell, we put a 1 if the program halts

764
00:34:09,090 --> 00:34:12,030
on that input and a 0 if it loops forever. Okay,

765
00:34:12,110 --> 00:34:13,449
but we don't know the answers yet. That's the

766
00:34:13,449 --> 00:34:15,530
whole point of the problem. Right. But for the

767
00:34:15,530 --> 00:34:17,110
sake of the mathematical proof, we're going to

768
00:34:17,110 --> 00:34:18,949
use a technique called proof by contradiction.

769
00:34:19,230 --> 00:34:21,769
We are going to assume that the impossible machine

770
00:34:21,769 --> 00:34:24,829
actually exists. Suppose, just for a moment,

771
00:34:24,929 --> 00:34:28,230
that some genius at MIT actually built the perfect

772
00:34:28,230 --> 00:34:30,369
halting problem solver. Let's call it machine

773
00:34:30,369 --> 00:34:34,170
H. You hand H any program and any input, and

774
00:34:34,170 --> 00:34:36,989
it instantly spits out a 1, meaning it halts.

775
00:34:37,269 --> 00:34:39,869
or a zero, meaning it loops. It works perfectly

776
00:34:39,869 --> 00:34:42,570
every time. Okay, we have the magic debugger.

777
00:34:42,610 --> 00:34:44,989
It can instantly fill out every single cell in

778
00:34:44,989 --> 00:34:47,230
our infinite spreadsheet correctly. Sipster then

779
00:34:47,230 --> 00:34:49,610
walks us through how Turing used this magic machine

780
00:34:49,610 --> 00:34:52,750
to build a paradox. He said, let's use machine

781
00:34:52,750 --> 00:34:56,030
H as a subroutine to build a new, highly malicious

782
00:34:56,030 --> 00:34:58,329
Turing machine. Let's call this new machine D

783
00:34:58,329 --> 00:35:00,789
for Diagonal. How does the malicious machine

784
00:35:00,789 --> 00:35:03,539
work? Machine D takes a program as input. Let's

785
00:35:03,539 --> 00:35:05,559
say it takes program X. The very first thing

786
00:35:05,559 --> 00:35:08,059
D does is hand program X over to our magic solver

787
00:35:08,059 --> 00:35:11,039
H. It asks H, hey, what does program X do when

788
00:35:11,039 --> 00:35:13,360
it has fed its own source code as input? That's

789
00:35:13,360 --> 00:35:16,340
a bit recursive, but okay. H is magic, so H analyzes

790
00:35:16,340 --> 00:35:18,059
it and gives a perfect answer. It says either

791
00:35:18,059 --> 00:35:21,679
it halts or it loops. Now comes the malice. Machine

792
00:35:21,679 --> 00:35:24,019
D looks at the answer from H and deliberately

793
00:35:24,019 --> 00:35:26,139
does the exact opposite. Wait, what do you mean?

794
00:35:26,300 --> 00:35:30,389
If the magic solver H says program X halts, Our

795
00:35:30,389 --> 00:35:33,070
new machine D intentionally forces itself into

796
00:35:33,070 --> 00:35:36,389
an infinite loop. It refuses to halt. But if

797
00:35:36,389 --> 00:35:39,230
the magic solver H says program X loops forever,

798
00:35:39,550 --> 00:35:42,289
our machine D immediately halts and prints done.

799
00:35:42,550 --> 00:35:45,170
Okay, I see the mechanism. We have built a machine

800
00:35:45,170 --> 00:35:48,389
whose entire purpose is to spite the magic debugger,

801
00:35:48,409 --> 00:35:51,150
but it relies on the debugger to exist. Exactly.

802
00:35:51,150 --> 00:35:54,110
And now the trap closes. The grid is infinite.

803
00:35:54,170 --> 00:35:56,800
It contains every possible program. Therefore,

804
00:35:56,980 --> 00:35:59,320
our newly created malicious machine D must be

805
00:35:59,320 --> 00:36:01,519
somewhere on that list. It has a row in the spreadsheet.

806
00:36:01,820 --> 00:36:05,000
Let's say it's row 500. Fine. Row 500. Now we

807
00:36:05,000 --> 00:36:06,960
ask the ultimate question. What happens when

808
00:36:06,960 --> 00:36:09,019
we take our malicious machine D and we run it

809
00:36:09,019 --> 00:36:11,039
and we feed it its own source code as the input?

810
00:36:11,239 --> 00:36:13,820
Oh, no. I can feel my brain tying itself in a

811
00:36:13,820 --> 00:36:16,099
knot. Let me trace the logic. Trace it. Machine

812
00:36:16,099 --> 00:36:18,380
D starts up. It receives its own code. What is

813
00:36:18,380 --> 00:36:20,099
the first thing it does? The first thing it does

814
00:36:20,099 --> 00:36:23,039
is ask the magic solver H. It asks, hey H, what

815
00:36:23,039 --> 00:36:25,519
does machine D do when fed the code from machine

816
00:36:25,519 --> 00:36:28,820
D? And H has to give an answer. Suppose H says

817
00:36:28,820 --> 00:36:31,900
machine D will eventually halt. But the programming

818
00:36:31,900 --> 00:36:34,960
for D says do the opposite. So if H says it halts,

819
00:36:34,960 --> 00:36:37,960
D intentionally goes into an infinite loop, which

820
00:36:37,960 --> 00:36:41,099
means H was wrong. Okay, so suppose H realizes

821
00:36:41,099 --> 00:36:43,380
that and instead says machine D will loop forever.

822
00:36:43,730 --> 00:36:45,929
But if H says it loops, the programming for D

823
00:36:45,929 --> 00:36:49,010
commands it to immediately halt, so H is wrong

824
00:36:49,010 --> 00:36:52,130
again. The paradox explodes. The magic solver

825
00:36:52,130 --> 00:36:55,050
H is trapped in a logical contradiction. It is

826
00:36:55,050 --> 00:36:57,650
guaranteed, mathematically, to be wrong about

827
00:36:57,650 --> 00:37:00,449
machine D. But our initial assumption was that

828
00:37:00,449 --> 00:37:03,070
H was a perfect solver that is never wrong. The

829
00:37:03,070 --> 00:37:05,130
only way out of the paradox is to realize that

830
00:37:05,130 --> 00:37:07,670
the initial assumption was false. The magic solver

831
00:37:07,670 --> 00:37:10,619
H cannot exist. Precisely. We have mathematically

832
00:37:10,619 --> 00:37:12,579
proven that the halting problem is fundamentally

833
00:37:12,579 --> 00:37:15,880
undecidable. No algorithm, no AI, no supercomputer

834
00:37:15,880 --> 00:37:18,800
from the year 3000 will ever be able to reliably

835
00:37:18,800 --> 00:37:21,559
analyze any arbitrary code base and determine

836
00:37:21,559 --> 00:37:23,920
if it halts. It's not a limit of our engineering

837
00:37:23,920 --> 00:37:26,340
intelligence. It's a structural limit of logic

838
00:37:26,340 --> 00:37:29,659
itself. That is just staggering. It gives me

839
00:37:29,659 --> 00:37:32,199
chills. We proved that there is a wall in the

840
00:37:32,199 --> 00:37:34,280
universe of knowledge that we can never, ever

841
00:37:34,280 --> 00:37:37,809
climb over. And it gets deeper. Cantor's diagonalization

842
00:37:37,809 --> 00:37:40,429
doesn't just prove the halting problem is unsolvable.

843
00:37:40,690 --> 00:37:43,849
It reveals a terrifying truth about the ratio

844
00:37:43,849 --> 00:37:46,889
of problems to solutions. If you count up every

845
00:37:46,889 --> 00:37:49,309
single possible Turing machine, every program

846
00:37:49,309 --> 00:37:52,050
that could ever be written, you find it's a countably

847
00:37:52,050 --> 00:37:53,750
infinite set. You can put them in a list. One,

848
00:37:53,869 --> 00:37:56,250
two, three. But the number of problems, the number

849
00:37:56,250 --> 00:37:58,610
of possible languages. The set of all possible

850
00:37:58,610 --> 00:38:01,949
infinite sequences of zeros and ones is uncountably

851
00:38:01,949 --> 00:38:04,750
infinite. It's a bigger infinity. like the infinity

852
00:38:04,750 --> 00:38:07,510
of real numbers on a continuous line. Because

853
00:38:07,510 --> 00:38:09,670
the infinity of problems is strictly larger than

854
00:38:09,670 --> 00:38:12,130
the infinity of programs, we mathematically guarantee

855
00:38:12,130 --> 00:38:14,210
that we will run out of programs. Vastly more

856
00:38:14,210 --> 00:38:16,630
problems exist than there are programs to solve

857
00:38:16,630 --> 00:38:18,710
them. The overwhelming majority of mathematical

858
00:38:18,710 --> 00:38:21,530
truths are completely uncomputable. We are just

859
00:38:21,530 --> 00:38:24,429
exploring a tiny island of decidability in an

860
00:38:24,429 --> 00:38:27,269
infinite ocean of the unknown. That really reframes

861
00:38:27,269 --> 00:38:29,789
my entire view of computer science. We think

862
00:38:29,789 --> 00:38:31,809
we are masters of logic, but we're really just

863
00:38:31,809 --> 00:38:35,230
playing in a tiny sandbox. And once Sipser establishes

864
00:38:35,230 --> 00:38:38,269
this one major crack in the foundation, the undecidability

865
00:38:38,269 --> 00:38:41,190
of the halting problem, he introduces a technique

866
00:38:41,190 --> 00:38:43,789
to essentially spread that crack to other problems.

867
00:38:44,050 --> 00:38:46,670
This brings us to the concept of reducibility.

868
00:38:47,190 --> 00:38:50,730
Reducibility is a powerful analytical tool. Once

869
00:38:50,730 --> 00:38:52,389
you have found one problem that is impossible

870
00:38:52,389 --> 00:38:54,849
to solve, you can use it as a weapon to prove

871
00:38:54,849 --> 00:38:57,210
that other, seemingly unrelated problems are

872
00:38:57,210 --> 00:39:00,369
also impossible to solve. I try to explain reducibility

873
00:39:00,369 --> 00:39:03,250
as a chain reaction of impossibility. If I can

874
00:39:03,250 --> 00:39:05,210
take a new problem, let's call it problem B,

875
00:39:05,449 --> 00:39:07,909
and I can mathematically show that solving problem

876
00:39:07,909 --> 00:39:09,769
B would somehow accidentally give me the power

877
00:39:09,769 --> 00:39:12,389
to solve the halting problem, then problem B

878
00:39:12,389 --> 00:39:15,489
must also be impossible. That is the exact logic.

879
00:39:15,630 --> 00:39:19,510
If A reduces to B, and A is unsolvable, B must

880
00:39:19,510 --> 00:39:22,449
be unsolvable. And Sipster details a fascinating

881
00:39:22,449 --> 00:39:24,670
technique for creating these reductions using

882
00:39:24,670 --> 00:39:26,710
something called computation histories. Let's

883
00:39:26,710 --> 00:39:29,269
unpack that. What is a computation history? It

884
00:39:29,269 --> 00:39:31,170
is exactly what it sounds like. It's a complete

885
00:39:31,170 --> 00:39:34,889
audit trail. A computation history is a massive

886
00:39:34,889 --> 00:39:37,969
string of symbols that records every single state,

887
00:39:38,150 --> 00:39:40,769
every single tape position, and every single

888
00:39:40,769 --> 00:39:43,250
tape symbol of a Turing machine, step by step

889
00:39:43,250 --> 00:39:45,090
from the moment it starts to the moment it halts.

890
00:39:45,210 --> 00:39:48,309
It is a frozen snapshot of the entire computation

891
00:39:48,309 --> 00:39:50,949
process. Okay, so if a Turing machine halts,

892
00:39:51,010 --> 00:39:54,289
a finite computation history exists for that

893
00:39:54,289 --> 00:39:57,409
run. Yes. And Sipser uses this concept to reduce

894
00:39:57,409 --> 00:40:00,409
the terrifyingly abstract halting problem down

895
00:40:00,409 --> 00:40:03,079
to a seemingly innocent physical -sounding puzzle

896
00:40:03,079 --> 00:40:06,159
called the post -correspondence problem, or PCP.

897
00:40:06,280 --> 00:40:08,159
This is one of my favorite parts of the theory

898
00:40:08,159 --> 00:40:10,599
because PCP sounds so trivial. It sounds like

899
00:40:10,599 --> 00:40:12,900
a children's game. It's basically a domino matching

900
00:40:12,900 --> 00:40:14,920
puzzle. Can you explain the rules of the game?

901
00:40:15,320 --> 00:40:17,880
Imagine you are given a box of special dominoes.

902
00:40:18,119 --> 00:40:20,639
But instead of dots on the top and bottom halves,

903
00:40:20,940 --> 00:40:23,619
these dominoes have strings of text. For example,

904
00:40:23,699 --> 00:40:25,719
one domino might have the string A on the top

905
00:40:25,719 --> 00:40:27,960
and AB on the bottom. Another domino might have

906
00:40:27,960 --> 00:40:30,489
B on the top and A on the bottom. You have a

907
00:40:30,489 --> 00:40:32,809
finite set of these domino types, and you have

908
00:40:32,809 --> 00:40:35,230
an infinite supply of each type. Okay, I have

909
00:40:35,230 --> 00:40:37,670
my pile of text dominoes. What is the goal? The

910
00:40:37,670 --> 00:40:40,050
goal is to line up a sequence of these dominoes

911
00:40:40,050 --> 00:40:42,590
side by side on a table. You want to arrange

912
00:40:42,590 --> 00:40:44,570
them so that if you read all the letters across

913
00:40:44,570 --> 00:40:48,110
the top halves from left to right, it forms the

914
00:40:48,110 --> 00:40:50,829
exact same string of text as reading all the

915
00:40:50,829 --> 00:40:53,090
letters across the bottom halves from left to

916
00:40:53,090 --> 00:40:56,190
right. It sounds incredibly simple, like a puzzle

917
00:40:56,190 --> 00:40:58,409
you'd buy at an airport gift shop to kill time

918
00:40:58,409 --> 00:41:00,880
on a flight. Find the sequence that makes the

919
00:41:00,880 --> 00:41:04,179
top and bottom match. It does sound simple, but

920
00:41:04,179 --> 00:41:06,579
Sipser proves that it is mathematically impossible

921
00:41:06,579 --> 00:41:09,340
to write an algorithm that can universally solve

922
00:41:09,340 --> 00:41:11,639
this domino game. The problem is undecidable.

923
00:41:11,860 --> 00:41:13,860
And he proves this by connecting dominoes to

924
00:41:13,860 --> 00:41:16,440
Turing machines. How on earth do you reduce a

925
00:41:16,440 --> 00:41:18,960
computer program to a domino? It's a brilliant

926
00:41:18,960 --> 00:41:21,320
piece of mathematical encoding. Sipser shows

927
00:41:21,320 --> 00:41:23,380
how you can take the transition rules of any

928
00:41:23,380 --> 00:41:25,579
given Turing machine and translate those rules

929
00:41:25,579 --> 00:41:29,500
into a specific, custom set of dominoes. He designs

930
00:41:29,500 --> 00:41:31,440
the top and bottom strings of the dominoes so

931
00:41:31,440 --> 00:41:33,719
perfectly that the only way the top string will

932
00:41:33,719 --> 00:41:36,019
ever catch up and match the bottom string is

933
00:41:36,019 --> 00:41:38,300
if the sequence of dominoes physically spells

934
00:41:38,300 --> 00:41:41,219
out a valid step -by -step computation history

935
00:41:41,219 --> 00:41:44,000
of that Turing machine reaching an accept state.

936
00:41:44,239 --> 00:41:45,840
Wait, let me make sure I'm grasping this. You

937
00:41:45,840 --> 00:41:48,340
encode the machine into the tiles. If the game

938
00:41:48,340 --> 00:41:51,199
has a winning match, the match literally is the

939
00:41:51,199 --> 00:41:53,940
audit trail of the machine halting. Exactly.

940
00:41:54,960 --> 00:41:56,599
Imagine you did have an algorithm that could

941
00:41:56,599 --> 00:41:59,320
solve the domino game. Yeah. A PCP solver. You

942
00:41:59,320 --> 00:42:01,280
could take any computer program translated to

943
00:42:01,280 --> 00:42:03,559
dominoes, hand those dominoes to your PCP solver,

944
00:42:03,639 --> 00:42:06,059
and ask, is there a match? And if the solver

945
00:42:06,059 --> 00:42:08,340
says, yes, there is a match, that means a halting

946
00:42:08,340 --> 00:42:11,199
computation history exists, which means the program

947
00:42:11,199 --> 00:42:13,980
halts. And you just solved the halting problem.

948
00:42:14,980 --> 00:42:17,739
But we already rigorously proved that the halting

949
00:42:17,739 --> 00:42:21,280
problem is unsolvable. Therefore, your assumption

950
00:42:21,280 --> 00:42:24,000
that a PCP solver could exist must be false.

951
00:42:24,489 --> 00:42:26,809
By mapping the logic of Turing machines into

952
00:42:26,809 --> 00:42:29,469
the matching rules of strings, we prove that

953
00:42:29,469 --> 00:42:32,429
a children's puzzle is mathematically unsolvable

954
00:42:32,429 --> 00:42:35,550
by any computer. That is the sheer power of reducibility.

955
00:42:35,730 --> 00:42:38,530
It maps the terrain of the impossible. We create

956
00:42:38,530 --> 00:42:41,110
this hierarchy of unsolvability, proving that

957
00:42:41,110 --> 00:42:43,670
these diverse problems are secretly all the same

958
00:42:43,670 --> 00:42:45,789
impossible problem wearing different disguises.

959
00:42:46,179 --> 00:42:47,860
But as we reach the end of the computability

960
00:42:47,860 --> 00:42:50,559
section, Sipser takes us into some advanced topics

961
00:42:50,559 --> 00:42:52,960
where the undecidability gets incredibly weird.

962
00:42:53,460 --> 00:42:55,619
Specifically, when machines start talking about

963
00:42:55,619 --> 00:42:58,119
themselves. This leads us to the recursion theorem.

964
00:42:58,380 --> 00:43:00,400
The recursion theorem is profound because it

965
00:43:00,400 --> 00:43:02,320
addresses a fundamental philosophical paradox

966
00:43:02,320 --> 00:43:05,280
about self -reproduction. We look at biology

967
00:43:05,280 --> 00:43:07,639
and we see cells dividing and replicating themselves

968
00:43:07,639 --> 00:43:10,619
effortlessly. But when we try to apply that to

969
00:43:10,619 --> 00:43:13,320
mechanical logic, we hit a wall. Right, the paradox

970
00:43:13,320 --> 00:43:15,809
of the blueprint. If I want to build a factory

971
00:43:15,809 --> 00:43:18,150
that builds cars, the factory has to be much

972
00:43:18,150 --> 00:43:20,269
more complex than the car. It has to contain

973
00:43:20,269 --> 00:43:22,449
all the tools plus the blueprint for the car.

974
00:43:22,650 --> 00:43:24,570
So if I want to build a machine that prints a

975
00:43:24,570 --> 00:43:26,909
perfect replica of itself, the machine needs

976
00:43:26,909 --> 00:43:29,789
to contain a blueprint of itself. But that blueprint

977
00:43:29,789 --> 00:43:31,989
must also contain a blueprint of the blueprint

978
00:43:31,989 --> 00:43:35,530
and so on, leading to an infinite regress. The

979
00:43:35,530 --> 00:43:37,389
machine would have to be infinitely large to

980
00:43:37,389 --> 00:43:38,889
contain a description of its own description.

981
00:43:39,230 --> 00:43:41,929
That is the intuitive block. But mathematics

982
00:43:41,929 --> 00:43:45,000
provides an escape hatch. The recursion theorem

983
00:43:45,000 --> 00:43:47,980
proves rigorously that a Turing machine can indeed

984
00:43:47,980 --> 00:43:50,119
compute its own description and print itself

985
00:43:50,119 --> 00:43:53,219
out without needing an infinite regress of blueprints.

986
00:43:53,440 --> 00:43:55,719
How does it avoid the infinite loop? By splitting

987
00:43:55,719 --> 00:43:58,199
the task into two parts using self -reference.

988
00:43:58,300 --> 00:44:00,579
It designs a program with a part A and a part

989
00:44:00,579 --> 00:44:03,380
B. Part A's only job is to be a data payload.

990
00:44:03,699 --> 00:44:06,139
It contains the exact text of the instructions

991
00:44:06,139 --> 00:44:08,440
for part B. Okay, so part A is just a string

992
00:44:08,440 --> 00:44:11,119
of text. What does part B do? Part B contains

993
00:44:11,119 --> 00:44:13,760
the actual logic. The instructions in Part B

994
00:44:13,760 --> 00:44:16,880
say, take the text payload from Part A. Use that

995
00:44:16,880 --> 00:44:18,760
text to calculate what the code for Part A must

996
00:44:18,760 --> 00:44:21,400
look like. Then print out that calculated Part

997
00:44:21,400 --> 00:44:23,780
A code and follow it immediately by printing

998
00:44:23,780 --> 00:44:26,679
the payload text itself. Oh, it's like a snake

999
00:44:26,679 --> 00:44:29,190
eating its own tail. It doesn't contain a blueprint

1000
00:44:29,190 --> 00:44:31,130
of the whole machine. It contains a procedure

1001
00:44:31,130 --> 00:44:33,030
that knows how to construct the other half of

1002
00:44:33,030 --> 00:44:35,530
itself based on the data it was given. Exactly.

1003
00:44:35,630 --> 00:44:38,030
It is mathematically rigorous self -reference.

1004
00:44:38,230 --> 00:44:40,469
And this isn't just an abstract theory. It is

1005
00:44:40,469 --> 00:44:43,150
the foundational logic for how self -replicating

1006
00:44:43,150 --> 00:44:45,650
systems actually function in the real world.

1007
00:44:45,969 --> 00:44:48,750
If you have ever seen a quine in programming

1008
00:44:48,750 --> 00:44:51,550
a program whose only output is its own source

1009
00:44:51,550 --> 00:44:54,780
code, it uses this exact bipartite logic. It

1010
00:44:54,780 --> 00:44:56,659
is also the underlying theoretical framework

1011
00:44:56,659 --> 00:44:58,820
for how computer viruses reproduce and spread.

1012
00:44:59,099 --> 00:45:01,300
It's amazing how these abstract thought experiments

1013
00:45:01,300 --> 00:45:04,599
from the 1930s perfectly describe modern cybersecurity

1014
00:45:04,599 --> 00:45:07,699
threats. And Sipser doesn't stop at self -reference

1015
00:45:07,699 --> 00:45:09,760
in programs. He applies it back to mathematics

1016
00:45:09,760 --> 00:45:12,460
itself, exploring the decidability of logical

1017
00:45:12,460 --> 00:45:14,719
theories. This is where we touch on the ideas

1018
00:45:14,719 --> 00:45:17,960
of Kurt Gödel. Sipser asks, can we write an algorithm

1019
00:45:17,960 --> 00:45:20,239
to determine if a mathematical statement is true

1020
00:45:20,239 --> 00:45:23,239
or false? To answer that, we have to define the

1021
00:45:23,239 --> 00:45:25,539
universe of mathematics we're working in. Sipser

1022
00:45:25,539 --> 00:45:27,380
starts simple. Let's look at the mathematical

1023
00:45:27,380 --> 00:45:30,079
theory of natural numbers. But we only allow

1024
00:45:30,079 --> 00:45:32,360
the operation of addition. So we can ask questions

1025
00:45:32,360 --> 00:45:35,599
like, for every x and y, does there exist a z

1026
00:45:35,599 --> 00:45:38,679
such that x plus y equals z? Is that decidable?

1027
00:45:38,699 --> 00:45:40,880
Can a machine always answer statements like that?

1028
00:45:41,059 --> 00:45:43,880
Surprisingly, yes. Sipser shows that the theory

1029
00:45:43,880 --> 00:45:46,000
of natural numbers with only addition is completely

1030
00:45:46,000 --> 00:45:49,059
decidable. You can actually build complex, finite

1031
00:45:49,059 --> 00:45:51,699
automata that process the binary representations

1032
00:45:51,699 --> 00:45:55,219
of numbers and perfectly, algorithmically evaluate

1033
00:45:55,219 --> 00:45:58,059
any logical statement involving only addition.

1034
00:45:58,300 --> 00:46:01,079
It is a complete, decidable system. Okay, so

1035
00:46:01,079 --> 00:46:03,940
addition is safe. But mathematics is more than

1036
00:46:03,940 --> 00:46:06,860
just addition. What happens when we add multiplication

1037
00:46:06,860 --> 00:46:09,420
to the mix? The moment you introduce multiplication

1038
00:46:09,420 --> 00:46:12,500
alongside addition the entire system collapses

1039
00:46:12,500 --> 00:46:15,099
into undecidability. Why? What makes multiplication

1040
00:46:15,099 --> 00:46:17,440
so dangerous to logic? Because multiplication

1041
00:46:17,440 --> 00:46:20,519
gives the mathematical language vastly more expressive

1042
00:46:20,519 --> 00:46:23,579
power. Once you have both addition and multiplication

1043
00:46:23,579 --> 00:46:26,380
you have enough complexity to encode the step

1044
00:46:26,380 --> 00:46:28,320
-by -step behavior of Turing machines directly

1045
00:46:28,320 --> 00:46:31,139
into mathematical equations. You can formulate

1046
00:46:31,139 --> 00:46:34,289
a complex polynomial equation that essentially

1047
00:46:34,289 --> 00:46:36,869
acts as a simulation of a Turing machine. You

1048
00:46:36,869 --> 00:46:38,670
can create an equation that says this equation

1049
00:46:38,670 --> 00:46:41,269
has an integer root if and only if Turing machine

1050
00:46:41,269 --> 00:46:44,690
X halts. Oh, wow. We are reducing the halting

1051
00:46:44,690 --> 00:46:47,130
problem to algebra. Exactly. And because the

1052
00:46:47,130 --> 00:46:49,090
halting problem is fundamentally undecidable,

1053
00:46:49,269 --> 00:46:51,510
the mathematical theory of addition and multiplication

1054
00:46:51,510 --> 00:46:55,650
must also be undecidable. No algorithm can universally

1055
00:46:55,650 --> 00:46:58,130
determine if arithmetic statements are true or

1056
00:46:58,130 --> 00:47:01,170
false. This connects directly to Gödel's first

1057
00:47:01,170 --> 00:47:03,570
incompleteness theorem, which proved that in

1058
00:47:03,570 --> 00:47:05,769
any sufficiently complex mathematical system,

1059
00:47:05,909 --> 00:47:07,869
there will always be true statements that can

1060
00:47:07,869 --> 00:47:09,849
never be proven within the rules of that system.

1061
00:47:09,949 --> 00:47:12,389
The limits of computation are the limits of mathematics

1062
00:47:12,389 --> 00:47:15,190
itself. We are mapping the boundaries of absolute

1063
00:47:15,190 --> 00:47:18,409
truth. And that brings us to one final, fascinating

1064
00:47:18,409 --> 00:47:21,269
concept in this section. Kolmogorov complexity,

1065
00:47:21,590 --> 00:47:24,489
or descriptive complexity. If we can't compute

1066
00:47:24,489 --> 00:47:27,110
everything and we can't prove everything, how

1067
00:47:27,110 --> 00:47:29,190
do we measure the fundamental information contained

1068
00:47:29,190 --> 00:47:32,409
in a piece of data? It is a profound shift from

1069
00:47:32,409 --> 00:47:35,789
asking, can we compute it, to how much computation

1070
00:47:35,789 --> 00:47:38,909
does it contain? Sipser explains Kolmogorov complexity

1071
00:47:38,909 --> 00:47:41,989
by looking at strings of data. How do we mathematically

1072
00:47:41,989 --> 00:47:43,989
define whether a string is simple or complex

1073
00:47:43,989 --> 00:47:46,389
or random? Let's use an example. If I have a

1074
00:47:46,389 --> 00:47:49,369
string of a million zeros. intuitively, that

1075
00:47:49,369 --> 00:47:51,650
has very little information. It's highly predictable.

1076
00:47:51,869 --> 00:47:53,710
But if I have a string of a million completely

1077
00:47:53,710 --> 00:47:57,250
random coin flip bits, zeros and ones mixed chaotically,

1078
00:47:57,389 --> 00:47:59,849
that feels like it has a high amount of information.

1079
00:48:00,710 --> 00:48:03,650
But how do we define that rigorously without

1080
00:48:03,650 --> 00:48:07,010
relying on human intuition? The genius of Kolmogorov

1081
00:48:07,010 --> 00:48:09,760
complexity. is that it defines the information

1082
00:48:09,760 --> 00:48:13,400
content of a string as the length of the shortest

1083
00:48:13,400 --> 00:48:15,800
possible computer program that could generate

1084
00:48:15,800 --> 00:48:17,980
that string. Oh, that is such a clean definition.

1085
00:48:18,239 --> 00:48:20,559
Let's apply it. For the million zeros, I don't

1086
00:48:20,559 --> 00:48:22,480
need a million bits of code. I can just write

1087
00:48:22,480 --> 00:48:25,659
a tiny program in Python. Print zero times one

1088
00:48:25,659 --> 00:48:27,860
million. The program is maybe 20 characters long.

1089
00:48:28,199 --> 00:48:30,639
Because a tiny program can generate a massive

1090
00:48:30,639 --> 00:48:33,000
string, the Kolmogorov complexity of that string

1091
00:48:33,000 --> 00:48:35,360
is extremely low. It is highly compressible.

1092
00:48:35,619 --> 00:48:37,360
Exactly. The pattern allows for compression.

1093
00:48:37,579 --> 00:48:39,679
But what about the purely random string of a

1094
00:48:39,679 --> 00:48:42,820
million coin flips? By definition, true randomness

1095
00:48:42,820 --> 00:48:45,179
has no pattern. There is no mathematical shortcut

1096
00:48:45,179 --> 00:48:47,980
to generate it. So if I want a program to output

1097
00:48:47,980 --> 00:48:51,579
that specific random sequence, the shortest possible

1098
00:48:51,579 --> 00:48:53,760
program I could write would just be a print statement

1099
00:48:53,760 --> 00:48:56,900
containing the entire sequence with all million

1100
00:48:56,900 --> 00:48:59,280
digits hard -coded in. Precisely. The shortest

1101
00:48:59,280 --> 00:49:01,099
program to generate the string is essentially

1102
00:49:01,099 --> 00:49:04,420
as long as the string itself. It is incompressible.

1103
00:49:04,900 --> 00:49:07,880
And that incompressibility is the algorithmic

1104
00:49:07,880 --> 00:49:10,380
definition of randomness. The length of that

1105
00:49:10,380 --> 00:49:13,219
shortest program is the true absolute measure

1106
00:49:13,219 --> 00:49:16,320
of the string's information content. Okay, let's

1107
00:49:16,320 --> 00:49:18,940
take a deep breath. We have been in the theoretical

1108
00:49:18,940 --> 00:49:21,679
stratosphere. We have mapped the absolute edge

1109
00:49:21,679 --> 00:49:24,260
of what is possible to compute. We know there

1110
00:49:24,260 --> 00:49:26,480
are problems that algorithms simply cannot solve

1111
00:49:26,480 --> 00:49:29,099
and truths that math cannot prove. But let's

1112
00:49:29,099 --> 00:49:31,239
bring it back to reality. Here is the practical

1113
00:49:31,239 --> 00:49:34,219
problem. Just because a Turing machine can theoretically

1114
00:49:34,219 --> 00:49:36,940
solve a problem doesn't mean it is useful. If

1115
00:49:36,940 --> 00:49:39,440
a machine takes 100 trillion years to calculate

1116
00:49:39,440 --> 00:49:42,000
the optimal route for a delivery truck, the fact

1117
00:49:42,000 --> 00:49:44,760
that it is decidable is useless. And that transition

1118
00:49:44,760 --> 00:49:47,840
from the purely theoretical, can it be solved,

1119
00:49:48,099 --> 00:49:51,420
to the brutally practical, how long will it take?

1120
00:49:51,639 --> 00:49:53,960
Launches us into part three of Sipser's text,

1121
00:49:54,340 --> 00:49:57,000
complexity theory. We are now entering the race

1122
00:49:57,000 --> 00:49:59,480
against time and space. We enter chapter seven,

1123
00:49:59,639 --> 00:50:02,840
time complexity. And the foundational tool we

1124
00:50:02,840 --> 00:50:05,980
use to talk about time is big O notation. If

1125
00:50:05,980 --> 00:50:07,780
a listener has ever sat through a software engineering

1126
00:50:07,780 --> 00:50:10,900
job interview, they know big O. It is the lingua

1127
00:50:10,900 --> 00:50:13,679
franca of algorithm analysis. Big O notation

1128
00:50:13,679 --> 00:50:16,199
is a mathematical tool that allows us to ignore

1129
00:50:16,199 --> 00:50:18,920
the small, messy, hardware -specific details.

1130
00:50:19,260 --> 00:50:21,820
We don't care if one processor is a bit faster

1131
00:50:21,820 --> 00:50:24,480
than another or if a loop takes three low -level

1132
00:50:24,480 --> 00:50:26,980
instructions versus five. Big O strips all that

1133
00:50:26,980 --> 00:50:29,039
away to focus strictly on asymptotic behavior.

1134
00:50:29,260 --> 00:50:31,320
That's us. How does the time required to solve

1135
00:50:31,320 --> 00:50:33,420
the problem scale as the size of the input grows

1136
00:50:33,420 --> 00:50:35,780
toward infinity? Right. If I double the size

1137
00:50:35,780 --> 00:50:37,860
of the input list, does the algorithm take twice

1138
00:50:37,860 --> 00:50:40,400
as long? That's linear time O of n. Does it take

1139
00:50:40,400 --> 00:50:42,940
four times as long? That's quadratic time O of

1140
00:50:42,940 --> 00:50:45,559
n squared. Or does the time double every time

1141
00:50:45,559 --> 00:50:48,159
I add a single item? That's exponential time

1142
00:50:48,159 --> 00:50:50,800
O of 2 to the n, and that is a nightmare. Using

1143
00:50:50,800 --> 00:50:53,500
this asymptotic lens, Sipser introduces the two

1144
00:50:53,500 --> 00:50:56,019
most important classes in all of complexity theory,

1145
00:50:56,400 --> 00:50:59,719
the class P and the class NP. Let's break these

1146
00:50:59,719 --> 00:51:02,579
down carefully. The class P stands for polynomial

1147
00:51:02,579 --> 00:51:05,530
time. These are the problems that can be solved

1148
00:51:05,530 --> 00:51:08,010
on a standard deterministic Turing machine in

1149
00:51:08,010 --> 00:51:10,809
a time that scales as a polynomial like n squared

1150
00:51:10,809 --> 00:51:13,789
or n cubed. Things like sorting a list of names

1151
00:51:13,789 --> 00:51:16,190
alphabetically or finding the shortest path through

1152
00:51:16,190 --> 00:51:19,070
a maze. The time it takes scales reasonably as

1153
00:51:19,070 --> 00:51:21,550
the problem gets bigger. For all practical purposes,

1154
00:51:21,789 --> 00:51:23,989
p roughly corresponds to the class of problems

1155
00:51:23,989 --> 00:51:26,429
that are efficiently solvable by computers. And

1156
00:51:26,429 --> 00:51:29,090
then there is the mysterious class np. np stands

1157
00:51:29,090 --> 00:51:32,409
for non -deterministic polynomial time. Technically,

1158
00:51:32,590 --> 00:51:34,469
these are problems that could be solved in polynomial

1159
00:51:34,469 --> 00:51:37,090
time if we had that magical parallel universe

1160
00:51:37,090 --> 00:51:39,469
branching, non -deterministic Turing machine

1161
00:51:39,469 --> 00:51:41,550
we talked about earlier. But we don't have magical

1162
00:51:41,550 --> 00:51:43,750
guessing machines. We only have deterministic

1163
00:51:43,750 --> 00:51:46,670
computers. So how should we think about NT in

1164
00:51:46,670 --> 00:51:49,369
the real world? We have to shift our perspective

1165
00:51:49,369 --> 00:51:53,719
from solving to verifying. The class NP represents

1166
00:51:53,719 --> 00:51:56,679
the set of all problems where if someone magically

1167
00:51:56,679 --> 00:51:58,800
hands you the correct answer, you can write an

1168
00:51:58,800 --> 00:52:01,420
algorithm to verify that the answer is indeed

1169
00:52:01,420 --> 00:52:04,539
correct. And that verification process runs very

1170
00:52:04,539 --> 00:52:07,559
fast in polynomial time. This is a crucial distinction.

1171
00:52:07,659 --> 00:52:10,590
I love framing it this way. P is the class of

1172
00:52:10,590 --> 00:52:12,369
problems where you can easily write a book from

1173
00:52:12,369 --> 00:52:15,090
scratch. NP is the class of problems where if

1174
00:52:15,090 --> 00:52:16,949
someone hands you a finished manuscript, you

1175
00:52:16,949 --> 00:52:19,449
can easily read it to verify if it is grammatically

1176
00:52:19,449 --> 00:52:22,150
correct. It is a vast difference between finding

1177
00:52:22,150 --> 00:52:24,670
a solution and verifying a solution. Give me

1178
00:52:24,670 --> 00:52:27,449
a concrete example. Let's look at a giant Sudoku

1179
00:52:27,449 --> 00:52:31,750
puzzle. Not a 9x9 grid, but a massive 10 ,000x10

1180
00:52:31,750 --> 00:52:34,889
,000 grid. Solving that from scratch is a nightmare.

1181
00:52:35,170 --> 00:52:37,309
You have to guess a number, follow the implications,

1182
00:52:37,750 --> 00:52:40,389
hit a dead end, erase hundreds of boxes, and

1183
00:52:40,389 --> 00:52:42,969
try again. It takes an agonizing amount of time

1184
00:52:42,969 --> 00:52:45,730
to find the solution. But if a genius walks into

1185
00:52:45,730 --> 00:52:47,710
the room and hands you a completely filled out

1186
00:52:47,710 --> 00:52:50,010
grid, you don't need to be a genius to check

1187
00:52:50,010 --> 00:52:51,869
their work. You just write a simple script that

1188
00:52:51,869 --> 00:52:53,730
scans the rows and columns to make sure there

1189
00:52:53,730 --> 00:52:56,030
are no duplicate numbers. Verifying the solution

1190
00:52:56,030 --> 00:52:58,820
takes seconds. Therefore, Sudoku is in the class

1191
00:52:58,820 --> 00:53:01,780
NP. The verification is fast, even if the solving

1192
00:53:01,780 --> 00:53:04,539
is slow. That is a brilliant analogy, and it

1193
00:53:04,539 --> 00:53:06,539
leads directly to the most famous, most important

1194
00:53:06,539 --> 00:53:08,440
unsolved problem in all of computer science,

1195
00:53:08,619 --> 00:53:11,639
and arguably all of modern mathematics, the P

1196
00:53:11,639 --> 00:53:14,219
versus NP question. Are finding and verifying

1197
00:53:14,219 --> 00:53:17,300
actually the same thing? Does P equal NP? That

1198
00:53:17,300 --> 00:53:20,199
is the million -dollar question. Literally, the

1199
00:53:20,199 --> 00:53:22,559
Clay Mathematics Institute offers a million dollars

1200
00:53:22,559 --> 00:53:26,429
to anyone who can prove it. If P equals NP, it

1201
00:53:26,429 --> 00:53:28,889
means that for every single problem where a solution

1202
00:53:28,889 --> 00:53:31,869
is easy to verify, there exists a brilliant hidden

1203
00:53:31,869 --> 00:53:34,869
mathematical shortcut to actually find that solution

1204
00:53:34,869 --> 00:53:37,570
easily from scratch. It implies that solving

1205
00:53:37,570 --> 00:53:39,969
Sudoku is fundamentally no harder than checking

1206
00:53:39,969 --> 00:53:42,289
Sudoku. We just aren't smart enough to know the

1207
00:53:42,289 --> 00:53:44,150
trick yet. And the implications of that would

1208
00:53:44,150 --> 00:53:47,269
change human history. If P equals NP and solving

1209
00:53:47,269 --> 00:53:49,789
is as easy as verifying, we could cure diseases

1210
00:53:49,789 --> 00:53:52,250
practically overnight by rapidly calculating

1211
00:53:52,250 --> 00:53:54,789
perfect protein folds. We could perfectly optimize

1212
00:53:54,789 --> 00:53:57,170
global logistics and eliminate supply chain waste.

1213
00:53:57,489 --> 00:54:00,710
But we could also break every single password

1214
00:54:00,710 --> 00:54:03,030
and encryption system on Earth because cryptography

1215
00:54:03,030 --> 00:54:05,170
relies on finding the key being much harder than

1216
00:54:05,170 --> 00:54:08,110
verifying the key. But let's be real. Almost

1217
00:54:08,110 --> 00:54:10,150
every computer scientist on Earth believes that

1218
00:54:10,150 --> 00:54:13,190
P does not equal NP. We intuitively know that

1219
00:54:13,190 --> 00:54:15,030
creating a masterpiece is harder than recognizing

1220
00:54:15,030 --> 00:54:17,889
one. But why is it so incredibly hard to prove

1221
00:54:17,889 --> 00:54:20,489
mathematically? To understand the sheer gravity

1222
00:54:20,489 --> 00:54:24,349
of why PVC NP is so hard to resolve, Sipser introduces

1223
00:54:24,349 --> 00:54:28,309
a concept that is truly breathtaking. NP completeness.

1224
00:54:28,590 --> 00:54:31,489
In the early 1970s, researchers Stephen Cook

1225
00:54:31,489 --> 00:54:34,210
and Leonid Levin independently proved something

1226
00:54:34,210 --> 00:54:36,630
miraculous, known as the Cook -Levin theorem.

1227
00:54:36,889 --> 00:54:39,090
They proved that there is a master problem within

1228
00:54:39,090 --> 00:54:43,250
the class NP. It's called SAT. or Boolean satisfiability.

1229
00:54:43,469 --> 00:54:47,110
What exactly is the SAT problem? SAT asks a fundamental

1230
00:54:47,110 --> 00:54:50,510
logic question. Imagine a complex Boolean formula,

1231
00:54:50,710 --> 00:54:53,550
a massive algebraic equation using logical variables

1232
00:54:53,550 --> 00:54:56,030
like X, Y, and Z, connected by logical operators

1233
00:54:56,030 --> 00:54:59,849
like A and D or R, and not two. The problem asks...

1234
00:55:00,050 --> 00:55:02,070
Is there any possible combination of assigning

1235
00:55:02,070 --> 00:55:04,150
true or false to these variables that makes the

1236
00:55:04,150 --> 00:55:06,710
entire massive formula evaluate to true? It's

1237
00:55:06,710 --> 00:55:09,130
like finding a master key for a complex set of

1238
00:55:09,130 --> 00:55:11,510
interlocking digital locks. Flipping the switch

1239
00:55:11,510 --> 00:55:13,849
to true forces that switch to false, which triggers

1240
00:55:13,849 --> 00:55:16,489
this AND gate. It's a massive puzzle. Exactly.

1241
00:55:16,710 --> 00:55:19,030
Clearly, if someone hands you a list of true

1242
00:55:19,030 --> 00:55:21,949
-false settings, it is trivial to plug them in

1243
00:55:21,949 --> 00:55:25,139
and verify if the equation equals true. So SAT

1244
00:55:25,139 --> 00:55:28,139
is an NP. But Cook and Levin prove something

1245
00:55:28,139 --> 00:55:31,039
unbelievable. They prove that every single other

1246
00:55:31,039 --> 00:55:34,159
problem in NP, every puzzle, every routing problem,

1247
00:55:34,340 --> 00:55:36,760
every scheduling problem, every protein folding

1248
00:55:36,760 --> 00:55:39,539
simulation can be mathematically translated quickly

1249
00:55:39,539 --> 00:55:42,559
and efficiently into a SAT problem. Let me make

1250
00:55:42,559 --> 00:55:44,639
sure I am fully grasping the weight of this.

1251
00:55:44,800 --> 00:55:47,880
They prove that SAT is a universal translator

1252
00:55:47,880 --> 00:55:50,670
for computational hardness. If you have a problem

1253
00:55:50,670 --> 00:55:52,429
about packing a shipping container perfectly,

1254
00:55:52,730 --> 00:55:54,869
you can run the rules of your shipping container

1255
00:55:54,869 --> 00:55:57,929
through an algorithm and out pops a massive Boolean

1256
00:55:57,929 --> 00:56:00,289
formula. And if you solve that Boolean formula,

1257
00:56:00,530 --> 00:56:02,750
the true -false answers magically translate back

1258
00:56:02,750 --> 00:56:04,929
into exactly how to pack your boxes. That is

1259
00:56:04,929 --> 00:56:06,989
exactly what it means. And the consequence is

1260
00:56:06,989 --> 00:56:09,570
world -shattering. If you could find a fast polynomial

1261
00:56:09,570 --> 00:56:12,449
time algorithm to solve SAT from scratch, you

1262
00:56:12,449 --> 00:56:14,409
could use this translation process to solve all

1263
00:56:14,409 --> 00:56:17,579
NP problems quickly. SAT is the keystone. If

1264
00:56:17,579 --> 00:56:19,360
you solve SAT, you solve everything. You prove

1265
00:56:19,360 --> 00:56:22,440
P equals NP. We call SAT an NP -complete problem.

1266
00:56:22,719 --> 00:56:25,480
And once Quick and Levin proved that SAT was

1267
00:56:25,480 --> 00:56:28,539
the master problem, a floodgate opened. Researchers

1268
00:56:28,539 --> 00:56:30,800
started looking at thousands of other problems

1269
00:56:30,800 --> 00:56:33,639
and found that they are also NP -complete. Yes.

1270
00:56:33,980 --> 00:56:37,780
Richard Karp published his famous 21 NP -complete

1271
00:56:37,780 --> 00:56:41,219
problems shortly after, finding the largest interconnected

1272
00:56:41,219 --> 00:56:43,400
group of mutual friends in a social network,

1273
00:56:43,639 --> 00:56:46,650
the clique problem. Figuring out if a subset

1274
00:56:46,650 --> 00:56:48,929
of numbers in a ledger adds up to exactly zero,

1275
00:56:49,170 --> 00:56:52,210
subset sum, finding a route for a delivery driver

1276
00:56:52,210 --> 00:56:55,650
that visits every city exactly once without backtracking

1277
00:56:55,650 --> 00:56:58,309
the Hamiltonian path problem, they're all NP

1278
00:56:58,309 --> 00:57:01,130
-complete. It's a terrifying web of intractability.

1279
00:57:01,489 --> 00:57:03,829
We've proven that thousands of seemingly unrelated

1280
00:57:03,829 --> 00:57:06,530
problems across economics, biology, and logistics

1281
00:57:06,530 --> 00:57:09,309
are secretly all the exact same mathematical

1282
00:57:09,309 --> 00:57:11,909
problem wearing different disguises. If you solve

1283
00:57:11,909 --> 00:57:14,170
one, you solve them all. If one is hard, they

1284
00:57:14,170 --> 00:57:16,539
are all hard. But as we rage against these limits

1285
00:57:16,539 --> 00:57:19,000
of time, Sipser reminds us that time isn't our

1286
00:57:19,000 --> 00:57:21,239
only constraint in the physical world. Sometimes

1287
00:57:21,239 --> 00:57:23,460
the clock is ticking, but we run out of whiteboard

1288
00:57:23,460 --> 00:57:26,019
space first. We run out of memory. And so in

1289
00:57:26,019 --> 00:57:29,380
Chapter 8, Sipser shifts gears to space complexity.

1290
00:57:30,110 --> 00:57:33,030
We leave the domain of time and focus on PSBase,

1291
00:57:33,030 --> 00:57:35,070
the class of problems that can be solved using

1292
00:57:35,070 --> 00:57:37,349
a polynomial amount of memory on the Turing tape.

1293
00:57:37,510 --> 00:57:39,949
When we were looking at time, we had this massive,

1294
00:57:40,150 --> 00:57:43,730
agonizing unknown. Does non -determinism add

1295
00:57:43,730 --> 00:57:46,989
power? We don't know if P equals NP, but when

1296
00:57:46,989 --> 00:57:49,969
we shift to space, to memory, Sipster gives us

1297
00:57:49,969 --> 00:57:52,809
a definitive mathematical answer. He introduces

1298
00:57:52,809 --> 00:57:55,090
Savage's theorem, and we need to explain exactly

1299
00:57:55,090 --> 00:57:57,070
how this works, so let's dive into the mechanism.

1300
00:57:57,550 --> 00:58:00,150
Savage's theorem is a brilliant piece of recursive

1301
00:58:00,150 --> 00:58:02,730
logic. It proves that a deterministic Turing

1302
00:58:02,730 --> 00:58:05,010
machine can simulate a non -deterministic Turing

1303
00:58:05,010 --> 00:58:07,469
machine using incredibly little extra memory.

1304
00:58:08,260 --> 00:58:10,719
Specifically, if a non -deterministic machine

1305
00:58:10,719 --> 00:58:12,900
needs a certain amount of space to solve a problem,

1306
00:58:13,119 --> 00:58:15,400
the deterministic machine only needs that amount

1307
00:58:15,400 --> 00:58:18,679
of space squared. A squared increase. So if the

1308
00:58:18,679 --> 00:58:20,780
magical guessing machine uses 10 megabytes of

1309
00:58:20,780 --> 00:58:23,639
RAM, my standard laptop only needs 100 megabytes

1310
00:58:23,639 --> 00:58:25,900
to simulate it perfectly. How does it do that

1311
00:58:25,900 --> 00:58:28,519
without taking infinite time or space? It uses

1312
00:58:28,519 --> 00:58:30,619
a divide -and -conquer strategy, specifically

1313
00:58:30,619 --> 00:58:33,579
designed to reuse space. The problem is essentially

1314
00:58:33,579 --> 00:58:36,559
pathfinding. Can the machine get from the start

1315
00:58:36,559 --> 00:58:39,139
state to the accept state within, say, a million

1316
00:58:39,139 --> 00:58:41,860
steps? The deterministic machine doesn't try

1317
00:58:41,860 --> 00:58:44,960
to track every single path simultaneously. Instead,

1318
00:58:45,300 --> 00:58:47,559
it guesses the exact middle point of the computation.

1319
00:58:47,900 --> 00:58:51,320
It says, is there some halfway state? State C,

1320
00:58:51,539 --> 00:58:54,300
such that I can get from start to C in 500 ,000

1321
00:58:54,300 --> 00:58:57,280
steps. AD, I can get from C to accept in 500

1322
00:58:57,280 --> 00:58:59,619
,000 steps. Okay, it splits the problem in half.

1323
00:58:59,880 --> 00:59:02,199
Now, it recursively asks the same question about

1324
00:59:02,199 --> 00:59:04,219
the first half. It guesses a quarter waypoint.

1325
00:59:04,400 --> 00:59:06,940
And it keeps drilling down until it's just asking,

1326
00:59:07,079 --> 00:59:09,440
can I get from this state to the next state in

1327
00:59:09,440 --> 00:59:12,099
one step? Which is trivial to check in the rulebook.

1328
00:59:12,300 --> 00:59:14,059
But wait, if it's drilling down and saving all

1329
00:59:14,059 --> 00:59:15,980
these halfway points, doesn't it run out of memory

1330
00:59:15,980 --> 00:59:18,889
storing the path? This is the genius of space

1331
00:59:18,889 --> 00:59:21,809
reuse. Once the machine successfully proves it

1332
00:59:21,809 --> 00:59:24,309
can get from start to the halfway point, it erases

1333
00:59:24,309 --> 00:59:26,909
all the scratchpad memory it used to prove that

1334
00:59:26,909 --> 00:59:29,389
first half. It only keeps the fact that start

1335
00:59:29,389 --> 00:59:32,650
to halfway is true. Then it reuses that exact

1336
00:59:32,650 --> 00:59:35,550
same blank tape to start calculating the path

1337
00:59:35,550 --> 00:59:38,489
from halfway to accept. Oh, space is reusable.

1338
00:59:38,530 --> 00:59:40,989
Time is gone once you spend it, but memory can

1339
00:59:40,989 --> 00:59:43,389
be wiped and overwritten. Exactly. Because it

1340
00:59:43,389 --> 00:59:45,570
continually erases and reuses the pay for each

1341
00:59:45,570 --> 00:59:48,409
branch of the recursive tree, the maximum depth

1342
00:59:48,409 --> 00:59:50,130
of the memory required is just the number of

1343
00:59:50,130 --> 00:59:52,530
times you halved the problem, multiplied by the

1344
00:59:52,530 --> 00:59:55,409
space needed to store one state. Mathematically,

1345
00:59:55,469 --> 00:59:58,150
this works out to a squared relationship. Savage's

1346
00:59:58,150 --> 01:00:00,710
theorem definitively proved that NPS space exactly

1347
01:00:00,710 --> 01:00:04,260
equals PS space. Non -determinism does not give

1348
01:00:04,260 --> 01:00:06,440
you fundamentally new classes of memory power.

1349
01:00:06,699 --> 01:00:08,900
That is so elegant. And just like we had NT -complete

1350
01:00:08,900 --> 01:00:10,800
problems serving as the master keys for time

1351
01:00:10,800 --> 01:00:12,840
complexity, we have PS -based complete problems

1352
01:00:12,840 --> 01:00:15,420
for memory. Sipser discusses the ultimate memory

1353
01:00:15,420 --> 01:00:18,179
problem, TQBF, or quantified Boolean formulas.

1354
01:00:18,980 --> 01:00:22,260
TQBF is like the SAT problem on steroids. Instead

1355
01:00:22,260 --> 01:00:24,880
of just asking, is there any true -false setting

1356
01:00:24,880 --> 01:00:28,159
that works, TQBF adds quantifiers like for all.

1357
01:00:28,659 --> 01:00:31,340
And there exists. It asks questions like, is

1358
01:00:31,340 --> 01:00:34,280
it true that for all values of X, there exists

1359
01:00:34,280 --> 01:00:37,699
a value of Y such that this massive formula is

1360
01:00:37,699 --> 01:00:39,840
true? This sounds exactly like the logic of a

1361
01:00:39,840 --> 01:00:42,820
two -player game, like chess or Go. It is exactly

1362
01:00:42,820 --> 01:00:45,719
the logic of a finite, perfect information game.

1363
01:00:46,030 --> 01:00:48,070
When you're looking for a winning strategy in

1364
01:00:48,070 --> 01:00:50,449
chess, you're mathematically asking, does there

1365
01:00:50,449 --> 01:00:52,949
exist a move I can make such that for all moves

1366
01:00:52,949 --> 01:00:54,730
my opponent might make in response, there exists

1367
01:00:54,730 --> 01:00:57,210
a counter move I can make, and so on, cascading

1368
01:00:57,210 --> 01:00:59,190
down to a checkmate. Because you have to explore

1369
01:00:59,190 --> 01:01:01,269
every single possible response your opponent

1370
01:01:01,269 --> 01:01:03,710
could make, the game tree branches out exponentially.

1371
01:01:04,389 --> 01:01:06,929
Exploring all those futures takes an unimaginable

1372
01:01:06,929 --> 01:01:09,789
exponential amount of time. But because of the

1373
01:01:09,789 --> 01:01:12,230
space reuse trick we just learned, finding that

1374
01:01:12,230 --> 01:01:14,610
winning strategy requires very little memory.

1375
01:01:15,070 --> 01:01:17,170
You just evaluate one single path down to the

1376
01:01:17,170 --> 01:01:19,309
end of the game, record if it's a win or loss,

1377
01:01:19,510 --> 01:01:21,949
erase the board, and evaluate the next path.

1378
01:01:22,309 --> 01:01:24,590
You only ever need enough memory to store the

1379
01:01:24,590 --> 01:01:26,550
current layout of the chessboard and the sequence

1380
01:01:26,550 --> 01:01:28,670
of moves you are currently checking. Therefore,

1381
01:01:28,809 --> 01:01:31,150
finding a universal winning strategy for games

1382
01:01:31,150 --> 01:01:34,329
like this is PS case complete. It requires polynomial

1383
01:01:34,329 --> 01:01:37,949
space, but likely exponential time. Sipser also

1384
01:01:37,949 --> 01:01:41,989
touches on the extreme low end of memory. Sublinear

1385
01:01:41,989 --> 01:01:44,670
space. Can you solve problems using less memory

1386
01:01:44,670 --> 01:01:46,710
than it takes to even store the question itself?

1387
01:01:47,110 --> 01:01:50,150
He talks about the classes L and NL, which stand

1388
01:01:50,150 --> 01:01:53,050
for logarithmic space. You can, but you have

1389
01:01:53,050 --> 01:01:55,030
to restrict the machine. You have to treat the

1390
01:01:55,030 --> 01:01:57,449
input tape as read -only. The machine can scan

1391
01:01:57,449 --> 01:01:59,849
the input, but it can't write on it. It only

1392
01:01:59,849 --> 01:02:02,670
has a tiny microscopic scratchpad tape of logarithmic

1393
01:02:02,670 --> 01:02:04,909
size to work with. Think of it like trying to

1394
01:02:04,909 --> 01:02:07,349
solve a maze printed on a giant poster, but you

1395
01:02:07,349 --> 01:02:09,269
are only allowed to use a tiny post -it note

1396
01:02:09,269 --> 01:02:11,969
to keep track of your coordinates. And even in

1397
01:02:11,969 --> 01:02:15,150
this incredibly restricted space, Sipser presents

1398
01:02:15,150 --> 01:02:19,369
a shocking proof. NL exactly equals con NL. Yes,

1399
01:02:19,469 --> 01:02:21,449
the theorem proven by Emmerman and Solipseni.

1400
01:02:21,550 --> 01:02:24,429
It means that the problem of finding a path through

1401
01:02:24,429 --> 01:02:28,010
a graph using only a tiny post -it note of memory

1402
01:02:28,010 --> 01:02:31,369
is exactly as computationally difficult as proving

1403
01:02:31,369 --> 01:02:35,389
that no path exists. For a very long time, computer

1404
01:02:35,389 --> 01:02:37,829
scientists assumed that proving a negative verifying

1405
01:02:37,829 --> 01:02:40,469
that a path is impossible would require exploring

1406
01:02:40,469 --> 01:02:42,789
the whole map and therefore demand more space.

1407
01:02:43,210 --> 01:02:45,190
But through a very clever counting technique,

1408
01:02:45,409 --> 01:02:47,710
they proved it doesn't. Which brings us to the

1409
01:02:47,710 --> 01:02:50,849
agonizing realization of Chapter 9, intractability.

1410
01:02:51,090 --> 01:02:53,550
We have spent an hour talking about these NP

1411
01:02:53,550 --> 01:02:56,190
-complete and PS -space -complete problems. We

1412
01:02:56,190 --> 01:02:58,130
strongly suspect they are impossibly hard to

1413
01:02:58,130 --> 01:03:00,050
solve quickly, but we haven't actually proven

1414
01:03:00,050 --> 01:03:02,670
it. I have to ask the frustrating question. Can

1415
01:03:02,670 --> 01:03:04,750
we actually prove that any problem is hard, or

1416
01:03:04,750 --> 01:03:06,989
are we just historically bad at writing algorithms?

1417
01:03:07,309 --> 01:03:09,210
It's a fair question, and the answer is yes,

1418
01:03:09,329 --> 01:03:11,710
we can prove certain things are hard. Sipser

1419
01:03:11,710 --> 01:03:14,250
shows how using the hierarchy theorems, these

1420
01:03:14,250 --> 01:03:16,409
theorems are essentially Cantor's diagonalization

1421
01:03:16,409 --> 01:03:19,090
argument again, but scaled by resources. How

1422
01:03:19,090 --> 01:03:21,750
does that work? We artificially construct a problem

1423
01:03:21,750 --> 01:03:24,730
that is specifically designed to be computable

1424
01:03:24,730 --> 01:03:28,269
in, say, n -cubed time, but completely impossible

1425
01:03:28,269 --> 01:03:31,250
to compute in n -squared time. We proved that

1426
01:03:31,250 --> 01:03:33,250
by giving a Turing machine demonstrably more

1427
01:03:33,250 --> 01:03:35,909
time or more space, it could definitively solve

1428
01:03:35,909 --> 01:03:38,929
a strictly larger class of problems. We can mathematically

1429
01:03:38,929 --> 01:03:41,289
prove that certain generalized board games played

1430
01:03:41,289 --> 01:03:43,869
on an infinitely growing board require an exponential

1431
01:03:43,869 --> 01:03:47,530
amount of memory to solve. That is, EXPS space

1432
01:03:47,530 --> 01:03:51,110
completeness. We know they are hard. So if we

1433
01:03:51,110 --> 01:03:53,190
have the mathematical tools to prove that artificially

1434
01:03:53,190 --> 01:03:56,409
constructed problems are hard, Why is the PVSNP

1435
01:03:56,409 --> 01:03:59,110
question about real world problems so notoriously

1436
01:03:59,110 --> 01:04:01,869
difficult to prove? Why has no one claimed the

1437
01:04:01,869 --> 01:04:04,710
million dollar prize? Sipser answers this brilliantly

1438
01:04:04,710 --> 01:04:07,050
by explaining a concept called relativization.

1439
01:04:07,309 --> 01:04:09,489
Think back to all the foundational proofs we've

1440
01:04:09,489 --> 01:04:11,550
discussed, the halting problem, the hierarchy

1441
01:04:11,550 --> 01:04:14,289
theorems. They all relied on diagonalization.

1442
01:04:14,690 --> 01:04:16,670
They all treated Turing machines like black boxes.

1443
01:04:16,789 --> 01:04:19,130
They just fed inputs in, looked at the outputs,

1444
01:04:19,309 --> 01:04:21,170
and found contradictions. Right. The malicious

1445
01:04:21,170 --> 01:04:23,730
machine D didn't care how the magic solver H

1446
01:04:23,730 --> 01:04:25,650
worked internally. It just looked at the final

1447
01:04:25,650 --> 01:04:27,690
answer and flipped it. Relativization reveals

1448
01:04:27,690 --> 01:04:30,030
the devastating weakness of the black box approach.

1449
01:04:30,809 --> 01:04:32,849
Computer scientists show that if you use black

1450
01:04:32,849 --> 01:04:35,630
box techniques, you can invent theoretical mathematical

1451
01:04:35,630 --> 01:04:38,920
universes. We call them oracles. You can construct

1452
01:04:38,920 --> 01:04:41,360
one oracle universe where the mathematics dictate

1453
01:04:41,360 --> 01:04:44,420
that P equals NP. And you can construct a different

1454
01:04:44,420 --> 01:04:46,800
oracle universe where P strictly does not equal

1455
01:04:46,800 --> 01:04:49,480
NP. And because diagonalization only looks at

1456
01:04:49,480 --> 01:04:51,719
inputs and outputs, it works exactly the same

1457
01:04:51,719 --> 01:04:54,070
way in... both of those universes. Precisely.

1458
01:04:54,389 --> 01:04:56,329
Diagonalization is blind to the difference between

1459
01:04:56,329 --> 01:04:58,909
a universe where P equals NP and one where it

1460
01:04:58,909 --> 01:05:01,670
doesn't. Therefore, any mathematical proof that

1461
01:05:01,670 --> 01:05:04,210
relies solely on diagonalization will never be

1462
01:05:04,210 --> 01:05:06,789
powerful enough to solve the PV says NP question

1463
01:05:06,789 --> 01:05:09,570
in our reality. We hit a methodological dead

1464
01:05:09,570 --> 01:05:12,190
end. We need entirely new mathematics. We have

1465
01:05:12,190 --> 01:05:14,469
to pry open the black box and look at the wiring.

1466
01:05:14,650 --> 01:05:16,969
And looking at the wiring leads to the study

1467
01:05:16,969 --> 01:05:19,170
of circuit complexity as a new path forward.

1468
01:05:19,659 --> 01:05:21,500
Instead of looking at Turing machines and paper

1469
01:05:21,500 --> 01:05:24,179
tapes, we look at Boolean circuits' actual logical

1470
01:05:24,179 --> 01:05:26,699
gates, like A and D and OR are wired together.

1471
01:05:26,980 --> 01:05:30,000
We try to prove a physical limit, arguing that

1472
01:05:30,000 --> 01:05:32,500
a circuit must physically possess a certain minimum

1473
01:05:32,500 --> 01:05:35,300
number of logic gates to solve the SAT problem.

1474
01:05:35,579 --> 01:05:37,500
It's a completely different angle of attack,

1475
01:05:37,679 --> 01:05:39,460
trying to build a lower bound of complexity.

1476
01:05:39,980 --> 01:05:42,380
Exactly. And that shift toward modern research

1477
01:05:42,380 --> 01:05:44,599
brings us to the final frontier, Chapter 10,

1478
01:05:44,800 --> 01:05:47,800
Advanced Topics in Complexity Theory. This is

1479
01:05:47,800 --> 01:05:50,119
where Sipser gives us a taste of the active bleeding

1480
01:05:50,119 --> 01:05:53,179
edge of computer science. He starts with probabilistic

1481
01:05:53,179 --> 01:05:56,059
algorithms, the complexity class BPP. This is

1482
01:05:56,059 --> 01:05:58,739
wild to me. How does flipping a coin help a computer?

1483
01:05:58,980 --> 01:06:01,380
We spent this whole time defining deterministic

1484
01:06:01,380 --> 01:06:04,179
machines that follow strict rules. Why introduce

1485
01:06:04,179 --> 01:06:07,260
chaos? Because sometimes, sacrificing a tiny

1486
01:06:07,260 --> 01:06:10,260
bit of absolute mathematical certainty yields

1487
01:06:10,260 --> 01:06:13,570
massive... World altering gains in speed. If

1488
01:06:13,570 --> 01:06:15,929
you allow your algorithm to have access to a

1489
01:06:15,929 --> 01:06:18,230
random number generator to toss coins during

1490
01:06:18,230 --> 01:06:20,750
its execution, you can solve certain problems

1491
01:06:20,750 --> 01:06:23,110
highly efficiently that we have no idea how to

1492
01:06:23,110 --> 01:06:25,010
solve deterministically. Give me an example.

1493
01:06:25,269 --> 01:06:28,369
Prime numbers. For decades, the best practical

1494
01:06:28,369 --> 01:06:31,110
way to check if a massive 500 -digit number was

1495
01:06:31,110 --> 01:06:34,510
prime was to run a probabilistic algorithm. The

1496
01:06:34,510 --> 01:06:37,030
algorithm tosses some digital coins, does some

1497
01:06:37,030 --> 01:06:39,429
modular arithmetic based on those random numbers,

1498
01:06:39,510 --> 01:06:42,530
and outputs an answer. It's overwhelmingly likely

1499
01:06:42,530 --> 01:06:44,750
this is prime, or it is definitely composite.

1500
01:06:45,050 --> 01:06:46,989
But it could be wrong. Yes, there is a theoretical

1501
01:06:46,989 --> 01:06:49,670
chance of a false positive. But you just run

1502
01:06:49,670 --> 01:06:52,150
the algorithm again and again. Every time you

1503
01:06:52,150 --> 01:06:54,389
run it and it says prime, the probability of

1504
01:06:54,389 --> 01:06:57,230
it being wrong drops exponentially. After running

1505
01:06:57,230 --> 01:06:59,690
it 100 times, the mathematical chance of it being

1506
01:06:59,690 --> 01:07:01,949
wrong is less than the chance of a meteor striking

1507
01:07:01,949 --> 01:07:04,539
your server farm right now. For all practical

1508
01:07:04,539 --> 01:07:07,039
engineering purposes, probability creates certainty.

1509
01:07:07,219 --> 01:07:09,340
From there, we touch on alternation, leading

1510
01:07:09,340 --> 01:07:12,219
to the polynomial time hierarchy, and then into

1511
01:07:12,219 --> 01:07:14,659
one of the most conceptually fascinating areas,

1512
01:07:15,079 --> 01:07:18,360
interactive proof systems. This ties beautifully

1513
01:07:18,360 --> 01:07:20,340
back to what we said earlier about the class

1514
01:07:20,340 --> 01:07:23,219
NP being about verifying a written proof. But

1515
01:07:23,219 --> 01:07:25,719
what if the proof isn't a static book? What if

1516
01:07:25,719 --> 01:07:28,420
it's a conversation? In an interactive proof,

1517
01:07:28,719 --> 01:07:31,619
you have two theoretical entities. You have a

1518
01:07:31,619 --> 01:07:33,639
prover. who is an all -powerful computational

1519
01:07:33,639 --> 01:07:36,280
entity with infinite time and resources. And

1520
01:07:36,280 --> 01:07:39,039
you have a verifier, who is a weak, standard,

1521
01:07:39,119 --> 01:07:42,500
polynomial -time computer representing us. The

1522
01:07:42,500 --> 01:07:44,599
prover is trying to convince the skeptical verifier

1523
01:07:44,599 --> 01:07:46,840
that a certain mathematical statement is true.

1524
01:07:47,059 --> 01:07:49,099
And we need to walk through how a zero -knowledge

1525
01:07:49,099 --> 01:07:50,980
interactive prove actually works, because it

1526
01:07:50,980 --> 01:07:53,340
sounds like magic. How do you prove something

1527
01:07:53,340 --> 01:07:55,440
to me without showing me the proof? The classic

1528
01:07:55,440 --> 01:07:57,659
physical analogy is the two colored balls. Imagine

1529
01:07:57,659 --> 01:07:59,980
I have two billiard balls. One is red and one

1530
01:07:59,980 --> 01:08:03,150
is green. But you, the verifier, are completely

1531
01:08:03,150 --> 01:08:05,550
colorblind. To you, they both look identical

1532
01:08:05,550 --> 01:08:08,369
gray. Okay. I am the weak verifier. I can't tell

1533
01:08:08,369 --> 01:08:11,909
them apart. I am the powerful prover. I claim

1534
01:08:11,909 --> 01:08:14,530
to you these balls are different colors. You

1535
01:08:14,530 --> 01:08:16,310
want me to prove it, but I refuse to tell you

1536
01:08:16,310 --> 01:08:18,109
which one is red and which is green. I want to

1537
01:08:18,109 --> 01:08:20,250
give you zero knowledge, but still convince you

1538
01:08:20,250 --> 01:08:22,630
they are different. How do we do that interactively?

1539
01:08:22,869 --> 01:08:24,750
You take the two balls and hold them behind your

1540
01:08:24,750 --> 01:08:27,609
back. You bring one out and show it to me. I

1541
01:08:27,609 --> 01:08:30,090
look at it. Then you put it back behind your

1542
01:08:30,090 --> 01:08:33,130
back. Here's where the randomness comes in. You

1543
01:08:33,130 --> 01:08:36,409
secretly flip a coin. Based on the coin flip,

1544
01:08:36,609 --> 01:08:38,550
you either switch the balls behind your back

1545
01:08:38,550 --> 01:08:41,409
or you leave them in the same hands. Okay, I

1546
01:08:41,409 --> 01:08:44,050
randomly switch them or don't. Then I bring one

1547
01:08:44,050 --> 01:08:46,909
out again and say, did I switch them? Because

1548
01:08:46,909 --> 01:08:49,970
I can see color. If you switch them, the new

1549
01:08:49,970 --> 01:08:52,550
ball is a different color. And I say, yes, you

1550
01:08:52,550 --> 01:08:55,670
switched. If you didn't, I say no. I can answer

1551
01:08:55,670 --> 01:08:57,529
perfectly every time. But wait, if they were

1552
01:08:57,529 --> 01:08:59,409
actually the same color and I was just trying

1553
01:08:59,409 --> 01:09:00,810
to trick you, you wouldn't be able to tell if

1554
01:09:00,810 --> 01:09:02,369
I switched them or not. You would just have to

1555
01:09:02,369 --> 01:09:05,350
guess. Exactly. If I am lying and they are both

1556
01:09:05,350 --> 01:09:08,010
green, I only have a 50 % chance of guessing

1557
01:09:08,010 --> 01:09:10,090
correctly. If we do this experiment once, maybe

1558
01:09:10,090 --> 01:09:12,930
I just got lucky. But if we repeat this interactive

1559
01:09:12,930 --> 01:09:15,810
game 50 times in a row and I get the answer correct

1560
01:09:15,810 --> 01:09:18,329
every single time. The probability of you guessing

1561
01:09:18,329 --> 01:09:20,930
a coin flip 50 times in a row is astronomically

1562
01:09:20,930 --> 01:09:25,010
small. One in a quadrillion. So I, the weak colorblind

1563
01:09:25,010 --> 01:09:27,789
verifier, am now mathematically convinced beyond

1564
01:09:27,789 --> 01:09:29,689
a shadow of a doubt that the balls are different

1565
01:09:29,689 --> 01:09:31,529
colors, even though you never told me which was

1566
01:09:31,529 --> 01:09:34,109
which. That is the power of interactive probability.

1567
01:09:34,750 --> 01:09:37,289
And the landmark theorem in this field states

1568
01:09:37,289 --> 01:09:41,590
that IP equals PS base. By allowing the verifier

1569
01:09:41,590 --> 01:09:44,909
to toss coins and ask random questions and demanding

1570
01:09:44,909 --> 01:09:47,050
the prover answer them dynamically over multiple

1571
01:09:47,050 --> 01:09:49,750
rounds, we get an explosion of verification power.

1572
01:09:49,989 --> 01:09:52,130
You can interactively prove membership for any

1573
01:09:52,130 --> 01:09:54,029
problem that can be solved in polynomial space,

1574
01:09:54,289 --> 01:09:56,369
even if writing down the static proof would take

1575
01:09:56,369 --> 01:09:58,069
more paper than there are atoms in the universe.

1576
01:09:58,350 --> 01:10:00,729
It is stunning how deep the rabbit hole goes.

1577
01:10:01,390 --> 01:10:03,810
Sipser wraps up the book by touching on parallel

1578
01:10:03,810 --> 01:10:06,409
computation, what happens when you use millions

1579
01:10:06,409 --> 01:10:09,390
of processors at once, and finally, cryptography.

1580
01:10:09,770 --> 01:10:12,470
And I think cryptography is the perfect capstone

1581
01:10:12,470 --> 01:10:15,130
for this entire journey. I agree. Throughout

1582
01:10:15,130 --> 01:10:17,609
this entire text, we have been banging our heads

1583
01:10:17,609 --> 01:10:20,149
against these mathematical walls. We found problems

1584
01:10:20,149 --> 01:10:21,909
that are undecidable. We found problems that

1585
01:10:21,909 --> 01:10:25,529
are NP -complete and likely intractable. We view

1586
01:10:25,529 --> 01:10:28,050
these as limitations, as failures of computation.

1587
01:10:28,649 --> 01:10:32,029
But cryptography flips the script. Sipser shows

1588
01:10:32,029 --> 01:10:34,649
how these exact mathematical limitations are

1589
01:10:34,649 --> 01:10:37,289
the very foundation of modern security. We take

1590
01:10:37,289 --> 01:10:39,649
the intractability. And we weaponize it to protect

1591
01:10:39,649 --> 01:10:42,609
ourselves. Yes. Modern cryptography relies entirely

1592
01:10:42,609 --> 01:10:44,829
on the assumption that certain mathematical functions

1593
01:10:44,829 --> 01:10:47,430
are trapdoor functions. A trapdoor function is

1594
01:10:47,430 --> 01:10:49,149
an operation that is very easy to compute in

1595
01:10:49,149 --> 01:10:51,729
one direction, but computationally intractable

1596
01:10:51,729 --> 01:10:54,430
to reverse engineer unless you possess a secret

1597
01:10:54,430 --> 01:10:57,510
key. It's the PVS -NP discrepancy in action.

1598
01:10:57,789 --> 01:11:01,250
Exactly. Multiplying two massive 500 -digit prime

1599
01:11:01,250 --> 01:11:03,609
numbers together is easy. A standard computer

1600
01:11:03,609 --> 01:11:05,729
can do it in milliseconds. That is the verifying

1601
01:11:05,729 --> 01:11:09,130
part. But taking that massive... 1 ,000 -digit

1602
01:11:09,130 --> 01:11:11,430
result and trying to factor it back into its

1603
01:11:11,430 --> 01:11:13,890
original primes, that is believed to be intractable.

1604
01:11:14,050 --> 01:11:16,289
It would take a supercomputer billions of years

1605
01:11:16,289 --> 01:11:18,890
to guess the answer from scratch. The security

1606
01:11:18,890 --> 01:11:21,350
of your passwords, the safety of your bank accounts,

1607
01:11:21,489 --> 01:11:24,090
the encrypted data of the entire global internet,

1608
01:11:24,310 --> 01:11:27,029
it all rests precariously on the assumption that

1609
01:11:27,029 --> 01:11:29,130
finding is fundamentally harder than verifying.

1610
01:11:29,579 --> 01:11:32,279
If someone wakes up tomorrow and proves P equals

1611
01:11:32,279 --> 01:11:34,840
MP, or if someone builds a quantum computer that

1612
01:11:34,840 --> 01:11:37,239
circumvents these specific algorithms, the entire

1613
01:11:37,239 --> 01:11:39,699
architecture of digital privacy evaporates instantly.

1614
01:11:40,159 --> 01:11:42,539
We rely on the hardness of the universe to keep

1615
01:11:42,539 --> 01:11:46,079
our secrets safe. Wow. Okay. Let's try to pull

1616
01:11:46,079 --> 01:11:49,119
back and recap this epic journey. We started

1617
01:11:49,119 --> 01:11:51,020
at the absolute bottom with simple mechanical

1618
01:11:51,020 --> 01:11:53,970
turnstiles. the deterministic finite automata

1619
01:11:53,970 --> 01:11:55,970
completely devoid of memory, just reacting to

1620
01:11:55,970 --> 01:11:57,909
the present. We realized they couldn't count,

1621
01:11:58,029 --> 01:12:00,170
so we added a spring -loaded cafeteria stack

1622
01:12:00,170 --> 01:12:02,510
to get push -down automata, allowing us to process

1623
01:12:02,510 --> 01:12:04,390
the nested grammars of programming languages.

1624
01:12:04,689 --> 01:12:07,210
Then we abandoned the restrictions. We rolled

1625
01:12:07,210 --> 01:12:08,970
out the endless paper tape of the Turing machine,

1626
01:12:09,270 --> 01:12:12,590
giving our model random access to infinite memory.

1627
01:12:12,949 --> 01:12:15,949
We discovered the Church -Turing thesis, establishing

1628
01:12:15,949 --> 01:12:18,390
this simple machine as the ultimate boundary

1629
01:12:18,390 --> 01:12:20,989
of all algorithms. And once we found the boundary,

1630
01:12:21,109 --> 01:12:23,750
we found what lies beyond it. We confronted the

1631
01:12:23,750 --> 01:12:26,390
halting problem and used Cantor's infinite diagonal

1632
01:12:26,390 --> 01:12:29,289
grid to mathematically prove the existence of

1633
01:12:29,289 --> 01:12:32,550
the undecidable. We realized that the ocean of

1634
01:12:32,550 --> 01:12:35,829
unsolvable truths is vastly larger than our little

1635
01:12:35,829 --> 01:12:38,489
island of computation. Finally, we brought it

1636
01:12:38,489 --> 01:12:40,430
back to the physical reality of time and space.

1637
01:12:40,989 --> 01:12:43,949
We defined the efficient world of P, the verifiable

1638
01:12:43,949 --> 01:12:47,149
world of NP, and the universal master keys of

1639
01:12:47,149 --> 01:12:50,329
NP completeness. We saw how space can be reused

1640
01:12:50,329 --> 01:12:53,270
through Savage's recursive halving, and how randomness

1641
01:12:53,270 --> 01:12:56,050
and interactive dialogue can allow a weak verifier

1642
01:12:56,050 --> 01:12:58,590
to interrogate an omnipotent prover. We have

1643
01:12:58,590 --> 01:13:01,449
truly mapped the theoretical DNA of all computation.

1644
01:13:01,789 --> 01:13:03,590
But as we wrap this up, I want to leave our listeners

1645
01:13:03,590 --> 01:13:05,329
with something to chew on, something beyond the

1646
01:13:05,329 --> 01:13:07,750
textbook. If we take everything we just talked

1647
01:13:07,750 --> 01:13:09,449
about and connect it to the physical universe,

1648
01:13:09,689 --> 01:13:13,029
we reach a very strange conclusion. It is a profound,

1649
01:13:13,130 --> 01:13:16,210
almost unsettling philosophical thought. Think

1650
01:13:16,210 --> 01:13:18,510
about the fundamental laws of physics. They dictate

1651
01:13:18,510 --> 01:13:21,130
how particles interact, how forces propagate

1652
01:13:21,130 --> 01:13:24,930
step by step over time. Cause and effect. If

1653
01:13:24,930 --> 01:13:27,270
the universe operates on a strict set of rule

1654
01:13:27,270 --> 01:13:29,489
-based interactions, isn't the physical universe

1655
01:13:29,489 --> 01:13:32,029
itself just a massive, incredibly complex Turing

1656
01:13:32,029 --> 01:13:34,750
machine? It is calculating the next moment of

1657
01:13:34,750 --> 01:13:36,949
reality based on the state of the current moment.

1658
01:13:37,130 --> 01:13:39,689
And if the universe is a computer? Then the absolute

1659
01:13:39,689 --> 01:13:42,029
limits of computation we just explored are not

1660
01:13:42,029 --> 01:13:44,270
just limits of human software. They are limits

1661
01:13:44,270 --> 01:13:46,869
of physical reality. The theory dictates that

1662
01:13:46,869 --> 01:13:48,750
there must be physical phenomena happening right

1663
01:13:48,750 --> 01:13:52,069
now that are, by mathematical definition, computationally

1664
01:13:52,069 --> 01:13:54,750
undecidable. There may be complex systems and

1665
01:13:54,750 --> 01:13:56,930
fluid dynamics or quantum mechanics or biological

1666
01:13:56,930 --> 01:13:58,850
evolution that are fundamentally unpredictable.

1667
01:13:59,250 --> 01:14:02,090
Not because we lack the data. Not because our

1668
01:14:02,090 --> 01:14:04,289
sensors aren't good enough. But because the universe

1669
01:14:04,289 --> 01:14:06,609
itself cannot algorithmically resolve the outcome

1670
01:14:06,609 --> 01:14:09,649
faster than the event actually happens. The future,

1671
01:14:09,750 --> 01:14:12,850
in some aspects, is mathematically uncomputable

1672
01:14:12,850 --> 01:14:15,090
until it arrives. That is going to keep me up

1673
01:14:15,090 --> 01:14:17,689
tonight. The math isn't just in the machine.

1674
01:14:17,810 --> 01:14:20,569
The math is the fabric of the universe itself.

1675
01:14:21,180 --> 01:14:23,420
The limits of the Turing tape are the limits

1676
01:14:23,420 --> 01:14:26,750
of the cosmos. I want to encourage you, the listener,

1677
01:14:26,850 --> 01:14:28,930
to keep questioning the true nature of information.

1678
01:14:29,510 --> 01:14:31,569
Tomorrow, when you look at your phone or read

1679
01:14:31,569 --> 01:14:33,989
a string of text or wait for a complicated algorithm

1680
01:14:33,989 --> 01:14:37,470
to load a video, remember the invisible, immutable,

1681
01:14:37,569 --> 01:14:39,770
theoretical architecture that is holding it all

1682
01:14:39,770 --> 01:14:42,229
together. You are now armed with the ultimate

1683
01:14:42,229 --> 01:14:44,869
shortcut to being profoundly well -informed about

1684
01:14:44,869 --> 01:14:47,210
the true nature of logic. It has been an absolute

1685
01:14:47,210 --> 01:14:49,829
pleasure unpacking this vast landscape with you.

1686
01:14:49,909 --> 01:14:51,970
Keep exploring, keep questioning the systems

1687
01:14:51,970 --> 01:14:53,710
around you, and we'll see you on the next Deep

1688
01:14:53,710 --> 01:14:53,989
Dive.