# 2. Reasoning: Goal Trees and Problem Solving

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=PNKj529yY5c
**Transcript page:** https://www.withtranscript.ai/video/PNKj529yY5c

## Chapters

- 0:08 — Chapter 1 (0:08)
- 3:45 — Chapter 2 (3:45)
- 6:30 — Chapter 3 (6:30)
- 9:11 — Chapter 4 (9:11)
- 9:42 — Chapter 5 (9:42)
- 10:46 — Chapter 6 (10:46)
- 13:14 — Chapter 7 (13:14)
- 15:22 — Chapter 8 (15:22)
- 18:10 — Chapter 9 (18:10)
- 22:00 — Chapter 10 (22:00)
- 23:27 — Chapter 11 (23:27)
- 29:13 — Chapter 12 (29:13)
- 32:05 — Chapter 13 (32:05)
- 34:35 — Chapter 14 (34:35)
- 36:49 — Chapter 15 (36:49)
- 43:42 — Chapter 16 (43:42)

## Transcript

**[0:08]:** that's what we're going to talk about today is goals so just by way of um a little warm-up exercise I'd like you to uh look at that integration problem over there the one that's this one that's disappeared

**[0:40]:** so the question is can you do it in your head probably not the question is if a program can do that is a program in any sense of the word intelligent that's a background task I like you to work on as I talk today so today we're going to be modeling a little bit of human problem solving the kind that is required when you do a symbolic integration now you all learned how to do that you may not be able to do that particular problem anymore but you all learned how to integrate in high school or 801 or something like 1801 or something like that the question is how did you do it and is the problem solving technique that we are trying to model by building a program that does symbolic integration is that a common kind of is that a common kind of description of what people do when they solve problems so

**[1:31]:** the answer to the question is yes the kind of problem solving you'll see today is like generating test which you saw last time it's a very common kind of problem solving that we all engage in we all engage in it uh without thinking about it without having a name for it but once we get a name for it we'll get power over it and then we'll be able to deploy it it'll become a skill we not just witness it we not just understand it we'll use it instinctively as a skill so there you are you've got that problem there's your problem and what do you do to solve it I don't know uh look it up in a table uh you'll never find it in a table because of that minus sign and that five so you're going to have to do something better than

**[2:20]:** that so what you're going to do is what you always do when you see a problem like that you try to make you try to apply a transform and make it into a different problem that's easier to solve and eventually what you hope is that you'll simplify it sufficiently that the pieces that you've simplified to will be found in some small table of integrals so how long is this table it's not the case that we're going to look at a table with 388 elements because this is not the this is not a big table of integrals this is what a freshman might have in a freshman's head after taking a course in integral calculus one of the interesting questions is how many elements have to be in that table to get an A in the course we're interested in how much knowledge is involved it's one of the it's one of the elements of catechism

**[3:05]:** that I've listed over there that will be part of the goldar ideas Suite of the day so i' like to take that uh we'd like to take that problem and find a way to make it into another problem that's more likely or closer to being found in the table so what we're going to do is very simple graphically we're going to take the problem we're given and convert it into another problem that's simpler and we're going to give that process a name and we're going to call it problem

**[3:45]:** reduction and so in the world of integral calculus there are all sorts of simple methods simple Transformations we can try that will take a hard problem and make it into an easier problem problem and some of these uh Transformations are extremely simple and always safe some of them are just well let's try it and see what happens but some of them are safe and I'd like to make a short list of safe Transformations right now now I'm going to be going into some uh detail and that detail will be grungy and the question is why do I do it and it's educational philosophy is why I do it so here here's the educ ucational philosophy at one level you want to have a skill but if you're going to have a skill you have to understand

**[4:44]:** it so if you're going to have a skill you're going to have to understand it one level down if you're going to understand it you have to have witnessed it on a level lower than that so I'm not just going to talk about the idea of problem reduction because if I were just going to do that then we could all go home now so I'm going to show you a particular example of it so you understand it better and I'm going to show you the detail at even lower level than that so you'll witness the stuff that makes it possible to understand the stuff that makes it possible to build a skill so that's why I'm going through the the grungy detail so I don't know let's see uh maybe we can get some hints from that example but I wonder if somebody could volunteer

