1
00:00:00,000 --> 00:00:02,399
You know, usually when we talk about human language,

2
00:00:02,600 --> 00:00:06,660
there is this expectation of, well, organic messiness.

3
00:00:06,740 --> 00:00:10,380
Right. We tend to view language through like.

4
00:00:10,830 --> 00:00:14,269
a biological lens. You think of it as this living,

5
00:00:14,310 --> 00:00:17,010
breathing, evolving organism that shifts with

6
00:00:17,010 --> 00:00:19,949
culture and slang and historical migrations.

7
00:00:20,109 --> 00:00:22,109
Absolutely. It feels very tied to sociology.

8
00:00:22,429 --> 00:00:25,609
Yeah, exactly. You point to a weird grammatical

9
00:00:25,609 --> 00:00:27,969
quirk in English, like how the plural of goose

10
00:00:27,969 --> 00:00:30,489
is geese, but the plural of moose isn't meese.

11
00:00:30,589 --> 00:00:32,329
And you just shrug and say, well, that's just

12
00:00:32,329 --> 00:00:34,450
how people talk. It's human nature. It feels

13
00:00:34,450 --> 00:00:37,009
incredibly fluid from the inside. Like when we

14
00:00:37,009 --> 00:00:39,780
speak. We certainly don't feel like we are solving

15
00:00:39,780 --> 00:00:42,619
equations. You know, we feel like we are just

16
00:00:42,619 --> 00:00:45,000
expressing this chaotic stream of consciousness.

17
00:00:45,140 --> 00:00:47,520
Right. It is the absolute definition of organic

18
00:00:47,520 --> 00:00:50,119
chaos. But then you step into the world of theoretical

19
00:00:50,119 --> 00:00:52,799
linguistics and early computer science, and suddenly

20
00:00:52,799 --> 00:00:56,039
that biological messy lens is completely shattered.

21
00:00:56,219 --> 00:00:58,000
Oh, completely. It's a total paradigm shift.

22
00:00:58,119 --> 00:01:00,200
We are no longer looking at a cultural artifact

23
00:01:00,200 --> 00:01:02,420
or a sociological phenomenon. We are looking

24
00:01:02,420 --> 00:01:06,269
at a machine. like a cold, hard calculating machine.

25
00:01:06,650 --> 00:01:10,769
And that shift in perspective is, it's jarring

26
00:01:10,769 --> 00:01:13,689
for a lot of people at first, but it is necessary.

27
00:01:14,030 --> 00:01:16,290
Really necessary. But to truly understand the

28
00:01:16,290 --> 00:01:18,269
underlying architecture of how we communicate,

29
00:01:18,489 --> 00:01:21,170
we have to look at language as a rigid, formal

30
00:01:21,170 --> 00:01:24,870
system governed by absolute laws. We have to

31
00:01:24,870 --> 00:01:27,269
treat words and sentences as nothing more than

32
00:01:27,269 --> 00:01:29,730
strings of symbols subject to strict mathematical

33
00:01:29,730 --> 00:01:33,140
operations. And whether you are a computer scientist

34
00:01:33,140 --> 00:01:35,840
trying to build the next generation of artificial

35
00:01:35,840 --> 00:01:39,599
intelligence or maybe a linguistics nerd or just

36
00:01:39,599 --> 00:01:42,379
insanely curious about how the human mind actually

37
00:01:42,379 --> 00:01:44,659
organizes its thoughts before you even open your

38
00:01:44,659 --> 00:01:47,540
mouth, today's deep dive is going to fundamentally

39
00:01:47,540 --> 00:01:50,019
change how you see every single sentence you

40
00:01:50,019 --> 00:01:52,420
speak. I really believe it will. The text we're

41
00:01:52,420 --> 00:01:54,659
looking at today is just that important. It really

42
00:01:54,659 --> 00:01:57,379
is. Today, we are opening up a truly foundational

43
00:01:57,379 --> 00:02:01,060
text. We are looking at Noam Chomsky's 1959 paper

44
00:02:01,060 --> 00:02:03,920
on certain formal properties of grammars. The

45
00:02:03,920 --> 00:02:06,879
impact of this specific paper is, frankly, difficult

46
00:02:06,879 --> 00:02:09,439
to overstate. It sits squarely at this intersection

47
00:02:09,439 --> 00:02:12,039
of information theory, computer science, and

48
00:02:12,039 --> 00:02:15,280
linguistics. Because before this era, linguistics

49
00:02:15,280 --> 00:02:18,289
was largely about categorizing words almost like

50
00:02:18,289 --> 00:02:20,870
botany you know like collecting specimens of

51
00:02:20,870 --> 00:02:22,949
language and pinning them to a board just labeling

52
00:02:22,949 --> 00:02:26,909
things noun verb adjective exactly but this paper

53
00:02:26,909 --> 00:02:29,250
this paper translates the architecture of the

54
00:02:29,250 --> 00:02:32,629
mind Into algebra. Okay, let's unpack this. Our

55
00:02:32,629 --> 00:02:35,810
mission today is highly ambitious. We are going

56
00:02:35,810 --> 00:02:39,430
to break down this notoriously dense, mathematically

57
00:02:39,430 --> 00:02:43,310
rigorous paper concept by concept. We're going

58
00:02:43,310 --> 00:02:45,650
to trace the dependencies, explore the general

59
00:02:45,650 --> 00:02:48,030
theories, and we are going to translate these

60
00:02:48,030 --> 00:02:51,569
heavy symbolic theorems into intuitive aha moments.

61
00:02:51,770 --> 00:02:53,930
That's the goal. Right. We want to understand

62
00:02:53,930 --> 00:02:56,509
the exact mathematical boundaries of human thought

63
00:02:56,509 --> 00:02:58,250
without getting lost in the chalkboard equations.

64
00:02:58,810 --> 00:03:01,289
So to start us off, if we are treating language

65
00:03:01,289 --> 00:03:04,050
like a machine, how do we even define what a

66
00:03:04,050 --> 00:03:06,110
language is? Well, the foundational definition

67
00:03:06,110 --> 00:03:08,710
here requires us to strip away all meaning, emotion,

68
00:03:08,990 --> 00:03:12,030
and context. Which is hard to do. It is. But

69
00:03:12,030 --> 00:03:14,909
mathematically speaking, Chomsky defines a language

70
00:03:14,909 --> 00:03:17,930
simply as a collection of sentences. And each

71
00:03:17,930 --> 00:03:20,610
of those sentences is a finite length, constructed

72
00:03:20,610 --> 00:03:23,629
from a finite alphabet, or a finite vocabulary

73
00:03:23,629 --> 00:03:25,919
of symbols. Okay, let me pause there just to

74
00:03:25,919 --> 00:03:28,080
make sure I'm visualizing this correctly. The

75
00:03:28,080 --> 00:03:30,099
finite part makes sense. I mean, the English

76
00:03:30,099 --> 00:03:32,460
dictionary is thick, but it's finite. There's

77
00:03:32,460 --> 00:03:34,580
a set number of words. Right. And the alphabet

78
00:03:34,580 --> 00:03:38,599
is finite 26 letters. And any single sentence

79
00:03:38,599 --> 00:03:42,159
I speak has to be finite in length, if only because

80
00:03:42,159 --> 00:03:44,340
I eventually have to stop talking to take a breath.

81
00:03:45,039 --> 00:03:47,439
The physical constraints are finite, yes. But

82
00:03:47,439 --> 00:03:49,719
here is the paradox that really drives the entire

83
00:03:49,719 --> 00:03:53,060
field of cognitive science. Any language we actually

84
00:03:53,060 --> 00:03:55,020
care about studying, whether that is English

85
00:03:55,020 --> 00:03:57,539
or Mandarin or a programming language like Python,

86
00:03:57,699 --> 00:04:00,340
is fundamentally an infinite set of sentences.

87
00:04:00,620 --> 00:04:02,099
Because I can always just make up a brand new

88
00:04:02,099 --> 00:04:03,819
sentence that has never been uttered in the history

89
00:04:03,819 --> 00:04:06,669
of the universe. Exactly. I could say the purple

90
00:04:06,669 --> 00:04:09,110
walrus tap danced on a quantum computer made

91
00:04:09,110 --> 00:04:12,330
entirely of expired Swiss cheese. And boom, that

92
00:04:12,330 --> 00:04:15,469
is a brand new syntactically valid English sentence.

93
00:04:15,729 --> 00:04:18,730
It is. And you could theoretically add and then

94
00:04:18,730 --> 00:04:21,149
to the end of that sentence over and over again,

95
00:04:21,189 --> 00:04:24,050
extending it forever. So the set of all possible

96
00:04:24,050 --> 00:04:27,529
English sentences is infinite. Right. But the

97
00:04:27,529 --> 00:04:30,129
human brain, the actual organ that somehow contains

98
00:04:30,129 --> 00:04:34,310
and processes this language is a finite. physical

99
00:04:34,310 --> 00:04:38,089
object. It has a finite number of neurons. So

100
00:04:38,089 --> 00:04:40,529
the fundamental question is, how does a finite

101
00:04:40,529 --> 00:04:43,870
device manage an infinite set? Because we obviously

102
00:04:43,870 --> 00:04:46,089
don't just have an infinite list of sentences

103
00:04:46,089 --> 00:04:48,029
memorized in our heads. We couldn't possibly.

104
00:04:48,189 --> 00:04:50,170
There isn't enough storage space. Yeah. Therefore,

105
00:04:50,350 --> 00:04:52,389
we can only investigate the structure of this

106
00:04:52,389 --> 00:04:54,670
infinite language through the study of finite

107
00:04:54,670 --> 00:04:57,350
mathematical devices capable of enumerating its

108
00:04:57,350 --> 00:04:59,709
sentences. Enumerating meaning like generating

109
00:04:59,709 --> 00:05:02,470
them one by one. Yes. We need a finite set of

110
00:05:02,470 --> 00:05:04,269
rules that can generate the infinite possibilities.

111
00:05:04,689 --> 00:05:06,790
And Chomsky refers to these finite generating

112
00:05:06,790 --> 00:05:10,089
devices as grammars, which I think is a term

113
00:05:10,089 --> 00:05:12,790
we need to redefine for you, the listener, right

114
00:05:12,790 --> 00:05:14,370
now. Oh, definitely. Because when I hear the

115
00:05:14,370 --> 00:05:17,350
word grammar, I immediately think of my middle

116
00:05:17,350 --> 00:05:19,470
school English teacher telling me not to end

117
00:05:19,470 --> 00:05:22,449
a sentence with a preposition or, you know, scolding

118
00:05:22,449 --> 00:05:25,069
me for splitting an infinitive. Yeah, we have

119
00:05:25,069 --> 00:05:27,410
to completely discard that prescriptive definition.

120
00:05:28,290 --> 00:05:31,389
A grammar. in this formal mathematical sense,

121
00:05:31,629 --> 00:05:34,870
is not a rule book of etiquette. It is a function.

122
00:05:35,050 --> 00:05:37,550
A mathematical function. Think of it as a mechanical

123
00:05:37,550 --> 00:05:40,509
engine. It's a generative device that takes integers

124
00:05:40,509 --> 00:05:43,550
as inputs and outputs, valid sentences in the

125
00:05:43,550 --> 00:05:46,230
language. The entire infinite language is just

126
00:05:46,230 --> 00:05:48,250
the mathematical range of this grammar function.

127
00:05:48,699 --> 00:05:50,899
Okay, so we need a machine that spits out sentences.

128
00:05:51,199 --> 00:05:54,579
But if all we want is a machine to generate every

129
00:05:54,579 --> 00:05:56,660
valid English sentence, couldn't we just use

130
00:05:56,660 --> 00:05:58,620
the most powerful computer imaginable, like a

131
00:05:58,620 --> 00:06:01,480
general unrestricted Turing machine? Well, a

132
00:06:01,480 --> 00:06:04,139
Turing machine can simulate any computer algorithm

133
00:06:04,139 --> 00:06:07,480
in existence. It is the absolute ceiling of computational

134
00:06:07,480 --> 00:06:10,920
power. If you can program a rule, a Turing machine

135
00:06:10,920 --> 00:06:13,459
can execute it. Right. So, yes, theoretically,

136
00:06:13,600 --> 00:06:15,560
a Turing machine could easily be programmed to

137
00:06:15,560 --> 00:06:18,100
spit out valid sentences in a language. But reading

138
00:06:18,100 --> 00:06:20,420
through the introduction of the paper, Chomsky

139
00:06:20,420 --> 00:06:23,920
seems to aggressively dismiss that idea. He essentially

140
00:06:23,920 --> 00:06:27,060
says that if our grammar is just a general Turing

141
00:06:27,060 --> 00:06:30,399
machine, it is completely useless to us. Why

142
00:06:30,399 --> 00:06:33,100
would the most powerful machine be useless? The

143
00:06:33,100 --> 00:06:35,620
issue is transparency. A Turing machine is a

144
00:06:35,620 --> 00:06:38,149
black box. A black box. It might... perfectly

145
00:06:38,149 --> 00:06:41,290
enumerate this set of all valid sentences, but

146
00:06:41,290 --> 00:06:43,470
it tells us absolutely nothing about the underlying

147
00:06:43,470 --> 00:06:46,610
structure of those sentences. If we want a true

148
00:06:46,610 --> 00:06:49,470
scientific theory of language, the theory must

149
00:06:49,470 --> 00:06:52,290
provide what Chomsky calls a structural description.

150
00:06:52,569 --> 00:06:54,610
I want to make sure I grasp this difference between

151
00:06:54,610 --> 00:06:56,769
generation and structural description. Let me

152
00:06:56,769 --> 00:06:59,069
try an analogy here. Go for it. Imagine I have

153
00:06:59,069 --> 00:07:02,319
a magical black box that builds houses. I press

154
00:07:02,319 --> 00:07:04,240
a button on the side of the box. It rumbles and

155
00:07:04,240 --> 00:07:06,699
out pops a perfectly built, fully furnished,

