MIT Godel Escher Bach Lecture 5

the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer high quality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu all right hello welcome back today I think the fifth lecture um so I want to start off actually with some apologies um and it's going to be a bit of a sobering note um I want to quickly recap some of the things we talked about last lecture and um kind of bring forth some words of caution um but before I do that I want to also apologize um for this chapter um how many of you were kind of out of your chair excited reading this past chapter all right No in fact I see like the opposite of shooting your hand up uh um so I take it that most people didn't enjoy this last chapter okay yeah I mean neither did I um and really the only reason I I signed it as reading is that you guys could get kind of a fundamental idea of like Miu like the PQ system we had completely formal typographical system for encoding statements right and we could play in a very mechanical way way with these statements of course unlike PQ and Miu PQ to an extent um TNT typographical number Theory um has the advantage of coding something which we think we know things about and that being numbers and the property of natural numbers 0 1 2 3 4 and so on and truths about them um so I wanted you mainly to become familiar with the notation uh and become familiar with the idea that you can start with kind of couple seeds of of axioms and just by applying these kind of recursive rules of of development you could produce kind of a whole web of of new strings which happen to when interpreted provide truths or things which we think we know about numbers um and that was really the main point of this chapter uh they going to be a a few other things I'm going to highlight um but we're going to once again do a mish mash of uh of topics like we seem to do every lecture and um I think we'll have something exciting to show you so first off uh recap of yester not yesterday but yesterday in terms of learning uh last week um where we were interested in kind of fundamentally a theory of meaning um and this is already something I want to uh you know kind of offer my apologies for is in many ways we I think we provide a pretty convincing idea of what we think a theory of meaning is even though it's at it's not at all agreed upon in you know the academic linguistic pH philosophical Community what a theory of meaning actually is um what we kind of advertised is that um the meaning of kind of snow is white and what we take meaning to mean is that there's there's some sort of complex and in the words of Douglas Hof hofstad um an exotic isomorphism um so I could have like you know exotic or E for exotic um for the activity which goes on in your brain when you as you're visual perceptual devices hone in on the chalkboard and we see you know these These Broken bits of lim Stone against against this shell or whatever the chalkboards made out of um and as our our brain undergos kind of a complex set of edge detection algorithms we we hint this like light and dark here and here and here and here um and then as this comes into Focus um we we then recognize we have kind of global objects I don't know if you care about the quotations but you probably notice this group here and here and here um and then once you have these these broken down you then say Okay um I recognize these you then perform Edge detection on each of the letters and you say Okay s n o w spells snow snow then feeds to this whole kind of long and complicated conceptual semantic network of you know what I see the first time the memory of when you first saw snow falling um let's see uh you might just associate it with this the sensory feeling of cold um you might also associate snow with um going skiing or snowboarding um and all sorts of things um and you know just this contining to Branch out and it becoming a very individual thing and I think that's a very important point to notice is that um really what snow is white means to me is in some ways fundamentally different than what it means for you and that's a dangerous statement that means that uh kind of a theory of meaning lacks almost a formal mathematical single interpretation which we intend it to be like what we what philosophers and linguists always wanted is we wanted we want snow to point somehow to this exterior world the world which we live in and refer to the actual crystallized structure of water we we know as snow and that was you know the you know upstanding citizen meaning of snow and there was nothing else none of this you know personal understanding of like well there was that one time where we got caught in a blizzard in you know Kansas or whatever like you know we wanted to get rid of all kind of in individual interpretations um so I advertised this isomorphism between what the perceptual input of snow as white does and how and what that lights up in your brain um but then we kind of carried forth to another idea and we brought out this IDE this very very very connected notion of information so if you will cat your minds backwards um hoffstead talks about this record which we strap onto a you know a space shuttle or something and send it rocketing across the universe right and he kind of poses the problem of suppose some alien civilization stumbled Upon This Record and then said okay what is this and there is this kind of argument of of to what extent would the record mean anything when it was completely out of context of this kind of human cultural sociological entity which we support um here on Earth I mean what does does a rock a record mean to someone living on Alpha C Tor I don't I don't know um and one of the the the big arguments right away was that the structure of a record with kind of these very neat concentric grooves are actually spiraling um to be a little more appropriate and if somehow you know these aliens busted out their microscopes and and started you know analyzing little sections of of this strange you know artifact then they would then notice these kind of regularities in sort of grooves and then they would kind of ask well that's odd um I wonder if that means anything um and then this idea of them somehow from the record be able to reverse engineer what a record player might be or look like and then actually play the music so even assuming if they had somehow figured out this incredible like like string of ideas um even if they were to play the music would the music mean anything to them would it just sound like a bunch of garbled mish mash Latif you have a comment noise so Latif argues that music will just be noise how many of you agree with Latif you you think latif's right does anyone have the coones to stand up to Latif that they can hear at all so max is saying we're assuming that they can hear at all okay so let's go ahead and Grant them that right and if we're going to you know kind of engage in this philosophical dialogue let's grant them the ability to hear and let's even assume that they can hear in a similar frequency range that we do let's say if in many ways like somehow there's this Universal form known as a human and for planets with similar gravitational poles and things like that and just the fact that carbon happens to be a really stable molecule that Evolution carried out in almost exact Sense on this other planet would the music still mean the same thing would it have meaning yes well um The Sounds themselves would still you know pretty much sound the same but if there was somebody singing that probably wouldn't make any sense to them it would be like you know listen to any foreign music right like in a language that you don't understand okay so let's say like it was a piece of Bach right there's no vocals just kind of you know triumphant sounds of you know Glory or whatever uh Felix they wouldn't know what piano is all right so they probably wouldn't know what piano is but do you think they would still have this kind of trigger of of beauty or even kind of awe or desire over over the music even if they didn't know it just from The Sound where do those desires come from what Trigg those okay so let's I should be careful not desires but um just a sense of beauty do how how fundamental do you think a sense of beauty and organization is is in this music that's that's based on your somebody else just no somebody else says okay I can associate this with that this sounds more like this all this like uh uh makes me feel a certain way and that certain way makes me feel that it is beautiful so so even for individuals on this Earth what box music means is different to for everyone okay but it's still like there's still sensation there and I think that's one of the coolest things that you can um when when you listen to foreign music mhm you can in in many ways like decipher you know Despair and all these different feelings so maybe it really depends on if these people get the same certain Sensations in their mind from those different frequencies exactly but you know even putting aside the very complex semantic networks which everybody has internally when they trigger with this music um and you know assuming that these aliens don't have it I think in many ways you can make a good case that there's something about pattern which is fundamentally beautiful and music and that in many ways this is mathematically describable and that's kind of a careful note to think about right just the idea that pattern is itself Beauty and it's something which is universal right that pattern is detectable by anyone and that it is in some ways the only thing which there is to meaning the idea of pattern so last time we really connected pattern where I tried to connect to information now once again before we go running off and all sorts of tangents um I wanted to provide a word of caution right um because what what this means what information and in particular I I at least mentioned the idea of this kind of this entropy version of of information um and I not really going to explain this formula that well um sorry there's the Su Place minus I forgot the minus sign last time log PX but this is just this idea of like the probability assigned to something um and in some ways the less probable something is the less the more entropy there is to it or the other way around but either way like the the main thing I want to point out is that there are these mathematical ideas of of how to measure information in an entropy form and what this fundamentally boils down to is if you were to describe either this record or as we talked about previously a picture or a piece of music and just feed it kind of as a string of zeros and ones um we could actually assign certain values of of entropy and view this as a as a measure of information um and it's it's interesting that there are certain patterns that all languages and certain symbols share um and some of these are closely related to Notions of of entropy um and you can actually produce like an information entropic measure of the letters in the alphabet and that's just just based on how commonly they occur in language but there's yes sorry go ahead Li all these that's only sort of a thing the human mind can handle so it creates all these lunges that have the same structure okay so the chief argues that these patterns and languages emerge because that's all the human mind can handle but I would argue no because they've actually done the same analysis on DNA and DNA as far as a language presents the same patterns so unless you think the human mind created DNA um then uh I would argue no so and and once again so then I I talked about kind of also a related phenomenon and these are things for you to Google and and pursue in your own time is Zip's flaw um and it's this idea that if you were to take any language and or and you would just rank the symbols based on uh frequency of occurrence um there's actually a very nice power law behavior from the most the the first the second most common letter occurs exactly half the time as the first and the third most common letter happens exactly a third of the time in the first and there's this power law Behavior which comes out of languages if you just sort them by Common uh by frequently appearing symbols um and this is kind of an interesting argument zip was a I believe a linguist at Harvard in the' 40s um or 50s I'm not sure um and he said and he noticed this behavior and it's interesting because then you can take something and ask like is this a fake is this an actual language I have no idea what it means but I just notice these certain like reappearing symbols like that and I also notice you know that and then start ranking them and there's this idea idea that you can actually discern intelligible languages based completely on uh the the frequency of occurrence of these symbols but all this this are kind of has has a rigorous footing we talked about then a related notion um because fundamentally I said this picture doesn't capture what we mean by information um because if you take a picture where's my Eraser if you take a picture and you kind of have just a bunch of seething dog barf um and you convert it into these zeros and ones um and then then do this kind of information entropy analysis on it it might not differ all that much from you take a picture which has something like the serinsky gasket drawn on it which has obvious regularity obvious pattern and could be argued obvious meaning and so on at infinitum um so this measure this kind of Shannon in iny information these are it's all just kind of a field of information Theory which if you guys want to you can come to MIT and audit a class in if you want to um this kind of analysis on on this conversion to zeros and ones of of this versus you know the seething Dog Bar would be not that all distinguishable um so then we presented this other idea and we and we really got to play around with this is that well this obviously has meaning because I can write a short little program you know with some some syntax and Etc blah and then run it and it it's very short and it presents this entire picture like this this sequence of zeros and ones that go on for you know a million billion whatever digits um that's needed to encode the visual picture of of a serinsky gasket is actually an excessively long description it's kind of like taking a pendulum and then someone asking you to describe it and you going well it rocks there and back and there and back and there and back and you just keep saying that and then forever however long period of a time you want to describe the pendulum you just keep saying that you you record your voice saying that it's a very inefficient way to encode the regularities of the phenomenon there's the idea that this can actually be expressed mathematically using just kind of a idea of iteration of of symbols um and we had this we had this Linden Meyer system I have no idea if I'm spelling this correctly l i Linden not but there has to be a Meer lener oh so there's an NM okay NM I never won the spelling be um and was like f minus r minus or Plus+ Rus F and we could encode these and then we had this very nice program for expanding this out in a recursive Manner and it just took a little few lines of code um which takes much less information to encode the lines of code um than an actual picture of what's going on so this is this leads to a very important idea of kind of algorithmic information and we then really really started playing around with the idea idea of well all science ever does is reverse engineering we take phenomenon like the supinsky gasket or the regularities of a pendulum swinging back and forth respect to some angle Theta and we describe it very simply so we make our algorithmic content for the pendulum as low as possible by using these symbols to encode the regularities of the Dynamics here and I really apologize to those of you who haven't had calculus but these double dots indicate a rate of change of the rate of change of of the angle Theta um so we then started playing around with looking at cellular automaton which is essentially this grid and we and we divided up and the value of this grid whether it's black or white is somehow governed by the neighbors and by just playing around with those rules we suddenly stumbled upon an entire you know wealth of behavior by changing the number of colors it could have and how quickly it changed we could actually emulate a wave equation we could make splashes in a puddle using this kind of very simple finite and deterministic rule we modeled voting patterns by just saying well I'm going to make my color somehow dependent on what my neighbors are doing what my neighbors are thinking kind of indicating the dangers of group think if you always let yourself be effective by what other people are thinking we just become kind of a homogeneous culture um so somehow just by these very very simple rules which which Curran gracefully coded up in just a few lines we were suddenly describing huge Realms of complex behavior in the social physical and you know cultural worlds and that kind of presented some interesting ideas we started asking like well you know what about about this and that and I remember one line we ended up stumbling upon like was well because we see this self-similarity of of of behavior our our same voting rule which describes how humans act in groups um also describes gas droplet condensation if you have a bunch of spraying water on your on your shower curtain the reason why it droplets up is because you know each molecule of water is seeking to reduce its its overall energy and it can do that by grouping up with people and suddenly you got this clustering this cooning property which we saw in water droplets and then we start going oh like does that mean that you know the universe is fractal and that there's this Con Concepts which apply on all levels and you know we I I've kind of felt ourselves getting caught up in the moment and maybe leading you guys down paths which um although exciting aren't exactly well founded um it's not like everyone in the scientific Community if you went to them and said you know is the universe a giant fractal uh a lot of people would probably say no obviously not um and there would be some various reasons for this um because if you're talking about self-similarity along scales uh this view of well we you know we have the solar system the Sun and you know these tiny planets going around Etc and like aha but it's the same model that the atom is wrong WR one of the fundamental things in physics nowadays is patching up the disagreement in mathematical description and behavior of things at the atomic realm which is not at all like this it's in fact like if you guys have done chemistry and looked through the books you see these weird drawings of probability clouds which are governed by fundamentally quantum mechanics um and it doesn't at all match the classical mechanical description of the solar system um so in that sense no at all the universe is obviously not a fractal because the rules don't apply on all the same levels um and then I did this very exciting you know you know demonstration at least I kind of thought it was exciting at the time where I took a piece of paper and I and I crumpled it up and then I unfolded it and I said well the kind of topology and and morphology of the of the piece of paper is almost identical to the kind of thing we see in mountains and valleys and rivers um and this kind of pattern formation along scale the fact that what I do here on a very local level um is what we see on very large level I suggested this idea of of the universe conceptually being a fractal but what you know a mathematician or physicist might actually tell you is that uh my equations for describing the phenomenon are scale free and there there's this idea of being scale free and we do this all the time in fluid dynamics you know I can drag my finger through the water and see little vort vortices form behind my fingers and then we've actually got exact pictures of of mountains which pierce the clouds and and the clouds are flowing around this mountain tip and you get these Von Caren sheets where these vortices split off I think it's Von Carmen but there's so many beautiful pictures you can see in fluid dynamics and things like that so this being Mountain um or I could equally erase this and say finger right and I and really what I should be trying to do here is kind of is advocate the beauty and our and elegance and our formalism with mathematical equations and how when we can make these scale free and describe phenomenon all at all sorts of levels so I just wanted to be cautious um and not say things which will later get me in trouble um but aside from that I encourage you all to get carried away and explore new ideas and then the reason why karna and I fundamentally believe in Computer Science and Mathematics as a framework for thinking is that you can be as lofty and philosophical and out there as possible but at the end of the day you have to either be able to make it work rigorously with proof or by execution on a computer which for most intensive purposes is just as good as proof um because it either works or it doesn't right and you're thinking about the universe either works or it doesn't right and fundamentally you need falsifiability so there's a chance that you're thinking might not work right um and it's fun to be metaphysical and thought talk about you know things higher than the universe in space and time and what you know the structure of these things are but at the end of the day we want to be able to test our our observations or prove them mathematically or using computers so that's kind of my my sobering note of caution um and I'm sorry for those of you had to go through it and didn't want to hear it um now on to slightly more fun things first let me check the time so number Theory um I really want to just draw this draw your attention to the to the idea of of what we can take as to be an axiom and and why we just don't like we can't prove these things and if you you'll cast your eyes onto uh page 22 one uh you saw kind of this pyramid of right and you know we had 0 plus SS s0 equals SS s0 and so on um and well first of all I want to highlight some things some elegance and this is really what makes magicians the most anal creatures on the planet um is that you know we don't have numbers here we just have one number and that number is zero um and then every other number is just the successor of zero or the successor of the successor of the successor of zero or the successor times what we like to say in our meta language you know 1729 Z S's and then a zero um and that representing the number 1,729 um but there's some also Elegance in this the fact that you only need one concept A Z well two concepts you need a zero and you need the concept of a successor and suddenly you get the whole thing for free right which is which is pretty but what was highlighted by this example was that we don't have in our if we didn't assume it we wouldn't have we couldn't prove this this statement which says that for every a where a is some variable 0 plus a is a what a dll and obvious thing right but all we have at our disposal are are kind of these things and in fact we get this whole Mountain this pyramid of of of true statements um and we want to LEAP to this generality that well this is obviously the case but fundamentally our our our desire to LEAP to this conclusion comes from our our understanding our mental models of how numbers and how specifically integers behave um and that's an important point this this idea of really all we ever have at our disposal are are Al models and by making them rigorous and trying to make them rigorous through formal systems we really kind of see whether or not our definitions Encompass as much as we want so we could never actually prove this statement with the way that TNT was set up without this axium so we eventually had to assume it um and and hoffstead calls this uh just to write it here Omega inmp complete where Omega is kind of the thing we use to refer to all the integers at once um and and it's just that idea that even though we have this infinite stack of true things we don't have the thing which describes them all as a truth namely this um but you know this notion of mental model I think is really important um because I remember first seeing this proof in in high school and I remember just being kind of utterly shocked and in some ways horrified by it um so how many people believe the following 999 repeating is equal to one dur believes it naine believes it can anyone come up and Prove It Felix do you believe it can you prove it think about it first think about it first deep down um does anyone want to show off and leap to the chalkboard like a young GA and just go ahead and show this to me D is that something multiplying by 10 okay so I'm going to go ahead and take your suggestion and kind of lead you down the proof so we're going to call this thing X um we'll temporarily forget that we're it's one we're going to call X this 0.9 repeating um so dur re recommends we we take we consider the quantity 10x okay which think it's 9.9 repeating okay a bunch of hands if you stop it at Infinity one because it's approaching a number okay well without to the idea of a limit we can try to prove it more fundamentally uh I don't really know Felix do you know okay so Felix says we should subtract X okay so suddenly we get 9. oh sorry I mean X itself is 09 repeating dot dot dot so then when we perform the subtraction we get nine so we have now this new truth that 9x = 9 the only number which satisfies that is x = 1 and I actually will never forget the girl sitting next to me in pre-calculus when when my teacher first did this and she goes no it can't be but it's not one look cuz if it were one I would have WR written one right but somehow I wrote down a completely different number which was the same thing and this kind of shows the the the really important thing which mental models have to tell us we can have what appears to be a correct understanding of an object namely real numbers um but then we're continually surprised when they do things like this to us even at the most basic levels um so that's just kind these are just kind of meta statements about what mathematics does and what we do in mathematics um and in particular what we're doing in TNT is we we have this idea that number Theory should Encompass or at least TNT should Encompass all of our thoughts of number Theory and this goes back to what uid said about his axioms of geometry he said you know we we know these things should be fundamentally true or at least we believe they are to be they are true and that they Encompass all of our all of our knowledge of of geometry and that everything they produce as a result of those assumptions should be true and certain um but then we got the whole case with you know sacari and and you know gaus you know in hiding because of course gaus would discover it 50 years before everyone else and then show his notebooks goes oh sorry yeah I I did that theorem in between uh you know my first cup of coffee and my second cup of coffee um but um well good I'm glad you discovered it too um and just this concept of non- ucan geometry where where you break that fifth postulate that that if you have two par you have a a parallel line or a line and a point not on it that there exists unique line unique exclamation point um such that it does not intersect but if you're working on the surface of a sphere for example and you define your lines to be great circles and then in fact any possible line you draw or line is great circle um you actually have two intersection points something like that um although that's a terrible picture sorry um so you know Hilbert this very guy who who's trying to Advocate all this stuff involving number Theory uh said well we just have these fundamental axiomatic Notions of a point in line and the most we can get from them are their logical relationships with each other and the second we try to interpret these things we then get ourselves into trouble when we interpret the statement line and we we mean the straight thing on this flat board um and not the curvy thing on the surface of the Earth um we get ourselves into trouble because we're providing an interpretation and not sticking directly to the formalism shows you also one of the kind of dangers of getting away with your interpretations of what your formalities tell you um and I I'm kind of proud of hoffstead for for doing that and cautioning us against uh interpretation because it gets you in trouble I want to um and then you know finally first I'm going to field some questions about this chapter before uh I kind of introduce what Curran's going to do and um and then move on to newer and more exciting things TNT anything it I mean I remember sitting in an undergraduate seminar on girle erbach and someone going like what the was he talking about with these Supernatural numbers um and you know Omega inconsistency um because I mean these aren't trivial Concepts right I mean entire fields of mathematics have been devoted to them um so if you guys are feeling completely I understood this um in my sleep yes Sandra I was confused like how many rules TNT have talk about like sub categories um so incompass TNT right uh so he also talked propositional calculus and how he assumed that into TNT oh yeah and I'm I'm sorry but I didn't assign that earli as reading so that was kind of out of context all right um but did any of you guys try like the little exercises in in the book itself um there's one section I want to highlight um and I give you know browning points to everybody who gives me a right answer um because I think I have my own view of answers but I'm not sure if they're right this will also test your guys knowledge of the notation um so we have Tilda upside down a c colon backwards e B colon parentheses SSO um dot b um parallel lines C okay um first of all can someone tell me what this means by giving it an interpretation and then tell me whether or not it's true or false Latif there is no C for all of C it does not that there's a well here before we do the Tilda let's do this all right say again for all c for all C there exists no B there exists a or no B oh there exist a b there exists a b such that the successor of the sucess of Z * B is C okay so this without the Tilda is it true or false yes because if the TAA it's truth and why because two * anything is not going to the effect so fundamentally what this statement is saying is that for all numbers natural numbers um that number is even because it's divisible by two or it's a multiple of two um which is clearly not the case cuz um and using our rule of substitution or sorry specialization um we could have picked well let's say three or I'm sorry three doesn't exist in our system it's SSS o or zero um and through our interpretation we can see that well there is no number B there does not exist a b such that two times that number is three namly because three is on right okay so let's try a little harder one real quick so and then with the Tilda which means not our false statement is now made true all right so let's consider so this was round one round two for every C that not b col colon s s equals see all right anyone who is not Latif can answer I'm going to successfully knock you guys out so the last man standing actually gets the hardest question so first anybody willing to field an interpretation who's not Latif Max for doesn't exist such that and call it two * okay so for all C there does not exist a b such that 2 * B is C willing to you have a 50/50 shot on this oh that's f yeah there you go exactly it's false because uh we specify let's let C be two and clearly when there exists a b not not exists there exists to be namely one that 2 * 1 is one so we now have two people eliminated three all right so now let's try this uh for every C such that there exists a b damn it um not uh Tilda I mean s s o dob equals c d for every C there exists a b that is not 2 * b c okay and is that true or false so say again we have a there's not a c for every C for every C there exists a b there exist a b that is not such that this isn't such that 2 * Bal right so actually so specify let's go ahead and um so what did you say was this true or false false I think it's actually true um because if you have uh because this statement says that for every number um there there exists another number such that this doesn't work um but if you have say four um you could pick anything like three and two times three is not equal to four which is exactly what that is so instead of the tildas which I find really confusing because it's out front you could just consider it to be a not equals here um which I think is easier so this is true I believe um okay fourth round sorry even as I'm saying these things I'm getting tripped up on myself so I'm like notation is kind of cumbersome uh for all C such that successor successor of zero time b equals c all right so anyone who is neither Max nor Latif nor dur Sandra all right um there does not exist a b such that all C all numers such that that 2 * yeah exactly so first we you know it's easiest to consider without the TAA and just consider you know there exists a B for all C such that this is the case um and is so with the Tilda just to make at just the way it's written is this true or false false so wait hold on did I write down the right thing um okay so first let's consider the case without the Tila so we have this magical B such that any number we put in um this number is the product of two and that so if we had is there any one number such that any number is just equal to 2 * that so as an example we could specify C to be four or three yeah exactly three and then B to be one right and clearly we have found a c namely three such that 2 * 1 is not that so this is false with the Tilda it's true excellent good work you know I'm I just so say again no no no exactly like you can't um well you would Express one in this notation as just the successor of zero um so it's not that you don't have access to one it's just that in our notation um this is how we would write one basically all right but good I mean I'm glad I just want people to try these um so so two more to go I believe right um so anyone who is not any of the other four people have gone um riddle me this Batman be such that not for all C there exists ss0 * b equal C okay any be na * okay can you give me a truth evaluation so we have the B so let's if we and we're we're saying that for this specified value of B regardless of what we put in here this will hold right or to kind of say it a little more clearly and this involves some of the symbol shunting we you do in the chapter there exists a b where if you put in any c it's not going to equal and I think that's so you're say false or is it true there ex be such that not for every c 2 * B is whatever so let's pick three right and I mean yeah I mean this is this is actually I'm pretty sure true because the second you fix B let it be four right it's clear that not for every number 4 * 2 is that number right so in particular for you know six this is not the case right I can't put in any number and get it right are there still questions here last one do this one again do the next one all right do the next one so we're okay with this being true true okay yeah and it's really weird complicated logical relations that's why most of the time mathematicians don't use these things because they get tripped up on the symbols um whereas they already know up here what they're doing is right um so since we're running out of space I'm going to put the sixth round up here and let's try to do this quickly so we can pass off the show such that uh so there exists a b damn I'm not going to do the interpretation um backwards e b colon upside down a c colon um TAA parentheses SSO do B parallel lines C okay so anyone who's none of the previous five people Maya yeah give me interpretation and Truth value if you're brave there exists for so that there is not two right so equivalently I could replace the TAA with what other symbol line here right so I think that's easier um so there exists a b said for all c 2 * B is not equal to C so is that true or false it's true okay um this so there exists a b such that for all C so regardless of what you put in here okay so then it's false right ex see this flipping back and forth between these these existential and quantifier existential quantifiers and things like them uh can really make this confusing because what you have here is your is that there's a b such that regardless of what you put in here this equal this equality never holds um but that's not true because you can take any c eventually it's going going to work right because if we if we specified B to be two that's the thing which exists um then we we can find a c so it's not true that for all C and particularly that c value being four um so 2 * 2 is equal to 4 even though this thing claims that this value of B which we picked um would never be equal regardless of what you put in here so I think that's my answer key um true false true true false um and it fits his second hint he says either there are four true and two false or four false and two true and that's related to actually how you shunt these uh tildas um but once again like we don't I mean unless you're really planning on a life as a logician you're not going to have to spend a lot of time manipulating formal systems um um and as such it's good to get practice with this um just because the difficulty which you have of of taking in these new symbols and and forming kind of you know creating more space in your in your neural network for for fitting these places in is I think an important exercise um and that really goes back to that idea of a theory of meaning um and it's one of the last things I want to apologize before I hand off to the lecture to current is that when I say things like recursion and I say things like you know formal systems isomorphisms algorithmic information you know Shannon entropy etc etc um neuron Nets like these terms don't really mean the same thing for you people that it does to a professor who's been spending years working long nights torturing himself over solving these problems late into the night and that process of thinking again and again and making mistakes and then refining your mental your understanding of something forces you know certain parts of your brain to meet here and here and here and just by talking to it at you guys what I'm trying to really do is just Inspire an interest in what I'm saying um and it's not like I can condense somehow you know seven years of you know of undergraduate and postgraduate work into a 2hour leure and just immediately you know go into your brain and you know I want to put this near on here and there and there and suddenly you have the same depth of understanding about these subjects that you know Seth Lloyd or anyone else uh who's a specialist in these fields the kind of understanding they have I can't endow that in in just a simple two-hour lecture um unless I assign you know pages and pages of problems and you're working you know 100 hours a week um which I'm not going to do because I'm not evil but aside from that the fundamental thing to pull out here and I've noticed that I say fundamental on um I'll try not to um the important idea here is that you can start with essentially a basic set of statements which you think can capture something true and apply a recursive rule a recursive algorithm to producing new Str which can produce new things so as we go into the next part of today's lecture I want you to kind of think of this truth tree which we try to grow and it all starts kind of from piano axioms number Theory and we just apply these rules and create different statements it's just like the Miu tree that we made in the first lecture or two I noticed no one's challenged me on my 20 bucks um right so what happens is that these some of these things we start with those five basic axioms uh which which Hof stats outlines zero is not the successor of any number um let's see uh zero is not the successor of any number you have to assume that zero plus a number is just that number itself um and here we go yes he actually States them um in this form so you don't go ahead and give it an interpretation Genie is a gen right Genie is a zero J is a number every gen has a meta which is also a gen so every number has a successor which is also a number so Genie is not the meta of any gen so zero is not the successor of any other number different gens sorry this is Page 216 um different gens have different metas so if two numbers are not equal the next guy after them are also not going to be equal and then finally if Genie has X and each gen relays X to its meta then all gens get X and that's the principle of induction that if zero has a property p and the successor and any number relays that property P to its successor then all numbers have it because you can give from zero to one and one gives it to its successor and it's two and it always has that property p and that's what in mathematical induction relies on and you know from from these C these basic things you can actually derive most of number Theory and you just apply these that rule these inference these rules of induction and you start with this trunk and you you get a new theorem well since one and two aren't equal then two and three aren't equal so you just kind of add things to your tree based on these rules and it's completely local it's completely based on what you have at your given point and what rule you're willing to apply and then it's amazing the kind of emergent patterns which you can get and we happen to call that number Theory today I you'll shortly see some things which are a little more interesting um but on that note I think we're going to take two-minute break to de-stress and then get things set up for K to take over thank you okay so what he was actually talking about can also be called a context free grammar a context free grammar is something that has um symbols and production rules and the symbols here in this case are s and zero and the various mathematical operators but they're just symbols in terms of the the grammar and the production rules are the uh the rules of inference where you can take one string and perform some manipulation on a part of it to get a new string it's a rule of inference so you can use a similar system to Define moving around circles on the screen um so I'm I'm going to explain what's going on here this is a a program called context free it's an open source project that you can download and play with yourself so what's going on here the code um start shape just is the entry point it's not going to change and we Define a rule called spiral and inside this rule we have Circle which plots a circle on the screen and then we call spiral again and y space two means that we increment the Y position by two units and size space 0.9 means that we multiply the size of this by 0.9 every time we go up so this rule defines this image and what this program does is um when the thing gets too small to see it just stops doing it that's so this is actually an infinite recursion but it stops at some point because it gets so small so this is our framework and by changing this this code little by little we're going to get some amazing pictures so I'm going to just do these changes and explain them as I go so I just had this spacing to be two so it's clear that we're just drawing circles I'm going to decrease the spacing to be like 0.4 and uh render so it looks like that so I'm going to Define another rule um also called spiral and so as I go I'm going to explain the the more features of this language um when you define a rule that has the same name twice what happens is whenever you call this rule it um it calls one or the other with equal probability so what I'm going to do here is say um flip 90 which means flip our sort of frame of reference by 90° um actually first of all before I do this sorry I'm going to add a rotation so rotate one rotate one degree each time so it rotates a little bit you see that one degree each time so if we decrease the size by 0.99 every time it's going to get smaller a little bit slower so they see the spiral happen so if we do 0999 it'll be even more spiral so that's what we get uh I don't know why it's going off the screen there we go okay so now I'm going to Define another rule called spiral and flip by 90° so if i r this what do you guys think is going to happen what do you think it's going to flip so maybe I wasn't clear about what what it means to to call that flip thing so when we say rotate one we're rotating one degree this way so after after we call Flip when we say rotate one it's going to rotate the opposite direction so say we call the first rule like five times draws five of these circles then we call the second rule once it flips and then we call the first rule five more times it's going to just turn the other way a little bit and so initially they're going to be called with equal probability so if I render it this is what we get this sort of Meandering thing so what's happening is half the time it's calling the first rule which moves the circle up a little bit and rotates it and decreases its size and draws the circle and half the time we're calling this other rule which flips the direction in which we're rotating so this is what we get um another feature of the language is we can change the probabilities at which these things are called so let say 0.1 I put 0.1 right next to the second spiral rule the flipping rule so that means well if I don't specify a number it gets one so that means that the first rule is going to get called with a probability one and the second rule is going to be called with a probability 0.1 and this is whenever maybe oneus one minus that first will all probability oneus because you're rolling a die you can never go beyond probability point right so talking talking about probability um what what it actually does I think is is computes the sum and then takes the fraction of that sum that each of the rules have for probability either way this one happens less probable than 50% now so we can see that it goes for slightly longer periods of iteration without any flipp so if we do it again uh decrease it 01 it'll flip even less and the the the the uh yeah flips with even less frequency so if we make it 01 uh it flips a lot less so already we're seeing these really cool pictures being generated by such simple rules simple context reg grammars any questions so far so what happens if I add inside this rule another instance of spiral without the flip what does this mean first it f and then just yeah so more or less she said first this flips and then it goes on without flipping so yeah with this rule instead of um just flipping what it's going to do is start this one off on its tangent and also just keep going its original way without flipping so we'll render this and see what it does so it it does exactly that see whenever it branches it it also keeps going its original Direction so we can um change some parameters around and we're going to get some organic looking forms so if we decrease the probability no increase probability of branching we get this just goes out of control so maybe that's not what we want to do so now I put it back um if we multiply size by 099 yeah there we go now we increase the probability of branching and we get these trees like look at it it looks like a tree um it's really wild so if we increase the probability of branching even more we get thicker trees because they Branch more uh it's pretty wild Isn't It Isn't that cool so it makes you wonder like does nature use these sort of context free grammars in in the way it grows plants or is it like a Linden Meer system is it fixed these like Global rules that get applied at smaller and smaller scales I think in nature what we see is sort of a mix a mixture of both cuz some plants have very regular features and some plants don't so it's sort of it's still a mystery like plants but it looks pretty organic so I'm just amazed by this uh sort of thing so I can you know play with the parameters and get really cool growths so let's think about this as a model of plant development um we're modeling that that the size of the plant is just constantly shrinking and when it branches it's it's Mass sort of doubles which is sort of a bad model think about a tree think about a tree just going up and then when it branches uh it all it still keeps going up but a branch like goes off to the side so we can change our grammar to do this and we'll get some tree like things so I'm going to do it so this is the rule the the rule on top is just the rule that it does when it's going just just going so I'm going to change this to just um increment Y and I'm going to change this to so one of these is going to be the it's just going to go straight and the other one is going to branch and get smaller so sign um9 for for just going straight and what flip does in this context well first I'll explain it later we say rotate 45° and size is 0.3 so what we get is this very spark structure so we can increase the probability of branching to like5 maybe N2 so we get these things that sort of look like trees so I'll just explain the rules in case you didn't follow so the first spiral in this rule this part of the rule encodes for the fact that um whenever it branches the size gets a little smaller by a factor of 0.9 and you form this branch and this the second rule here says size 0.3 that means that the size of this Branch is3 the size of the original trunk um and the flip part flip 90 in this rule means that next time it branches it's going to branch that direction we can actually take it out and if we take out the flip um the branches will all just go in the same direction all the time so if you take it out see the they only go in One Direction so we could sort of play with um parameters here let's say .95 let's just see what happens uh yeah we get some pretty interesting things if we make the branches a little bit thicker maybe point4 see look at that it's like a tree or something any questions so far and comments so if we add a little bit of rotation to the main rule uh rotate one Dee yeah Latif does it also take a probability of that too say again when it calls itself inside it does it call itself the thing that calling or does it call the other one oh good question so he asked um when it calls itself like inside like this one or this one or this one which one does it call the up one or the right so which one does it call when you when you call spiral so this is where the probability comes in anytime you call it these there are these three instances where spiral is called inside of spiral so it calls either one with certain probabilities and the probability of the first one is one out of 1.02 and the probability of the second one is.2 out of 1.2 sorry the probability of the first one is one of 1.2 so it's a very high percentage and the probability of the second one being called is 0.2 out of 1.2 so yeah every time you call it from within anything it goes into this program and say you know tell me which one should I call and the program assigns which one it is based on these probabilities so doesn't matter if you put it put it have So you you're saying maybe we could put it outside put it inside the function so that the function I mean the thing itself the reason why I put it inside the function is so that it can yeah call itself so like what happens if you take a spiral flip 90 and you put it up in the top rope for spiral the signs cut that so you you're saying what what if I take this out of here and put it up here sure yeah I mean I don't know I don't know but it has to be inside a function in order like so I think the idea is that you have kind of two options here whether or not you're just doing the simple spiral circle routine or if um you're then doing this other spiral routine where they rotate 45 degrees and change the size by 04 instead of this spiral where you flip 90 and you change the size by 0.95 and notice that and see this was what I thought I'm not exactly sure how the algorithm is implemented but I think by having 0 2 next to the bottom spiral that means the top spiral is called only with probability 08 but that's obviously much higher than 0. 2 so every time the computer rolls its die it's trying to decide do I either execute the top spiral or do I execute the bottom spiral um and then the content of each of those those spirals um is then governs the behavior you see here so what what we did when we when we moved this up whenever we call spiral Spiral it branches we have two spirals now right and that's the probability of that one is really high so that means pretty much every time we're branching so we just get this mess of branches and it will'll never finish so yeah I mean there are all kinds of really interesting um modes that we can come come to with this so I'll take it out and put it back where it was um it's still Computing uh okay there we go it stopped oh yes so it it looks crazy doesn't it so if I take out that rotate it's all very regular it's sort of regular structure and we could change the angle maybe uh 60° I don't know or 90 even and it looks sort of like um roads maybe I don't know we had some conf it's like a tree like near a river or lake or something you can see that it's like sort of an not yeah it's like a you're saying maybe it's like a Riv a river with these little sub Rivers going off of it yeah I mean this kind of structure is found everywhere in nature it's really amazing so if we add a little bit of rotation to the to the main going forward rule rotate one we get this sort of veiny that's when the wind yeah when the wind is blowing on the tree right or it looks a lot like uh Vines right when a Vine is crawling up a wall and you have or a root a root of a plant H underground yeah underground the root sort of looks like this so yeah or the special tree if you tried to do this so can I m the make the cotch snowflake or the the branching tree with this sort of thing I haven't tried uh maybe I could do it somehow but I um I don't think so I don't think I can because the how this program acts is completely random it's stochastic it chooses which rule to do on the Fly H would well it is still recursive it it's totally recursive but it's it it's not deterministic so it's something being deterministic gives it like absolute rigid regularity that we find in the cot snowflake or that branching tree that I showed earlier but yeah they're executed randomly so you get these irregular fractals but the serinsky gasket you can also generate stochastically using random die roll exactly and you you pick your three points and then you throw a random Dart and then what you then take the distance to the closest Edge and fill that point in right think you do that I forget so the chaos game the chaos game with the serinsky triangle um what you do is you have these three dots I did explain this once before but I'll just do it again quickly you have these three dots and you start at a certain point like say here and you take where you are and you choose at random one of the three dots and go halfway from where you are to that dot so say we choose this dot we go halfway there say we choose it again we go halfway then say we choose this dot we go halfway from here to here so after doing this like a thousand times we get all these points that in the limit if you were to do it an infinite number of times it would be the serinsky gasket and so it starts looking like there serinsky gasket after a little while so that's stochastic right I mean I don't know maybe I could code that in this language maybe it's possible I haven't tried so there's some some prepackaged examples that I sort of um have prepared um and one of the things that I want to talk about is these regions of stability and instability in the um in the system it's it's a very dynamic system and you get these different situations yeah look at this oh wait that's a PNG that's not the actual thing oh well just consider this open the actual one here it is so what's going on here all right what's going on here is I have this one rule um first of all this rule these two rules are similar to the ones that I'll just get rid of this one for sake of explanation so this is pretty cool right it's a tree so I'll explain the rules the first rule goes forward by unit of one and the circles are one so we can actually see all the little circles goes forward by one and degreases in size um the size is multiplied by 0 N9 so that that's that's the main Rule and then we have this other rule which has a probability 02 over 1.02 the sum of them and that's the branching rule so it just calls tree again with a rotation of 20° or minus 20° so it's 20 minus 20 so this is our rule um and it generates this tree and when we add this other rule so this is a rule that multiplies the size of the thing by five which is pretty um pretty extreme right but it happens with a very small probability so I I'll decrease the probability even more 0.003 so maybe 01 okay it just happened a few times so we can see that usually it doesn't happen all these all these branching and all these iterations it didn't happen but on this one here the size of it multiplied by five right so we had this bigger Circle and then it propagated more and then it happened again on this tip this very end branch of it and it happened again so I mean M this pattern appears in evolution actually which is really fascinating so in evolution you have these these species and whatnot or different strains of genome which sort of diverge and and Branch out and say at this point in time and the point in time being the number of iterations overall at this point in time say like some huge catastrophic event happened on the earth and this one organism or small set of organisms is the only one that survived so their weight so suddenly increased and then they propagated and spread themselves and and this is what we get this new um branching of of evolution and then the same thing happened here bam and then it branched again and it branched again so it's a very unstable unpredictable system because you could have these little events that just completely change the face of uh the system like here it's a stable system well like without this new rule it's a stable system we know it's always going to go down this the size is always going to get really smaller and smaller and smaller until it disappears that's guaranteed in the limit but with this system we introduce a rule which goes backwards so it makes the system unstable and much more unpredictable so if we um increase the probability of this rule to 0.001 the system goes out of control really quickly and we have 0.01 it just gets completely out of control and it just gets bigger and bigger and bigger until see see this this message here a shape got too big um so this is an error that we get when this when the thing just goes out of control so this would almost correspond to like meteorites being frequently thrown at the face of the Earth and only very few strands of species surviving at a time well this would yeah I guess this would correspond to that yeah destroying genetic diversity at more frequent internets yeah if we were to if we were to think of the metaphor to Evolution again I don't know I guess it would correspond to like just huge catastrophic events happening all the time and miraculously every time one species survives sort of extreme metaphor I don't know if it would really hold but but it's interesting this um regions of stability and instability in this space of parameters to the system so yeah it's pretty fascinating so I'll just show some more examples and then I'll be done um this thick tree yeah when we have certain parameter sets we get these really organic looking forms so if if we increase the probability of branching even more get these really nice thick organic looking trees so you asked that's the question so she asked um do organisms actually use this sort of system to live and and if like they had ones that didn't have a system and did have the system that evolutionary or not right so you're so you're you're asking this question like sort of from a different totally different angle she she's saying like um for a given organism if it develops this kind of recursive system is it evolutionarily more advantageous like trees I think I think for plants I think that's like the one of the main thing that plants sort of developed and that made them evolutionarily speaking more feasible more fit so that's why so maybe that's an important point to consider um however what would actually make a tree Bend like that okay let's say that it's a relatively calm area and we're not having hurricane force winds forcing our trees to bend that way what else would uh why why would a tree grow like that yeah re sunlight sunlight exactly photot taxes right and plants have this feedback mechanism where they're actually able to sense light and it's just like if I were to have a potted plant here and that light in the corner Illuminating us it wouldn't it would actually be able to dynamically change the probability of splitting and of course the method for that is actually a little different you have these oxin chemicals being exchanged collapses cell walls and a tree is actually very quickly able to grow and bend in a different direction um but um so it's not exactly just a probabilistic w what happened there uh it's not exactly just a probabilistic context free grammar um it's it's got to have some sort of feedback mechanism and then with the level of evolution changing the rules even there so yeah I mean look at all the the number of um Leaf branches when I say Leaf I mean the one on the end like there's so many of them and and it maximizes is the um the amount of sunlight that hits like it maximizes the amount of surface area on the tree so I think that's why that's one of the big reasons why it's more fit you had a question no I just had a comment I also Mak sense like you said the surface area and it wouldn't make any sense to have a branch at the bottom because all the light was already blocked from top right it wouldn't make any sense yeah if you had like some uh mutation where Branch did come on the bottom that tree wouldn't have any advantage right so you're getting at selection so he said like if there were some tree that had these set of rules that made it start branching at the bottom and on the top it would be selected against because it's not feasible cuz the light would be blocked out by the higher branches yeah that's that's the nature of evolution yeah yeah and that also looks like a prank you got the Cal cortex on the top that's very like C and you got the correction connections and exactly so so he said it's sort of like a brain like this is a cerebral cortex and you have all these connections that go out to the surface of the brain which have like all these you know brain cells or even a vein structure yeah veins the structure of the veins in your body coming out of your heart it just fractals out to all that your body so yeah it it's this sort of universal form that appears everywhere it's really amazing yeah so all we can do is sort of awe at it say wow they're like the same man but where does it come from what does it mean I don't know it's something that needs to be explored I think could it be that he had to be that way could it be that it had to be that way yeah what do you mean by that you can say that uh it's like the um most efficient algorithm and left um stress towards efficiency so at some point you had to like hit that algorithm and when it when it gets something good it doesn't want to let it go yeah so you're talking about like it being the like uh the whole system of like all biology and things evolving he said maybe it it's the only thing that works like it has to exist because it's the most efficient algorithm for for developing our biology our wors and so once it once it appeared it sort of took hold in this big evolutionary uh series of events and I think you're right and it it it also is coded in a very simple set of rules like look at this it's like it's very little text you know that encodes for all of this and I think similarly in our genomes like if if The evolutionary Paradigm comes up with an efficient way of encoding a certain set of rules to do something which is which is uh fit like which makes us more fit than than it sticks yeah I think I think this this notion of fractals and the recursive algorithm being encoded into our genomes is is a reasonable thing to hypothesize that also like show like behaviors like yeah ants an colonies oh man yeah yeah it's everywhere properties emerging properties yeah so I think I'm done I think this is my Spiel and I'll give it back to Justin I just want to kind of wrap things up kind of give a sense of conclusion and direction of where we're going um if you want to kill the projector so exactly kar's kind of you know hinting at an idea and we're all kind of at the brink of this this concept which I told you at the very beginning is the stated thesis of girdle eer boach which is that the Universe at a fundamental level is a formal system and that it obeys certain deter deterministic rules or perhaps probabilistic rules but kind of formal system nonetheless we have this kind of label which we just stick on something and that being the eye label which actually hides a lot of detail um just like in the way that um but trying to understand them in a fundamental way is the state goal of this course um and I'm still debating kind of because I'm kind of continuously and probabilistically modifying the course of this course um and I'm trying to decide and the stated plan right now is that after we do mumon and girdle and kind of get you'll get this weird Asian kick from both K and I um combining Zen and logic um and we talk about gerles in completeness theem finally um and then we're going to Leap Forward you know chapters in the book 16 to a self-re and self self-re and self-re chapter um which will be kind of a little over the top first of all it's a very long chapter 57 Pages um but it's going to have this idea of a kind of typographical genetics and we're going to look at how genetics and protein folding and kind of the processes which kind of make us um correspond to some of the formal systems we've been talking about in a prescribed way then we're going to LEAP backwards and since what I've realized this course has become is really a Topic's course of a bunch of things um then leap to essentially brains and thoughts because the bottom line is Hof st's thinking hasn't been patched through all the way otherwise we would have it solved we like ohuh good thing we solve Consciousness like we can go on and do other things it's not solved um and there are these huge kind of gaps missing between like okay I maybe I buy it that the universe is a formal system but what on Earth does girdles in completeness theorem have to say about physical systems um and Let's ignore all that and then start talking about the brain kind of these meta structures and the brain and the mind and thinking and artificial intelligence that kind of wrapping up the course um but then of course I'm also thinking about possibly showing a movie um and that being Waking Life I don't know if any of you have seen it um and that just being like essentially my gift to you guys for working so hard in this class um but I might need to get permission slips so that's yet to come and uh I I kind of apologize for whatever slow pace today's lecture was um hopefully next one will be a little more exciting um but other than that read mumon and girdle uh I want I meant to do the dialogue that precedes the chapter today but obviously we can't we can do it for next lecture if you want um and then um yeah that that should be fun and read that that handout from I'm a strange Loop because I think it'll exate and it's really what I'll be lecturing from for a large bit of next lecture so thank you all for showing up and uh have a good day

Channel: jasonofthel33t

Views: 35,992

Keywords: godel, escher, bach, js bach, self reference, incompleteness theorem, recursion, philosophy, mit, computer science, quine, Math

Id: PBDQL7hp7gk

Length: 98min 25sec (5905 seconds)

Published: Sun Dec 02 2012