**[5:28]:** a simple transfer that always is a good thing to do yeah Sebastian con take the constants out so we'll make that number two and we'll say that the integral of c f ofx DX is equal to C * the integral of FX DX other suggestions yes substitution what trig substitution trig substitution now this this is no no that's that's for day two we don't do trigger substitution here in the stuff that's safe always works never any doubt they are simpler things these are the safe Transformations what you're giving me is a euristic transformation often is helpful doesn't necessarily always work we're going to divide our Transformations into those two categories so I need another safe one

**[6:30]:** uh are The Architects are sitting over there divided not only by nationality but by course what uh Su of intergral interal yeah sum of integrals integral of sum

**[7:04]:** uh what's missing what's number one you're probably thinking it's already there because you've given me the transformation that involves a constant and you think of you can think of minus one as a constant whether you need a separate transformation or not of course depends on how you represent the knowledge and all of this knowledge all of this whole thing is was written in was written in an early form of lisp as a consequence the way in which minus was represented is different from the way minus one is represented so we need one more transformation rather Jim slel needed one more transformation when he wrote his famous integration program and that was that if you have the integral of minus F

**[7:51]:** ofx that's equal to minus the integral of FX so that almost completes our safe transformation set there's one more that I'm going to supply you because I don't think you'd guess it why should you it's number four there are more than this this is a sample and these are the ones we're going to need in order to solve that problem by way of illustration so uh the fourth one is that if you have the integral of P of X over Q ofx then you divide if you can wait reach way back into High School figure out how to divide polinomial but if the degree of the numerator is greater than the degree of the denominator then it's a knee-jerk always win you must do it divide it out so this then forms the core of an integration program that will integrate almost nothing but actually almost nothing is integrable anyway so it's a good head

**[8:55]:** start so let's see how we would put this uh into some kind of procedure

**[9:02]:** some kind of framework for deploying the knowledge that we're beginning to

**[9:11]:** develop what we're going to do is

**[9:17]:** apply all safe transforms

**[9:30]:** that's our step First Step then we're going to look in the

**[9:42]:** table and then we're going to do a test to see if we're

**[9:51]:** done and if we are we report

**[9:57]:** success but we're not likely to get done with just that stuff but you know what uh there was one transformation up here which breaks my little diagram which one is it it's the third one right because this picture does not reflect what happens when you apply number three because it breaks the problem up not into just one problem but into a whole bunch so we have to extend our graph Graal our graphical device for talking about this by a little bit and and show what is called an and

**[10:46]:** node so we've got a program core we've got a table of integrals we've got a few Transformations we've got an architecture a way of putting that stuff together and now we we can try it out on our sample problem so let's have a go at

**[11:08]:** that let's see uh this one immediately transforms into 5x 4 over 1 - x^2 to 5es DX and that in turn immediately transforms into the integral of x 4th over 1 - x^2 to the 5 DX this program by the way is a dawn age program this was written by a nearly blind and subsequently completely blind graduate student by the name of James slel in 1960 a long time ago the reason I give it to you today is because it is because if I describing it I'm giving you a one lecture course in artificial intelligence he anticipated so much of the subsequent 20 years that talking about his program which is possible in one day is a miniature introduction the whole field so slagel as he was doing this on an antique computer almost no memory almost no speed only slightly faster than mice running around on a treadmill uh he was able to write

**[12:24]:** a program that did extremely well when the when benchmarked against freshman and the way way you Benchmark against freshmen of course is you you give it an examination drawn from the previous MIT finals for four or five years the hardest problems and this was the hardest problem that had solved so at this point with what we've got so far we would be stuck we have no transformation that can take us further so we need something else and what we need by way of something else is some Transformations that we will describe as I don't know perhaps we'll call them urtic

**[13:14]:** Transformations a funny word meaning a method that often Works isn't guaranteed to work it's not an algorithm in the usual sense that we talk about algorithms but rather it's a it's a it's an it's an it's an attempt so these things I'm going to talk about now are sometimes useful not always useful sometimes take it into a blind alley don't always work but you can't get an A in calculus without knowing some of them so you said some kind of trig substitution so here is some kind of trig substitution we'll call this um tic transformation a you have a function of sign sin x cosine X tangent of X cent of X secant of X and cosecant of X and we all know from High School trigonometry that we can rewrite that as a function of sinx and cosine

