Introduction

Well, shall we begin? We've gone through computers. Pretty much. What they can do and so on. We're now going to look at the question of the representation of information. And I have to be very careful about the word information because it's likely be misunderstood. There's a whole theory about this matter, lasting for a long while. And in the forties, Shannon created a theory of information, called Information Theory. Bell Laboratories wanted them to call it Communication Theory which was a better word, but we have to live with the other one. And I will take up information theory and how far information is from what you are inclined to believe information is. Now you remember in machines at the bottom there were gates that you opened and closed. They were either current or non-current when you consulted a memory cell and so on. At the very bottom there were just simply these elementary events. But then in your nervous system, the physiologists tell you, either a nerve conducts a signal, or it doesn't. Now we have to look at how things are going to be represented in this machine. I'm going to use the binary one for good purposes. It's easier to do than anything else. And we're transmitting information from one place to another.

Source Illustration

We had a source. Nothing is said about the source. There is a source of information. It may be mathematical formulas. It may be a novel. It may be the marks on a music sheet. It may be the marks we now have for recording dance, which we've only created recently. It may be any source of symbols. Nothing is said about the source. Therefore, the theory is very widespread. From the source, we go to an encoding. We take this stuff and encode it into some different form, possibly. The identity encoding is an encoding. Just don't do anything. But in general, there is an encoding. The encoding goes on, into a channel. Radio, over-the-air television, to a cable. Book. Print. The acoustics. I'm sending a message to you. It's going over the acoustic channel to a room in the atmosphere. There is a channel. Now what is important is that to this channel is entered noise. From this goes a decoder. And then the sink. After all we're sending a message from something to something. We're concerned with the fidelity. Now first I want to impart to you this is different from other theories which you've learned. When you learned physics, for example, there was the idea of an exact mass or exact force. Now of course when you came down to the laboratory you knew you couldn't measure something exactly right, but the uncertainty was added on at the back end of physics. Here we are putting uncertainty in right here. We're saying that channel does not send information reliably. We're accepting at the very bottom that nothing is reliable. Information theory and coding theory both assume that there is a noise to be combated. Quantum mechanics is something a little different and we will take up a chapter in quantum mechanics one of these days. But the uncertainty in quantum mechanics is not this kind. Now your problem is: here's a source, by suitable coding and decoding can I combat the noise in the channel? Now what we normally do is divide this into two parts: source encoding and channel. Given the source I encoded, I take advantage, if I can, of what structure the source has. Then I look at the channel and say, “Well now, how can I encode this so that the decoder, which of course has got the channel and this source, can probably get the answer in spite of the errors?” Now to make the course graphic, I'm here at this side. You are here at this side. Something is out here to your decoder. Now you know the rules I'm supposed to be following for encoding both channel and source. You know those rules. What you don't know is what I shoved in. What you know is what came out. And so your problem is, how can you make a very good estimate of that? Now the real design problem is, how do we design this, particularly this piece although this partly, so that you can probably write in your guess as to what I said. That's the underlying problem. Now I'm talking as if I were sending from here to there as a convenient method, but it is exactly the same problem as sending from now to then. I have some information and a computer. You ship it. You encode it onto a disk. You may not know it but when this stuff goes onto a disk it's been encoded in a different form. At the other end when you want to read it, the disk gets called up, the decoding instruction goes by, and bits are thrown out. So, this is the decoding part. This is the encoding part, when you're writing disks. The same way in various machines. You have various ways of doing encoding, it occurs in a lot of places.

Transmission through space and time are really the same kind of problem

So, transmission through space and transmission through time are really the same kind of problem exactly, but I will generally talk as transmission from here to there through space. The computer has some information here. Well I want to ship it there. I have it here. I want to get it there. I got it there I want to something else with it. I'm shipping it around, here, there and yon, and there's bound to be errors. Shannon recognized this and I recognized that you cannot build perfectly reliable equipment and as you try to build more and more reliable equipment once you get fairly well along, its enormously expensive to get further. Thus, I told you, a couple of times I believe, given a differential analyzer, which was commercially available, to get one with one binary digit more of accuracy, we've got to increase the cost by a factor of 10.