156
00:07:06,720 --> 00:07:09,939
structurally sound house. That's our Turing machine,

157
00:07:10,079 --> 00:07:12,240
right? It's generating the language of houses

158
00:07:12,240 --> 00:07:14,620
perfectly. That fits the model. Yes. Yeah. The

159
00:07:14,620 --> 00:07:16,860
output is perfectly valid. But if I'm an architect

160
00:07:16,860 --> 00:07:20,720
or like a civil engineer, that magical black

161
00:07:20,720 --> 00:07:23,060
box teaches me absolutely nothing about how to

162
00:07:23,060 --> 00:07:24,980
build a house. It doesn't give me a blueprint.

163
00:07:25,139 --> 00:07:27,100
It doesn't tell me that the concrete foundation

164
00:07:27,100 --> 00:07:30,160
has to be poured before the walls go up. or that

165
00:07:30,160 --> 00:07:32,279
the roof's weight has to be distributed across

166
00:07:32,279 --> 00:07:35,639
load -bearing beams. It just gives me the final

167
00:07:35,639 --> 00:07:38,379
product. That is a phenomenal way to visualize

168
00:07:38,379 --> 00:07:41,019
it. Yeah. Chopsky is demanding the blueprint.

169
00:07:41,769 --> 00:07:44,290
He argues that just generating the sentences

170
00:07:44,290 --> 00:07:48,290
isn't enough. The theory must include a functional

171
00:07:48,290 --> 00:07:50,689
vi, which he labels with the Greek letter phi,

172
00:07:50,949 --> 00:07:53,490
that applies to the grammar and the sentence

173
00:07:53,490 --> 00:07:55,990
to yield that structural description. Why is

174
00:07:55,990 --> 00:07:58,069
the blueprint so important, though? I mean, if

175
00:07:58,069 --> 00:08:00,310
the machine works, why do we care how it works?

176
00:08:00,529 --> 00:08:03,069
Because that structural description is the only

177
00:08:03,069 --> 00:08:05,610
way to explain how a human speaker or hearer

178
00:08:05,610 --> 00:08:08,829
actually understands a sentence. A flat string

179
00:08:08,829 --> 00:08:10,990
of words doesn't contain meaning on its own.

180
00:08:11,290 --> 00:08:13,610
The meaning is derived from how those words relate

181
00:08:13,610 --> 00:08:16,420
to each other. The blueprint tells us how to

182
00:08:16,420 --> 00:08:19,379
resolve ambiguities. It shows us why two sentences

183
00:08:19,379 --> 00:08:21,699
that look very different might actually share

184
00:08:21,699 --> 00:08:24,040
the exact same underlying structure. Right, right.

185
00:08:24,300 --> 00:08:26,000
Without the blueprint, you don't have language

186
00:08:26,000 --> 00:08:28,319
comprehension at all. You just have a parrot

187
00:08:28,319 --> 00:08:31,259
repeating noises. Which feels incredibly relevant

188
00:08:31,259 --> 00:08:33,220
today. I mean, if we look at what is happening

189
00:08:33,220 --> 00:08:35,240
right now in the world of artificial intelligence

190
00:08:35,240 --> 00:08:38,039
and large language models, this is the exact

191
00:08:38,039 --> 00:08:40,440
debate we are having. Oh, the parallel is striking.

192
00:08:40,679 --> 00:08:43,519
We have these massive AI chatbots that can output

193
00:08:43,519 --> 00:08:46,710
perfectly valid, highly... eloquent paragraphs.

194
00:08:47,070 --> 00:08:49,929
They act like incredibly powerful Turing machines

195
00:08:49,929 --> 00:08:53,269
enumerating sentences. Yes. A language model

196
00:08:53,269 --> 00:08:56,090
predicts the next word with astonishing accuracy,

197
00:08:56,429 --> 00:08:59,590
generating a beautiful output. But linguists

198
00:08:59,590 --> 00:09:01,850
and cognitive scientists are asking Chomsky's

199
00:09:01,850 --> 00:09:05,549
exact question from 1959. Does this machine actually

200
00:09:05,549 --> 00:09:08,389
possess a structural description? Exactly. Does

201
00:09:08,389 --> 00:09:10,350
it have the blueprint or is it just a statistical

202
00:09:10,350 --> 00:09:13,029
black box? Chomsky was warning us over 60 years

203
00:09:13,029 --> 00:09:15,639
ago. that enumerating the set of sentences is

204
00:09:15,639 --> 00:09:18,539
the easy part. The true mystery, the theoretical

205
00:09:18,539 --> 00:09:21,080
gold, is in the internal architecture of the

206
00:09:21,080 --> 00:09:24,519
structure. That is wild. Generating text is cheap

207
00:09:24,519 --> 00:09:27,600
understanding structure is everything. So if

208
00:09:27,600 --> 00:09:29,860
a Turing machine is too much of a black box,

209
00:09:30,100 --> 00:09:32,460
we need to design a different kind of machine,

210
00:09:32,539 --> 00:09:35,299
one that is slower, more transparent, where we

211
00:09:35,299 --> 00:09:37,440
can watch it lay every single bit of the sentence.

212
00:09:37,519 --> 00:09:40,179
How do we build that? Well, to get away from

213
00:09:40,179 --> 00:09:42,820
the black box, we need a system that builds sentences

214
00:09:42,820 --> 00:09:46,320
step by step in a highly restricted way that

215
00:09:46,320 --> 00:09:49,500
leaves a visible trace. Chomsky introduces a

216
00:09:49,500 --> 00:09:51,940
basic mathematical system for this, which he

217
00:09:51,940 --> 00:09:54,919
calls a semi -group under concatenation. Semi

218
00:09:54,919 --> 00:09:57,860
-group under concatenation. That sounds like

219
00:09:57,860 --> 00:09:59,960
a terrifying college course I would drop on the

220
00:09:59,960 --> 00:10:02,120
first day. How do we translate that into plain

221
00:10:02,120 --> 00:10:04,840
English? The terminology is dense, I know, but

222
00:10:04,840 --> 00:10:07,220
the concept is very straightforward. A semi -group

223
00:10:07,220 --> 00:10:08,960
in this context just means we have a collection

224
00:10:08,960 --> 00:10:11,559
of symbols. Okay. And concatenation is simply

225
00:10:11,559 --> 00:10:13,960
the mathematical operation of linking things

226
00:10:13,960 --> 00:10:16,799
together in a chain or series. So we are just

227
00:10:16,799 --> 00:10:18,919
smushing symbols together side by side. If I

228
00:10:18,919 --> 00:10:21,419
have symbol A and symbol B, I concatenate them

229
00:10:21,419 --> 00:10:24,000
by just writing AB. That is literally all there

230
00:10:24,000 --> 00:10:27,620
is to it. The system operates entirely by sticking

231
00:10:27,620 --> 00:10:31,259
symbols next to each other. Now, this system

232
00:10:31,259 --> 00:10:35,000
has a vocabulary, which we'll call V, and Chomsky

233
00:10:35,000 --> 00:10:37,740
makes a crucial distinction by splitting this

234
00:10:37,740 --> 00:10:40,120
vocabulary into two totally different categories.

235
00:10:40,360 --> 00:10:42,639
Okay, what's the first one? First, we have the

236
00:10:42,639 --> 00:10:45,059
terminal vocabulary. Terminal meaning, like,

237
00:10:45,100 --> 00:10:47,559
the end of the line. Right. These are the actual

238
00:10:47,559 --> 00:10:50,960
final words or morphemes of the language. If

239
00:10:50,960 --> 00:10:53,460
we are modeling English... The terminal vocabulary

240
00:10:53,460 --> 00:10:56,879
consists of words like John, comes, the apple,

241
00:10:57,059 --> 00:10:59,480
running. When you hit a terminal symbol, you

242
00:10:59,480 --> 00:11:01,360
can't break it down any further within the grammar.

243
00:11:01,480 --> 00:11:03,019
Okay, makes sense. What's the second category?

244
00:11:03,259 --> 00:11:05,600
The second category is the non -terminal vocabulary.

245
00:11:06,120 --> 00:11:08,320
These symbols never actually appear in the final

246
00:11:08,320 --> 00:11:10,700
spoken sentence. Oh, interesting. Yeah. They

247
00:11:10,700 --> 00:11:13,379
are abstract structural placeholders. These are

248
00:11:13,379 --> 00:11:15,720
your grammatical categories, things like noun

249
00:11:15,720 --> 00:11:18,840
phrase, verb phrase, adjective, or even just

250
00:11:18,840 --> 00:11:21,120
the abstract concept of a sentence. So if I'm

251
00:11:21,120 --> 00:11:23,320
looking at a blueprint of a house, the terminal

252
00:11:23,320 --> 00:11:25,840
symbols are the actual two by fours, the nails

253
00:11:25,840 --> 00:11:28,700
and the drywall, the physical stuff. And the

254
00:11:28,700 --> 00:11:30,860
non -terminal symbols are the abstract labels

255
00:11:30,860 --> 00:11:33,580
on the blueprint, like master bedroom area or

256
00:11:33,580 --> 00:11:36,419
kitchen wall. You can't physically touch a kitchen

257
00:11:36,419 --> 00:11:39,019
wall concept, but you eventually fill it in with

258
00:11:39,019 --> 00:11:41,580
actual drywall and paint. A perfect extension

259
00:11:41,580 --> 00:11:44,700
of the analogy. Now, to make this machine actually

260
00:11:44,700 --> 00:11:48,120
do something, it needs a motor. And the motor

261
00:11:48,120 --> 00:11:51,179
of this grammar is a finite set of rewriting

262
00:11:51,179 --> 00:11:54,320
rules. Rewriting rules. Yes. In the mathematical

263
00:11:54,320 --> 00:11:57,350
notation, a rule looks like this. You have a

264
00:11:57,350 --> 00:11:59,330
string of symbols, an arrow pointing to the right,

265
00:11:59,409 --> 00:12:01,950
and another string of symbols. So X arrow Y,

266
00:12:02,149 --> 00:12:04,610
meaning wherever I see X, I am allowed to erase

267
00:12:04,610 --> 00:12:07,909
it and rewrite it as Y. Exactly. But to maintain

268
00:12:07,909 --> 00:12:10,570
absolute mathematical rigor, Chomsky doesn't

269
00:12:10,570 --> 00:12:12,490
just let us make up whatever rewriting rules

270
00:12:12,490 --> 00:12:15,730
we want. He establishes four strict axioms that

271
00:12:15,730 --> 00:12:18,470
govern how these rules can operate. These axioms

272
00:12:18,470 --> 00:12:20,509
are kind of like the laws of physics for our

273
00:12:20,509 --> 00:12:22,679
grammar machine. I want to dig into these because

274
00:12:22,679 --> 00:12:24,399
reading through the paper, the axioms felt almost

275
00:12:24,399 --> 00:12:26,559
painfully obvious at first glance, but I suspect

276
00:12:26,559 --> 00:12:28,759
there is a deep mechanical reason for each of

277
00:12:28,759 --> 00:12:31,100
them. There absolutely is. Let's take the first

278
00:12:31,100 --> 00:12:33,960
one. Axiom one states that the rewriting relation

279
00:12:33,960 --> 00:12:37,419
is irreflexive, meaning you cannot have a rule

280
00:12:37,419 --> 00:12:40,139
that simply rewrites a symbol as itself. You

281
00:12:40,139 --> 00:12:43,000
can't have A arrow A. Why even bother making

282
00:12:43,000 --> 00:12:45,419
that a rule? Who would write a rule that does

283
00:12:45,419 --> 00:12:47,649
nothing? Think about it from the perspective

284
00:12:47,649 --> 00:12:50,830
of a literal unthinking machine or a computer

285
00:12:50,830 --> 00:12:54,370
program trying to resolve a process. If the machine

286
00:12:54,370 --> 00:12:57,629
encounters the symbol A and the rulebook says

287
00:12:57,629 --> 00:13:01,149
you must rewrite A as A, what happens? The machine

288
00:13:01,149 --> 00:13:04,590
replaces A with A, then it looks at the new A,

289
00:13:04,710 --> 00:13:06,710
consults the rulebook, and the rulebook says

290
00:13:06,710 --> 00:13:09,620
rewrite A as A. Oh, I see. It's an infinite loop.

291
00:13:09,840 --> 00:13:11,740
Precisely. The machine freezes. It just sits

292
00:13:11,740 --> 00:13:13,940
there forever rewriting the same symbol. The

293
00:13:13,940 --> 00:13:16,080
system would crash. A generative grammar must

294
00:13:16,080 --> 00:13:18,559
always be moving forward, making progress toward

295
00:13:18,559 --> 00:13:20,799
a final terminal string. An irreflexive loop

296
00:13:20,799 --> 00:13:23,860
halts all progress. So axiom one prevents the

297
00:13:23,860 --> 00:13:25,779
machine from freezing. Okay, that makes perfect

298
00:13:25,779 --> 00:13:27,679
sense. What about the next one? Axiom two is

299
00:13:27,679 --> 00:13:29,679
a defining boundary. It states that a symbol

300
00:13:29,679 --> 00:13:32,220
belongs to the non -terminal vocabulary if and

301
00:13:32,220 --> 00:13:34,519
only if there is at least one rule that rewrites

302
00:13:34,519 --> 00:13:36,909
into something else. So if a symbol can be broken

303
00:13:36,909 --> 00:13:39,529
down, it's non -terminal. If there is no rule

304
00:13:39,529 --> 00:13:41,889
to break it down, it's terminal. The mathematical

305
00:13:41,889 --> 00:13:45,110
consequence of that is profound. It means the

306
00:13:45,110 --> 00:13:48,350
machine knows exactly when its job is done. When

307
00:13:48,350 --> 00:13:50,970
the string contains only symbols that have no

308
00:13:50,970 --> 00:13:53,830
rewriting rules associated with them, the derivation

309
00:13:53,830 --> 00:13:57,289
naturally terminates. Without Axiom 2, the machine