**[14:27]:** X or we can rewrite that as a function of tangent of X and cosecant of X or we can rewrite that as function of cotangent of X and the secant of X so that's a transformation from trigonometric form into another trigonometric form it's not always a good idea sometimes it helps

**[15:02]:** well that's just uh part one of our suite of aristic

**[15:11]:** Transformations

**[15:22]:** stop there are others that we need to have in our in our repertoire in order to solve the problem one of them is a family of Transformations which I'll show you only one it goes like this if you have the integral of a function of the tangent of X then you can rewrite that as the integral of a function of Y over 1 + y^2 Dy so that's a transformation from a trigonometric form into a polinomial form so it gets rid of all that trigonometric garbage we don't want to deal with and there's a whole family of things like that just as there was a family of Transformations like so but this is enough to give you Flavor now there's a c that we need as well and that's going to be your proper kneejerk reaction you see something of the form 1 - x^2 what do you do when you see that what's that

**[16:41]:** r 1 6 * 1 - 1- 6 you can do that but there's another thing you can do chrisan you got something we can suggest how's where's our Hungarian our Turk our Young Turk yeah what do you think I actually don't remember I mean I think well let's see cosine s+ sin = 1 so what's that suggest here so suggest that we make a transformation that involves x = s y so Sila doesn't actually have to remember that anymore because going forward she will never have to integrate any anything personally in her life she can just simulate the

**[17:47]:** program so these go from polinomial form back into trigonometric form so you have three of these urtic Transformations we got four safe Transformations let's let's see if we can make any progress on our integration

**[18:10]:** problem okay so keeping track of what we've been using this is safe transformation number one this is safe transformation number two what do we do next we decided there were no more safe Transformations that apply but now we can look at our Uris Transformations and behold we see what what applying trans transformation C suggests that we do xal the sin

**[18:49]:** Y and now we get the integral of uh s to the 4th y over cosine to 4 y Dy right all good I see some confused worried concerned looks maybe I've made a mistake perhaps I should use notes well no wait a minute for those of you who have a concerned look remember that if x equals a sin y then DX is equal to cosine y Dy that's why it's cosine to the 4th not cosine to the 5th as you were perhaps thinking it might be so now we made some progress we look at this we say are there any safe Transformations that apply the answer is no now we look for a urtic transformation that might apply IA what do you see which one what's that

**[20:05]:** she said something un intelligible what she probably said is that this looks like a pattern that might match with the aristic transformation a right because we have a function in which the variable is buried universally in SS or cosiness or tangents or cotangents or secants or cosecants and we know we can rewrite that in one of three ways it's already written as a function of s and cosine but we can also rewrite that in terms of tangent and cosecant or cotangent and secant so when we do that we can go this way and we can get the integral of one over the cotangent of X DX that's G2 up there no that's G3 up there or we can do it now this path and get the integral of tangent of X DX and of course those are both to the fourth but you know what I've broken my little graphical diagram again where did it go it's

**[21:22]:** disappeared yeah there it is how have I broken it because with transformation a I've introduced the possibility that a particular problem can be transformed in more than one kind of problem any of which will be the solution to my problem so so far I've got an an node but now I've got to introduce an or node

**[22:00]:** because now we have an example of something can be solved one of two different ways we don't care which one it is now you'll notice that there's already some confusion here because how can you tell the difference between an Ann and an or note so the universal convention and you draw an arc over the N noes and that makes it look like an A so it's easy to remember so those are n nodes and now we have the method of problem reduction and this is something sometimes called a problem reduction tree sometimes it's called an Andor

**[22:38]:** tree and sometimes it's called the gold

**[22:44]:** tree because this tree of problems is a tree that shows how our goals are all related to one another so these are items for your vocabulary that are all synonymous problem induction tree Andor tree gold tree all the same thing now you have a name for it you've got some power over it so when we get a situation like this unlike the previous situation which we suggested might come up in transformation

