Chomsky Hierarchy - Computerphile

Key Takeaways

recently we've had a request saying can computer file do something on finite State autometer and in considering what to do about that um it did seem to me that it would be a good idea to look at where finite State autometer sit in the scheme of things we've done a lot about touring machines for example we've covered the fact that really every single computer of any sort nowadays is a touring machine so what I'd like to do is to uh refer to a diagram which shows if you like the various types of touring machine a hierarchy where as you go inside you make less and less demands on what you need and if you look at this set of circles here I can even relate it back to some of the videos we've done previously you will remember that when we were doing the aan function we eventually decided that it's of the recursive sort which means it will terminate but it could take an awful long time if you remember in leading up to that I said there's a certain sort of touring machine outside that which is a real so and so which says sometimes the algorithm you give me will give an answer and you're happy but sometimes I will go into a loop and when you say how can I detect in general that you're in a loop the answer is you can't and we've done other videos of my colleague Mark jgo all about the halting problem as it's called and then we went one even worse we've been out in the Outer Perimeter of hyperspace here to say are there some problems that are so awful that no algorithm can exist and we did the Busy Beaver if you remember which is for a a sort of encoding of a particular touring machine it says look there's not a general algorithm here I'm not trying to do n factorial what I'm asking is for Machines of this sort can can you predict how many zeros they'll print out and the answer is there isn't an algorithm that can say how do those Busy Beaver PRS behave in general if only there was what you have to do is to run them all and just exhaustively say I don't know there isn't an algorithm just try them what happened after girdle and touring and others in the 1930s did all this is people started to say well these touring machines you know it's wonderful they're a pencil and paper thing but you could imagine building Hardware to do them and of course those are general purpose computers as we now know them but people said is there a sort of subset of touring machines where you can either say it doesn't need more than a definite amount of ram guaranteed that would be nice to know and those come out to be in this Inner Circle of type one here then people start to say hey there's this thing called a pushdown store which the Americans call a stack that's a one-ended memory device you you can't dip into it arbitrarily you can either take something off the top or push something new on the top so any addition or or any reading of your memory can only be done at the top of the stack is that a sort of special case yes it is and we've looked at that with your towers of Hanoi haven't we yes towers of Hanoi is a classic example of something where you just want to get hold of the whole bunch of discs and sort them in your hand like Ram you know just park that one the store that one there think about it put them back together and plun them back on the rod but you can't do that you can only do it one-ended and for something that you know you could I could do that in two or three moves if only I could take all the discs off you end up having to do 64 moves and then there's one right in the middle in this Inner Circle here that needs no memory at all in principle and that's what these finite State autometer are all about you might ask who discovered all this who filled in all these gaps because there we are with churing who perversely discovers the most General thing going in the 1930s but people don't know the simpler story underneath well the person who discovered it is still with us I think he must be in his late 80s now his name is Noam Chomsky and I think my friends say that you ought to pronounce it hsky like the in Lo but I'm happy to be put right on that he's genius NE genius guy I think he's been at U Harvard MIT places like that ever since who was young he really was talented he's a linguisti if you study the structure of natural languages any languages computer languages even I think I'm righted saying you're a linguisti well in the late 1950s he started saying look to understand natural languages better I'm going to look at the most restrictive form of language I can think of you know really simple things how about a language whose words are just strings of the letter I so I I I is a word five eyes I I I I I is a word any number of eyes is a different word how simple can that be yes very simple and then he went on to say things like yeah um what's a bit more complicated than that because those very simple languages as we'll find next time don't need any memory at all they really don't and what's the one that sits outside he didn't more investigations and said ah there is one where a one-ended memory will work yeah these are the Chomsky type two so remember Chomsky it goes as it were the opposite way around type zero is the most General right the recursively innumerables subset of type zero is the recursively enumerables that really do terminate aiman type one is the one where it needs Ram but you can predict how much RAM so he discovered that sort that's the type one touring machines with a predictable and finite amount of ram requirements and he just filled in the whole picture and in the period really from about 1959 to the middle 1970s huge amount of work filling in the middle of this diagram and that includes things like computer languages alol how to pause them how to compile them it was all filled in in the middle of this diagram but all basically referring back to that work that Chomsky did in 1959 saying these are the language varieties or 110 and when you get to 25 I put it inside a double circle which is the convention because that's the finished State you've put in 25p and the thing sort of thinks for a while and eventually goes and prints you out a ticket