310
00:13:57,289 --> 00:13:59,110
wouldn't know the difference between an abstract

311
00:13:59,110 --> 00:14:01,690
noun phrase marker and the actual word apple.

312
00:14:02,200 --> 00:14:04,480
It might try to keep breaking down the word apple

313
00:14:04,480 --> 00:14:07,460
into smaller pieces indefinitely. It's the mechanism

314
00:14:07,460 --> 00:14:09,879
that tells the machine, stop, you've hit the

315
00:14:09,879 --> 00:14:12,179
bedrock, the sentence is finished. I love how

316
00:14:12,179 --> 00:14:14,659
physical this feels. There are also two special

317
00:14:14,659 --> 00:14:16,919
boundary symbols in the vocabulary represented

318
00:14:16,919 --> 00:14:19,600
by hash marks, like a hashtag. What do those

319
00:14:19,600 --> 00:14:22,460
do? The boundary symbol hash is crucial for defining

320
00:14:22,460 --> 00:14:24,320
the edges of the universe we are working in.

321
00:14:24,960 --> 00:14:27,220
Axiom 3 dictates that you can never erase these

322
00:14:27,220 --> 00:14:29,000
boundary symbols from the left or right ends

323
00:14:29,000 --> 00:14:31,340
of the string. And you can never insert a new

324
00:14:31,340 --> 00:14:32,960
boundary symbol into the middle of a string.

325
00:14:33,120 --> 00:14:35,559
They are sacred borders. They tell the machine,

326
00:14:35,700 --> 00:14:37,600
this is where the sentence begins and this is

327
00:14:37,600 --> 00:14:39,940
where it ends. Do not build outside this property

328
00:14:39,940 --> 00:14:42,700
line. Exactly. And the final axiom, axiom four,

329
00:14:42,840 --> 00:14:45,340
just guarantees that our set of rewriting rules

330
00:14:45,340 --> 00:14:48,460
is strictly finite. Right. Which ensures we are

331
00:14:48,460 --> 00:14:50,720
still dealing with a finite device as we established

332
00:14:50,720 --> 00:14:53,929
in our foundational problem. So with these laws

333
00:14:53,929 --> 00:14:56,549
of physics in place, let's actually run the machine.

334
00:14:56,789 --> 00:14:58,789
Let's do it. Let's look at a derivation sequence

335
00:14:58,789 --> 00:15:01,850
step by step using a simplified version of Chomsky's

336
00:15:01,850 --> 00:15:04,389
own example. I want to see the bricks being laid.

337
00:15:04,610 --> 00:15:06,669
Okay, we always start with the most abstract,

338
00:15:06,789 --> 00:15:09,409
highest level symbol possible. The initial string

339
00:15:09,409 --> 00:15:11,690
consists of a left boundary mark, the symbol

340
00:15:11,690 --> 00:15:14,450
S for sentence, and a right boundary mark, hash,

341
00:15:14,610 --> 00:15:17,230
S, hash. Okay, we have our property lines, and

342
00:15:17,230 --> 00:15:19,389
right in the middle is just a giant sign that

343
00:15:19,389 --> 00:15:22,639
says a sentence will go here. Now the machine

344
00:15:22,639 --> 00:15:24,960
consults its rulebook. It finds a rule that says

345
00:15:24,960 --> 00:15:28,500
S can be rewritten as A followed by B. So the

346
00:15:28,500 --> 00:15:30,860
machine applies the rule. Our new string is hash,

347
00:15:31,080 --> 00:15:34,720
A, B, hash. And let's ground those abstract letters.

348
00:15:34,980 --> 00:15:38,340
In Chomsky's example, A is the non -terminal

349
00:15:38,340 --> 00:15:41,000
symbol for a noun phrase and B is the non -terminal

350
00:15:41,000 --> 00:15:43,899
symbol for a verb phrase. Correct. So our abstract

351
00:15:43,899 --> 00:15:46,259
sentence has now been split into a noun phrase

352
00:15:46,259 --> 00:15:48,360
and a verb phrase. And the machine keeps going.

353
00:15:48,539 --> 00:15:51,279
It finds a rule for A. The rule says A rewrites

354
00:15:51,279 --> 00:15:54,809
as C. where C stands for singular noun. So the

355
00:15:54,809 --> 00:15:58,730
string is now hash, C, B, hash. We have a singular

356
00:15:58,730 --> 00:16:01,009
noun and a verb phrase. It's getting more specific.

357
00:16:01,409 --> 00:16:03,570
Yes, the machine looks at B. The rule book says

358
00:16:03,570 --> 00:16:06,070
B, the verb phrase, rewrites as a terminal lowercase

359
00:16:06,070 --> 00:16:08,809
symbol B. Let's say this terminal symbol B is

360
00:16:08,809 --> 00:16:11,049
the actual English word comes. Oh, so we've hit

361
00:16:11,049 --> 00:16:12,730
bedrock on the right side of the sentence. The

362
00:16:12,730 --> 00:16:16,009
string is now hash, C, lowercase B, hash or hash.

363
00:16:16,450 --> 00:16:19,929
Singular noun comes hash. Almost done. One step

364
00:16:19,929 --> 00:16:23,250
left. The machine looks at C. The rule says C

365
00:16:23,250 --> 00:16:25,250
rewrites as the terminal lowercase symbol A.

366
00:16:25,450 --> 00:16:27,590
And let's say A is the word John. The string

367
00:16:27,590 --> 00:16:31,570
is hash, AB, hash, hash, John comes, hash. Yes.

368
00:16:31,830 --> 00:16:33,669
We've hit terminal bedrock across the entire

369
00:16:33,669 --> 00:16:35,970
string. There are no more non -terminal symbols

370
00:16:35,970 --> 00:16:38,889
to rewrite. Axiom 2 kicks in, the machine halts,

371
00:16:38,889 --> 00:16:40,970
and we have our sentence. We have successfully

372
00:16:40,970 --> 00:16:43,509
generated a sentence. But remember our critique

373
00:16:43,509 --> 00:16:45,570
of the Turing machine. Right. Generating the

374
00:16:45,570 --> 00:16:48,389
output is only half the battle. Exactly. We demanded

375
00:16:48,389 --> 00:16:51,320
a blueprint. We demanded a structural description

376
00:16:51,320 --> 00:16:54,159
that explains how the sentence was built. So

377
00:16:54,159 --> 00:16:56,460
where is the blueprint? Well, I would normally

378
00:16:56,460 --> 00:16:58,399
think that once the sentence is printed out,

379
00:16:58,460 --> 00:17:01,159
a linguist would come along, read John comes,

380
00:17:01,480 --> 00:17:04,099
and draw a little diagram on a talk board pointing

381
00:17:04,099 --> 00:17:06,400
out that John is a noun and comes is a verb.

382
00:17:06,619 --> 00:17:08,900
That is how humans usually do it after the fact.

383
00:17:09,119 --> 00:17:12,240
But the genius of Chomsky's formalization is

384
00:17:12,240 --> 00:17:14,960
that the blueprint created itself. Wait, really?

385
00:17:15,240 --> 00:17:17,660
Yes, because we started with a single symbol

386
00:17:17,660 --> 00:17:20,160
S. and strictly followed rules that replaced

387
00:17:20,160 --> 00:17:22,759
one symbol with others, this linear sequence

388
00:17:22,759 --> 00:17:25,099
of string replacements automatically maps out

389
00:17:25,099 --> 00:17:27,740
a mathematical structure called a labeled tree.

390
00:17:27,980 --> 00:17:31,039
Oh, like a family tree or a corporate organizational

391
00:17:31,039 --> 00:17:34,099
chart. Exactly that. So the S is the CEO at the

392
00:17:34,099 --> 00:17:36,559
top. The S splits into two vice presidents, A

393
00:17:36,559 --> 00:17:39,180
and B. The vice president A manages a director

394
00:17:39,180 --> 00:17:41,799
named C, who manages a frontline worker named

395
00:17:41,799 --> 00:17:44,920
John. Vice president B manages a frontline worker

396
00:17:44,920 --> 00:17:48,130
named Cums. That hierarchy is the structural

397
00:17:48,130 --> 00:17:51,869
description. In traditional linguistics, drawing

398
00:17:51,869 --> 00:17:54,430
that tree is called immediate constituent analysis.

399
00:17:55,240 --> 00:17:57,700
What Chomsky proved here is that the tree is

400
00:17:57,700 --> 00:18:00,740
not a subjective diagram drawn by a linguist

401
00:18:00,740 --> 00:18:03,460
interpreting a sentence. The tree is literally

402
00:18:03,460 --> 00:18:06,400
just the exhaust fumes of the machine. Yes. It's

403
00:18:06,400 --> 00:18:09,140
the chronological history of every single decision

404
00:18:09,140 --> 00:18:12,019
the rewriting machine made. The structural description

405
00:18:12,019 --> 00:18:14,380
is identical to the generative history of the

406
00:18:14,380 --> 00:18:17,849
sentence. If you know the exact sequence of rewriting

407
00:18:17,849 --> 00:18:20,369
rules the machine used, you have mathematically

408
00:18:20,369 --> 00:18:22,809
defined the grammatical structure of that sentence.

409
00:18:23,009 --> 00:18:25,950
It removes all human subjectivity from grammar.

410
00:18:26,049 --> 00:18:29,049
It is pure, traceable mathematics. That is an

411
00:18:29,049 --> 00:18:31,470
incredible aha moment. The act of building the

412
00:18:31,470 --> 00:18:33,609
sentence is the grammar of the sentence. Right.

413
00:18:33,690 --> 00:18:35,730
Okay, so now we have this brilliant transparent

414
00:18:35,730 --> 00:18:38,509
machine called a phrase structure grammar that

415
00:18:38,509 --> 00:18:40,250
gives us both the sentence and the blueprint.

416
00:18:40,589 --> 00:18:43,140
But Chomsky doesn't start there. He takes this

417
00:18:43,140 --> 00:18:45,019
machine and starts tinkering with its engine,

418
00:18:45,180 --> 00:18:47,500
which brings us to one of the most famous concepts

419
00:18:47,500 --> 00:18:50,420
in all of computer science, the Chomsky hierarchy.

420
00:18:50,779 --> 00:18:53,819
Yes. Having established the basic mechanics of

421
00:18:53,819 --> 00:18:57,160
how rules rewrite strings, Chomsky asks a crucial

422
00:18:57,160 --> 00:19:00,460
scientific question. What happens to the generative

423
00:19:00,460 --> 00:19:03,180
power of this machine if we start artificially

424
00:19:03,180 --> 00:19:05,740
restricting the types of rewriting rules it is

425
00:19:05,740 --> 00:19:08,500
allowed to use? He creates four distinct levels

426
00:19:08,500 --> 00:19:11,619
of power from a completely unrestricted free

427
00:19:11,619 --> 00:19:14,259
-for -all down to a highly constrained, rigid

428
00:19:14,259 --> 00:19:18,619
system. Theorem 1 formalizes this nested hierarchy.

429
00:19:19,039 --> 00:19:22,119
Type 0 includes type 1, which includes type 2,

430
00:19:22,240 --> 00:19:24,859
which includes type 3. Let's define the boundaries

431
00:19:24,859 --> 00:19:26,519
of these levels. We already discussed the top

432
00:19:26,519 --> 00:19:28,740
level, type 0. This is the unrestricted Turing

433
00:19:28,740 --> 00:19:30,960
machine. Right. In type 0, there are absolutely

434
00:19:30,960 --> 00:19:33,319
no restrictions on the rewriting rules. You can

435
00:19:33,319 --> 00:19:35,319
rewrite any string of symbols into any other

436
00:19:35,319 --> 00:19:37,700
string of symbols in any order with no oversight.

437
00:19:37,819 --> 00:19:40,119
It can compute anything the universe allows to

438
00:19:40,119 --> 00:19:42,279
be computed. But as we discovered, that absolute

439
00:19:42,279 --> 00:19:44,920
freedom destroys our ability to easily extract

440
00:19:44,920 --> 00:19:47,839
a clean structural tree. The derivations can

441
00:19:47,839 --> 00:19:51,200
be so chaotic that the history is useless. So

442
00:19:51,200 --> 00:19:53,980
we impose a mathematical restriction. We create

443
00:19:53,980 --> 00:19:56,220
type 1 grammars. These are formally known as

444
00:19:56,220 --> 00:19:58,660
context -sensitive grammars. Context -sensitive.

445
00:19:59,240 --> 00:20:01,740
The name implies that the machine has to look

446
00:20:01,740 --> 00:20:04,240
at its surroundings. How is that written mathematically

447
00:20:04,240 --> 00:20:07,059
in the rule book? The restriction mandates that

448
00:20:07,059 --> 00:20:09,519
every rule must take a specific form. I'll read

449
00:20:09,519 --> 00:20:12,200
the notation and it'll translate it. Phi 1, A,

450
00:20:12,460 --> 00:20:16,099
Phi 2, arrow Phi 1, omega Phi 2. Okay, let's

451
00:20:16,099 --> 00:20:19,059
break that down into physical actions. A is our

452
00:20:19,059 --> 00:20:21,720
single non -terminal symbol. Let's say it's our

453
00:20:21,720 --> 00:20:24,579
noun phrase. Omega is the new string of symbols

454
00:20:24,579 --> 00:20:27,039
we want to replace A with. But what are the Phi

455
00:20:27,039 --> 00:20:29,920
symbols on either side? Think of phi 1 and phi

456
00:20:29,920 --> 00:20:32,619
2 as the context. The rule states that you are

457
00:20:32,619 --> 00:20:35,920
only allowed to transform A into omega if and

458
00:20:35,920 --> 00:20:38,960
only if A is sitting exactly between the string

459
00:20:38,960 --> 00:20:41,789
phi 1 on its left and phi 2 on its right. Oh,

460
00:20:41,809 --> 00:20:43,970
I see. It's like A is trying to get into an exclusive

461
00:20:43,970 --> 00:20:46,910
nightclub and Omega is the VIP section. The rule