**[23:27]:** a let's see we got 1 2 C and this one is um a it's an or node which one of these problems do we work on well SEL who considered himself to be modeling a freshman modeling the intelligence of a freshman modeling something that after all you have to be pretty smart to do right I mean most people don't know how to do integration everybody MIT knows how to do integration you would think that somebody therefore that knows how to do integration is pretty smart what would a smart person do when faced with his choice well a smart person would say which of these two problems is easier so how do you think you might determine which of two or many algebraic expressions is the easiest to uh to integrate what's your name and Andrew what do you think uh Bas which one feel feel yes feels

**[24:32]:** yes how would I decide yeah how would you decide how would you feel it I feel that the tent is more familiar which one I feel the yeah but I wonder how we can make a little bit more precise this idea of Simplicity uh the Young Turk has a suggestion plus I had a suggestion until you said this idea of simplicity so then I realized that what I was about to suggest wasn't going to um clarify Simplicity but I was going to say um whichever one we've had more encounters with or more experien with yeah if there was something here with a hyperbolic tangent you might say well stay away from that uh to which one of those the uh easier transformation on the next which she might do little look ahead and see which kind of thing would be next to you I don't know you know maybe oh we got lots of people

**[25:27]:** know I don't know all the names Erica I oh you can look it up at the table and see if there something something is in it you can do that but this is close this is tangent to the for so that's not table Ariel um I choose the one without the reciprocal why just because when people see one over like oh man it's just it's yeah we're on we on the right track CL um on an extremely simple level I choose whichever one has the Le symbols in the fewest symbols in it now we're really getting somewhere because you can measure that right a little program why Brett there you are I would say I mean every other exion can sort of be written as compounding a number of functions you can say all these functions multiply together divide it and you just choose the one with the least amount of operations well I heard it perhaps others didn't but what Brett said is to he suggested is that we should measure the depth of functional composition so the number of symbols

**[26:37]:** may not matter because if you had X Plus X Plus X Plus X to 100 out to 100 that would not be hard to integrate but if you got something that's really deep deeply nested has a lot of functional comp composition that could be a problem and that's in fact what slel decided to use after trying several trying trying several Alterna so if we measure the function the depth of functional composition this is the winner and we put the other one on the shelf for at least for the moment and now we have tangent to the 4th X DX do any of the safe transformation Supply which of the you know something has to apply otherwise it wouldn't be up here as an example so what of the what do the urtic Transformations apply Elliot yeah B Bravo military background like that maybe f z okay so B says it is in fact a function

**[27:35]:** of the tangent and when we do that we're going to make a substitution that Y is equal to the tangent so that means that this becomes the integral of Y to 4th over 1 + y^2 and that's by transformation B and the trans information is y equal tangent of X tangent I guess I've lost track of the fact that I've already transformed to Y but relabeling doesn't matter all right so that's progress maybe but um don't see this in any of the aristic Transformations what do I do now ah didn't have to look at thetic Transformations because one of the safe Transformations applies right because this thing is a rational function and the degree of the numerator is greater than the degree of the denominator so I have to divide and when I divide uh and that by the way is number four I get what is anybody good at high school algebra can help

**[28:53]:** me out with that y^ 2 - 2 + 2 1 + y exactly y^ 2 - 1 + 1 1 +

**[29:07]:** y^2 I

**[29:13]:** think now what now we're really getting close to getting through this because um that is a sum

**[29:30]:** and in virtue of the fact that it's a sum that divides into three pieces and the top piece is the integral of y^2 the middle piece is the integral of minus1 and the bottom piece is the integral of 1 over 1 + y^2 Dy in all

**[29:53]:** cases gosh if I look this up I found it right that's up there that's um number b or letter B so I'm done with that this one I can transform Again by virtue of one and now I get the integral of Dy that's in there that's b as well and this one I don't know but I better keep track of what I'm doing here this is an and node so I've got to do all of those I can't give up on that last thing and that end uh transformation is transformation number three so this is in the table this is in the table we still have this to do uh but that's C ustic transformation C we have 1 + y^2 then with a transformation C with y That's y^ 2 y equals tangent of Z then we get to the integral of DZ and that's in the table and we're done so now we've