Getting another bit or decimal digit is very expensive

Getting another bit or another decimal digit is very expensive. So, you like to keep the noise down. On the other hand, you want a machine that’s going to be reliable. You want a desk calculator. Work at your desk and, somehow or other, you can use it for a whole year and it's not going to give you a wrong answer. How are you going to do it? That's the problem. One way is to over engineer. The thing operates so slowly it is bound to work right, but you want a fast machine. You want a cheap machine.

What we are resorting to is coding theory to escape doing things right

So, what we are resorting to is coding theory to escape the necessity of doing things right because it's too expensive to do it right. Very simple but very difficult fact.

symbols need not be the same length

Now I might as well begin with, over here, the symbols need not be of the same length. Mathematical formulas are of different lengths. The Morse code, which you learned, of dots and dashes. Some were shortened. Some were long. Why? The most common one “e” was a dot. Some obscure letter like “j” was three dashes and a dot. Now the Morse code was a ternary code. It was not binary. It has dot, dash, and space. So, it's not really binary code, but it is a code of variable length and we need to look at the question of, variable length codes going in, variable length codes coming out. How are we going to cope? Well let's take one code. I have four symbols. Now in reality, of course, there are hundreds of symbols. The alphabet has 26 letters uppercase, lowercase, a bunch of punctuation, other things. The ASCII code has two to the seventh symbols but currently on the blackboard I'm going to use four. That's going to be the code. Now if I send and you receive. Huh, I didn't get the right code. Pardon me while I look and peek at what I should have had – oh one (01). Oh, I have zero, oh oh (00). Oh, I see oh oh (00). It might have also been s2 s4. There is no way, even without noise, you could tell whether I meant one or the other code. It is not uniquely decodable because some symbols are the prefix of others. That's one of the faults. So that kind of a code, although in conception you might have one which is not absolutely uniquely decodable, by and large you want unique decodability. So that kind of code is no good. If I take the code. Then I say I can decode this stuff. Any string. There is a decoding tree. If I start here, I get a zero. I come to s1. If I get a one, I need to look at the next digit. If I get a 1, I need to look at next digit, s3. Then I get a 1, s4. 1 1 1 is s4. And you see, all I have to do is follow that tree. I get a 1 0 this is s2. I get a 1 1 0 there. I get a 1 1 1, I get a 0, I get a 0, I get a 1 0, I get a 0, I get 0, I get 0, I get a 1 0, I get a 1 1 0, and so on. It's evidently a string of bits come by you can decode and there's no ambiguity. You simply follow down that decoding tree, bing, bing, bing. Now I want to call your attention to a very important fact. You only look at each bit only once. You do not have to look at bits again and again and make guesses. It's straightforward decoding. It's uniquely decodable. Now this was not. This was not uniquely decodable. Well that's uniquely decodable so we got one idea in our heads: unique decodability and why you want it. I want to take up a second one: instantaneous decodability. It's the same code reversed. Now suppose you receive a zero and a string of ones. What will you have to do? You will have to start here. Mark off three ones, three ones, three ones, until you come down there and know how many ones went with that zero, right? It's uniquely decodable but you can't start decoding until the end. It's not what we call instantaneous decodable. Where is this, as it came in, I could decode. The moment I came to 1, the terminal positions, I had the known letter. Now it's obvious instantaneously decodable ones are better than not instantaneous, and I'll prove a little later today McMillan’s theorem, that there is no profit in having other than an instantaneous decodable one. If there is another code that meets uniqueness, unique decodability, there is an instantaneous one which will do it. So why bother with those?

Unique instantaneously decodable codes

