name of this course is theory of computation and let us spend a little time to understand the scope of this course. Now, we have the word computation in the title and it is saying that our course is about the theory of this entity called computation. Now, when we talk of computation today clearly what we understand as computation is that you write some programs and you run the programs and computers and then in that way you carry out a computation. So, fundamental activity behind computation or the way computation is carried out by executing programs. So, what are programs? Let me write this term which we are all familiar with programs and in a way we can say that our theory is about programs. There can be various theories I need to now say clearly specifically what we mean by our theory that we will discuss here. But again if we think of the word program we know there is something fundamental behind this term even more fundamental because after all a program is nothing but nothing but an algorithm expressed in a programming language. So, we can say programs express algorithms you see already we are making an abstraction in this that we are saying that programs express algorithms. So, more fundamental notion than program is the notion of an algorithm. So, going back again what we can see that our theory is about theory of algorithms theory of computation, theory of programs, theory of algorithms all more or less denote the same thing in our context. What are algorithms for? We all know that let us let us let us enunciate clearly we know that algorithm what it does is it computes or it gives us a recipe for computing and input output mapping. So, let us again write this an algorithm is a recipe for carrying out input to output this seems obvious enough that when I have a program it is executing an algorithm and what is that algorithm? That algorithm is a finite effective step by step process or description of a process which we are calling a recipe more familiar term for carrying out a transformation of the given input to an output. Another way of saying this would be that an algorithm tells us how to how to compute a function. So, you see if I write like this a recipe for carrying out input to output transformation. So, in picture it will be like this is an algorithm and as we know that it tells me for a given input how to get its output. And then we can see this as telling me what is the output for let us say the input x if I call that output if I term that output output for x as f of x then we are we are dealing with an even more fundamental familiar concept is that of a function. So, as you know a function f is a mapping from some domain to some range and in this case the domain is this domain of all inputs and the range is the range of all outputs for a specific function. You may have an intuitive understanding of a function you may have an idea what the function should compute in other words given an x what f x should be, but that is not enough for actually obtaining given an x the value f x for that what we say is that we have to given algorithm to compute that function. So, we can say that an algorithm computes a function again that is kind of very straight forward simple understanding every algorithm computes a function. So, let us write this here every algorithm computes I should have said tells us how to compute the distinction should be clear between algorithm and function we all understand function is an abstract notion which tells me that here is this mapping between input and output domain and range and algorithm is telling me how to obtain the output for a specific input right. In other words we are using the word computes in that sense. Now, I can see basic goal of our theory is to figure out for what functions we can have algorithm. Now, that might sound a little unfamiliar we may think that if we can dream of a function if we can define a function if we can in some way tell somebody else about a function then that itself should be an algorithm, but really that is not the case. For example, let me provide a very simple illustration consider this function which is is prime right this takes a number. So, let us say my domain is the set of numbers and the range is is unknown and by that what I mean is supposing I say is prime and then apply it on a number then it is going to be the output is going to be or the answer the value of this function on the on the argument n is going to be either yes or no and now let me define when I want the answer to be yes and when I want answer to be no. So, let us say it should be yes if n is a prime the number n you have given as argument is a prime and it should be no if n is not a prime right. So, you have defined this function, but you see clearly we are not seeing this definition itself is not telling me given an n how to actually come up with the answer and the right answer and that would be as you know and you have surely written a program to compute this function you will have to give an algorithm which will tell me how to given an argument n which is a number n how to figure out whether it is a prime or not and that how to should be expressed in terms of simple operations which can be carried out on a computer right. So, these are all we know in other words we would like to write a program to compute this function. So, you see that underlying that program that algorithm is computing a function. So, coming back what we what we are trying to say that it may be possible to define a function, but the definition of the function does not immediately point out in all cases to an algorithm to compute that function. If that is the case then at least you can now see that there is a possibility that I may be able to define a function I may be able to describe what the output should be without having an idea how to obtain the correct answer. Although we have not possibly encountered such situations in our programming experience, but it might surprise you when I tell you that actually it is a fact that for most functions there are no algorithms to compute. In other words if you think of the class of all functions then only a tiny fraction only a tiny subset of these functions admit algorithms to compute them and this is something which we will be able to prove which we will able to demonstrate in our theory. So, in other words let me say a primary goal of our theory is going to be to figure out which functions can admit or will admit algorithms to compute them. Basic goal of our course that we are going to go through in this series of lectures may say as it is to identify the class of functions which admit algorithms to compute them. So, what we are saying is that there are some functions which are of the kind that for function f there is an algorithm compute f and there are some other functions rest do not any algorithms. So, in this class of functions that if you give me an input a then I will be able to tell you by carrying out by computing the corresponding algorithm for f what the value of the function will be on the argument a whatever be the argument, but in this case it may be that for some inputs I will be able to give, but there may be inputs for which I will not be able to tell you what the output is. In other words I will not have an algorithm in general to compute that function and as I said that most of the functions unfortunately if you like they fall in this class that they do not admit any algorithm to compute them. So, at the end of the course in principle you should be able to not only have examples which are very clear and which are in a way important of functions for which we will not have any algorithms we should be able to prove that such is the case with those functions and in principle again we will have the knowledge of the techniques to demonstrate that a function does not admit any algorithm to compute it and that as I said is going to be at the very end of this course. Now, the way we look at this problem although this is the fundamental thing this is our basic goal is to identify the class of functions which admit algorithms to compute them, but you will see in the course actually we will not talk about functions. Instead we will talk about a problem which is kind of related and I will have to show you the relation and that problem is called the membership question given a set and given an element whether that element is a member of that set. So, this is the question that will engage us for most of the course and let me clearly explain what that question is. So, let me understand let us understand what this problem is set membership problem actually very simple to state. So, very general problem that you know you have some set S and our problem is that given any A as input to decide if A is a member is an element of the set S. So, very simple there is a set in some way we understand what is that set and now you give me some element A and we would like to know whether this element belongs to the set S or not. Now, as I said all the time in this course will really be talking about this problem what we will do is we will be able to show various kinds of algorithms not the way you study in algorithms course, but through various models of computation the classes of set for which we can carry out this problem. Now, what is the connection between set membership problem and the basic goal that I had talked of here? You see if you think of a function f then remember that we said that function f notationally we always write like this that a function f is a mapping from some domain to some range r. Now, you might know that there is a very natural set which is associated with any function and that is that set is called the graph of f and that graph of f is a set and what is that set? That set is a set of tuples a, b such that f of a is equal to b. Now, the point is this that with every function f the you can associate such a graph and now suppose we cannot decide we cannot give an algorithm to compute or to carry out or to solve the set membership problem of graph of f. So, let us write it down suppose we show that there is no algorithm solve the set membership problem for the set graph of f remember this is a set and as we said this is this particular set is defined like this. Suppose we show that there is no algorithm to solve the set membership problem for the set graph of f then we can conclude that there is no algorithm to compute f also that there is no algorithm to compute f. So, what I am saying is that if we show that there is no algorithm to solve the set membership problem of graph f then there is no algorithm to compute the function f itself and this is quite easy to see and we can very easily prove the equivalent contrapositive statement and which will see that if there is an algorithm to compute f then there is an algorithm to solve set membership problem of graph f. So, if you have an algorithm to compute f then if somebody gives you this tuple a b now and you have an algorithm to compute f then what you can do is look at the first argument and compute f of a using the algorithm let me write this suppose there is an algorithm then a b given as input we compute f a using the algorithm for computing f. Somebody has given you the algorithm to compute f so you use that algorithm to compute f of a. So, a is what the first argument of this tuple and now supposing b is f of a then of course a b this implies actually b equal to f of a if and only if a b is a member of graph of f. So, therefore using the algorithm for computing f I can solve the set membership problem the set membership problem was given a b check whether this tuple is a member of graph of f this tuple is going to be a member of graph of f if and only if f a is equal to b and now I have an algorithm to compute f and therefore clearly give I take the first argument I compute f of a check whether b is equal to f of a and then I can answer whether a b is a member of the set graph of f. So, therefore this statement we have proved it is so easy right now if I can show therefore that there is no algorithm for computing for there is no algorithm to solve the set membership problem of graph f then I have shown that there is no algorithm to compute f and this is the reason you see that a function which is not computable we will be able to get to that fact by looking at the graph of that function and proving that graph of f is something is a kind of set is a set for which I have no algorithm to solve the set membership problem. Now, what does it buy you know instead of functions then I can talk only about sets and sets are more fundamental and in a way simpler objects and therefore the theory at least notationally becomes simpler although it manages to show existence of functions which for which we have no algorithms to compute those functions through the study of you know some kind of sets and this is the reason most of the in fact entire course will concentrate on sets and their membership problem rather than functions. In fact, although that is the basic goal in our mind because we would like to talk about programs and whether or not we can have a program to compute certain things you will see in fact that this problem is not something we tackle in its generality. What I mean is that the kind of sets for which we will consider set membership problem these sets are going to be very special kinds of sets and what are the sets for which we will consider set membership problem. See these sets are so let me write it our sets are going to be sets of finite strings. Let me explain these terms and talk of strings I need to first talk of alphabet and to talk of alphabet I need to talk of symbols. Now, so let me first use the term symbol what is a symbol we are not going to define it some only thing we would like to say about symbols that they are as you know them for example, 0, 1 these are symbols. Similarly, a, b these are symbols and what another term that we are going to use is called alphabet. So, an alphabet is a finite set of as an example this is an alphabet. There are two symbols 0 and 1 the set comprising of these two symbols is an alphabet. Also another example could be a, b, c, d all the way through z and you can of course give many other examples of finite sets which are made up of or which comprise of symbols and now let us just consider this set a, b, c. So, this is an alphabet because this consists of it has three members three symbols a, b, c and again another familiar term is a string over these symbols. So, what is a string? String is we just write an ordered way we write these symbols one after another up to some point. So, let us say b, a, a, b, c this is a string over this alphabet. So, we can we can we can formally define all this more carefully, but this notion is so simple you get it immediately that this is a string in which the first symbol is b second symbol is a. So, there is a notion of ordering we can talk of first second third fourth fifth and also there is a notion of length because this has you can see the its length is 5 because it has 5 symbols and this is also a finite string there could have been infinite strings over the same alphabet, but we will restrict ourselves to finite strings over an alphabet. Now, suppose sigma is an alphabet then sigma star denotes the set of all finite strings over. Now, supposing my sigma is 0 1 suppose as example I take sigma is 0 1 then what is sigma star it is not difficult to see. So, what are the strings over this alphabet they are going to be binary strings. And we said sigma star denotes the set of all finite strings over sigma and this is the binary alphabet. So, therefore, sigma star in this case is going to be the set of all finite binary strings. So, as we are saying that consider the binary alphabet which consists of just two symbols 0 and 1 in that case the sigma star is going to be the set of all finite binary strings. By this what do I mean to finite binary strings you know we do not allow in sigma star to have an infinitely long string, but all strings whose lengths of finite they will be members of sigma star and those are the finite binary strings. So, there is really no upper bound on the length of strings which we have in sigma star, but at the same time every string any particular string that we take in sigma star that has a finite length. Is this notion clear this is an infinite set and all its members are you know have finite lengths like set of numbers set of integers that is an infinite set. Each integer itself is some kind of finite object it is let us say 10000 it could be 1 billion it could be a trillion. So, number can be arbitrarily large similarly here the strings can be arbitrarily large, but each string in sigma star is finite. So, now there is one very very important notion that we are going to introduce and that notion is that of a formal language.  So, sigma star recall that it has the set of all binary by binary strings over the alphabet sigma and you take some of them possibly an infinitely many of them leaving may be some out and that constitutes a formal language over the alphabet sigma. So, it is clear that for this alphabet for sigma is again binary alphabet 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 right. This is a set of strings over the alphabet 0 1 and clearly this is a subset of this set sigma star. So, this is a language. So, we can say that this is an example of a binary language because all its strings are over the symbol 0 1 and this of course, a finite language, but more interesting would be the example let us say L 1 say x is in 0 1 this is an alphabet. Now, I am putting the star over it. So, I mean x is a binary string such that x has even number of 0s and even number of 1. How many such strings are there clearly infinitely many at the same time not all binary strings are in this language L 1. So, L 1 is an example of a language over 0 1 which is infinite right, but which is not the entire sigma star. So, this language L 1 is a proper subset of we can write like this is a proper subset of sigma star. So, we have introduced a number of terms let me just say demerit them and briefly explain once more what each are each of these symbols is. So, first of all we talked of symbols then we talked of alphabet, then we talked of strings over an alphabet, then we talked of sigma star for alphabet sigma and finally, we talked of a formal language very quickly symbols are like 0 1 these are symbols alphabet is set of symbols. So, this is an alphabet string over an alphabet over this alphabet 1 1 0 1 0 1 1 this is a string right sigma star over this alphabet is the set of all finite binary strings.  So, therefore, L such a formal language is also a set which has a number of finite strings in general over the alphabet that we are dealing with in this case in this example at least that alphabet was the binary alphabet. Now, the connection with what we were saying before is this that we shall be concerned with the set membership problem. So, now, therefore our problem is going to be somebody has some formal language L in mind and the problem therefore is very concrete they give me a string and I have to determine whether that string is a member of the formal language. Now, very briefly although we had set in terms of the graph of a function is can be seen as a set, but then what is the justification of talking about or restricting ourselves only to set membership problems of languages and that is because the idea is really very simple is it when you write a program then that program takes some input and that input is what is actually a string because that input you have you need to key it in through the keyboard or maybe it is coming through a file whatever it is you can think of that input to be a string over some alphabet and the output is again in general is of course not yes or no as in the set membership problem, but here we appeal to what we said earlier because our goal is to show that something cannot be done by programs and so if that is a function then if we can show that the corresponding graph which is going to be in this case going to be basically strings you know basically graphs those graphs of those functions that we are interested in since our inputs are going to be strings outputs are going to be strings. So, these are going to be pairs of strings pairs of strings themselves can be seen as a string and therefore it is really a set membership problem where the sets are really sets of strings and these strings are finite strings right I mean you never or it does not make sense to say that my input is a string which is infinitely long because such a input you can never even provide to the program completely for that program your program to work on that input. So, inputs are always finite and in fact they are always finite strings in the programming context. So, therefore this restriction is not something which is very restrictive right although it seems a great restriction you see from functions we are coming to set membership and then again we are saying that we are not interested in all kinds of sets, but only sets which are just sets of strings over finite alphabet. Now, that really is the basic issue in this course that you know ultimately of course we will be talking about you know this question of whether certain set membership problem admits an algorithm or not, but we will come to that goal in a series of steps if you like. So, what we are going to do is we are going to do we are going to invert the problem in some sense we will think in terms of models of computation let me write this term and that means some abstract way we are saying we will describe a class of algorithms and that abstract way in fact going to be by specifying what are called automator. These are again terms which will be much clearer when we see really examples of and we deal with them. So, our models of computations let me just say this for the time being automator of various kinds. So, we will define a class of automator and then we will ask the question what kinds of set membership problem this class of automator can solve the kinds of automator that we are going to see. We will start with a very simple class of automator they are called finite state. Now, even here there will be various kinds you will see later deterministic non deterministic and then we will study what kinds of languages for which this model of computation can solve their set membership problem after which and this is this is going to take at least you know 15 20 lectures and then we will talk about in terms of automata that is going to be pushed down automata and again we will study the classes of languages for which pushed down automata will be adequate to solve their membership problems. Then finally, we will look at the most general class of automata which is possible you might have heard of disturb therefore, Turing machines and as we go along there will be many other things you know we will study and for example, we will study the notion of grammars and here we will study a regular grammar context free grammar will briefly mention what are context sensitive grammar and then finally, they have you know unrestricted grammar and there will be some correspondence with these things that we are going to study and it is at this point so as I said at the almost when we come to the end of the course or in the last part of the course we are going to encounter set membership problems for which there will be no algorithms to solve. We will stop here and in the next lecture onwards we will start with finite state automata and we will be dealing with them for quite some time.