**[31:12]:** solved the problem it's the hardest problem that appeared in that half decade on MIT 1801 finals this is exactly the problem that was given except that it started here I put the other two pieces on just to illustrate a couple other Transformations but that's a problem that it's solved and now that we've seen in the example we can finish up what um what we talked about a little bit ago uh having to do with the architecture of this

**[31:49]:** thing so far all we've done is talk about the safe Transformations but now we know that if we're not done we need to find a problem to work

**[32:05]:** on using that depth of functional composition business and then after that we apply urtic transformation

**[32:28]:** and the way slel designed his program is he found just one problem to work on did one transformation then went back around the loop because these theistic Transformations a little harder to apply than the than the safe ones so I've giv you an accurate portrayal of what this program did except for one thing which I would like now to go back and patch up and that thing is over here um you know what to do with something like um

**[33:04]:** this well we got to that in a board that's disappeared but when we tried to deal with this we had to find a urtic transformation and when we decided to work on this it must have been the case that this was the simplest problem at the leaf note at a leaf no that has not yet been solved so what's the functional composition depth of this it's three back over here we have something that has a depth of functional composition of two so when the program actually ran on this particular problem it stopped a few inches short of the finish line and went back and screwed around with that other problem for a little bit before it gave up and came back here so it's always looking across the whole the whole tree the leaves of the tree whenever it has to find a place to work on with a urtic trans formation it happened to

**[33:59]:** look at all the leaves of the tree that had not yet been dealt with tried to find the easiest one and that could involve a lot of backing up and and and starting over on a branch of the tree that had previously ignored a small detail not a particularly important one but now where are we we've got the we've got that guy there we got our complete architecture

**[34:35]:** we've got our solved problem and now we can start reflecting on what we've done we can say for example how good an integration program is this and the answer is it was pretty good this machine that slel was using was a machine that was over in building 26 and we were so proud of it that it was behind glass and you could go there and watch the tape spin it was really a delight 32k of memory that's 32k of memory it's amazing that he was able to do anything with a machine of of uh that size let's see yes here's a clean one well

**[35:27]:** can't do board geometry and talk at the same time we can now ask some questions about how well the program performed it was given 56 of the hardest problems and it got 54 right what happened when it didn't get the other two uh well you might be right if you said oh it probably ran out of memory since it had 32k but in fact it just was like lacking two Transformations uh that were needed in order to solve the whole entire set of uh final quiz problems so it when a program fails is often the most interesting question you can ask this is an exception this failed for uninteresting reasons on two of the 56 problems that it that were that it was given to now you next question you can say is um what is the depth of the tree in the maximal case and the answer is it's that case we just worked out and since I've once again lost the whole tree I'll tell you that it dep its depth was seven when you take

**[36:41]:** off that minus5 so the in the worst case this thing had to go down seven

**[36:49]:** levels that's the worst case a more interesting question is what was the average depth

**[36:59]:** and that was approximately three and now we're beginning to say something not only about slagel's model of how a freshman works but we're beginning to say something about the nature of the domain in the domain of calculus problems integrable Expressions that are given to freshmen in that domain the average depth of problem reduction needed to solve the problem is three that's say not very not very complicated if it were 10 you'd say wow how can anybody ever do those problems if it were five you'd say Well only people destined to be math professors are going to get anything right but three as ordinary mortals can do pretty good job another question of even greater interest is how many branches were unused

**[38:05]:** here's an unused here's a branch that turned out to be unused didn't pursue that and so you might say well maybe there are a lot of unused branches maybe you have to be pretty smart about your your method for determining what problem to work on because otherwise you'll go down a lot of rat holes and guess what here's another statement about the domain in the domain of problems that freshmen can work on a final the number of unused branches is about one so that means this tree kind of keeps itself together and doesn't run down to a very large bushy useless tree so this means that the depth of functional composition which Brett suggested as a technique for recognizing the right problem to work on was a choice that didn't actually matter because the tree doesn't grow deep it doesn't grow broad it doesn't matter what you use to decide what to work on because