But that's the second thing you need to know: I want unique instantaneously decodable codes so that even without noise I would be able to do it. If I didn't have those properties you'd be in trouble, particularly this one, having to wait until the very end of the message received and having to work your way back of a really long message is not terribly satisfactory. No way. So, we don't want that. We want instantaneous decodable codes. I think the next thing I want is a Kraft inequality. But I better peek to make sure I'm not forgetting something. Oh, let's do two examples first.

Two Examples: 5 Symbols

I'm going to have to have five symbols and since we haven't got lots of blackboard space we'll just have to erase. One code. The other code. I assert they both have decoding trees. This one. Zero goes to s1, s2, s3, s4, and s5. 0, 1 0, 1 1 1 0, so on. This one is different. s0, s1, s2, s3, s4. This is long and lean. That’s more bushy. They're both uniquely decodable codes. Which one is preferable? Well, what you want out of the code? One thing you want is the average length of a code to be fairly short. In other words what you really are going to care about is the average length of the code, L, which is the probability of the symbol times the length of the symbol summed over all the alphabet. And I apologize for the use of Q, because it's going to confuse you with probability 1 minus P, but it's the standard notation in this field. Q is the number of symbols, so I'll stick with it. So, you read this, you read other books. Otherwise it'll be troublesome. Well suppose these probabilities are 1⁄2, 1⁄4, 1/8, 1/16, and 1/16. I have 1⁄2, times 1, length 1, plus 1⁄4, times length 2, plus 1/8, times length 3, plus 2 of length of probability 1/16 of length 4. 1/2 plus 1/2 is 1, plus 3/8, 1 plus 3/8 plus 8/16, 1⁄2, 1 and 7/8. This one will be 1⁄2, times 2, plus 1/4, times 2 plus 1/8, times 2, plus 2, times 1/16, times 3. Which will be 1, plus 1⁄2, plus 1⁄4, plus 3/8. 1 and 3⁄4. Well let's see. 2 and 1/8. So, this one, on the average, is longer than this one with those probabilities. On the other hand, suppose all the probabilities were the same. Each was probability 1/5. Each probability 1/5. I would have 1/5, 1 plus 2, plus 3, plus 4, plus 4. 8, 10, 14/5. Here I will have 1/5, of 2 plus 2, plus 2, plus 3, plus 3. 6, 8, 10, 12. 12/5. This one is shorter than that one. So, what is going to be the best code must depend upon the frequency of the symbols being sent, right? And as a loose rule, when you have almost all the same probabilities a bushy sort of squarish code would be much better than a long lean one. When you have high variability, this tends to be better than that. So, there are some general rules, which we have to follow, telling us that some codes are very effective for some reasons, some are effective for others. I have not yet talked about what I'm going to do about the noise. That'll come in the third lecture on coding theory under Hamming codes, which I worried about and said, “How can I do it to take care of that?” Meanwhile I'm only worried about, can I even get through codes and how do I go after reasonable things in coding theory. Now I come to a Kraft inequality.

Kraft at Bell labs

