Chomsky Hierarchy - Computerphile
ฝัง
- เผยแพร่เมื่อ 12 ม.ค. 2016
- Uncomputable through to finite state - Professor Brailsford explains Chomsky's hierarchy.
Turing and the Halting Problem: • Turing & The Halting P...
"Most Difficult Program" - Ackermann Function: • The Most Difficult Pro...
Busy Beaver Turing Machines: • Busy Beaver Turing Mac...
Finite State Automata: • Computers Without Memo...
Reverse Polish & The Stack: • Reverse Polish Notatio...
Programming in Postscript: • Programming in PostScr...
Professor Brailsford's Notes: bit.ly/computerphile_Chomsky
Professor Brailsford's t-shirt kindly supplied by Peleg Bar Sapir
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
Chomsky's hierarchy is also the hierarchy of formal grammars of formal languages
His voice is so soothing.
Hey Mittens is here too! He's everywhere
razor5cl Hello!
+CatnamedMittens “Michael Bialas” He kinda sounds like Winnie the Pooh
Waiting impatiently for computerphile video to interview Mr Chomsky =)
+François A is it really worth his time
+YumekuiNeru
Chomsky does interviews all the time. It's worth our time :)
those are usually for new content or new opinions though rather than basic introductory stuff right
YumekuiNeru I've seen him be interviewed by his students and others for all sorts of stuff. He actively tries to be accessible.
François A Chomsky will do interviews/debates with just about anyone who asks.
I emailed Noam thanking him for his work and he replied.
You get a tasty cookie award
noam chomsky is criminally underrated
Choam Nomsky
Соɾу ℛ., wow! When did that happen? Back when he did the work? Or more recently, when you discovered it (maybe when you saw this video)?
What's his email?
Professor Brailsford is my favorite Computerphile person.
>Professor Brailsford is my favorite person.
You should do more Theoretical Computer Science. Machine Learning (SVM's, regression, KNN, etc) or like the difference between Stochastic and Deterministic computing. Video's like that.
agree
Data science and machine learning is really boring especially for entertainment videos.
Vladislav Boshnakov Speak for yourself.
+Vladislav Boshnakov Adaboost and maybe perceptron algorithms have interesting stories about their inception, SVM has an interesting way of practical computation, and in the case of neural networks, results can be entertaining.
+David Futschik Hmm, yeah neural networks could make an interesting video. I like this idea.
so grateful for this video! I am studying computer science right now and my lectures aren't covering this kind of overview, everything is very granular and practical. It's so helpful to know this stuff
Hehe... the irony of Chomsky, an anarchist, developing a hierarchy... :-p
The irony being that he was a linguist, but linguists found little or no use for his mathematical innovation.
The computer scientists, on the other hand, lapped it up.
The anarchists oppose unjust hierarchies, in other words, they are not against all forms of hierarchies.
there's no irony in this, only if you do not know what anarchism stands for. the circle around A symbolizes order. how can you get order if not through some sort of hierarchy
@@danijelstarcevic007 There is irony. If you don't try to be overly strict, if you allow yourself to be loose, there is.
@@PedroTricking sure
I want Professor Brailsford to read me bedtime stories. He's the best!
I didn't expect to hear about Chomsky here!
Chomsky is Underated When it comes to Computer Science, His work Influence IBM FORTRAN, Language, Without FORTRAN, Compilers for advanced Software wouldn't Exist All the Advanced Video GRAPHICS Games Fast Microprocessors probably wouldn't Either, At least as we Know them
I have to say that I have the exam of fundamentals of information technology next week and this video filled most of my gaps and questions about Chomsky's Hierarchy.
Thank you for sharing this video and thanks Professor Brailsford for his very clear explanation.
Really looking forward to watch and learn more about FSA in the coming video!
I wish I had taken Computer Science in school. I gained a love of it after graduating and am trying to piece it all together after the fact...
It's always a pleasure to watch Brailsford be so enthusiastic. All my (excuse my description) 'older' teachers were always boring as all hell but Brailsford is always a blast to listen to.
Great video! :-) Since you started with the Chomsky hierarchy and Finite State Automata, you could also do a few videos about program compilation (lexical parsing, syntax parsing, abstract syntax tree, intermediate representation, compiler optimizations, three address code etc.). Also a video about assembly language could be interesting - just a few ideas :-)
+Jakub Beránek could be? i'd say "would be"!
+Jakub Beránek
I'm perfectly happy to progress,eventually, to elementary parsing and LL(k) LR(k) as subsets of the deterministic Type 2 circle. But it all depends on how the viewing figures turn out as to how far we can develop some of the details.
@@djdedan I might not be interesting - though if the teacher is the same, I doubt it.
I love Professor Brailsford's vids!
Beautiful, one of my favorite topics during university!
Had no idea Chomsky ever did more than politics/sociology... Mind-Blown!
+Ionuț Dorobanțu Seriously? He is famous for revolutionizing linguistics and helping spark the birth of cognitive science. That's his initial claim to fame.
Chomsky is a sort of universal genius.
Not really he has two narrow fields of expertise. politics and cognitive science. Don't think he has an artistic bone in his body.
Those list the fields impacted by his work which was on a very narrow focus (linquistics). But his work was so important it has had a broad range of application. His two areas of expertise are linguistics/cognitive science, and then politics. He doesn't paint. He doesn't write novels, knows very little about pop culture or sports. He has made no discoveries in biology or physics or chemistry.
@@lenglain ur a sad person
So glad I found this channel.
that noam chomsky appears everwhere gash danggit...
plus i'd have to side with american's on "stack" vs "push down store" :-/
+Max Schneider A C++ vector isn't a stack though, it also has push_front, so you can't really say that the C++ vector is defining a stack push operation as 'push back'. The actual C++ stack just has push, which is about as open-ended as you can get in terms of naming the operation.
+DjDedan I'm torn about that. The key to it is that I can't yank a piece out of the middle like a Jenga tower. "Stack" doesn't help distinguish that fact much.
Still a stack. First out or last out or both first and last out still a stack. Correction: see comment below.
Except you can do push_front() followed by pop_back() which turns the vector into a queue, so saying 'push front' is a name for a push operation is wrong, it's identifying the type of push and if you want it to function like a stack, the identifiers must match.
I could easily write an array class with a function called 'push_banana()' and a function called 'pop_banana()', this still acts like a stack, but does that mean I can call a push operation 'push banana'? No, it does not.
Should have been more specific in saying 'collection' rather than incorrectly generalizing 'stack'.
Noam Chomsky is one of the smartest people of the last century.
+Bad Bandwidth You must be a troll.
+Bad Bandwidth A prolific author, but vastly overrated.
+Fabio P Your face is overrated. What a moronic comment.
***** Nice. Very mature.
+Fabio P Care to elaborate on why he is overrated?
Given you've talked about this, it might be worth talking about general recursive algorithms vs primitive recursive algorithms.
+Cíat Ó Gáibhtheacháin He did, in the videos about the Ackermann function.
+Cíat Ó Gáibhtheacháin I don't think I've seen any Computerphile bits on tail recursion. That would be a nice addition. Maybe Professor Brailsford would like to discuss the subject.
Chomsky is awesome
I've never gotten around to researching FSA, so I don't know how they are constructed or how they do their work. I'm really looking forward to get an introduction to this topic by Computerphile. :)
more theoretical computer sci videos we need !!!
cool，nice intuition, great help! thanks~
Weird to hear Chomsky mentioned without any mention of his political activism. A great linguist but outside of academia, i`m sure his work on US foreign policy is what he is best known for.
+calvinjones Not outside the US.
+Linvael Search amazon for him...
+calvinjones Chomsky's influence has been felt in many different disciplines. He is often referred to as "the father of modern linguistics", where his greatest contributions lie. He is also a central figure in what is known as the 'cognitive revolution' in psychology. Then there is the contribution mentioned in this video to compiler theory in computer science, as well as some important contributions to the philosophy of science. Amazingly, his political writing and activism was concurrent with all of this from the Vietnam war onward. He is the most cited living author in the world, and one of the most cited in history.
+calvinjones he also appears in biology (his linguistic theory is very influential on the evolution of language, which is driven by the evolution of the brain) and now he appears in computer science... but yes i first heard of him through his political activism, the guy is pure renaissance man!
+calvinjones I had no idea Chomsky was involved in politics!
Had to learn this in Programming Languages course couple years ago.
It is incredible that this is the way languages are studied now. Like real languages.
At some point I will really sit down and learn about Chomsky's work.
+Cotonetefilmmaker Actually the theory is highly controversial-or rather it is controversial that it is useful to think of natural languages in these terms, as Chomsky points out in every single lecture he gives on linguistics (for at least the past ten years, possibly more). Broadly, neuro and psych types tend to be less interested in this way of conceiving of language, while linguistics itself is split down the middle into pro- and anti-Chomskyan camps (sad but true). There are notable neuro exceptions though. Check out the work of Angela Friederici on Broca's area, a potential locus of complex syntactic processing in the brain.
I would appreciate hearing more about non-deterministic Turing machines.
I didn't understand anything in this video.
lol
+Raumance Don't feel bad he didn't really explain that that the circle thing was the Chomsky Hierarchy. The explanation was also a bit wordy. From what I understood, if a program need no memory it is in in circle the in the center and you prgress further out the more memory you need to the point where you exhaust all memory. This would be the outside of the circles.
+Raumance
I wanted to set the scene first with the Chomsky "circles" diagram. I'm hoping that it will all begin to make more sense to you as we do specific examples from within each of those nested circles.
+Raumance To make it simple, FSA doesn't need memory because FSA is memory.
Take an example of an automatic door. Let's say, there's a button that opens/closes door depending on the current state of the door. And that button, when pressed, calls some interrupt in the system.
The memory-way of implementing would be a method like this (assuming initial state is door being closed):
setOnButtonPress = onButtonPress; // connect your interrupt
door = closed;
onButtonPress: if(door = open) closeDoor; door = closed; else openDoor; door = open;
The FSA-way of implementing the same thing would be more like this (still assuming initial state is door being closed):
setOnButtonPress = onDoorClosed;
onDoorClosed: openDoor; setOnButtonPress = onDoorOpen;
onDoorOpen: closeDoor; setOnButtonPress = onDoorClosed;
If you approach the problem with memory, you have to have a variable "door" holding the state of the door. If you go with FSA approach, the program changes state and there is no memory needed.
Raumance It Just means that Two STATE machine .The two are its PROGRAM, no other memory state is required like a Light Switch on and off. more COMPLEX machine will have more bits like 8 16 32 ECT .And do Require Memory because they have more than yes and no States
We got the history with this video. We still need DFAs/SMs covered.
Knowledge of how these levels relate to memory usage is really abstract way to approach the topic. I think it would be better to present how to define a language, and what rules you have to follow while defining to fall into more and more restrictive categories. Possibly with a special on regular expressions somewhere in there.
Linvael I believe That Regular Expression Relates to Finite State machine and Context Sensitve Language, While Recursively Enumerable Relates to Algorithms State machine and Context Free Language
Hello Computerphile!
Please give us a reading list by Professor Brailsford, if possible.
Thanks for your videos.
Did you ever do an episode on Quantum Computers?
Professor Brailsford looks and acts almost exactly like my late grandfather. It's uncanny how similar they are. That's a good thing, mind, gramps was the shit.
I would love to see a video on pushdown automata.
That shirt is fantastic
The interesting thing is that the computers we actually have are finite state machines. They have a very large finite number of states, to be sure. But they are finite.
This is what you call interdisciplinary work!!! :P
Does anyone remember which video they talked about bigger and smaller infinities?
New subscriber here. Thanks.
Great video, can't wait for the next one. However, I'm still waiting for a video on quantum computers. Isn't there ANYONE who will talk to you about them!
If you hear this guy talking (or even just look at him) you can feel he's wise
That's called being in a cult.
the shirt!!!! someone made it for him!
someone made that shirt, awesome
Just watched that video: log(b2) 10 = 3.322
That makes me happy, too... would have been better without the glitter tho \s
I've been working on splicing system and formal language theory for a few months, why only now i found this channel? :(
I had no idea that Chomsky had anything to do with computer science
"Like the 'ch' in 'lock'." Brilliant ;)
Jimmy De'Souza I was seriously amused and you didn't tell me any news :) Have a close look at my spelling which matches his pronunciation.
Jimmy De'Souza It's day and night from when he just says the "ch" so I really don't get why you are so up in arms about this.
I typed in a Dragon 32 program called write on but it won’t work shall I send you it to have a look at so you can have a look at it thanks????
I'd be quite interested in DNS records. How they propagate and so on
How does a computer distinguish between the binary behind different file types (say between a picture file and a sound file)? How does it know certain machine code should be translated to a picture or sound etc.?
+Daniel Davies The first part of a file (you can call it the header), tells the computer how to interpret the rest.
+Harald Husum Thank you!
The file extension tells it
So pretty much every modern computer is basically a sophisticated manifestation of the ideal Turing machine. So what's the Turing Machine equivalent for quantum computers? I imagine it would be quite different.
Is there an almost-solution to the halting problem that is usually right, but not always? Or a machine that feels TC but where halting is decidable? I need this for... um... research.
I don't know about any such approaches that work with general programs. It is certainly not impossible. It is only impossible to determine for a general program with a general input whether it will halt or not. The halting problem doesn't say anything about the decidability for a special task. So it is certainly conceivable that there might be heuristics which are usually right.
What is USUALLY right? What does that mean? If you always guess the same way and pick well, you're right at least 50% of the time
Finite State Machines DO have a type of memory - state memory. The simplest form of a Moore State Machine is combinatorial logic followed by state register.
We all know a FSM cannot REMEMBER things like the number of a's it has read while reading a^nb^n as input. Using the limited memory a FSM has, it can only remember the finite number of states and the state transitions. Does a Moore Machine remember the number of symbols scanned? I am unaware.
Usually I understand at least 80% of your videos but this time I had no idea what you were talking about
+Henrix98 This is advanced class university stuff. Core only without fluff.
Make a video about esoteric programming languages like Befunge, brainf*ck and whitespace (to expand on the concept of turing machines) :O
If you're confused, watch all the linked videos first. This is a bit of a "now that we are all on the same page, here's this other idea" video.
Haha someone made him the Log2 10 shirt that he said he'd wear in another video when he was explaining the number of bits in a computer required for different numbers of different digit counts.
This is probably the most theoretical topic that computer science undergraduates traditionally learn. Do formal languages and automata theory have any use in software engineering?
+ElagabalusRex Yes. For example, regular expressions can be translated into finite automata, and this automata can then be "executed" when matching a string.
+ElagabalusRex Yeah, it's actually pretty important for making compilers (probably other things, too).
+David Vaughan Every computer program is basically a compiler. It accepts some kind of input and produces an output based on input.
+ElagabalusRex Sure. Understanding the theory helps you know the limits of what you can and can't do with each type of machine. For instance: You can't validate all XML or JSON with a regular expression or a finite state machine.
Language theory is super helpful when writing non-trivial language parsers or designing a new language. (I have done that twice in my career)
David Vaughan Indeed. But understanding it helps you to decide when to switch from ad hoc approach to automata. I know, I've written too many programs with ad hoc method when automata would have been better approach .... and vice versa. Which means I'm a poor learner ... but that's nothing new.
An example problem for each tier would have been nice. But how can you say that all computers are Turing machines, don't Turing machines have infinite memory? And finally, there's a typo in the description, it should be "Uncomputable through to finite state".
My son is named Noam after mr. Chomsky, but for his political work. I found it quite risible, then, that he should pop up here.
So this is why every programming language has a "But Sometimes, just in case" clause.
Do you think he sounds like David Attenborough, or is it just me?
This is one chapter of our High School Computer Science Book. Are you learning the basics of this in highschool?
+switchhax Do you learn the pumping lemma and all the proofs at High School?
No, we do the "Regular Languages" Part, the rest in this chapter is about what you need to prove/test different levels of language.
+switchhax If you do CS in college, you'll learn all the details of it in an upper level class called Automata and Formal Languages (or so it's called at my university).
+switchhax High school? What kind of badass high school you go to? I learned this stuff in the university ... and it was an advanced topic, which you didn't have to learn if you only wanted a bachelor degree.
I must calm you, we only make the basics of type 3 and what kind of concept you need to prove the different types. But how theses concepts work isn´t realy explained. From these concepts we only learned moreon the finite-state automaton.
Where is the human brain in the hierarchy?
What about the nervous system of a roundworm (smallest number of neurons for any living creature).?
I vaguely recall reading somewhere that there are some neural network variants which have been found to be Turing Complete. In which case, it's probably the case that the human brain is also Turing Complete.
Every useful computing device is a Turing machine but with limited memory. That includes Turing machines. If you get really pedantic, every machine that doesn't have infinite memory is a finite state machine, but that's silly, so we call them Turing machines that can run out of memory. A worm is probably closer to a real finite state machine
I love Chomsky and all his work, but it is questionable whether he, and certainly he alone, did the mathematical work on establishing the hierarchy. As I understand it, his main innovation was to see how such a hierarchy could be used to guide our theories about (the cognitive system behind) natural language. I believe Marcel Schutzenberger, who was also at MIT in those early days, was the real mathematical heavyweight in this work. Not to detract from Chomsky.
Happy to be corrected on this btw. And I'm sure there were others involved. Geoff Pullum, a respected mathematical linguist, has claimed (in his talk at the Cognitive Revolution 50 Years On event) that Emil Post was a crucial yet undercited inspiration to Chomsky in thinking about classes of string rewriting rules.
I'm lost but i l like being lost sometimes.
Can you discuss something on Genetic Algorithms ?? Plz
lol....Chomsky needs no introduction mang!
📺💬 When we are working with the recursive problem the time the American introduces a new device that can stack memory from the top and put it at the bottom, in the time it cannot access the memory address but few of them can create new possibilities to manage memory for sorting algorithms or hierarchy condition problem.
🧸💬 That benefits much especially the recursive function when you can perform time differentiate functions, For decryption cipher text you can sum for the target characters in the role but with differentiate you know first which sequence is important and turn the adding function use to break the code breaker into a pieces. ( read the previous VDO, there are multiple of methods for the cylindrical problem and Z-stop, P-stop )
🧸💬 A adding function can stop a new code breaker because it is easy and you cannot perform pattern determination without the correct pattern, result = ( previous cipher X current K ) + pattern, and when decrypting you just subtract the current message from the previous message or input its patterns.
🐑💬 In place of each line calculation now we know the difference of adding and product differentiation and the push-pop memory makes the game changed. The adding function still had powerful for new code breakers that is because you cannot direct substitution. ( read the previous VDO, the substitution method help about recursive problem )
Excellent pronunciation of "Chomsky" by Prof. Brailsford. He really nailed it. It's a Hebrew name of course.
0:40 *fewer and fewer
+Nulono
Groan ! Yes I started the sentence by intending to say "... less and less demand" and ended up by pluralising "demand" into "demands" for some reason. And the "demands", being denumerable, require the use of "fewer" . Fair point :-)
Did he just say linguistician
WAIT THAT'S A REAL WORD????????????????
didnt understand a bit...
ok gramps, where is the cookie
And then he went on to say things like iiiiii xD
Who doesn't know Chomsky??
Can confirm, the "ch" in his name is pronounced as in Scottish "loch". It's an Israeli name.
Apparently his mother was from modern-day Belarus (father from modern-day Ukraine). Similar language situation there, though.
He himself thinks it's "ch" like in "channel". But initially yes, it was Homsky, but the pronunciation changed with time, and here in Russia and probably any post Soviet place, we call him Homskiy (Хомский)
hi
+Bryzum FuckGoogle hi
+fugooglestupid you having a nice day?
Push Down Store? I like Stack better. That was my takeaway.
With all due respect: *linguist
+Monothefox with all due respect... liguistician..
both terms are equally valid
+AwesomeVindicator The term 'linguistician' never caught on. People, like me, who do research on how language works almost universally call themselves 'linguists', Chomsky included. This is admittedly confusing for people who understand this word to refer to people who speak many languages.
from wiktionary:
A person who studies linguistics is usually referred to as a linguist. The more accurate term 'linguistician' is too much of a tongue-twister to become generally accepted. - "Teach Yourself Linguistics", by Jean Aitchison
+cavalrycome A person who speak many languages is a polyglot a person who studies language would be a linguist.
He is genius.... Ah no... NEAR genius.
Hehe look at me guys i invented wired useless grammar let's called by my name so people don't forget me
Not every computer is a touring machine heh
+Victor Parker Computer == Turing machine
+Victor Parker Turing
Lol @ both of you trying to correct me. I didn't make a typo ;D
Computer == Turing machine.
Computer != touring machine.
Understand? :)
+Victor Parker Lol, sorry, I've red Turing :P
Chomsky has done so much to improve the human condition. Socialism or barbarism, folks
he never understand BF Skinner, neither bayes theorem
Fluid theory (Reproduction/Feed/Reasoning) decanted selfmultidimentionalover...
The polydynamics of the movement generates pseudo-autonomy as material property, of the autogenous phenomenon; existing.(...)
Simultaneous as my unidimensional variability...
unidimensional variability = live-beings
The social justice warriors are going to love this video.
I don't understand, how is America to blame for this?
Thing about Chomsky's lingustics theories is that they all break down or become ridiculously complicated and not believable if presented with a natural language sufficiently distinct from English (primarily in grammar and sentence structure). In most linguistics departments that aren't focused on indogermanic languages, Chomsky hasn't been relevant for years.
Of course, a simple hierarchy like this isn't really a theory, but just that, a hierarchy, a tool, and as such not subject to that.
joelproko No I studied them in Detail ,Their Perceived Complexity is The Result of Error in LOGIC of Language design using Formal Grammar, In Automata Theory FSM, Ect, . Chomsky Generative Grammar tried to correct this Error but was never implemented in Compilers and Software FRAMEWORK
This rambling makes no sense at all