**[39:07]:** in the worst case you'll just generate a couple of extra useless nodes but they very quickly run to run to dead ends and you don't have to do anything more with

**[39:17]:** it so now the next thing we need to do is back even further away from this program and ask ourselves some questions about the nature of the of what we've been doing and that brings me to the things I've got on that upper right hand board one of those things is a catechism having to do with knowledge and what we've done informally as we went through this program was we've asked questions such as what kind of knowledge is involved in doing this well knowledge about transformation knowledge about how gold trees work and when we're done with a problem knowledge about what things don't need to be transformed because you can look them up in a table that's the kind of knowledge that is involved in doing 1801 and if you do 180 circuit Theory 6o circuit Theory or 6o Maxwell's equations it's the same thing you have to ask questions of this sort about the

**[40:14]:** nature of the knowledge involved and question number one is always what kind of knowledge is involved is it kof's laws Maxwell's equations what is it the next question is how is the knowledge represented and our answers here are well all this stuff ultimately was represented in Lis s Expressions some of the knowledge was recorded in a table of s Expressions that show what Transformations there are there was a similar table of integrals knowledge about gold trees was embedded in a procedure so it was procedurally represented and so for each of the categories of knowledge there's a way it gets represented how is it used straightforward Transformations are used to make the problem simpler the table is used to trim off and completely to to to serve as the bottom of the tree those are the ways in which the knowledge is used and then there's a question of course of how much knowledge is required

**[41:13]:** something that's useful to know if you're um if it's late at night you have two finals the next day and you're not sure which course you should study so how much knowledge might you suppose was actually in this program I've shown you a glimpse of the kind of knowledge that's involved in the program I've answered a little bit of question five what exactly but how much knowledge was involved you might be surprised by the answer first of all the table of integrals I've uh listed only three things there there are lots of other things you can think of like integral of e to the x is e to the X but in the end what SLO found is a table of only 26 elements was enough to solve all of these problems how about the um Transformations here the safe ones about 12 how about the euristic ones about 12 so just a little few

**[42:15]:** bits of pieces of knowledge here and there are sufficient to do everything you need to do in order to deal with like integration problems on a calculus final that was a surprise another surprise of a similar kind also about knowledge is that the relationship between the method to be used and the characteristics of the problem was almost a diagonal table that means that you could in this domain make the right transformation almost all the time if you're a little bit smart and never back up that was an observation made by Joel Moses who became subsequently our proost here at MIT for a while and he wrote a program that could solve anything even you know the it would beat the most dedicated mathematicians at integration and it's the and it's descendant are in mat lab today but this is how it all works and now you could write one of these things yourself partly because

**[43:13]:** you now have this catechism this is the kind of stuff you should ask anytime you're dealing with a new domain it will make you smarter and this is of course meta knowledge this is knowledge about knowledge so this this uh tired aphorism isn't quite what we are going to complete ourselves with we're going to say that knowledge about

**[43:42]:** knowledge is where the real power is now there's one final thing that this program does for us it tells us something about our appreciation of what it means to be intelligent you know that in the beginning of this power I ask you to think about whether a program that could do symbolic integration would be in any way or should be considered to any degree intelligent and I'm imagining that even in the day in these days of met lab and whatnot that many of you said well yes I learned how to do that MIT or late in high school so it must be smart but now that we've completed this discussion I also expect that your feeling of intelligence in this program is somewhat diminished because what happens is that when we understand how something works its intelligence seems to vanish and you've seen this in your friends right they solve some well no they they

**[44:42]:** solve some problem they seem super smart then they tell you how they did it and they don't seem so smart anymore so let me conclude the uh let's conclude our discussion today with a little story I I was once um long time ago I was talking with a a student who said computers cannot be intelligent and I said okay maybe you're right but let me show you this program so I showed it the integration program working on problems like this and after uh I showed him a couple of those examples he says well all right I I guess maybe they can be intelligent I'm learning how to do that it's not always easy then I made a fatal mistake I said let me show you how it works and we spent the an hour going through it like this and at the end of that time he turned to me and said I take it

**[45:37]:** back it's not intelligent after all it does integration the same way I do