I always wondered who Kraft was, once I realized it was a name of a person. And only after I came here, did I discover that he was at Bell Labs, or had been. So, I don't know really who Kraft was. Now Kraft says, there's a number K, i running from 1 to q, 1 over 2 to the Li, where the two comes from the fact I'm using binary. If I were using a ternary base, I'd use a three. If I was using a base with 17 symbols, I’d put a 17 in, but we're working in binary for simplicity. Now this, he says, for unique decodability, must be less than or equal to one. Now when you think about it, that is saying the Li’s must be large. I cannot have a large number of small Li’s because then the sum would be too big. Now the proof is easy. But the original proof, God help you, was a mess. When I came to write a book on it, I looked at the proof, even after it had been polished up for a lot of years and looked at it and said, “Boy that's a mess. Let's see if we can find a simpler one.” So, I said let's look at induction. These trees I've been drawing. Now if the tree had only one branch, obviously length 1, I'll have you less than 1. If it had two branches 1/2 plus 1/2 is 1, so the thing is true if there are 2 distinct branches and if there's only one branch it's going to be all right. So, I'm going to make the induction hypothesis that if it's true for K -1, can I prove it is true for K? What I will do is I'll cut this in half. Now look at this bunch. Now that will have a length of K’ and this how will have a length of K2. Now if I'm going to have unique decodability, this must be less than 1⁄2, this must be less than 1⁄2, by the induction hypothesis. When I attach this other one on, each length will be one longer when I attach it on. So, I'll get it. 1/2 K’ plus 1/2 K2 and that'll be less than equal to 1. So, there I am. Very easy proof. Very simple. So, I have this proposition. It must be so. Now let's see some ones which you can and cannot. Suppose I have those that's 1⁄2, plus 1⁄4, plus 1⁄4, plus 1/8, that's 9/8. There is no unique decodable code with those lengths. You cannot make one. If I had 1⁄2, plus 1⁄4, plus 1/8, plus 1/8, is exactly 1. Yes, I can have a 1, 2 and 2, 3 lengths. Now, of course, I remind you again, codes are going to be 40 and 50 symbols long. I can only write simple ones. In fact, I had to go to five one time to demonstrate that simple property. In general they’re very long. Now one thing I want to remind you is something which I forgot to say earlier, when you're designing a code, you're going to want the machine to do the encoding and you’re going to want to know when you're at the end.

Exit symbol: When am I done?

So, what you need is an exit symbol. When am I done? Which you, from the stuff he wants, you add that on. A very, very low probability. And when you hit that, you exit out and don't come back to the beginning of the tree to look for the next bit because you're done. You want to have an exit symbol. This is something that is very, very often forgotten. When do you quit? For example, in Fortran, there's a stop symbol saying, “I'm done.” I'm done with the programming, right? But there's another stop. I'm done with the encoding. The compiler has one stop to say it's done. Your running program has another stop saying I’ve done all the computing, right? They are different levels of language, or metal languages, that you’ve got to watch yourself, in computers, languages above a language. In English we talk about the English language in English and we get ourselves confused. But it’s the only thing we've got. So, we talk about language. We do it by quotes. We do it by gestures. We do it by accents. In order to talk about a language, you have to use a language. But you want to be clear, when you talk about a language, you're above it. The compiling is above the running language. It's talking about how to treat that language up here. Would you go and tell the machine how to run the problem? So, there has to be these two different stops. You need one in every language, alphabet you write. There should always be an exit symbol, for your benefit, to escape the translation process and know when you're done. The failure to do that is a very common one and it causes all kinds of trouble.

How the unique decode-ability works in proof