462
00:20:46,910 --> 00:20:48,990
says A can only transform and get into the VIP

463
00:20:48,990 --> 00:20:51,589
section if it brings two specific bouncers with

464
00:20:51,589 --> 00:20:53,450
it. That's a great way to picture it. If the

465
00:20:53,450 --> 00:20:56,029
left bouncer, Phi 1, and the right bouncer, Phi

466
00:20:56,029 --> 00:20:59,009
2, aren't physically standing next to A in the

467
00:20:59,009 --> 00:21:01,710
string, the rule doesn't trigger. A is stuck.

468
00:21:01,970 --> 00:21:04,829
That is an excellent visualization. The context

469
00:21:04,829 --> 00:21:07,509
surrounding the symbol dictates whether the transformation

470
00:21:07,509 --> 00:21:10,450
is legal. That is the essence of a type 1 grammar.

471
00:21:10,650 --> 00:21:13,069
But what if we want to restrict the machine even

472
00:21:13,069 --> 00:21:16,170
further? What if we fire the bouncers? Okay,

473
00:21:16,210 --> 00:21:18,250
moving down the hierarchy. That brings us to

474
00:21:18,250 --> 00:21:20,710
type 2 grammars, universally known as context

475
00:21:20,710 --> 00:21:23,230
-free grammars. Context -free, so the rule gets

476
00:21:23,230 --> 00:21:25,849
simpler. Much simpler. The restriction for type

477
00:21:25,849 --> 00:21:29,470
2 simplifies the rule format down to just. A

478
00:21:29,470 --> 00:21:32,829
arrow omega. No bouncers. The context is completely

479
00:21:32,829 --> 00:21:36,049
null. The symbol A is rewritten entirely independently

480
00:21:36,049 --> 00:21:38,630
of its surroundings. It does not matter what

481
00:21:38,630 --> 00:21:40,569
symbols are sitting to the left or the right

482
00:21:40,569 --> 00:21:42,849
of our noun phrase. The rules for how a noun

483
00:21:42,849 --> 00:21:44,789
phrase can be expanded into smaller components

484
00:21:44,789 --> 00:21:47,490
remain exactly the same regardless of where it

485
00:21:47,490 --> 00:21:49,650
appears in the sentence. And then at the very

486
00:21:49,650 --> 00:21:51,910
bottom, we have the most mathematically restrictive

487
00:21:51,910 --> 00:21:55,049
level, type three, which are called finite state

488
00:21:55,049 --> 00:21:58,549
grammars. How strict do the rules get here? Extremely

489
00:21:58,549 --> 00:22:01,930
strict. Restriction three says that a non -terminal

490
00:22:01,930 --> 00:22:04,329
symbol can only be rewritten in one of two very

491
00:22:04,329 --> 00:22:07,519
specific ways. Either A rewrites as a single

492
00:22:07,519 --> 00:22:10,579
terminal lowercase, A followed by exactly one

493
00:22:10,579 --> 00:22:15,539
single non -terminal capital B, or A simply rewrites

494
00:22:15,539 --> 00:22:17,920
as the single terminal lowercase a. So if I'm

495
00:22:17,920 --> 00:22:20,650
tracing the tree. Every single time a node branches,

496
00:22:20,970 --> 00:22:24,109
it immediately spits out one final terminal word

497
00:22:24,109 --> 00:22:26,950
and leaves exactly one abstract symbol to be

498
00:22:26,950 --> 00:22:29,509
processed next. It's a completely linear one

499
00:22:29,509 --> 00:22:32,089
-way progression. It forces the derivation to

500
00:22:32,089 --> 00:22:34,130
move strictly from left to right one word at

501
00:22:34,130 --> 00:22:36,490
a time. It's the simplest possible generative

502
00:22:36,490 --> 00:22:39,109
mechanism. So we have this beautiful, clean hierarchy.

503
00:22:40,039 --> 00:22:41,660
But Chomsky doesn't just name these categories.

504
00:22:41,900 --> 00:22:44,099
He uses rigorous proofs to determine exactly

505
00:22:44,099 --> 00:22:45,700
what these different machines are capable of.

506
00:22:45,779 --> 00:22:47,440
And theorem three is a massive breakthrough.

507
00:22:47,660 --> 00:22:49,859
Theorem three proves that each type one language

508
00:22:49,859 --> 00:22:52,440
is a decidable set of strings. Right. Now, I

509
00:22:52,440 --> 00:22:54,960
know decidability is a huge concept in computability.

510
00:22:55,279 --> 00:22:58,019
Why is this theorem such a big deal for us? To

511
00:22:58,019 --> 00:22:59,460
appreciate the breakthrough, you have to look

512
00:22:59,460 --> 00:23:02,539
at the alternative. With a type zero unrestricted

513
00:23:02,539 --> 00:23:05,279
Turing machine, we run into the famous halting

514
00:23:05,279 --> 00:23:08,009
problem. First proved by Alan Turing. A halting

515
00:23:08,009 --> 00:23:10,589
problem. Yeah. If I hand a type zero machine

516
00:23:10,589 --> 00:23:13,349
a random thousand word string of symbols and

517
00:23:13,349 --> 00:23:15,809
ask, is this a valid sentence in your language?

518
00:23:16,130 --> 00:23:18,589
The machine might start calculating and never

519
00:23:18,589 --> 00:23:21,289
stop. Because it's allowed to do anything. Exactly.

520
00:23:21,450 --> 00:23:24,109
It might get caught in a complex web of derivations,

521
00:23:24,109 --> 00:23:26,369
constantly expanding and shrinking the string,

522
00:23:26,529 --> 00:23:28,769
calculating until the heat death of the universe

523
00:23:28,769 --> 00:23:31,769
without ever giving me a yes or no answer. A

524
00:23:31,769 --> 00:23:33,970
type zero language is generally an undecidable

525
00:23:33,970 --> 00:23:36,700
set. But theorem 3 proves that if we restrict

526
00:23:36,700 --> 00:23:39,799
the machine to type 1 context -sensitive rules,

527
00:23:40,059 --> 00:23:43,220
the set becomes decidable. Meaning, if I hand

528
00:23:43,220 --> 00:23:45,779
a computer a type 1 grammar and a random string

529
00:23:45,779 --> 00:23:48,299
of words, I am mathematically guaranteed that

530
00:23:48,299 --> 00:23:50,460
the computer will eventually halt and give me

531
00:23:50,460 --> 00:23:52,779
a definitive, yes, this is a valid sentence,

532
00:23:52,880 --> 00:23:55,259
or no, it is not. Yes. How does Chomsky prove

533
00:23:55,259 --> 00:23:57,720
that? What is the mathematical trick? The mechanism

534
00:23:57,720 --> 00:24:00,799
of the proof relies on a very subtle but powerful

535
00:24:00,799 --> 00:24:04,529
feature built into type 1 rules. Notice that

536
00:24:04,529 --> 00:24:07,269
in a type 1 rule, you are replacing a single

537
00:24:07,269 --> 00:24:11,150
symbol A with a string omega. Chomsky adds a

538
00:24:11,150 --> 00:24:13,769
specific stipulation here. Omega cannot be a

539
00:24:13,769 --> 00:24:16,349
null string. It cannot be empty. So whenever

540
00:24:16,349 --> 00:24:18,849
you apply a rule, you are always replacing one

541
00:24:18,849 --> 00:24:21,309
symbol with one or more symbols. You can never

542
00:24:21,309 --> 00:24:23,869
replace a symbol with nothing. Think about the

543
00:24:23,869 --> 00:24:26,109
physical consequence of that rule on the string

544
00:24:26,109 --> 00:24:28,750
itself. With every single step of the derivation,

545
00:24:28,789 --> 00:24:31,490
every time the machine runs, the resulting string

546
00:24:31,490 --> 00:24:33,829
of symbols either stays the exact same length

547
00:24:33,829 --> 00:24:36,990
or it grows longer. It can never, ever shrink.

548
00:24:37,210 --> 00:24:40,009
Oh, I see where this is going. If it can't shrink,

549
00:24:40,130 --> 00:24:42,440
it creates a boundary. Precisely. Let's say you

550
00:24:42,440 --> 00:24:44,160
want to test a specific sentence. Let's call

551
00:24:44,160 --> 00:24:46,839
it x. And sentence x is exactly 10 words long.

552
00:24:47,000 --> 00:24:49,480
Because we know the strings in a type 1 derivation

553
00:24:49,480 --> 00:24:52,019
can only grow, we only have to ask the computer

554
00:24:52,019 --> 00:24:54,559
to generate all possible derivations that result

555
00:24:54,559 --> 00:24:56,799
in strings of 10 words or fewer. Because if a

556
00:24:56,799 --> 00:24:59,180
derivation reaches 11 words, it can never shrink

557
00:24:59,180 --> 00:25:01,519
back down to match our 10 -word sentence. It's

558
00:25:01,519 --> 00:25:04,480
mathematically impossible. Exactly. And because

559
00:25:04,480 --> 00:25:06,980
the vocabulary is finite and the length is capped

560
00:25:06,980 --> 00:25:10,339
at 10, there is a strictly finite number of possible

561
00:25:10,339 --> 00:25:13,170
derivations to check. The computer generates

562
00:25:13,170 --> 00:25:15,809
that finite pile of sentences. It looks through

563
00:25:15,809 --> 00:25:18,430
the pile. Right. If our sentence X is in the

564
00:25:18,430 --> 00:25:21,349
pile, the answer is yes. If it's not in the pile,

565
00:25:21,529 --> 00:25:24,970
the machine can confidently answer no. Secure

566
00:25:24,970 --> 00:25:26,750
in the knowledge that any further computation

567
00:25:26,750 --> 00:25:29,349
would only produce sentences longer than 10 words.

568
00:25:29,589 --> 00:25:33,130
That is so elegant. By forcing the string to

569
00:25:33,130 --> 00:25:35,730
only grow, he creates a mathematical ceiling

570
00:25:35,730 --> 00:25:38,410
on how far we have to search. The halting problem

571
00:25:38,410 --> 00:25:40,970
is solved. The set is decidable. It's beautiful

572
00:25:40,970 --> 00:25:44,049
math. It really is. But because Chomsky is incredibly

573
00:25:44,049 --> 00:25:47,049
thorough, he drops a massive curveball in the

574
00:25:47,049 --> 00:25:50,289
footnotes. Footnote 7a. He proves that while

575
00:25:50,289 --> 00:25:52,849
every type 1 language is decidable, the reverse

576
00:25:52,849 --> 00:25:55,069
is not true. There are languages out there that

577
00:25:55,069 --> 00:25:56,890
are perfectly decidable, but they are absolutely

578
00:25:56,890 --> 00:25:59,589
not type 1. Yes. And he proves this using the

579
00:25:59,589 --> 00:26:01,670
diagonal language argument. This is one of the

580
00:26:01,670 --> 00:26:03,589
most beautiful proof techniques in mathematics.

581
00:26:04,269 --> 00:26:06,730
It was originally developed by George Cantor

582
00:26:06,730 --> 00:26:08,849
to prove that some infinities are larger than

583
00:26:08,849 --> 00:26:11,589
others. It was adapted by Alan Turing for the

584
00:26:11,589 --> 00:26:14,170
halting problem, and Chomsky deploys it here

585
00:26:14,170 --> 00:26:17,910
to map the outer limits of type 1 grammars. It's

586
00:26:17,910 --> 00:26:20,250
heavy theoretical computer science, but I want

587
00:26:20,250 --> 00:26:22,049
to try and walk through it because the logic

588
00:26:22,049 --> 00:26:25,049
is fascinating. How do we build a language that

589
00:26:25,049 --> 00:26:28,150
is decidable but definitely not type 1? We do

590
00:26:28,150 --> 00:26:30,210
it by building a paradox. Let's start with a

591
00:26:30,210 --> 00:26:33,049
thought experiment. Assume we can create an effective...

592
00:26:33,369 --> 00:26:35,849
ordered infinite list of every single possible

593
00:26:35,849 --> 00:26:38,809
type 1 grammar in the universe. We will label

594
00:26:38,809 --> 00:26:41,509
them grammar 1, grammar 2, grammar 3, and so

595
00:26:41,509 --> 00:26:43,950
on forever. Okay, we have a master registry of

596
00:26:43,950 --> 00:26:46,210
every type 1 machine. Now alongside that, we

597
00:26:46,210 --> 00:26:49,240
make a second ordered infinite list. This list

598
00:26:49,240 --> 00:26:52,000
contains every possible finite string of symbols

599
00:26:52,000 --> 00:26:54,859
you could ever randomly type on a keyboard. String

600
00:26:54,859 --> 00:26:58,079
1, string 2, string 3, going on infinitely. So

601
00:26:58,079 --> 00:27:00,420
we have two infinitely long lists sitting side

602
00:27:00,420 --> 00:27:03,180
by side. The list of machines and the list of

603
00:27:03,180 --> 00:27:06,140
random strings. Now, we are going to act as the

604
00:27:06,140 --> 00:27:09,200
creators of a brand new language. We will call

605
00:27:09,200 --> 00:27:11,859
our language M. We're going to build the rules

606
00:27:11,859 --> 00:27:14,980
for what belongs in language M step by step by

607
00:27:14,980 --> 00:27:17,289
looking down our two lists. How do we decide

608
00:27:17,289 --> 00:27:19,930
what gets into language M? We go to step one,

609
00:27:20,009 --> 00:27:21,890
we look at string one, we walk over to grammar

610
00:27:21,890 --> 00:27:24,650
one and we ask it, can you generate string one?

611
00:27:24,789 --> 00:27:27,250
Remember, because type one is decidable, grammar

612
00:27:27,250 --> 00:27:29,309
one will always give us a straight yes or no

613
00:27:29,309 --> 00:27:31,650
answer. Right, it won't freeze. If grammar one

614
00:27:31,650 --> 00:27:33,589
says yes, yes, I can generate string one, we

615
00:27:33,589 --> 00:27:36,730
ban string one from our new language M. If grammar