They came across a giant orca, on closer inspection something didn't look right. Talking to animals is a bit difficult, and we're excluding Koko from the equation, as he's the gorilla who knows to use and understand sign language. We're talking about whales and the way they communicate with us. It's a bit weird, yes, but bear with us, because this story is one of a kind. Just when you thought you've heard it all, a man saw a whale that was trying to make him understand that something was wrong. And when the man got closer, it was obvious the whale was slowly dying if it didn't get some help. Mick Miniguz is a boat captain and he organizes tours for people who want to watch whales in California. But one day, he saw a humpback whale that looked like she needed some help. But what could he do? Miniguz couldn't just dive with his team and help the whale on his own. He knew he needed more people to the rescue mission. Something had to be done fast, of the whale's life would be in danger. He had a boat, but he needed more than his crew of divers. So, he called some experts at the Marine Mammal Center, who are a non-profit organization based in California. They had a lot more experience. The rescue organization has been saving mammals in the same situation as this whale was and Mick knew they were experienced over decades of saving sea creatures. But this case was one of a kind. The Marine Mammal Center's main focus is to save animals that are hurt in the ocean and release them. So far, they have rescued over 20,000 mammals in the sea, sea lions, seals, and whales. Mick reached out and they all went back to Farallon Islands. Wondering if they were too late to the rescue, a few crabbers told Mick the injured whale's last location. So they went to the place and hoped the whale was still alive. Then, they reached her, she was 50 feet long. The troubled whale was still alive, but something was not right. She had an awkward swimming pattern. She kept remaining at the surface of the water when normally, a whale comes to the surface to take a breath and then it dives back. What was wrong with the poor whale? The lead diver, James Mosquito, knew something was wrong. He and his team dived and immediately saw what was wrong. The whale was caught in a very strong rope, called Blue Steel. She was trapped. Crabbers used the rope to attach their traps to boys, but the rope should have been at the bottom of the ocean. The whale had no chance of surviving if the rope wouldn't have been removed. But it was easier said than done. You won't believe what they did next. There were almost 250 feet long ropes around the whale and she couldn't move freely. And then, when the whale came up to take a peek above the water, she looked at the divers as if she was begging to be helped, said James. James said that, the whale came up on a breath, came up, put its eye above the surface, looked at me, I could tell it was looking at me, and just stayed there. She was silently waiting to be rescued. And when they got closer. The whale was in terrible pain, as the ropes tore into its body, tearing bits of blubber and as she struggled to get free, she was making it worse. The divers didn't have much time to help her, so they dived under the whale. It was shocking. Diving under the whale, James couldn't believe what he saw. Not only the whale was all tangled in rope, but there were lines all around her, going through her mouth and twisting around its tail. James lost hope. I was the first diver in the water, and my heart sank when I saw all the lines wrapped around it, said James. He also said that in those moments, he didn't think we were going to be able to save it. But they had to try. It was even worse. The whale constantly came up to get air and remain to the surface, because deep underneath her body, there was a 3,000 pound anchor that kept pulling her down. The poor whale was struggling to keep her blowhole above the surface of the water, fearing that if she went into the water, she might never be able to come up for a breath of air. Thankfully, she was a gentle mammal. Five hours later. The divers were lucky that the whale was swimming gently, as a flick of the tail could have caused serious injuries to the men. But even with the danger lurking, the men couldn't back down. They had to save the whale. It took the team 5 long hours to set the whale free. And then, James witnessed a most remarkable moment, next I know, I have this whale coming right up at me, it was like a slow moving bus. James continues, it literally stopped 6 inches away from my chest, and then nudged me forward like your household dog does when he wants to be pet. So he petted the whale. And then, she kept asking for more. It turned on its side and put its eye right next to me, and looked. I started petting her again, so it was definitely a feeling of affection. Everyone was so proud that the whale has been rescued and James even got an unforgettable thank you from the creature he loves so much.