Well let’s go on and see some more in this book. Now I haven't proved that the Kraft inequality is true. I merely proved that if it's applied some are very nice. I want to give you the examination of how the unique decodability runs into the proof. I got the Kraft, but I really didn't prove the less than 1⁄2. I merely showed that if it’s less than one, it would be less than 1. So, I'm going to write K equals summation i equal 1 to q, 1 over 2 to the Li and 1 is less than or equal to Li is less than or equal to some letter L maximum. Now I'm going to raise this thing to the nth power. Instead of sending you one symbol, I'm going to send you a whole string of symbols, n of them. OK. It's what we call the nth extension. What we talked about earlier. You've got a stream of symbols. You’ve got know when the end of one comes to go back and start translating again. Well this will become, then, a sum i running from 1 to q. Now the shortest one will be n, and the longest one will be nL. Now how many can there be? But well like use a K here. So long look at that. Now there are n sub K symbols of length K. I assert it cannot be more than 2 to the K because there are only 2 to the K different symbols of length K, correct? So this is less than 2 to the K over 2 to the K, and that's n L minus n plus 1 because when you count all numbers from 5 to 10 the difference is 5 and then you have to add one on for the N value, right? Now, let's look at this thing. If K were bigger than 1, I can raise n so this power will exceed this linear structure in n, this is after all linear in n, only if K is less than 1 will I escape. So I assert that if I have unique decodability, the K must be less than 1. I use that unique decodability or I went from here to here. Now let's be careful that does not assert that if I have a code which obeys the Kraft inequality that I will have unique decodability. No. It only says that there exists a code which will do the trick. So let me give you an example of how you do it. And I need to peek since I didn't try to remember everything. To demonstrate I’m brilliant I could have easily memorized it but why fool you, you know I'm not bright anyhow. Oh yes. Two two three three and four fours. What's the K? That's 1⁄4, plus 1⁄4, plus well 3 1/8’s. Two of them. Plus 4 1/16’s is 1/4. 1⁄4, plus 1⁄4, plus 1⁄4, plus 1⁄4, equals 1. So that kind of code can exist. How do I find it? Well it's easy. Proceed in an orderly fashion. The first one I'm going to write the smallest binary digit I can, of length 2. Now I get another 2. Next one we go 1 0 but I got to have length 3, so I put a 0 here. Now the next will be 1 1 0 but I got to have length 4. And you see, I always have just enough room. If I keep building numbers as small as I can but extending them just as far as I have to, I'm always going to come out obeying the Kraft inequality. So, if I have the inequality, I can find the code.

Just because it satisfies the craft and equality does not mean it’s a uniquely decode-able instantaneous code.

I remind you. Just because it satisfies the Kraft inequality does not mean that is it uniquely decodable instantaneous code. But it says that I can design one. I've showed you how I can from a bunch of lengths which satisfied it. Now let me talk about the Kraft inequality a bit more. If the Kraft inequality is unequal, I can do one of two things. I could add another symbol, or I can shorten the length of one of them. So, you can see that if the Kraft inequality is not held at one, the code is not as good as it could be. I could shorten it, or I could add another symbol to get more communication stuff through. In general, what you would do is undoubtedly shorten one of the lengths. So, the Kraft inequality being one is a really good measure of have you got a good code. It should be just exactly one and there will be an instantaneous uniquely decodable code if you do so.

Communication of symbols

So, we've talked about communication of symbols from the first picture I drew from that end to this end without the noise. You see how encoding could be done and you can see how the source encoding given the probabilities I will design so the most common symbols are short, and the long ones are the unlikely ones. Much like the Morse code. If they're all equally the same, then I'm pretty well stuck with what is called a block code. They're all the same length or almost the same length. Those are ones you're more familiar with. But you notice when I used a variable length code your first feeling of by God how I break it up at the receiving end into the individual chunks? You simply go down that decoding tree. You pick the next bit and branch, pick the next bit and branch, and when you come to a leaf you emit the symbol and go back to start. You read the next bit. So, you simply go down the message, reading a bit at a time, bing, bing, bing, and branching or, when you hit a leaf, emit and pick up a next bit. Start again. You inspect each bit once and only once. So, the stream of bits from one end to the other end without the noise can be gotten through.

Discussion of the next lectures

The next lecture will be on the question of how do I find a good code with variable length that is just about the best I can do. How do I find that? And the next lecture after that is, how do I cope with the noise? So the next lecture is really on the source encoding, how could I take advantage of what I know about the source to officially encode? And the last one will be on how do I code to combat the noise in that channel so that you at your end have a decent chance of knowing what I sent from my end. Now I've left a lot of time because I want to talk about this matter of information.

Information theory