616
00:27:36,730 --> 00:27:39,990
one says no, I cannot, we welcome string one

617
00:27:39,990 --> 00:27:42,970
into language M. So we are acting like a rebellious

618
00:27:42,970 --> 00:27:45,329
teenager. We are looking at whatever the grammar

619
00:27:45,329 --> 00:27:47,430
on the list does, and we are purposefully doing

620
00:27:47,430 --> 00:27:50,470
the exact opposite. A perfect analogy. Then we

621
00:27:50,470 --> 00:27:52,650
move to step two. We ask grammar two if it can

622
00:27:52,650 --> 00:27:55,210
generate string two. We do the opposite of its

623
00:27:55,210 --> 00:27:57,910
answer to define our language M. We go diagonally

624
00:27:57,910 --> 00:28:00,009
down the list. Step three, step four, step N.

625
00:28:00,250 --> 00:28:02,509
Always ensuring that our new language M differs

626
00:28:02,509 --> 00:28:04,690
from the behavior of grammar N regarding the

627
00:28:04,690 --> 00:28:08,170
Nth string. We build this whole language M and

628
00:28:08,170 --> 00:28:09,950
then some mathematician comes along and says,

629
00:28:10,049 --> 00:28:13,049
hey, your new language M is clearly a type one

630
00:28:13,049 --> 00:28:15,950
language. It must be hiding somewhere on your

631
00:28:15,950 --> 00:28:18,509
infinite master registry of type one grammars.

632
00:28:18,529 --> 00:28:21,250
And how do you prove them wrong? Because if they

633
00:28:21,250 --> 00:28:23,670
claim that language M is, say, grammar number

634
00:28:23,670 --> 00:28:27,589
500 on the list, we just look at step 500. By

635
00:28:27,589 --> 00:28:31,049
our rebellious definition, language M does the

636
00:28:31,049 --> 00:28:34,029
exact opposite of whatever grammar 500 does to

637
00:28:34,029 --> 00:28:37,150
string 500. Exactly. Therefore, language M cannot

638
00:28:37,150 --> 00:28:40,109
possibly be grammar 500. It cannot be grammar

639
00:28:40,109 --> 00:28:42,349
1 million. It cannot be any grammar on the list

640
00:28:42,349 --> 00:28:45,049
because it is designed to disagree with every

641
00:28:45,049 --> 00:28:47,910
single grammar on at least one specific string.

642
00:28:48,089 --> 00:28:50,839
The logic is inescapable. Therefore, language

643
00:28:50,839 --> 00:28:53,240
M simply does not exist within the realm of type

644
00:28:53,240 --> 00:28:56,299
1 languages. It is outside the boundary. But

645
00:28:56,299 --> 00:28:59,359
because we have a clear step -by -step mechanical

646
00:28:59,359 --> 00:29:01,920
procedure for deciding exactly what goes into

647
00:29:01,920 --> 00:29:05,359
language M, it is by definition a decidable language.

648
00:29:05,640 --> 00:29:07,960
It's a mathematical magic trick. We proved a

649
00:29:07,960 --> 00:29:10,200
boundary exists by building something that willfully

650
00:29:10,200 --> 00:29:12,900
violates it. Okay, so all of this math leaves

651
00:29:12,900 --> 00:29:15,460
us feeling pretty incredibly impressed with type

652
00:29:15,460 --> 00:29:18,460
1 grammars. They use context, they solve the

653
00:29:18,460 --> 00:29:21,099
halting problem, they are massively powerful.

654
00:29:21,740 --> 00:29:24,380
We should just use type 1 for all human language

655
00:29:24,380 --> 00:29:27,059
and call it a day, right? Mathematically, that

656
00:29:27,059 --> 00:29:29,680
might seem tempting, but linguistically, it would

657
00:29:29,680 --> 00:29:32,380
be a complete disaster. A disaster. Yeah. In

658
00:29:32,380 --> 00:29:35,119
section 4 of the paper, Chomsky exposes a fatal

659
00:29:35,119 --> 00:29:37,980
defect in type 1 grammars when applied to the

660
00:29:37,980 --> 00:29:40,220
actual structure of human thought. Let's break

661
00:29:40,220 --> 00:29:42,940
down this defect. But first, to understand why

662
00:29:42,940 --> 00:29:45,279
type 1 is flawed, we have to understand why it's

663
00:29:45,279 --> 00:29:48,140
so powerful in the first place. Chomsky uses

664
00:29:48,140 --> 00:29:50,799
lemma 2 to demonstrate a specific superpower

665
00:29:50,799 --> 00:29:54,619
that type 1 has, which type 2 does not. He introduces

666
00:29:54,619 --> 00:29:56,680
a hypothetical mathematical language with cross

667
00:29:56,680 --> 00:29:58,799
dependencies. This cross dependency language

668
00:29:58,799 --> 00:30:01,500
is defined by a very specific pattern of symbols.

669
00:30:01,700 --> 00:30:04,079
The sentences must look like this. A certain

670
00:30:04,079 --> 00:30:06,700
number of A's followed by the exact same number

671
00:30:06,700 --> 00:30:09,730
of B's. then a repeat of that first number of

672
00:30:09,730 --> 00:30:11,690
A's, followed by a repeat of that first number

673
00:30:11,690 --> 00:30:14,950
of B's, ending with a string of C's. So A to

674
00:30:14,950 --> 00:30:17,549
the power of N, B to the power of M, A to the

675
00:30:17,549 --> 00:30:20,230
power of N, B to the power of M, and then C,

676
00:30:20,289 --> 00:30:23,230
C, C. Correct. So if I have five A's and three

677
00:30:23,230 --> 00:30:25,230
B's at the start of the sentence, I absolutely

678
00:30:25,230 --> 00:30:28,049
must have exactly five A's and three B's later

679
00:30:28,049 --> 00:30:30,230
in the sentence. It's a matching game across

680
00:30:30,230 --> 00:30:33,069
a long distance. And Chomsky proves that a type

681
00:30:33,069 --> 00:30:36,579
one context -sensitive grammar can successfully

682
00:30:36,579 --> 00:30:39,380
generate this cross -dependency language. Why?

683
00:30:39,839 --> 00:30:42,119
Because the context rules act as a rudimentary

684
00:30:42,119 --> 00:30:44,720
form of memory. Right. Because the rules require

685
00:30:44,720 --> 00:30:47,079
the machine to look at the bouncers, the symbol

686
00:30:47,079 --> 00:30:49,599
standing next to it. The grammar can essentially

687
00:30:49,599 --> 00:30:52,319
copy a string of information and carry it across

688
00:30:52,319 --> 00:30:54,220
the derivation sequence to reproduce it later.

689
00:30:54,319 --> 00:30:57,180
It can look back and say, ah. My context tells

690
00:30:57,180 --> 00:30:59,359
me we had five A's and three B's over on the

691
00:30:59,359 --> 00:31:00,960
left side of the sentence, so I need to force

692
00:31:00,960 --> 00:31:03,220
the right side of the sentence to match. It has

693
00:31:03,220 --> 00:31:06,680
situational awareness. Exactly. But theorem four

694
00:31:06,680 --> 00:31:08,839
proves that a type two context -free grammar

695
00:31:08,839 --> 00:31:11,160
cannot generate this language. Yeah. Think about

696
00:31:11,160 --> 00:31:13,339
the definition of type two. The rule is just

697
00:31:13,339 --> 00:31:16,059
A, arrow, omega, there is no context. There are

698
00:31:16,059 --> 00:31:18,769
no bouncers. The symbol A transforms blindly

699
00:31:18,769 --> 00:31:21,569
with no idea what is happening on the other side

700
00:31:21,569 --> 00:31:24,869
of the sentence. It has amnesia. It cannot remember

701
00:31:24,869 --> 00:31:27,430
that it generated five A's earlier, so it cannot

702
00:31:27,430 --> 00:31:29,549
mathematically guarantee it will generate five

703
00:31:29,549 --> 00:31:33,150
A's later. So on paper, type one is superior

704
00:31:33,150 --> 00:31:35,609
because it has this situational awareness. That

705
00:31:35,609 --> 00:31:38,130
is the mathematical illusion. It has more generative

706
00:31:38,130 --> 00:31:41,150
power, yes. But remember our foundational requirement

707
00:31:41,150 --> 00:31:44,640
from the very beginning of the deep dive. Generation

708
00:31:44,640 --> 00:31:46,880
is not enough. We need the structural description.

709
00:31:47,140 --> 00:31:49,660
We need the blueprint, the parsing tree. And

710
00:31:49,660 --> 00:31:53,220
here is where type 1 collapses. Lemma 1 proves

711
00:31:53,220 --> 00:31:56,019
that the situational awareness of type 1 allows

712
00:31:56,019 --> 00:31:59,460
it to perform a very dangerous operation. A permutation.

713
00:31:59,819 --> 00:32:02,000
A permutation, meaning changing the order of

714
00:32:02,000 --> 00:32:04,740
things. Exactly. Lemma 1 shows that in a type

715
00:32:04,740 --> 00:32:07,039
1 grammar, you can easily create a rule that

716
00:32:07,039 --> 00:32:09,660
looks like this. xb arrow bx, you are taking

717
00:32:09,660 --> 00:32:11,740
the symbol x and the symbol b, and you are just

718
00:32:11,740 --> 00:32:13,779
swapping their positions in the string. Because

719
00:32:13,779 --> 00:32:16,839
type 1 allows context, in this case, x acting

720
00:32:16,839 --> 00:32:19,160
as a context for b, the machine, can execute

721
00:32:19,160 --> 00:32:21,059
this swap perfectly well to generate the final

722
00:32:21,059 --> 00:32:23,200
string of words. Okay, let's bring this out of

723
00:32:23,200 --> 00:32:25,119
the math and into English to see why this swap

724
00:32:25,119 --> 00:32:28,309
is so catastrophic. Let's say our machine is

725
00:32:28,309 --> 00:32:30,450
building the underlying structure for a simple

726
00:32:30,450 --> 00:32:33,849
declarative sentence. It drops three abstract

727
00:32:33,849 --> 00:32:37,450
symbols, a noun phrase, followed by a modal verb,

728
00:32:37,650 --> 00:32:40,289
followed by a main verb. And let's say the terminal

729
00:32:40,289 --> 00:32:43,230
words for those are John, will, and come. The

730
00:32:43,230 --> 00:32:45,789
machine generates the string, John will come.

731
00:32:46,250 --> 00:32:49,049
And if we look at the tree, the blueprint generated

732
00:32:49,049 --> 00:32:52,349
by that history, it is perfectly clean. The word

733
00:32:52,349 --> 00:32:54,569
John traces straight up to the noun phrase node.

734
00:32:55,069 --> 00:32:57,069
The word will traces straight up to the modal

735
00:32:57,069 --> 00:32:59,289
note. But now let's say we want to turn that

736
00:32:59,289 --> 00:33:01,250
declarative statement into a question. We want

737
00:33:01,250 --> 00:33:03,809
to say, will John come? To do this, our type

738
00:33:03,809 --> 00:33:05,990
1 machine uses that permutation rule we just

739
00:33:05,990 --> 00:33:08,150
talked about. It looks at the noun phrase, John,

740
00:33:08,309 --> 00:33:11,789
and the modal, will, and it swaps them. XB becomes

741
00:33:11,789 --> 00:33:14,349
BX. The machine outputs the strain perfectly.

742
00:33:14,589 --> 00:33:16,910
The words read from left to right, will John

743
00:33:16,910 --> 00:33:19,869
come? The generation was successful. But wait,

744
00:33:19,990 --> 00:33:22,670
if I am a linguist trying to understand the blueprint...

745
00:33:23,029 --> 00:33:25,109
The tree is supposed to just be the history of

746
00:33:25,109 --> 00:33:27,829
the derivation. So if I trace the lines straight

747
00:33:27,829 --> 00:33:29,730
back up from the words in their new positions,

748
00:33:29,910 --> 00:33:33,349
what happens? The lines cross. The tree gets

749
00:33:33,349 --> 00:33:36,750
hopelessly tangled. Let's trace it. The word

750
00:33:36,750 --> 00:33:39,309
will is now in the first position in the sentence.

751
00:33:39,849 --> 00:33:42,069
If you trace the lines straight up from that

752
00:33:42,069 --> 00:33:44,829
first position, the tree will erroneously label

753
00:33:44,829 --> 00:33:48,150
will as the noun phrase. And John, which is now

754
00:33:48,150 --> 00:33:50,150
sitting in the second position, will trace straight

755
00:33:50,150 --> 00:33:52,940
up and be labeled as the modal verb. Exactly.

756
00:33:53,039 --> 00:33:55,279
The tree is lying to us. The blueprint is fundamentally

757
00:33:55,279 --> 00:33:58,299
structurally false. Will is not a noun. John

758
00:33:58,299 --> 00:34:01,019
is not a modal verb. If an AI used this tree

759
00:34:01,019 --> 00:34:03,059
to try and understand the sentence, it would

760
00:34:03,059 --> 00:34:05,740
think John was an action you could perform. The

761
00:34:05,740 --> 00:34:07,839
extra mathematical power of the type 1 grammar,

762
00:34:07,960 --> 00:34:09,860
the power that allowed it to do cross dependencies

763
00:34:09,860 --> 00:34:12,659
and permutations, is the exact thing that destroys

764
00:34:12,659 --> 00:34:15,260
the structural integrity of the constituent analysis.

765
00:34:15,980 --> 00:34:19,039
The lines cross, the nodes mislabel the words,

766
00:34:19,139 --> 00:34:21,289
and the blueprint is useless. So we are caught

767
00:34:21,289 --> 00:34:23,869
in a trap. Type 1 is computationally powerful,

768
00:34:24,110 --> 00:34:26,550
but linguistically bankrupt. We have to abandon

769
00:34:26,550 --> 00:34:29,610
it. We have to step down the hierarchy to type

770
00:34:29,610 --> 00:34:33,269
2, the context -free grammars. Because in type