Hey, welcome everybody to our last sales enablement session of 2018. And in the spirit of kind of giving and sharing, I wanted to cover a topic that I think will help all of you when you try to position premium and ultimate, but it's a spirit of giving that is a two-way street. So let me jump over and share something in Chrome, and we want to make this both a discussion and interactive. So here we go. This was the issue Mark proposed at open source versus commercial, and he suggested, made the observation when we have the ultimate page about why ultimate. So what we've done and what I've done and worked on this week is I created a why premium page, and I've also updated why ultimate, I got the little new as of this week, that's incorrect, why premium is new as of this week. And I have an open MR for you to give feedback and for us to collaborate together. So let's just walk through this thing. And I need to update the pricing page to point to it. Today the pricing page has a link to the why ultimate. Why premium? I got to change this to add that link here in a few minutes. I'll probably do it right after this call. But let's take a look at why ultimate. We created this page about, I don't know, four or five months ago in response to the need or the interest in being able to have a leaf behind that gives someone an overview of why should they buy ultimate? Why should they consider ultimate? And this week I've spent some time looking at both creating a new why premium page and iterating on why ultimate as well to add some graphics and images to it. I want to direct you all to that and you can take a look and follow along. My ask of all of you is this is collaborative. We want to improve these pages so that way they can be used not only on the web, but as a leave behind that you could use when you meet with customers either you could email it to them as a PDF or you could have it printed out and leave it on their desk after you've met with them face to face. That's the goal of this and what we're trying to get to. So why ultimate? It starts off at the top level of what ultimate is about and how ultimate helps focusing on portfolio management security and compliance. And then we showcase a couple of things. We were showing roadmaps within the visual. We show the different project portfolio management capabilities with epics. And then we highlight the features that exist and we also highlight things that are coming. This will be continued to iterate with Victor as we get more input on portfolio management evolving along with a simple value statement as to what's what's included in that capability. Next we follow with security as to the importance of that showcasing the security dashboard and then explaining the capabilities around static application security testing DAST dependency scanning container scanning and the security dashboard. All of this comes together to help people have security and showcase future security metrics and then to deliver applications faster and more effectively showcasing the operations dashboard which we did deliver last month along with Kubernetes monitoring and Kubernetes logs and improvements around operations. And then the last two bits at the bottom one around license management which we listed as a compliance capability along with our future for SOC2 compliance and then guest users and chat ops show up as an other. Honestly I'm of the opinion I'd like to clean this up in short but at this point we haven't and I'd welcome your feedback on that as we go through this. Included the note at the bottom that ultimate includes for our business support and for business hour support and account manager and on the web at least we have a call to action to contact sales. So that's the why ultimate hasn't changed a lot since it was created a while ago we added I did out of the graphics this week to improve its readability to make it less of a overload of text and I have Luke standing by to potentially turn it into a PDF when we're ready. I don't want to do it before we're ready. It's not and to be clear we're not going to have a print button on this thing to print it as a PDF dynamically what we'll do is create a PDF from this content periodically. Going on this is the new why premium page and we wanted to get to a why premium page because a lot of people are considering premium and we wanted to have also a leave behind to talk about the value of premium and and looking at it is help helping IT organization scale how they do DevOps delivery supporting you know high availability geographic replication progressive deployment and lots of capabilities. So in summarizing it it starts off with developer productivity with high availability and geo both helping teams to be more productive regardless of where they're at. We also then move on to project planning we make project planning better we have you know when you look at backlog management because we can have multiple issue boards at the group level we can start to scope and plan things at a group level more effectively with with premium it's not exactly a feature but it's a capability that you can start to manage a backlog better because you can have issue you can have a sign ease on the on the backlog on the issue boards etc. We have milestones boards and lists we can manage that as well. Again at the group level multiple issues multiple issue boards the group level really helps teams to be able to manage their projects and to manage who's working on what more effectively. We have feature flags deploy boards incremental deployments can area deployments all sorts of capabilities at premium to make it easier for people to deploy with confidence to not have to deploy in a way that they're unsure what's going to happen that they can leverage GitLab to deliver and deploy their applications or release some more effectively and this thing we include maven repository protected environments all these capabilities show up with GitLab premium which are valid which deliver value to someone who's building and delivering applications. We make it easier to manage the development process for example and the screenshot is one of the new review process where you can create a group of comments and submit basically a merge request review. We have verified committers signed commits and group file templates which also help teams to establish consistent practices. And then at the end we also have the note about four hour business support which is a differentiator I think for premium as well along with contact sales to learn more about premium. I haven't created a page like this for starter and to be perfectly honest I don't think we should I think we should stop at this point and encourage people to be looking at premium or ultimate I think these are pages for you to help sell and for you to help connect with people and with that in mind I'm going to point to the MR that's open and I will put the link to this I'll put this link into Slack I'll put it into chat as well so that way you can get to it but I welcome your input and I welcome your your insight as to what's missing what else we should add to it what might be incorrectly stated or you don't feel comfortable with all of those things would be useful because I want this to be something that you can use as an asset as you engage with people and so for that that summarizes the value of ultimate the value of premium why ultimate why premium where we're going with this I'd like to you know we can stop the recording we can go into discussion and Q&A.