We will have a section on information theory. We've been talking about sending information, but let's be careful. I have this idea in my head, and now I'm trying to get into your head, namely, what do we mean by information? I'm going to use some words to say it. If you go home tonight and explain it to your spouse, or a friend, you will use different words. Thus, although it is common to say that the idea is contained by the words, they aren't. In order to get the idea into somebody else's head, you will use different words. In fact, if I say something and you don't understand it, and you ask me what did you say, I'm inclined not to use the same words but use some other words hoping the other words will somehow or other get through, because the first ones didn't. And indeed, about a third time through, I'm going to try a third way of describing an idea to someone else if they don't get it the first time. Therefore, the idea is not in the words. What the idea is, I don't know. I'll tell you how I measure it. I'm teaching a class in calculus. The topic, among other things, is integration by parts, we'll say. Final exam. I think integration by parts is important, so I arrange a couple of direct questions and one that requires using integration by parts in order to get the answer. So perhaps it occurs three times on the exam. I look. If the student can do those three, I conclude he has, or she has, the idea of integration by parts. If they can't, I look and ask where did they fumble up? Was it an algebraic slip or was it they didn't grasp the idea? So how do I measure when you have an idea? By taking a few samples and seeing if you behave the way I think you should if you have the idea. I never know if you have the idea. I have no way of ever finding out. No way at all. Now some of you have lived long enough to realize that although a person has behaved a certain way all the time, up to this moment, suddenly they behave differently. You realize that they had a different idea than you did of what the basic underlying idea was. There is no way of me knowing have you got the idea? Not at all. We deal with ideas. We don't know what they are. We don't know what information is. I intimated last time that I couldn't very well expect you to write a program which would recognize information because if I could, I could connect the program up to a random source and in a random source, ultimately, the next theory of physics would come along. If I could recognize it, then I’d have it. All knowledge will come out of a random source if you wait long enough, but we don't know how to recognize knowledge. That's the trouble. I can't tell you what knowledge is. I can't tell you what information is. I can't tell you what ideas are. Until I start talking about them. You are all right. It's the same position I told you once before of St. Augustine who said I know what time is until you ask me and then I don't know. In the same way you always think you know what information is, what knowledge is, and what ideas are, but when you begin to press very hard, like in your business, writing a program that does it, you begin to find that you don't know what you were talking about. Well the information theory, and I’ve been talking about information every time, is covered by the following trick. When I drew the original picture, I said there was a source. We didn't discuss the source. We assume that those symbols are uniquely recognizable. We're not saying we know what the symbols mean. We are saying that every time that symbol comes by, it has exactly the same meaning. Like every time in a calculus course you see the integral sign, you know what it means. Or if you saw a divide sign, you know what it means. Now that is a much bigger restriction than you think. What mathematicians approved, and we will come to this several times along the way, a theorem due to an Austrian named Gödel, who was crazy as a fruitcake but nevertheless, a very bright guy. He proved that if you have a unique set of symbols, always recognizable, you cannot within the system prove that the system is consistent. That it will not give contradictory results.

We have never proved that arithmetic is consistent

Thus, we have never, believe it or not, proved arithmetic as consistent. We have not proved that if you take your income tax and add up one way or add up another way, you won't get different results. Most of you believe that you'll always get the same result if you do it right, but we have not proved that. We cannot prove within a system that a system is consistent. Our language, however, is not that way, in spite of the fact that Gödel’s theorem speaks about uniquely recognizable symbols, our words don't have a fixed meaning.

Our words have variable meaning

Our words have variable meaning, even in one discussion. “Tall” will mean different kinds of things. A tall building or a tall story, where “tall” has quite different meanings. And furthermore, even in a debate, the meaning of a word will slide slowly and definitely so that you cannot claim I am dealing with language when I deal with this model here. I am dealing with a model which has a very, very peculiar property. That source. Every time that symbol came by, I could recognize it as that symbol. I then encoded it. I shipped it through the channel. You decoded it. You passed it on to the sink. And if there was no noise in the channel, or if the noise was combated, the thing came through exactly right. What doesn't in our damn language? It doesn't at all. There are small variations all the time. You will find out, if you were to press very closely, friends of yours have a somewhat different idea of what your organization is. They will have different ideas. They're not exactly the same. They've seen the same things, but they believe differently. In fact, it's a standard experiment and done in psychology. A group of two or three people or sometimes the whole class like this. In a class like this, I'm talking and suddenly somebody comes in there, shoots a gun, I fall down. He rushes out. Somebody suddenly walks in and says, write down what you saw. Some students will say, “the guy fired three times.” Somebody else will say fired twice. Some of you will say he did such-and-such before he fires. Somebody else will say something else. There'll be an amazing amount of difference between what you think you saw and what would be on the film, if they took a film of it, which they often do. You cope with that problem. The lack of uniqueness and the belief to some extent that you think in terms of words is very dangerous business.