771
00:34:33,269 --> 00:34:35,389
2, a symbol rewrites entirely independently.

772
00:34:35,789 --> 00:34:37,909
The branches of the tree drop straight down.

773
00:34:38,030 --> 00:34:41,489
They never cross. The tree stays pure and honest.

774
00:34:41,789 --> 00:34:44,329
That is the necessary compromise. Which brings

775
00:34:44,329 --> 00:34:46,170
us to a major inflection point in the paper.

776
00:34:46,969 --> 00:34:49,090
We know we have to step down to type 2 to keep

777
00:34:49,090 --> 00:34:51,389
our trees honest. But the natural scientific

778
00:34:51,389 --> 00:34:54,650
question is, why stop there? Right. Why use a

779
00:34:54,650 --> 00:34:57,150
complex hierarchical phrase structure tree at

780
00:34:57,150 --> 00:34:59,829
all if we can go even simpler? Why not step all

781
00:34:59,829 --> 00:35:02,110
the way down to the absolute bottom of the Chomsky

782
00:35:02,110 --> 00:35:04,789
hierarchy? Why not use type 3, the finite state

783
00:35:04,789 --> 00:35:07,250
grammars? To rigorously answer this, Chomsky

784
00:35:07,250 --> 00:35:09,510
first has to prove exactly what type 3 grammars

785
00:35:09,510 --> 00:35:12,610
are. In theorem 6, he proves that type 3 languages

786
00:35:12,610 --> 00:35:14,789
are mathematically identical to finite state

787
00:35:14,789 --> 00:35:17,639
Markov sources. A finite state Markov source.

788
00:35:17,980 --> 00:35:20,539
I love visualizing this mechanism because it's

789
00:35:20,539 --> 00:35:23,900
so intuitive. Imagine a simple board game. The

790
00:35:23,900 --> 00:35:26,239
board has a finite number of spaces, or states.

791
00:35:26,460 --> 00:35:29,059
You put your game piece on the space labeled

792
00:35:29,059 --> 00:35:32,059
initial state. To play the game, you roll a die,

793
00:35:32,280 --> 00:35:34,800
and based on the number, you move your piece

794
00:35:34,800 --> 00:35:37,659
to a new connected space. And the crucial rule

795
00:35:37,659 --> 00:35:40,199
of this machine is that every single time you

796
00:35:40,199 --> 00:35:42,139
transition your piece from one space to another,

797
00:35:42,360 --> 00:35:45,829
the machine emits one single terminal word. So

798
00:35:45,829 --> 00:35:48,510
I move a space. The machine says they. I move

799
00:35:48,510 --> 00:35:51,130
another space. It says dog. I keep moving from

800
00:35:51,130 --> 00:35:53,409
space to space, spitting out words one by one,

801
00:35:53,510 --> 00:35:55,869
moving strictly in a linear progression from

802
00:35:55,869 --> 00:35:58,150
left to right. I have no grand plan. I'm just

803
00:35:58,150 --> 00:35:59,989
looking at the space I'm currently standing on,

804
00:36:00,050 --> 00:36:02,369
rolling the die and moving to the next one until

805
00:36:02,369 --> 00:36:04,590
I finally land on the final state space and the

806
00:36:04,590 --> 00:36:07,260
sentence ends. That is exactly how a Markov source

807
00:36:07,260 --> 00:36:10,059
operates. It generates sentences from left to

808
00:36:10,059 --> 00:36:12,599
right and its next move is based only on its

809
00:36:12,599 --> 00:36:15,880
current state. It has absolutely no memory of

810
00:36:15,880 --> 00:36:18,119
the larger structure it is building. It cannot

811
00:36:18,119 --> 00:36:20,139
look back at the beginning of the sentence and

812
00:36:20,139 --> 00:36:22,079
it cannot plan for the end of the sentence. It

813
00:36:22,079 --> 00:36:24,500
is just a blind chain of transitions. This is

814
00:36:24,500 --> 00:36:27,059
essentially how early predictive text on cell

815
00:36:27,059 --> 00:36:29,480
phones worked, right? You type, I am going to

816
00:36:29,480 --> 00:36:32,420
the, and the phone looks at the current state.

817
00:36:32,940 --> 00:36:36,019
Run some probabilities and suggest store as the

818
00:36:36,019 --> 00:36:39,179
next transition. Yes. It is a highly efficient,

819
00:36:39,420 --> 00:36:42,380
probabilistic left -right generator. So the million

820
00:36:42,380 --> 00:36:44,699
-dollar quotient for cognitive science, can a

821
00:36:44,699 --> 00:36:47,199
Markov source, this simple board game, generate

822
00:36:47,199 --> 00:36:49,719
human language? To prove definitively that it

823
00:36:49,719 --> 00:36:52,119
cannot, Chomsky introduces definition seven,

824
00:36:52,280 --> 00:36:55,460
self -embedding. How does the math define a self

825
00:36:55,460 --> 00:36:57,760
-embedded structure? A grammar is self -embedding

826
00:36:57,760 --> 00:36:59,840
if it contains a non -terminal symbol, let's

827
00:36:59,840 --> 00:37:02,239
call it A, that can eventually rewrite into a

828
00:37:02,239 --> 00:37:04,780
string of symbols that contains A again. But

829
00:37:04,780 --> 00:37:07,119
crucially, that new A must be surrounded by other

830
00:37:07,119 --> 00:37:09,559
symbols on both sides. So A eventually drives

831
00:37:09,559 --> 00:37:12,820
a string like phi, A, piece AI. It's a cycle.

832
00:37:13,000 --> 00:37:15,480
You start with the concept of A, do a bunch of

833
00:37:15,480 --> 00:37:17,539
operations, and you end up with a new A buried

834
00:37:17,539 --> 00:37:19,619
right in the middle of the string. It's like

835
00:37:19,619 --> 00:37:22,139
a Russian nesting doll. You open the big doll,

836
00:37:22,320 --> 00:37:25,280
and inside is a smaller, identical doll, completely

837
00:37:25,280 --> 00:37:27,880
surrounded by the outer shell. A nesting doll,

838
00:37:28,039 --> 00:37:31,059
or the layers of an onion. Now, in theorem 7,

839
00:37:31,380 --> 00:37:34,340
Chomsky proves there are type 2 languages that

840
00:37:34,340 --> 00:37:37,159
utilize this nesting doll structure that absolutely

841
00:37:37,159 --> 00:37:39,920
cannot be generated by a type 3 Markov source.

842
00:37:40,829 --> 00:37:43,610
He uses an example from his earlier work, the

843
00:37:43,610 --> 00:37:46,210
mirror image language, which he calls L2. The

844
00:37:46,210 --> 00:37:48,710
mirror language. Explain the rules of this specific

845
00:37:48,710 --> 00:37:51,539
language. The rule is simple. but structural

846
00:37:51,539 --> 00:37:54,400
demanding. Every valid sentence in this language

847
00:37:54,400 --> 00:37:56,579
must consist of a string of symbols, which we'll

848
00:37:56,579 --> 00:37:59,159
call X, followed immediately by a second string,

849
00:37:59,340 --> 00:38:02,400
Y. But Y must be the exact mirror image, the

850
00:38:02,400 --> 00:38:05,420
reverse of X. So if my X string is the sequence

851
00:38:05,420 --> 00:38:08,059
apple, banana, orange, then my I string must

852
00:38:08,059 --> 00:38:10,099
immediately follow it as orange, banana, apple.

853
00:38:10,199 --> 00:38:12,539
The sentence folds in on itself. To generate

854
00:38:12,539 --> 00:38:16,099
this mirror language, a machine absolutely requires

855
00:38:16,099 --> 00:38:18,980
a self -embedding type 2 grammar. because the

856
00:38:18,980 --> 00:38:21,000
machine has to build the sentence from the outside

857
00:38:21,000 --> 00:38:24,559
in. It generates the first word, apple, and the

858
00:38:24,559 --> 00:38:27,780
last word, apple, simultaneously. Then it steps

859
00:38:27,780 --> 00:38:30,219
inward, generating the second word and the second

860
00:38:30,219 --> 00:38:32,960
to last word simultaneously. It embeds the structure

861
00:38:32,960 --> 00:38:35,340
inside itself. To properly close the sentence

862
00:38:35,340 --> 00:38:37,440
on the right side, the machine is forced to remember

863
00:38:37,440 --> 00:38:39,920
the exact sequence of the layers it opened on

864
00:38:39,920 --> 00:38:41,980
the left side. And here's the fatal blow for

865
00:38:41,980 --> 00:38:45,099
the Markov source. A finite state machine produces

866
00:38:45,099 --> 00:38:48,239
sentences linearly from left to right. It generates

867
00:38:48,239 --> 00:38:50,679
apple, then transitions to a new state and generates

868
00:38:50,679 --> 00:38:53,139
banana, then transitions to a new state and generates

869
00:38:53,139 --> 00:38:55,539
orange. It's just walking its game piece across

870
00:38:55,539 --> 00:38:57,980
the board. But by the time it reaches the middle

871
00:38:57,980 --> 00:38:59,940
of the sentence and needs to start generating

872
00:38:59,940 --> 00:39:02,139
the mirror image, it is standing on a new square.

873
00:39:03,010 --> 00:39:05,230
It has completely forgotten the path it took

874
00:39:05,230 --> 00:39:07,949
to get there. It has no center embedded memory.

875
00:39:08,190 --> 00:39:10,690
Wow. It cannot look back to match the left side

876
00:39:10,690 --> 00:39:12,969
to the right side. It is physically impossible

877
00:39:12,969 --> 00:39:16,309
for a pure left to right machine to build a nested

878
00:39:16,309 --> 00:39:19,030
mirror structure. Now, I know some mathematicians

879
00:39:19,030 --> 00:39:20,989
and engineers at the time were resistant to this.

880
00:39:21,130 --> 00:39:23,570
They loved finite state machines because they

881
00:39:23,570 --> 00:39:26,030
were easy to program. They argued, well, what

882
00:39:26,030 --> 00:39:28,070
if we just give the board game a memory upgrade?

883
00:39:28,309 --> 00:39:30,530
What if we give the finite state machine a little

884
00:39:30,530 --> 00:39:33,900
counter chip so it can tally up its moves? Chomsky

885
00:39:33,900 --> 00:39:36,960
anticipated that exact counter argument. He references

886
00:39:36,960 --> 00:39:39,679
a brilliant paper by a mathematician named Schutzenberger

887
00:39:39,679 --> 00:39:43,559
who tested exactly this hypothesis. Theorem 8

888
00:39:43,559 --> 00:39:47,079
in Chomsky's paper states that even if you artificially

889
00:39:47,079 --> 00:39:50,420
extend the power of a finite automaton by equipping

890
00:39:50,420 --> 00:39:52,980
it with a finite number of infinite counters,

891
00:39:53,199 --> 00:39:55,900
it still fails. It still cannot generate the

892
00:39:55,900 --> 00:39:58,539
mirror language L2. So throwing more RAM at a

893
00:39:58,539 --> 00:40:01,300
Markov chain doesn't fix the fundamental architectural

894
00:40:01,300 --> 00:40:04,239
flaw. A left -to -right architecture is simply

895
00:40:04,239 --> 00:40:07,079
incompatible with nested, center -embedded structures.

896
00:40:07,480 --> 00:40:10,119
Period. And this brings us to the profound linguistic

897
00:40:10,119 --> 00:40:12,619
and cognitive conclusion of this entire section.

898
00:40:13,119 --> 00:40:15,159
Chomsky points out that natural English has the

899
00:40:15,159 --> 00:40:17,179
essential structural properties of this mere

900
00:40:17,179 --> 00:40:20,300
language L2. We use nested, self -embedded dependencies

901
00:40:20,300 --> 00:40:23,179
all the time in casual conversation. Give me

902
00:40:23,179 --> 00:40:26,610
an example of how we nest dolls in English. Think

903
00:40:26,610 --> 00:40:28,690
of a sentence with embedded relative clauses.

904
00:40:29,329 --> 00:40:32,309
The rat that the cat that the dog chased bit

905
00:40:32,309 --> 00:40:34,889
ate the cheese. The rat that the cat that the

906
00:40:34,889 --> 00:40:37,329
dog chased bit ate the cheese. Yeah, my brain

907
00:40:37,329 --> 00:40:40,050
has to open a file for the rat, pause that file

908
00:40:40,050 --> 00:40:42,489
to open a file for the cat, pause the cat to

909
00:40:42,489 --> 00:40:44,889
resolve what the dog did, and then close the

910
00:40:44,889 --> 00:40:47,429
files one by one in reverse order to figure out

911
00:40:47,429 --> 00:40:49,949
who ate the cheese. We open a thought, we embed

912
00:40:49,949 --> 00:40:52,429
a subthought inside it, we close the subthought,

913
00:40:52,550 --> 00:40:55,110
and then we close the main thought. Because human

914
00:40:55,110 --> 00:40:58,030
language requires this center embedded memory

915
00:40:58,030 --> 00:41:00,989
to resolve clauses, human language cannot possibly

916
00:41:00,989 --> 00:41:03,789
be generated by a finite state Markov source.

917
00:41:04,090 --> 00:41:06,650
This is such a massive philosophical realization.

918
00:41:06,710 --> 00:41:09,630
It proves that humans do not just probabilistically

919
00:41:09,630 --> 00:41:12,630
emit words left to right like. basic algorithm

920
00:41:12,630 --> 00:41:14,750
predicting the next token. No, we don't. When

921
00:41:14,750 --> 00:41:17,110
you speak, you aren't blindly stepping to the

922
00:41:17,110 --> 00:41:20,670
next word based on the last word. You are conceptualizing

923
00:41:20,670 --> 00:41:23,730
and planning nested hierarchical structures in

924
00:41:23,730 --> 00:41:26,590
your head before your vocal cords even start

925
00:41:26,590 --> 00:41:29,659
vibrating. The mathematics prove that human cognition

926
00:41:29,659 --> 00:41:32,260
operates at least at the complexity of a type

927
00:41:32,260 --> 00:41:35,480
two grammar. We are not simple, linear, finite

928
00:41:35,480 --> 00:41:38,699
automata. It is a mathematically rigorous proof

929
00:41:38,699 --> 00:41:42,179
of the depth of human cognitive complexity, which

930
00:41:42,179 --> 00:41:44,510
leads us finally. To the grand finale of the

931
00:41:44,510 --> 00:41:47,610
paper, the most mathematically intense, conceptually

932
00:41:47,610 --> 00:41:49,849
brutal section of the text. The gauntlet. Because

933
00:41:49,849 --> 00:41:52,090
Chomsky is a rigorous scientist. He is not satisfied

934
00:41:52,090 --> 00:41:54,250
just waving his hands and saying type two is

935
00:41:54,250 --> 00:41:56,010
more powerful than type three because of nesting.

936
00:41:56,130 --> 00:41:59,110
He wants to isolate the exact pure mathematical

937
00:41:59,110 --> 00:42:01,929
power source of that difference. Right. We know

938
00:42:01,929 --> 00:42:03,909
type two can do things. Type three can't. But

939
00:42:03,909 --> 00:42:06,610
what is the exact mechanism? And Chomsky states

940
00:42:06,610 --> 00:42:09,550
it bluntly in Theorem 11. If a language is a

941
00:42:09,550 --> 00:42:11,610
type 2 language, it is not a type 3 language

942
00:42:11,610 --> 00:42:14,570
if and only if all of its grammars are self -embedding.

943
00:42:14,650 --> 00:42:17,750
Think about the weight of that claim. He's saying

944
00:42:17,750 --> 00:42:20,210
that the sole reason phrased structure trees

945
00:42:20,210 --> 00:42:22,849
are more powerful than a linear board game is

946
00:42:22,849 --> 00:42:25,550
self -embedding. If you take a type 2 grammar

947
00:42:25,550 --> 00:42:28,230
and artificially forbid it from ever using a

948
00:42:28,230 --> 00:42:31,150
self -embedding cycle, that complex tree grammar

949
00:42:31,150 --> 00:42:33,949
instantly collapses and becomes mathematically

950
00:42:33,949 --> 00:42:36,960
identical. to a Type 3 finite state machine.

951
00:42:37,219 --> 00:42:38,659
Wait, let me make sure I'm wrapping my head around

952
00:42:38,659 --> 00:42:41,179
this. If I made a personal rule for myself today

953
00:42:41,179 --> 00:42:43,880
that I would never, ever speak a self -embedded

954
00:42:43,880 --> 00:42:46,019
sentence. Well, hypothetically. Yeah, hypothetically.

955
00:42:46,039 --> 00:42:48,400
If I promised to never put a clause inside another

956
00:42:48,400 --> 00:42:52,260
clause, are you saying a simple, rigid, left

957
00:42:52,260 --> 00:42:54,860
-to -right, predictive text algorithm could perfectly

958
00:42:54,860 --> 00:42:57,400
replicate my entire language capability? Yes.

959
00:42:57,849 --> 00:43:00,110
That is exactly what theorem 11 proves. Without

960
00:43:00,110 --> 00:43:02,489
nesting, your language is just a Markov chain.

961
00:43:02,670 --> 00:43:05,230
That is staggering. But how on earth does Chomsky

962
00:43:05,230 --> 00:43:07,329
actually prove that? How do you mathematically

963
00:43:07,329 --> 00:43:09,869
prove that a grammar without self -embedding

964
00:43:09,869 --> 00:43:12,730
is just a finite state machine in disguise? He

965
00:43:12,730 --> 00:43:14,630
proves it through an exhaustive mathematical

966
00:43:14,630 --> 00:43:18,800
construction. Chomsky says to the reader, give

967
00:43:18,800 --> 00:43:21,559
me any regular non -self -embedding type 2 grammar.

968
00:43:21,659 --> 00:43:24,329
Let's call it grammar G. He then proceeds over

969
00:43:24,329 --> 00:43:26,969
the course of several pages to manually build

970
00:43:26,969 --> 00:43:29,929
a massive, incredibly complex type three grammar,

971
00:43:30,130 --> 00:43:33,469
which he names G prime. And his goal is to prove

972
00:43:33,469 --> 00:43:35,750
that G prime generates the exact same language

973
00:43:35,750 --> 00:43:38,309
as G. So he is going to build a finite state

974
00:43:38,309 --> 00:43:40,210
machine that perfectly mimics the tree machine.

975
00:43:40,489 --> 00:43:42,929
How does he build G prime? He has to create a

976
00:43:42,929 --> 00:43:46,170
dizzying array of new, highly complex, non -terminal

977
00:43:46,170 --> 00:43:48,630
symbols. The original tree grammar G year symbols

978
00:43:48,630 --> 00:43:52,010
were simple A, B, C. In this new flat grammar

979
00:43:52,010 --> 00:43:54,929
G', the non -terminal symbols look like a mathematical

980
00:43:54,929 --> 00:43:56,909
nightmare. How so? They are written as a left

981
00:43:56,909 --> 00:43:59,590
bracket, followed by B1, dot, dot, dot, BN, a

982
00:43:59,590 --> 00:44:01,989
right bracket, and a subscript I. Bracket B,

983
00:44:02,070 --> 00:44:05,369
1 through BN, close bracket, subscript I. That

984
00:44:05,369 --> 00:44:07,409
is completely unreadable. What does a bracketed

985
00:44:07,409 --> 00:44:09,550
list with a subscript even represent to the machine?

986
00:44:09,889 --> 00:44:12,429
It represents a specific pathway navigated through

987
00:44:12,429 --> 00:44:15,269
the parting tree. Let's visualize why this is

988
00:44:15,269 --> 00:44:18,969
necessary. A type 2 grammar generates a two -dimensional

989
00:44:18,969 --> 00:44:22,019
tree. branching downward and outward. A type

990
00:44:22,019 --> 00:44:24,840
3 grammar is just a one -dimensional flat line

991
00:44:24,840 --> 00:44:28,079
of transitions from one state to the next. Chomsky's

992
00:44:28,079 --> 00:44:30,739
bracketed symbols are a mathematical trick for

993
00:44:30,739 --> 00:44:34,380
flattening a 2D tree into a 1D line. How do you

994
00:44:34,380 --> 00:44:36,559
flatten a branching tree without losing information?

995
00:44:36,920 --> 00:44:40,320
I need an analogy here. Let's imagine the original

996
00:44:40,320 --> 00:44:43,159
type 2 tree is a massive branching underground

997
00:44:43,159 --> 00:44:46,440
cave system, and the derivation process is a

998
00:44:46,440 --> 00:44:49,349
hiker. exploring this cave. Every time the cave

999
00:44:49,349 --> 00:44:51,750
forks, the hiker goes down a level. Okay, I'm

1000
00:44:51,750 --> 00:44:54,030
the hiker. I start at the entrance, S, and the

1001
00:44:54,030 --> 00:44:56,389
cave immediately branches left and right. Now,

1002
00:44:56,449 --> 00:44:58,710
because we established that the original Grammar

1003
00:44:58,710 --> 00:45:01,630
G is strictly non -self -embedding, we know a

1004
00:45:01,630 --> 00:45:04,090
crucial geographical fact about this cave. There

1005
00:45:04,090 --> 00:45:06,769
are no infinite loops. A tunnel will never curve

1006
00:45:06,769 --> 00:45:09,090
around and feed back into itself. Because there

1007
00:45:09,090 --> 00:45:11,090
are no loops, the depth of this cave system is

1008
00:45:11,090 --> 00:45:13,630
strictly finite. It must eventually hit a rock

1009
00:45:13,630 --> 00:45:16,079
-bottom dead end. The sentences can't nest forever,

1010
00:45:16,260 --> 00:45:18,219
so the tree has to hit terminal words eventually.

1011
00:45:18,420 --> 00:45:20,639
Exactly. And because the depth is finite, there's

1012
00:45:20,639 --> 00:45:22,980
a strictly finite number of possible paths the

1013
00:45:22,980 --> 00:45:24,579
hiker can take from the entrance down to the

1014
00:45:24,579 --> 00:45:27,920
bottom. Chomsky's terrifying bracketed symbols,

1015
00:45:28,199 --> 00:45:30,840
the bracket B1 through Bn, are basically the

1016
00:45:30,840 --> 00:45:33,079
hiker's notebook. Oh, I see. It is a running

1017
00:45:33,079 --> 00:45:35,880
log of the exact path the hiker took to get to

1018
00:45:35,880 --> 00:45:38,400
their current location. B1 is the first fork

1019
00:45:38,400 --> 00:45:41,360
they took, B2 is the second fork, B3 is the third

1020
00:45:41,360 --> 00:45:44,000
fork, and so on. So instead of drawing a map

1021
00:45:44,000 --> 00:45:46,500
of the entire cave, the new flat machine just

1022
00:45:46,500 --> 00:45:48,820
keeps a running list of left and right turns

1023
00:45:48,820 --> 00:45:51,440
in its state name. It remembers where it is.

1024
00:45:51,519 --> 00:45:54,000
What about the little subscript I at the end

1025
00:45:54,000 --> 00:45:56,320
of the bracket? The subscript is the hiker's

1026
00:45:56,320 --> 00:45:58,699
directional heading. It is either a 1 or a 2.

1027
00:45:59,039 --> 00:46:01,199
A subscript of 1 means the hiker is currently

1028
00:46:01,199 --> 00:46:03,960
traveling downward, deeper into the cave along

1029
00:46:03,960 --> 00:46:06,860
the left wall. A subscript of 2 means the hiker

1030
00:46:06,860 --> 00:46:09,659
has hit the bottom, turned around, and is currently

1031
00:46:09,659 --> 00:46:12,599
traveling back upward to find... the next unexplored

1032
00:46:12,599 --> 00:46:15,619
branch. That is brilliant. The state name itself

1033
00:46:15,619 --> 00:46:18,300
is a set of GPS coordinates for navigating the

1034
00:46:18,300 --> 00:46:21,219
tree. So how do the rewriting rules work in this

1035
00:46:21,219 --> 00:46:24,340
flattened system? Chomsky lists four rules for

1036
00:46:24,340 --> 00:46:26,699
building G prime. Let's look at the first two

1037
00:46:26,699 --> 00:46:29,969
to see the hiker in action. Rule 1 says, if BN

1038
00:46:29,969 --> 00:46:33,250
rewrites as A in the original grammar, then bracket

1039
00:46:33,250 --> 00:46:37,309
B1 through BN subscript 1 rewrites as A, followed

1040
00:46:37,309 --> 00:46:40,690
by bracket B1 through BN subscript 2. Okay, let's

1041
00:46:40,690 --> 00:46:43,269
translate that to the cave. This rule says, if

1042
00:46:43,269 --> 00:46:45,369
the hiker is traveling downward, meaning subscript

1043
00:46:45,369 --> 00:46:47,809
1, and hits a dead end that emits the terminal

1044
00:46:47,809 --> 00:46:50,869
word A, the hiker drops the word A on the ground.

1045
00:46:51,050 --> 00:46:53,199
Correct. Then, the hiker updates their notebook

1046
00:46:53,199 --> 00:46:55,260
by changing their subscript from a 1 to a 2.

1047
00:46:55,380 --> 00:46:57,179
They have finished the leftward descent and are

1048
00:46:57,179 --> 00:46:59,199
turning around to head back up. Exactly. Now,

1049
00:46:59,199 --> 00:47:03,679
rule 2. If BN rewrites as CD, then bracket B1

1050
00:47:03,679 --> 00:47:06,400
through BN subscript 1 rewrites as bracket B1

1051
00:47:06,400 --> 00:47:09,300
through BNC subscript 1. This means if the hiker

1052
00:47:09,300 --> 00:47:11,539
is traveling downward and hits a fork that splits

1053
00:47:11,539 --> 00:47:14,219
into a left tunnel C and a right tunnel D, the

1054
00:47:14,219 --> 00:47:16,480
hiker always takes the left tunnel first. They

1055
00:47:16,480 --> 00:47:19,400
add C to their notebook to record the turn, keep

1056
00:47:19,400 --> 00:47:21,420
their subscript as a 1 because they're still

1057
00:47:21,420 --> 00:47:24,599
going down, and keep walking. By meticulously

1058
00:47:24,599 --> 00:47:27,260
mapping every single possible physical movement

1059
00:47:27,260 --> 00:47:30,420
in the cave into these flat bracketed state transitions,

1060
00:47:30,820 --> 00:47:34,539
Chonsky creates G prime. This new grammar just

1061
00:47:34,539 --> 00:47:37,460
moves from one notebook state to another, dropping

1062
00:47:37,460 --> 00:47:39,559
terminal words along the way in a straight line,

1063
00:47:39,719 --> 00:47:42,969
operating exactly like a Markov board game. Yes.

1064
00:47:43,190 --> 00:47:45,829
But to prove theorem 11, it is not enough to

1065
00:47:45,829 --> 00:47:48,570
just build the machine. Chomsky has to mathematically

1066
00:47:48,570 --> 00:47:51,190
guarantee that this monster G prime actually

1067
00:47:51,190 --> 00:47:54,130
works. He has to prove it generates every valid

1068
00:47:54,130 --> 00:47:56,670
sentence the tree would generate and never accidentally

1069
00:47:56,670 --> 00:47:58,809
regenerates a garbage sentence. And that is what

1070
00:47:58,809 --> 00:48:01,510
lemmas 3 through 10 are doing. It is a grueling,

1071
00:48:01,510 --> 00:48:04,210
relentless induction proof. It takes up pages

1072
00:48:04,210 --> 00:48:07,030
and pages of dense algebra. He is using simultaneous

1073
00:48:07,030 --> 00:48:08,989
induction on the length of the strings then.

1074
00:48:09,170 --> 00:48:11,590
Without reading the textbook math to you, the