Once you put something into words that is what you believe

Once you put something into words, that becomes what you believe. This is why I told you, if the boss is going to say no, and you want him to say yes, don't ever let him say no. Once he says, or she says, no, it is fixed much more firmly than not. Thus, when I witnessed an automobile accident one time with my wife, we were walking downtown in Chatham, I gave the two people both my name and address and we went shopping. I came back and, without discussing with my wife, I typed very carefully what I thought I saw without any discussion. As close as I could get to what I saw. I did not put it into words until I put it down on a piece of paper then because words tend to freeze something. This therefore this whole business I'm talking about here is marginally relevant to language. It's very relevant to machines. It is what machines do. It's what radio, television, the telephone, mathematics, other things do. It fits those situations perfectly. Symbols have a definite meaning and they're shipped from here to there and yon. Everything is definite. It's exactly the mathematical theory I need for machines. That's why we said Shannon should call it communication theory. It fits with communication. It doesn't fit exactly with you, but everybody is trying to make it fit to you. There's a great desire that these things which you hear will fit you as you are, or as other people should be. Well there's these differences. The symbols are not always the same things, they are not exactly right. And so, you get different results. The famous results of math don't apply to human beings. So, we've given elements of coding theory and I summarized it. I had to go through some very dull stuff. Uniqueness of a code. It's obvious, but I had to show you the codes, one-to-one codes, wouldn't necessarily be unique. The thing you need chiefly is, no symbol is the preface of any other symbol. Therefore, I can draw that decoding tree. The next important thing is, for variable length codes or any other codes, there is a decoding tree which looks at each bit once and only once. That I can cope with variable length codes. But if the symbols are variable probability, I probably want a variable length code, for efficiency. Now you may say that doesn't concern machines, but that's not quite true. Intel built some chips in which the instructions were a variable length. The most frequent instructions were very short. The other ones were very long. Because you can picture a machine. The code is not a bunch of blocks, the way you usually think, but a string of bits. And the bits that continue, pulled in and were simply decoded, like the decoding trees I've had here. I simply decoded them. When I hit a leaf, I obey that instruction. I keep on decoding. I get another leaf. I obey that instruction. I had to use variable length; therefore, the total storage of the program would be significantly less. By the mere business of building a couple of registers, always lowering this one, then shifting them over this way, and counting down this way, shifting those off, and so on, you can see how I would be able to build a variable length decoder which might be very much more efficient. For a machine. For humans, it’s another question entirely. So I leave it to you to start thinking about these vexing questions which I raised in artificial intelligence. How much of what we now do or want done will we be able to get machines to do? And the answer, of course, is what can you program? It's really not, can I build a machine? It's what can you program? Therefore, you need if you're going to use machines in new and novel ways to understand better than you do now, probably, just what your ideas are on varying topics, and how to get some of these amorphous ideas down. The greatest contributions of the greatest mathematicians are often the definition. When you nail an elusive idea down, you nail it down to be something very definite, and that's what it is. Of course, you do some damage in the definition, but that's what you'll have to do. You'll have to, as it were, firm up the idea of what your organization is and how shall it function, and then you can write programs and do other things to cause it to operate in that fashion. Until you write the program's - not too easy unless you're prepared to go to neural nets and fuzzy sets, which I'm not going to talk about much in this class. So I see you Thursday and we'll talk about how to get efficient coding.