1075
00:48:11,590 --> 00:48:14,010
listener, how does induction actually prove this

1076
00:48:14,010 --> 00:48:16,650
works? Think of mathematical induction like knocking

1077
00:48:16,650 --> 00:48:20,190
over an infinitely long line of dominoes. Chomsky

1078
00:48:20,190 --> 00:48:22,230
doesn't try to prove the machine works for every

1079
00:48:22,230 --> 00:48:24,789
possible infinite length of sentence all at once.

1080
00:48:24,869 --> 00:48:28,070
That's impossible. Instead, he first proves that

1081
00:48:28,070 --> 00:48:30,590
his flat machine works perfectly for a tiny,

1082
00:48:30,750 --> 00:48:33,559
microscopic sentence. That's knocking over the

1083
00:48:33,559 --> 00:48:35,860
first domino. Okay. The baseline is established.

1084
00:48:36,239 --> 00:48:39,900
Then he proves a mechanism. He says, assume the

1085
00:48:39,900 --> 00:48:41,940
machine works perfectly for a sentence of length

1086
00:48:41,940 --> 00:48:44,960
tack. I can mathematically guarantee that adding

1087
00:48:44,960 --> 00:48:47,280
one more word moving to length tack plus one

1088
00:48:47,280 --> 00:48:50,519
will not break the machine. That is proving that

1089
00:48:50,519 --> 00:48:53,260
if any one domino falls, it is guaranteed to

1090
00:48:53,260 --> 00:48:55,659
knock over the next one in line. And because

1091
00:48:55,659 --> 00:48:58,239
he proved the first domino falls. and he proved

1092
00:48:58,239 --> 00:49:00,179
the mechanism linking them, he mathematically

1093
00:49:00,179 --> 00:49:02,280
guarantees that the dominoes will fall forever.

1094
00:49:02,420 --> 00:49:04,300
The machine will hold up no matter how long the

1095
00:49:04,300 --> 00:49:06,960
sentence gets. Exactly. Throughout this domino

1096
00:49:06,960 --> 00:49:09,360
chain of proofs, he constantly relies on our

1097
00:49:09,360 --> 00:49:11,880
starting premise to kill off impossible errors.

1098
00:49:12,199 --> 00:49:15,119
For example, in Lemma 6, he writes out a hypothetical

1099
00:49:15,119 --> 00:49:17,300
scenario where the flat machine accidentally

1100
00:49:17,300 --> 00:49:19,699
generates an invalid derivation. But then he

1101
00:49:19,699 --> 00:49:22,400
looks at the math and says, wait for this error

1102
00:49:22,400 --> 00:49:25,659
to happen. Symbol BM would have had to loop back

1103
00:49:25,659 --> 00:49:28,920
around and embed itself. But we explicitly stated

1104
00:49:28,920 --> 00:49:31,260
at the very beginning that this cave has no loops.

1105
00:49:31,420 --> 00:49:34,599
It is non -self -embedding. Exactly. Since the

1106
00:49:34,599 --> 00:49:37,239
loop is geometrically impossible, the hypothetical

1107
00:49:37,239 --> 00:49:40,219
error is mathematically impossible. The contradiction

1108
00:49:40,219 --> 00:49:42,440
proves that the flat construction holds firm.

1109
00:49:42,639 --> 00:49:46,170
He builds this up step by step. Lemma 8 proves

1110
00:49:46,170 --> 00:49:48,730
the transitions work for branching nodes. Lemma

1111
00:49:48,730 --> 00:49:51,050
10 proves you can take any 2D tree and break

1112
00:49:51,050 --> 00:49:53,090
it down into a sequence of flat 1D transitions.

1113
00:49:53,469 --> 00:49:56,070
And then we hit Lemma 12, which spans two full

1114
00:49:56,070 --> 00:49:59,409
pages of agonizing subscripts. What is the conceptual

1115
00:49:59,409 --> 00:50:02,530
takeaway of Lemma 12? Lemma 12 proves the reverse

1116
00:50:02,530 --> 00:50:05,409
operation. It guarantees that if you have a sequence

1117
00:50:05,409 --> 00:50:07,670
of flat transitions in your new GPRIME machine,

1118
00:50:07,909 --> 00:50:10,510
you can perfectly reinflate it back into a valid

1119
00:50:10,510 --> 00:50:13,280
2D tree in the original grammar. He mathematically

1120
00:50:13,280 --> 00:50:15,440
guarantees that the flattening process is completely

1121
00:50:15,440 --> 00:50:18,239
lossless. No structural information is destroyed

1122
00:50:18,239 --> 00:50:20,480
when you squish the tree into a line. Which leads

1123
00:50:20,480 --> 00:50:24,280
to the final triumphant strike, theorem 10. If

1124
00:50:24,280 --> 00:50:26,920
G prime is formed from G by the construction,

1125
00:50:27,260 --> 00:50:30,519
then there is a derivation of Z in G if and only

1126
00:50:30,519 --> 00:50:33,159
if there is a derivation of Z in G prime. The

1127
00:50:33,159 --> 00:50:35,880
two grammars, despite looking completely different,

1128
00:50:35,980 --> 00:50:38,750
are functionally... perfectly equivalent and

1129
00:50:38,750 --> 00:50:41,690
since g prime was explicitly built using only

1130
00:50:41,690 --> 00:50:43,889
rules that go from left to right and which are

1131
00:50:43,889 --> 00:50:46,269
the defining rules of a type 3 finite state grammar

1132
00:50:46,269 --> 00:50:48,969
then any non -self -embedding type 2 grammar

1133
00:50:48,969 --> 00:50:52,150
can be perfectly losslessly simulated by a simple

1134
00:50:52,150 --> 00:50:54,909
type 3 markov source exactly the only thing a

1135
00:50:54,909 --> 00:50:57,349
markov source cannot simulate is a self -embedding

1136
00:50:57,349 --> 00:51:00,969
loop therefore theorem 11 stands absolute the

1137
00:51:00,969 --> 00:51:03,250
sole source of excess generative power of phrase

1138
00:51:03,250 --> 00:51:05,269
structure grammars over finite state machines

1139
00:51:05,269 --> 00:51:07,699
is self -embedding it is like a biologist sifting

1140
00:51:07,699 --> 00:51:09,980
through millions of lines of DNA and isolating

1141
00:51:09,980 --> 00:51:12,599
the exact single gene that separates two different

1142
00:51:12,599 --> 00:51:15,940
species. Chomsky dug through the chaos of unrestricted

1143
00:51:15,940 --> 00:51:18,440
Turing machines, navigated the tangled lying

1144
00:51:18,440 --> 00:51:21,599
trees of context -sensitive rules, built impossible

1145
00:51:21,599 --> 00:51:24,539
hypothetical languages, and squished 2D structures

1146
00:51:24,539 --> 00:51:27,480
into 1D lines, all to isolate this one, pure

1147
00:51:27,480 --> 00:51:30,679
mathematical property. Self -embedding. The ability

1148
00:51:30,679 --> 00:51:33,500
to pause a thought, open a new thought inside

1149
00:51:33,500 --> 00:51:36,860
it, and return to the original thought. That

1150
00:51:36,860 --> 00:51:39,019
geometric loop is the spark that makes human

1151
00:51:39,019 --> 00:51:41,900
language possible. And it is the strict mathematical

1152
00:51:41,900 --> 00:51:45,420
boundary that simple finite automata cannot cross.

1153
00:51:45,719 --> 00:51:48,860
It is a profound realization. By translating

1154
00:51:48,860 --> 00:51:51,639
language into pure algebra, Chomsky didn't just

1155
00:51:51,639 --> 00:51:54,139
classify different types of grammars. He mapped

1156
00:51:54,139 --> 00:51:56,360
the absolute boundaries of computational power

1157
00:51:56,360 --> 00:51:59,079
itself and placed human cognition squarely on

1158
00:51:59,079 --> 00:52:02,269
the map. It is a staggering achievement. To summarize

1159
00:52:02,269 --> 00:52:04,750
this incredible journey for you, we started by

1160
00:52:04,750 --> 00:52:07,070
looking at language not as a cultural quirk,

1161
00:52:07,070 --> 00:52:09,349
but as a mathematical function enumerating an

1162
00:52:09,349 --> 00:52:11,949
infinite set. We learned that simply generating

1163
00:52:11,949 --> 00:52:14,250
the right words isn't enough. We need a structural

1164
00:52:14,250 --> 00:52:16,369
description, a blueprint, to actually understand

1165
00:52:16,369 --> 00:52:19,210
the sentence. We traversed the Chomsky hierarchy

1166
00:52:19,210 --> 00:52:22,050
from the unrestricted black box chaos of type

1167
00:52:22,050 --> 00:52:25,030
0 down through the ranks. We rejected the power

1168
00:52:25,030 --> 00:52:28,110
of type 1 because its context -sensitive permutations

1169
00:52:28,110 --> 00:52:31,070
tangled our parsing trees and lied to us about

1170
00:52:31,070 --> 00:52:34,059
what words were. And finally... Through a grueling,

1171
00:52:34,059 --> 00:52:36,900
brilliant mathematical construction, we prove

1172
00:52:36,900 --> 00:52:39,539
that the magic of type 2 and the magic of natural

1173
00:52:39,539 --> 00:52:42,880
human language lies entirely in the power of

1174
00:52:42,880 --> 00:52:45,960
the nesting doll. Self -embedding. A rigorous,

1175
00:52:46,199 --> 00:52:48,599
exhaustive, and ultimately beautiful framework

1176
00:52:48,599 --> 00:52:51,300
that changed cognitive science forever. But as

1177
00:52:51,300 --> 00:52:53,619
we wrap up this deep dive, I want to leave you,

1178
00:52:53,739 --> 00:52:56,260
the listener, with a final, slightly provocative

1179
00:52:56,260 --> 00:53:00,079
thought to mull over. Because Chomsky, ever the

1180
00:53:00,079 --> 00:53:02,920
relentless scientist, ends this monumental paper

1181
00:53:02,920 --> 00:53:05,559
with a cliffhanger he really does he notes that

1182
00:53:05,559 --> 00:53:07,619
while we have neatly categorized these mathematical

1183
00:53:07,619 --> 00:53:10,280
types it doesn't actually appear easy to arrive

1184
00:53:10,280 --> 00:53:12,659
at a perfect structural characterization for

1185
00:53:12,659 --> 00:53:15,099
natural languages that are type 2 but beyond

1186
00:53:15,099 --> 00:53:17,539
type 3. But more importantly, he hints and he

1187
00:53:17,539 --> 00:53:19,440
goes on to prove in his subsequent work that

1188
00:53:19,440 --> 00:53:22,119
even the beautiful self -embedding type two phrase

1189
00:53:22,119 --> 00:53:24,820
structure grammars aren't enough to capture a

1190
00:53:24,820 --> 00:53:27,260
full natural language like English. He realized

1191
00:53:27,260 --> 00:53:30,239
they are still too rigid to easily handle the

1192
00:53:30,239 --> 00:53:32,980
complex, elegant, sometimes paradoxical ways

1193
00:53:32,980 --> 00:53:36,400
we naturally speak. He argues that to truly capture

1194
00:53:36,400 --> 00:53:39,320
human language, we require an entirely different,

1195
00:53:39,420 --> 00:53:41,940
even more powerful device sitting on top of the

1196
00:53:41,940 --> 00:53:45,519
phrase structure, something he calls. transformational

1197
00:53:45,519 --> 00:53:48,000
grammars. Operations that can take an entire

1198
00:53:48,000 --> 00:53:50,880
massive parsing tree pick it up and mathematically

1199
00:53:50,880 --> 00:53:53,900
transform it into an entirely new tree maintaining

1200
00:53:53,900 --> 00:53:56,260
the underlying meaning while radically changing

1201
00:53:56,260 --> 00:53:58,500
the surface structure of the sentence. It adds

1202
00:53:58,500 --> 00:54:01,019
an entirely new dimension of computational complexity

1203
00:54:01,019 --> 00:54:04,570
to the model. So ask yourself this. If human

1204
00:54:04,570 --> 00:54:06,909
language fundamentally requires a computational

1205
00:54:06,909 --> 00:54:09,610
device even more complex than the nested self

1206
00:54:09,610 --> 00:54:11,610
-embedding phrase structures we just spent an

1207
00:54:11,610 --> 00:54:13,989
hour mathematically dissecting, what does that

1208
00:54:13,989 --> 00:54:16,070
say about the sheer staggering computational

1209
00:54:16,070 --> 00:54:19,050
horsepower hidden inside your own brain every

1210
00:54:19,050 --> 00:54:21,090
single time you casually open your mouth to order

1211
00:54:21,090 --> 00:54:23,329
a cup of coffee? It suggests that the machinery

1212
00:54:23,329 --> 00:54:26,079
of the human mind is far more intricate. more

1213
00:54:26,079 --> 00:54:28,559
mathematically sublime than we ever could have

1214
00:54:28,559 --> 00:54:30,639
imagined before this paper was published. Remember

1215
00:54:30,639 --> 00:54:33,360
where we started? Comparing the organic messiness

1216
00:54:33,360 --> 00:54:36,099
of biology to the cold rigidity of a mathematical

1217
00:54:36,099 --> 00:54:39,000
machine. Well, Chomsky built the X -ray machine.

1218
00:54:39,119 --> 00:54:41,380
He pointed it at our messy, chaotic language,

1219
00:54:41,440 --> 00:54:43,519
and he showed us the bones. And it turns out

1220
00:54:43,519 --> 00:54:45,980
the skeleton of human thought is made of pure

1221
00:54:45,980 --> 00:54:48,039
mathematics. Thank you for joining us on this

1222
00:54:48,039 --> 00:54:50,699
incredibly dense, mathematically rigorous deep

1223
00:54:50,699 --> 00:54:52,840
dive into the formal properties of grammars.

1224
00:54:52,920 --> 00:54:55,039
Keep exploring the structures hidden in plain

1225
00:54:55,039 --> 00:54:55,340
sight.