1
00:00:25,039 --> 00:00:28,070

okay why don't i get started um  so  okay what would what have we been doing  um so last time we considered a bunch of  uh procedures for testing properties of  various automata and grammars  the acceptance problem for dfas  for anaphase  the acceptance problem which is really  the generation problem for context-free  grammars  and emptiness problems for dfas and and  and context-free grammars  and also um  we looked we we showed that atm is  turning recognizable like there's a  question here in the chat already about  that yes we did show that that was the  universal turing machine that we  presented at the end that's what shows  that atm is turning recognizable  um  we mentioned that uh it's not atm is not  decidable uh which we promised we will  prove today and we will do so okay so  that is the plan  um proving atm is undecidable  and we'll introduce the method for doing  that called the diagonalization method  i will also show the complement of atm  is  uh turing on rec unrecognizable even  though atm itself is recognizable the  complement is not  and  then we will introduce another method  called the reducibility method for  showing other problems are not decidable  and give a one example of another  problem which is not decidable assuming  we have time to get to it if not we will  uh  uh delay that part until uh next  tuesday's lecture  all right acceptance problem for uh  touring machines uh so just um  as i mentioned we showed that atm um  which is the language of turing machines  and inputs where the machine accepts the  input  um  we showed that was recognizable we  claimed it was decidable today we're  going to prove it's not decidable  all right now the method  uh that  uh we're going to use um which is really  the only method out there um for proving  uh um  some pro you know a problem was  undecidable is the decoder  diagonalization method i mean ultimately  we're going to show the reducibility  method as well but it really depends on  having already shown some other problem  undecidable  via  the diagonalization method so ultimately  everything hinges on the diagonalization  method which is really all we have um  and uh so  to  uh introduce the diagonalization method  i'm going to  make a bit of a  digression into a  uh branch of mathematics called set  theory or  it's part of mathematical logic where  the method of diagonalization was first  uh  conceived of uh back in the late 19th  century by a mathematician called georg  cantor  and cantor was considering the problem  of how do you compare  the relative sizes of infinite sets  you know for finite sets um  the  uh  the problem of comparing somebody said  that the cantor went crazy that is that  is true um  and maybe i i i don't know why he went  crazy but  um he um he did go uh he had some mental  problems unfortunately um  and so  so how do we compare the sizes of sets  in general if they're finite sets we can  just count them up  we can say oh this set has  uh 11 elements and the other set has uh  10 elements so the 11 one with 11 is  bigger or if they both have 11 they're  the same size well that's not going to  work for infinite sets because you can't  count them up um  and so he had cantor had the following  idea for comparing the sizes of infinite  sets  um and that was  basically um to see whether you can have  a function  that would map  from one set to the other set with  certain properties  and those properties are um called  traditionally well i mean  in the past have been called the  one-to-one and onto properties for the  function i'll tell you what that means  um but the concept is very simple um so  a one-to-one function is one a function  that's mapping from a to b those are the  two sets whose sizes we're trying to  compare  and  uh the function being one to one just  means that there are no collisions if  you have two different elements of a  they're never going to map onto the same  element of b  so two different elements of a always  map onto two different elements of b  so that's the one-to-one property it's  also called injective um  and um the other property is called onto  or surjective um which is that the range  of f has to be all of b so you're not  allowed to miss any elements b you have  to hit everything  um  and when you have the both of those  properties it the function is called the  one-to-one correspondence or a bijection  also  okay um  now uh another way of looking at i don't  want to make this overly more  complicated than it needs to be it just  simply means that two sets are  considered to be the same size if we can  match up the elements with one set with  elements of the other set you just pair  them up  you know for example well  if you look have finite sets um that  into that idea that informal idea just  works exactly as you would expect you  know for example if we have two sets  here's a set of puppies here's a set of  kittens  um  now we want to show that those two sets  have the same size we could count them  up as i mentioned and see that there are  six elements in both  but it's counting up does not work for  infinite sets  so  um we can just match up the elements of  the the puppies with the kittens  and then we know they're we have the  same number of puppies as kittens  okay now that has the advantage of it  making sense when you have infinite sets  so we're just going to extend that idea  and apply it to infinite sets too and  then we'll have a notion of what it  means for two infinite sets to have the  same size  and you might wonder what do you get you  know are all infinite sets of the same  size when you use this notion or or not  what happens um well some strange things  do happen but there actually are quite  some interesting um  uh structure there that uh that emerges  so if um  so anyway  i don't want to rush on uh questions on  any of this if you want to uh  quick question this hopefully was not  too hard but i want to make sure  everybody's together with me on it so we  can pop in uh  i'll give a few seconds for a chat if  you have any uh questions  um  the rain the range of the set is all of  the elements that you hit as you look at  the different possible elements of a so  all of the things that f hits the  standard notion of range of a function  um  so the range of s f has to be equal to b  you have to hit everything  um right uh  can you think of a one-to-one  correspondent says relabeling yeah i'm  not sure that's helpful but yes you can  think of as a re-labeling of the  elements in a sense but uh yeah  i just think of it as a matching up  um all right so let's move on um  so uh  coming out of this notion of sets of  being of the same size there was this  notion of countable sets as we'll see in  a minute um  so  let's do an example  let's take the set of natural numbers  you know one two three four dot dot dot  and the set of integers  which includes the natural numbers but  but also the negative numbers in zero um  so the  natural numbers are typically referred  to as n the  integers are typically referred to as z  and  how do we  what do we think of the relative sizes  of um  n and z  well n is a subset of z it's a proper  subset of c so you might at first glance  think that z is larger and they're not  really going to be of the same size  but it actually it turns out that  there's a very simple way  you know the arithmetic and the  properties of infinite sensor can be a  little bit surprising and there is a way  of matching up all of the elements of z  with elements their own elements of n um  and so you can show that as uh  following that definition that these two  sets are in fact of the same size so  let's just quickly go that goes make  sure you see that  um  so here is n  here is z i'm going to write down a  table which shows how they match up and  here's the function f of n that i'm  going to be describing that's the um the  one-to-one correspondence  and so here are the natural numbers  dot one through seven dot dot dot and  here are the elements of z that i'm  gonna be matching up this is how the  function is working so one i'm gonna you  know f of one is gonna be zero f of two  is gonna be minus one f of three is  gonna be one  um and i'm just giving you a way to  match up each of the natural numbers  with with integers  so that every single integer has its own  natural number and vice versa um  [Music]  so four goes to minus two five goes to  two six goes to minus three seven goes  to three and then minus four and then  four minus five then five and so on  you're clearly going to cover all of the  integers in this way and each of the  natural numbers is going to have its own  integer and there's never going to be  any collisions there's never going to be  two natural numbers assigned to the same  integer so this is meets the uh the  conditions of a one-to-one  correspondence and shows that the  natural numbers and the um and the  integers have the same size  uh following this definition um  okay let's do one that's slightly  more  complicated um and perhaps slightly more  surprising  which is that if you consider all of the  rational numbers  and um then they have the same that is a  collection even though the rational  numbers seem to be much richer and  more numerous than the integers from  this perspective they have the same size  and for the simplicity of my uh  my presentation i'm going to consider  only the positive rational numbers which  i'm going to write as q plus  so those are all of the positive  rational numbers that can be expressed  as a ratio of two natural numbers  and um i'm going to show that there is a  one-to-one correspondence between the  rations between these positive rational  numbers and and the natural numbers  okay so  um  here i'm going to again make a table  just as i did up uh up above um  so comparing the natural numbers and the  positive rational numbers  and  to do that i'm going to write down over  here on the side just to help you see  how i'm getting this table  a table a separate table that can that  has all of the rational number positive  rational numbers appearing you know in  kind of a nicely organized way um here  are all the rational numbers here that  have one as a numerator that have two as  a numerator and and so on and going  through across the columns the different  denominators  um so it's the the numbers inside here  represent all of the different rational  numbers and so whatever rational number  you have  m over n  um  that's going to appear down the nth row  in the nth column  that number is going to appear so  they're all going to show up  and i'm going to use this  table here to fill out this function  um  so uh  here are all the natural numbers and the  way i'm going to assign  the  rational numbers to appear over here is  i'm just going to work my way in from  the corner  and i'm going to do that by kind of  doing layers so first i'll take the one  in this  this number here in this corner then  i'll do these three that surround it and  then these guys that's around that and  these guys sort of in shells going  around the previous ones that i've  already covered  okay so  let me illustrate that  so here's one over one my first rational  number that i'm going to enter then to  the table  appearing right over there so next i'm  going to go 2 over 1  that's going to appear in the table over  there  now we have 2 over 2. now that's  actually a little bit uh problematic  because 2 over 2 has already been done  um and if we put that in  uh because 2 over 2 equals 1 over 1  they're both the equal to the rational  number one  so if we put two over two in this table  over here then we would no longer have  the one-to-one property because both one  and three would be mapping to the same  point um so we're just going to simply  skip over two over two  um  i'll show that as kind of graying it out  so we're not gonna  we're not gonna add that one onto the  table onto my function  um  so but so we'll skip over that we'll go  to one over two which is um has not been  seen before  and then we're just going to continue  doing the same thing now going to this  next shell out here  three over one  three over two  three over three  same thing i'm going to skip over that  one  2 over 3  1 over 3. i hope you're getting the idea  um so i'm not going to fill this  together i ran out of room to  put fill out this table some more but  just to look at how the process is going  to continue here i would get 4 over 1.  now 4 over 2  again is the number we've previously  seen because that's the that's the  rational number 2. we saw that up here  when we had 2 over 1 so we're going to  have to skip that one  4 over 3 four over four  that was going to skip  three or four and so on  okay so by uh following this procedure  i'm going to be able to define this  function now this function is not  particularly nice in terms of having a  an elegant closed form but it is a  the total legitimate function in the  sense of being a mapping from  natural numbers to  the positive rational numbers  and it has the one-to-one correspondence  property  so it pairs up each of the  natural numbers with each of the um  uh positive rational numbers um they  each get their own  mate in a sense and so that shows that  the rational numbers despite the fact  that they're dense and they have all  sorts of very sort of more much bigger  seaming they really and from this  perspective of the sizes of the sets  they have the same size as the  natural numbers do and so with that it  suggested  the following definition that a set is  countable  if it has the same size as the natural  numbers or it's finite  from this perspective we're going to be  focusing on infinite sets uh but yeah  countable or countably infinite  sometimes people say uh if it has the  same size as the natural numbers or  otherwise you have to include the finite  sets as well and countable means you can  just sort of go through the the sets the  the elements of the set kind of  as a list  so you can count them the first one the  second one the third one the fourth one  dot dot dot and once you can do that and  that counting is going to hit everything  then you know um you can match them you  can pair them up with the natural  numbers and so therefore you have a  countable set okay um  [Music]  so as we've shown  both z  the integers and the positive rational  numbers are countable sets  okay now  you might think that well since we're  allowing ourselves to do something as  arbitrary in a way as this kind of a  function  to match up the natural numbers with  whatever set you're trying to um  to measure  that every set is going to be countable  if you think about it that way because  it seems like you're allowing two too  too many possibilities and that all the  infinite sets are going to end up being  the same size as the natural numbers  well that isn't in fact is not true  um  and i don't know i i i  can't or as the one who discovered that  um i don't know if that was surprising  or not um but uh it is kind of uh  interesting i think that there are  different sizes of infinities um  and uh so uh we're gonna now take a look  and see uh that but i want to again um  i want to uh stop and make sure we're  all together can we always find a closed  formula for f somebody's asking me um  i don't know  for this particular f uh  you probably could but it would probably  be very messy um  um but in general that's not a  requirement  having a closed form for the for the  mapping function any function is allowed  as long as it's a one-to-one  correspondence  um  are we all together on this is this are  we comfortable with the notion of  some infinite sets  having the same size as the natural  numbers and therefore we're going to  call them countable sets and we're going  to show some other sets are going to  have um more elements they're going to  be uncountable they're going to be  beyond  strictly speaking strictly larger sets  in the sense that we won't be able to  put them into a one-to-one  correspondence with the integers um so  then the smallest infinity yes n is the  smallest um  smallest one so  any infinity is going to have um  you know you can always i don't think  you even need it you need a special  you know you can always  and whenever you have an  internet collection you can always find  a subset which is going to be  a countable subset uh so it's uh  and is going to be the smallest of the  infinities but there are bigger ones  all right why don't we move on  okay so um  the example of a set that we will show  is not countable an uncountable set as  we call it um is the  uh set of real numbers which you i  you know  we all know what these are i hope uh  these are all of the numbers that you  can express by possibly infinite decimal  representations like pi or e square root  of two  um or on any of the other familiar ones  you know um rational numbers are also  members of uh  are also count as real numbers and  integers too um  and so  uh but you know there are these  additional numbers that you can get by  uh  decimal expansions which may not be  rational  um  and that collection even though in some  ways it looks somewhat similar to the  rational numbers um the real numbers i  hope i said that right the real numbers  um uh the the uh which is the set i'm  considering here the ones with the  infinite decimal expansions they  actually are much larger  um  so  um  the theorem is and this was discovered  by kantor um that uh r is an uncountable  set  and the reason why i'm introducing this  is um besides that i think it's  interesting um  uh  and has some some relation uh to uh the  kinds of things we're doing but it's  really for the purposes right now is to  introduce this method called  diagonalization  um  okay uh that's we're gonna use later on  again but this is the first time it  appeared  so we're going to  use a proof by contradiction in order to  show that r the collection of real  numbers  is uncountable and we'll assume for  contradiction that r is countable  okay  um  so  if we assume that r is countable it  means we have by definition a one to one  correspondence from the natural numbers  to the real numbers  okay so we can match up  all of the natural numbers with  uh the real numbers in a one-to-one and  onto fashion so we can pair up the  natural numbers with the real numbers  and we will cover all of the real  numbers by doing that and we can make a  table  just like i did before  here it is  um  and you can fill this out with all of  the real numbers  and um  that was what the assumption means and  i'm going to show you that that's  impossible something is going to go  terribly wrong if you do that  um now uh  you might disagree you might be  surprised you might think well  uh professor sipser is wrong um you know  that i'm gonna work on this overnight  and forget the rest of my classes and  i'm gonna come up with a list of  uh all the real numbers i'm gonna fill  them out here and show that that's  impossible um so let's say  hypothetically just for my example's  sake um here is the list that you came  up with um  so you know you had to match up  something with the one let's say e had  to that was a special case so you're  gonna stick that with one and then pi  came out to be the number that you you  connected up with uh two you wanna see  what i'm doing here i'm making a list  i'm trying to make my one my  correspondence my matching up between  the natural numbers and my real numbers  that i'm hypothesizing to exist for a  contradiction  so three  i i don't know three is gets connected  to zero i'm making this up obviously uh  not on the spot i wrote the slide you  know uh yesterday but uh here's a square  root of two showing up for whatever  reason here is one seventh  here is some other number which i'll be  interested if you recognize that one  that's a that's a subtle one um  this is one point two three four one  point yeah some some familiar looking  sequence here and whatever it is  whatever it is this is what you came up  with you claim that this is to work as  uh very good you somebody got it  it's i to the eighth power but let's not  get hung up on that please um  i to the either power oddly enough can  be seen as a real number under you know  if you define the uh  imaginary exponentiation  uh which is weird but anyway  let's uh let's not get too distracted um  so here's my list of numbers my real  numbers that i've matched up in my table  here with the natural numbers  now something's go i claim something  goes wrong what goes wrong i'm going to  show you that you actually  uh did not  do as you claimed  that there's actually um at least one  number that's missing from this list and  i'll exhibit that number i'm going to  show you what that number is i'm going  to explicitly come up with a number and  show you that there's that number it's  missing from the list um so here  it's going to be a number x  x is the x is the one that's missing  so how am i going to get x  so x well i'm going to start it off with  zero point and then i'm going to fill  out the rest of the places and how am i  going to get those places i'm going to  look at the table here  so i want to look at to get my first  digit after the decimal point of x  i'm going to look at the first digit  after the decimal point of the very  first number  so i take the first number look at the  first digit after the decimal point  and which happens to be a 7  and the number i'm going to put in for x  is not going to be 7 it's going to be  anything except 7.  let's say  8. um  for my next digit of x  i'm going to look at  so my second digit of x i'm going to  after the decimal everything's going to  be after the decimal point now uh so i'm  not going to keep saying that i'm going  to look at the second digit of the  second number uh which is a four  uh after the decimal point um  uh  there it is  and for the second digit of x i'm going  to use something which is  anything besides four five  i have some flexibility here um so i  could have used six i could have used  seven  i'm going for those of you who have seen  this before who are gonna nitpick on me  i'm gonna stay away from nine and zero  just because there are some little um  edge cases that arise there which i  don't want to get into because i don't  think it's interesting for this argument  um but since i have some flexibility i'm  going to avoid zeros and nines probably  just nine is all i really need and then  um  the argument is just going to work fine  okay  so uh the next digit is a zero  uh for the third digit of the third  number is a zero the third digit of x is  going to be anything except for zero be  a one  then i have a two here  anything except a two  six  uh then five anything except a five a  one a nine anything except a nine an  eight  and so on there's an eight  there's a two and dot dot dot i'm just  gonna keep doing that  and i'm gonna say  you missed that number whatever it is  but that number it's a that's a number  after i'm all done it's going to be the  decimal representation of something  and that number uh i claim  is absent from the table  and you might say well  you know it's really there  um it's just on the  um  23rd row  you just didn't get to it on your slide  but it's there well i'm going to say i  know it's not in the 23rd row because it  differs from the number in the 23rd row  at the 23rd digit  because i constructed it that way  this number is designed  explicitly to be different from each of  the numbers that's on the list  okay so it can't be on the list because  it's been constructed to be different  from each of them in at least one place  so it's i think this is a beautiful  argument and it shows that  uh no matter how you try to come up with  a one-to-one correspondence you're going  to fail you know you might say oh you  know like  you know just one number you know it did  so much hard work and missing just one  number can i get partial credit  you know and put this one on the list  now i fix it no obviously there are many  many numbers that are missing if you put  this one on the list i'm going to  construct another number that was  missing  so  um this is uh  you know  there's just not no possibility of  fixing this and in fact you know the um  the real numbers are  are uncountable cannot be matched up  with the natural numbers and there's  nothing  it can't even come it doesn't even come  close um  so um  here's summary what i just said  um f is not a one-to-one correspondence  no matter what you try to do you can't  come up with a one-to-one correspondence  so that's the contradiction  okay so that proves that  r is uncountable  okay and that's why by the way we call  this a diagonalization because we're  going down this diagonal here that's  where the term that's where the name has  come from  okay um  so i i'm happy to  okay that's it uh  somebody's asking me  i'm actually i have a  um  is it here i can't remember it's here i  have a uh check-in coming about this and  somebody is kind of um anticipating that  by asking uh the the actual rather  famous question about there being a  possible infinity in between  the natural numbers and the real numbers  we know the real numbers now are bigger  than the natural numbers but is there  something that's in between i mean this  is a very very famous problem um  uh which i'll talk about you know when  we get to our check-in which is coming  up  um  well somebody is objecting just the way  i've defined x using this procedure that  really really can't in a sense state  you know but it x is a number x is the  result of  what what this procedure is it's you  know following this procedure we're  converging on some particular value and  so that is the value um if you want you  know we can make a more precise way of  determining i mean i so i we don't have  the flexibility of choosing the way i  did in my example we can make a precise  procedure for coming up with these  digits but  i don't think there's anybody thinks  there's anything  that's um  there's any shortcoming in this argument  in terms of the way we're defining x  it's i i think it's worth understanding  this  because it's really going to set the  groundwork for our proof that atm is  undecidable which is a little i think  perhaps slightly more abstract in a way  um in the way it sort of comes across  i'm going to try to can make connect the  two  but uh i think it's helpful to  understand at least this argument  because this argument is kind of  diagonalization in its kind of most  raw form  all right i think we're good um so let  why don't we continue then um  so there are a number of corollaries  that follow from the statement that the  real numbers is uncountable um  uh  first of all if you let script l be the  collection of all languages if you want  to consider over some particular  alphabet that's fine but that's not  going to be really uh  you know important for this uh  point that i'm trying going to make so  uh l  uh script l is the collection of all  languages um so every subset  of sigma star  every subset of sigma star is a language  um so look at all those possible subsets  um so that includes you know 0 to the k  1 to the k plus every other language you  can ever think of and more all possible  languages  um so that  the collection of all languages is  uncountable  there's uncountably many different  languages out there  i don't want to belabor this point you  can just take this if you don't quite  follow the the quick argument i'm going  to make here but um  uh you can make a correspondence  one-to-one correspondence from all  languages to the reals  so that each language gets its own real  number  and the way i'm going to think about  that let's put the real numbers into  binary form  and if you imagine here being sigma star  all of the possible strings of sigma  star  you know written out in their standard  order  um and now if you have a language here a  it's just some arbitrary language so  that's going to have some of the strings  of um of sigma star appearing like zero  is appearing but one is not appearing  zero zero is appearing in zero one but  not these three  um and i'm gonna associate to a  my language  some real number in binary by putting in  a zero in the decimal representation or  the binary representation i should say  um  for that  string  if it's not there and a one if it is  there  um and so a real number because there's  infinite many infinitely many yes no  choices  in the binary representation can  represent a language because of each of  the yes no choices of a string being  present or not i'm going to put a one  for when the string is present the zero  when it's not present so each  uh language has its own real number and  each real number is going to be  associated to its own uh language here  i'm restricting myself to real numbers  between zero and 1  that's not going to be an essential  point so let's not get hung up on that  so  [Music]  the  the fact that  the  the languages can be  uh  put into one-to-one correspondence with  the real numbers  um  shows that the collection of all  languages is also uncountable  now another  observation here another point worth  noting is that if you look at sigma star  itself  the strings  uh all possible strings that's a  countable set  the collection of all possible languages  is uncountable but the collection of all  possible finite strings  is countable because i can just list  them  here is my list of all possible strings  which you can put into a table if you  like to think of it matching up with the  natural numbers in that way  now i'm get i'm trying to make a point  here which is that  if you take am which is all possible  turing machines script m is all possible  turing machines the collection of all  possible turing machines is countable  there are only countably many different  turing machines  and you can argue that in all sorts of  messy different ways but i think the  most simple way to see that  is to think about each turing machine as  having a description  which is a string  so the collection of all descriptions of  turing machines is just a subset of  sigma star which we already know is  countable  and the subset of any countable set is  going to be countable  so  anyway  i think it's worth  remembering  that  the collection of all turing machines is  countable  um whereas the collection of languages  is uncountable and that tells you right  there  that some language is not decided  because there are more languages than  touring machines  we have uncountably many language only  countably many turing machines so that's  fewer turing machines than languages  there's no way to map all the languages  onto turing machines so there's going to  always be some languages that got  unmapped  um and so in particular there are going  to be some languages which are  undecidable there are going to be some  languages which are not touring  recognizable  and anything based on some automata kind  of um  definite definition process is going to  be some languages that you're not going  to be not going to be defining  um  okay now what this corollary shows you  that there is some language out there  which is not decidable what we're going  to show next is that there is a specific  language atm which is not decidable  okay and but first i think we have a  check-in coming up  and  let me give you a little bit of  background here because this is relevant  to this question that i got  about intermediate sized sets so  the question of whether there is a set  of size between the natural numbers and  the real knit numbers  strictly in between so bigger than the  natural numbers not the same size as the  natural numbers but not the same size as  the real numbers either  um but in between uh in size  um  that was hilbert's question number one  out of his list of 23 that i talked  about a few lectures back  it's interesting that he put it as  number one in that very privileged  special place  because i know hilbert was very  he felt that the understanding infinity  was a really central issue in  mathematics and that if we can't answer  a question like this we don't really  understand infinity um  uh you want to understand what kind of  sizes of infinities are there um we know  there's the real numbers bigger than the  than the natural numbers is there  something in between so fundamental  really um  but uh it was shown uh during the course  of the 20th century really in two  separate steps one in the 1930s by  girdle one in the early 1970s by cohen  that we can't answer this question by  using the standard axioms of mathematics  you know it's  the the answer can go either way  and it's both of them are consistent  with the axis of mathematics so you're  never going to be able to prove  that there is a set whose size is in  between  or that you or that there is no such set  it's just impossible to prove either  direct either way  using the standard axiom in mathematics  which actually is kind of remarkable um  and so my question for you is and this  is really a philosophical question not  one that um is directly and you need to  know about material in the course just i  think it's just a matter of your own  interest i hope you find it interesting  if you don't you pick a wren you can  just answer it randomly um  but um  what's going on here that we can't  answer that question about whether there  is a set of intermediate sides is it  because our axioms for mathematics are  inadequate  or  maybe there is no such thing as a  mathematical reality you can talk about  you know you know what's what's real  here what what what's the reality either  there is a set in between or not  if you imagine all of these things have  their own reality to them well then  there's going to be an answer and then  you would expect well maybe we could  find better axioms which will actually  give us that answer or you can say well  there is no reality  and um  you know it  infinite sets are kind of human  constructs anyway so we can make them  kind of play out any way we like  mathematicians argue about that to this  day um  and um it is as i say really it's a  philosophical question but just out of  curiosity let's see how you guys end up  uh deciding on that one um so here's the  poll  five seconds to go please vote  and uh we're going to end the polling  one two three now  all right here we go  so there's no right answer  um  i think if most mathematicians were  to um  i think the instinct of most logicians  especially i'm not sure our general  mathematicians really even care about  this question but logicians um  would probably have an instinct that  probably there are sets in between  there's no reason that there shouldn't  be  um  you know it seems kind of strange that  there should be this sort of jump uh  from the  natural numbers to the real numbers and  why nothing in between um  but um  it's uh  i don't think that question is really  settled  so  all right let's continue on i think we  are  um okay so we're gonna  um  a coffee break is coming in case you're  wondering so this is on my last slide  before then but this is an important  slide so please uh hold hold out  um  so here is our  uh promised theorem of the day  i'm going to show that atm is not  decidable the acceptance problem for  turing machines  and it's all going to be contained on  this one slide we're going to give a  proof by contradiction using  diagonalization  and we're going to assume some turing  machine h decides atm  and we're going to get a contradiction  so let's first of all make sure we  understand what h is doing  so h gets an input a turing machine and  an  input and h is going to be a decider so  it always halts  with an accept or a reject  it's supposed to accept if m accepts w  and reject if it doesn't so in other  words it's going to reject if m rejects  w either by whole by halting or by  looping  that's the job of h  and we're assuming we can do that  but we will see a contradiction occur  so the way we're going to do that  is is really kind of just one step here  in a way and we're going to use h to  construct another turing machine d  h is going to be a subroutine to d  we've already seen us doing that in the  past  d is going to do something a little  strange  just to just to warn you um  these input is just a turing machine no  in no w  and  what  d is going to do  using its subroutine h  is going to simulate h  on input  m comma the description of m now what is  that  well the description of m is just some  string  so what h is trying what it's asking h  uh to tell to answer is does m  accept  the string representing m's own  description  it's as if we're feeding m into itself  which seems like a totally twisted thing  to do  um  you might say  uh  you know  why would you ever feed a program into  itself  somebody's written cannibalism here  yeah kind of uh i said it's it's worse  because it's  not eating somebody else it's eating  himself  okay but  um  i claim  that we actually there are actual cases  in practice  where we do this  we feed programs into themselves  and uh the example that i know of where  this is done  is when you're making a compiler  you might want to make a compiler and  then written in the same language that  it's compiling and then you feed the  compiler into itself  they may say why even bother because  it's already obviously if once it's  running you don't need to  compile it again um but actually you  know an example where this was really  used  was when there was an optimizing  compiler i think for c uh written on  early unix machines  and the optimizing compiler for c was  written in c  so you would feed the optimizing  compiler  into the regular compiler first of all  now you had the um  compiler running  but it was unoptimized  so but now that it's the optimizing  compiler is running  you can feed the optimizing compiler  into that which is itself now you have  an optimized optimizing compiler  so it really makes  some there is a at least one case where  this has actually been done uh in  practice  um not that we really care this is a  theory class but just for fun to observe  that  so here h is trying to say well does n a  m end up accepting when it's fed  the description of itself  you know at least mathematically  speaking that's a reasonable uh thing to  ask  and then what  d is going to do when it gets the answer  back from h  h as a decider don't forget  is d is going to do the opposite  whatever h does it's going to accept if  h rejects and rejective h accepts  um so let's in summary let's pull this  together some  you know it's easy to understand in the  end what is d doing  d is going to accept d is also going to  be decided by the way so d d is always  going to either accept or reject  just the opposite of what h tells it to  do so d is going to accept  m  exactly when m doesn't accept m because  you know when m doesn't accept m  h is going to reject  um and so then d is going to accept so d  accepts m if and only if m doesn't  accept that that's exactly the condition  in which d accepts it  i think it's important to just step back  and make sure you understand this line  because we have only one line left  to get our contradiction  right are we together d accepts m if and  only if m doesn't accept m that's just  by the that way we've defined setup d  now  what we're going to do is feed in  instead of m to d and not some arbitrary  fee  we're going to use feed in d into d  and that is going to be our  contradiction because d is now going to  accept d if and only if d doesn't accept  e and that's certainly impossible  okay  that's our contradiction which proves  that h cannot exist and therefore atm is  undecidable  okay so we're done  except for the one point which is that  um  why is this a  diagonalization  and i think you can get that from the  following picture  if you imagine here writing down all  possible time i'm making i'm going to  make a table here here is a list of all  turing machines  okay uh including d which is a machine  which i  built  under the assumption that h exists so d  appears here somewhere but here are the  all the other turing machines and here  are all these descriptions of the turing  machines along the uh labeling all of  the columns  okay so these are the rows labeled these  are the column labels and inside i'm  going to tell you  uh the answer for whether a given  machine  accepts a given input  so for example m1 accepts its own  description but rejects the description  of m2 but accepts the description of m3  i don't know you know i'm obviously  making this up i don't know what m1 is  but just hypothetically that's what the  machine m1 does  um so i'm just filling out this table  and you know this is  d  uh h could get the answer to any of the  elements in this table because it can  test whether m4  um accepts the description of m3 so it  could h could fill out this table  so maybe m2 is a machine that always  rejects it's a very unfriendly rejecting  machine  m3 is a very friendly machine it accepts  all inputs and for its reject sum and  accepts other dot dot dot  now i want to look and see what does d  do  um  now based on the information i've  already given you we can understand what  d does  so for example what does d do when i  feed it the description of m1  what does d do  well we can look over here d accepts m  if and only if m doesn't accept m so d  is going to accept  um  m1 if and only if m1 does not accept m1  well m1 does accept m1  so d  does the opposite d rejects  so okay i'm highlighting here  d rejects because it's going to d is  going to do the opposite of what the  machine does on its own it on input  um so m2 on so d on m2 you have to look  what m2 does on m2 it rejects so d does  the opposite of that it accepts  and similarly  uh  you know all each one of these things  these answer is going to be the opposite  of what the machine does on its own  description  um just by virtue of the definition of  date  okay and so on so far so good  but the problem is what happens when d  is fed itself  because as you can see  you know um we're we're heading for  we're heading for trouble because this  is a diagonal down here  d is just one of the rows that diagonal  is going to  intersect that row at this point  and d is defined to be going to be doing  the opposite of what that element is but  it can't be the opposite of itself  okay and so that's that's the  contradiction  so i think you know where um  uh  i i'm gonna call us give us a little  break here um and then you can also text  me in the meantime we'll be happy to  answer some questions during during that  a little over four minutes to go so  let's see let me see if i can  answer your questions  okay what's so special about atm that  enables us to do this why can't we do  this on adfa for example  um so that's a good question i i i  and  the answer is that um  you know  you know in a sense  you know we can do this on dfa i mean i  i think this is perhaps a bit bit of a  stretch but you know dfas could not  answer adfa i mean we could prove that  in other ways as well you know by uh  because  you know we could use things like the  pumping lima and it's not clear even how  you formulate adf8  but what's important here is that the  um it's really the model talking about  itself  um that really is where the problem  comes up  so if you try to push this argument  through to show that adfa is not  decidable by touring machines you're  gonna fail  um  because you know we're starting off with  a turing machine and um i mean  i think i'm gonna confuse myself if i  try to just repeat it but um you're you  won't get a contradiction because the  turing machine is not a find out  automaton  um  okay um  will this argument get into self loops i  don't see why there was there is some  self-reference perhaps we're going to  talk about that a little later because  we're going to come back and revisit  this argument um  you know in a  in a week or so when we talk about the  recursion theorem which talks about  machines that can refer to themselves  but this is a little bit of a head  getting ahead of ourselves so  uh somebody's commenting on this  reminding them of the barber paradox if  you remember that the  which has some similarity you know the  there's a town in which uh there is a  barber which shaves every man who  doesn't shave themselves  which seems you know he's a very good  barber so there's some people who shave  themselves  and  all the rest the barber shavers uh the  question is does the barber shave  himself because he shaves only those men  who don't shave themselves so you got a  same kind of a contradiction there is a  there is a relationship there  um  so somebody wants to know where did we  use the decidability so we used the  decidability to come up with h  um  you know once we know that atm is  decidable then we have that h function  and then we can build d  um so that's where that's the the the  chain of that's the chain of reasoning  um  so you assume atm is decidable then you  have the decider  and then  called h and then you can build d um  somebody wants to see the previous slide  well  uh what part of this one do you want  uh  so i'll leave that up there why can't we  why can't we apply the proof that all  touring machines are countable to all  languages well because turing machines  have descriptions  languages general languages don't have  descriptions  and so that's uh why okay the candle has  burned to the to the bottom and it's  time to move on um  so now let's look at the  uh acceptance problem for kuwatama  i'll give you a q automaton an input  and i want to know does it accept the  input is that going to be decidable  and you have you have your choices it's  either yes  it is decidable because these are  similar to put down automata and apda is  decidable  or no because yes would con contradicts  results that we know at this point or we  don't have enough information to answer  the question  okay let's put that up  one second  all right  that's it ready going gone  uh so  yes the answer is uh well no  the answer is the indeed the answer is b  um  uh true that uh cubitamina are similar  to push on automata but all these atomic  are kind of similar to each other and  that's not going to be good enough  uh  well the homework has asked you to do is  to show that you can simulate turing  machines with q automata  so if you can answer the question about  whether the queue automata uh will  accept their input that would allow you  to be able to answer questions about  whether turing machines accept their  input and we just proved that's not  possible  so um  uh  it would get it be a contradiction if we  could answer  uh if we could decide a qa  now we have an example of an undecidable  language let's look at an example of an  unrecognizable language  now atm is not going to serve  that purpose because atm  um  [Music]  is  um  recognizable is turning recognizable as  we pointed out by the universal turing  machine  so uh atm is undecidable however how  about an unrecognizable language  for that we will see that the complement  of atm  will serve so the complement of atm  is  neither decidable nor even recognizable  that's not turing recognizable  and that's going to follow from a pretty  basic theorem that connects  recognizability and decidability that i  put up here on the screen  which is that if you have a language  where it and its complement are both  recognizable then the language turnout  turns out to be decidable in fact the  language and its complement are decided  but but being decidable is closed under  complement so that's something you  should be aware of  um  but being uh okay  we'll get to that in a minute but  uh if um  uh  so anyway so we have a language and it's  complement both recognizable how do we  know the language is decidable so first  of all let's take the two turing  machines m1 and m2 that recognizes a and  a complement  and we're going to put those together  to get a decider for a  um  and that's going to work like this  it's going to be called t  so t says on input w what it's going to  do  it's going to feed w into m1 and m2 both  um a is a language by the way yes a is  when i'm telling you when i say it's  touring recognizable you know turing  recognizable only applies to languages  so so yes a um is often this symbol i'm  going to use for languages sometimes for  an automaton but  a is typically going to be a language  so um  [Music]  if uh so  now i'm trying to make t  be a decider for a  from the recognizers for a and a  complement  so i'm gonna  take an input to t  and feed it into both recognizers m1 and  m2  okay i'm going to run them in parallel  what's nice  is that because  um  m2 is a  recognizes the complement of what m1  recognizes  every string is going to be accepted  either by m1 or by m2  because every string is either an a or  an a complement  so if i run m1 and m2 on w until one of  them holds one of them accepts i know  i'm not going to run forever because  eventually one of the other ones have to  accept  so and then i got my answer because if  m1 accepts that i know i'm in the  language but if m2 accepts i know i'm in  the complement of the language no matter  the language so if m1 accepts then t  should accept if m2 accepts then t  should reject  um  now  so that proves that  nice little theorem uh written at the  top in blue  um so i got my decider for a  built out of the recognizers for a and a  complement  now immediately it follows that  the complement of atm is not touring  recognizable  because  we know  that atm itself  is recognizable but it's undecidable  if its complement were also on recognize  if the complement was also recognizable  then atm would be decidable but it isn't  so when something is  undecidable either it or its complement  have to be unrecognizable and in the  case for atm it has to be the compliment  because we already showed that it is  itself is recognizable  um  so that's the proof of that so here is a  little picture of the way the world  looks right now if you have here in the  middle of the decidable languages see  these are all languages here this venn  diagram of languages kind of we showed  earlier you know like the regular the  context free decidable recognizable  here i've got the recognizable and what  i'm calling the co  co code touring recognizable  this is the collection of all  complements  of recognizable languages so atm  bar atm complement is the complement of  a recognizable language this uh  region here is are all the complements  of the recognizable languages or the  so-called  co-turing recognizable languages  complement of  so atm is on this side atm complement is  on that side but if something's in both  by virtue of this theorem here then it's  decidable  okay  last check-in for the day  um from what we've learned so far  um which closure properties can we prove  for the class of  the touring recognizable languages  choose all that apply  well as i say  you don't have to get it right let's  let's not spend too much more time on  this because we'll we'll we'll talk a  little bit about it  um  almost all it's closed under almost all  of them but not all of them  because you know  are we done here i think we're done  five seconds  okay here we go ending polling  i'm not sure what the meaning of  the leading answer is here uh everybody  likes union i guess they're closed under  all of these operations except  complement so  um  but we just proved it's not closing the  confidence i'm a little  you know a little puzzled by why we have  so many votes for closure under  compliment  uh we have here atm  is touring recognizable but atm  complement is not touring recognizable  so right here on the slide  so i'm not trying to make you feel bad  but uh  um i'm trying to  just point out that you  think please um  so  um  now closure under union and intersection  i mean you could kind of get those  answers just by running things in  parallel the way we did the proof here  you just run both machines  and  if they both  give i mean it's a little tricky i  suppose you know if if if either one of  them accept um  then you can accept or if they both  accept you just wait until they both  have accepted otherwise you just keep  running um so the first two are pretty  straightforward um closure under  concatenation is also going to be  similar you just try every possible way  of cutting uh the string up into two  pieces  and run in parallel on and if you ever  find a way  of cutting it up and you run those two  and those two sides in parallel and if  they both um accept  um then uh then you can accept and star  is again very similar so there these are  not too bad um but i admit you know it's  not a whole lot of time to i have to  contend with something uh that you're  just getting uh used to  so let's um  uh  let's talk about the very last topic of  the day which is really going to be  setting ourselves up  for um tuesday's lecture next week um  and that's  how we are going to be showing other  languages are undecidable which is  something that  um i'm going to be expecting you guys to  be able to do um  this is um  the standard procedure for showing  languages are undecidable using what's  called the reducibility method  um  and what that does is it  takes as a starting point a language  that we already know is undecidable  typically atm  or it could be another one that you've  previously shown to be undecidable and  leverages that information to show other  languages are undecided  and um  it's using what's called reducibility  we're going to go into this  more carefully next time  but basically reducibility is a way of  using one problem to solve another  problem  and so we're going to show for example  uh let's take a look at the problem  called the holding the halting problem  which is like the famous problem for  turing machines um  uh you just want to know whether it  holds not necessarily whether it accepts  so it's very similar but not exactly the  same  and we're going to show that  this halting problem is similarly  undecidable now we could go back and do  the whole diagonalization but that seems  like  well that's more work than necessary now  that we already know atm is undecidable  because we're going to show that we can  reduce the atm  problem to the hold holding problem um  and we'll explain what that means again  uh later but um the idea is and as as  we'll show in an illustration uh shortly  that  by proving by contradiction um  if the whole thing if halt tm  were decidable then atm would be  decidable  and we know atm is not decidable and so  um  that's our contradiction  now  uh  the way we're going to show that if  whole team is decidable than atm is  decidable  is use a decider for whole tm to decide  atm with a suitable  um  you know uh  uh  modification  so basically we're gonna turn  and hold tm decider into an atm decider  and that's  how we're going to reduce the problem of  solving atm to the problem of solving  halt tm  let's just do an example like you know  if you've seen it before obviously this  is not going to be hard but for the many  of you who have not seen it before i it  i'm partly doing it this time just so we  can do it again next time and maybe  it'll sink in by virtue of repetition  so  um  so again so as i just said we're going  to assume the whole tm problem is  decidable and use that to show that atm  is decidable which we know is false we  showed it just earlier that it's not  so assume we have a decider for whole  team we'll call it r  and we're going to construct from our  decider for atm we'll call s  okay so we're again typical proof by  contradiction we're assuming the  opposite of what we're trying to prove  and then we're going to get something  crazy  okay so here my job now is i'm assuming  i have r which is a whole tm decider so  now i'm assuming i know how to  decide  if a turing machine and an input  eventually halts  not necessarily except just whether it  holds  you know it's conceivable you know you  have to bear with me here it's  conceivable that you could find a way to  test whether  you know turing machines halt on their  input even though we now know that  testing whether they accept their input  is not decidable  so you have to kind of be open-minded to  the possibility that we can  that the whole problem is decidable and  we're going to show that that's can't be  so we're going to show that  if we could decide the whole thing  problem then we can use that to decide  the uh the acceptance problem  okay so how do we how do we going to do  that so imagine now we can solve the  halting problem  so to solve the atm  which is what my job is  to do  so s is supposed to solve atm  i'm constructing two  machine as the site atm  i'm going to use first i'm given an mnw  i'm going to feed it into r since that's  really all i got  see if r  tells me  what happens  does m on w at least hold  well if r says no it doesn't hold  well then then i'm actually done  because if it m doesn't even hold on w  then it couldn't be accepting w so at  that point i know that m doesn't accept  w and i can reject right  off  so our you can see how it could  potentially be helpful but it's going to  be helpful in either way because if r if  r says m  does hold  well then i'm also good  because i don't know the answer yet but  what i do know is i can now simulate m  on w  until it holds because r has told me it  holds so i don't have to worry about  getting into a loop  um  uh so s can be confident in being a  decider for whatever it's doing um  because i'm running uh now m on w with a  guarantee that it holds  um  and now that going to tell me now  eventually the simulation of m w is  going to end up at an acceptor reject  and that's going to be the answer i need  so if m is accepted then accept and as m  is rejected then reject  and that's how s solves the atm using r  which which solves whole tia  but s can't exist  and so therefore r can't exist and  therefore whole tm can't be decidable  okay  so that quickly  um  okay  i'm not sure which diagram you wanted me  to show but anyway maybe we can do that  we're basically at the end of the hour  or end of that 90 minutes so let's do a  quick review and if you stick around i'm  happy to go back and look at any of the  other slides uh that you might have  missed something on  okay so just to recap we showed that  uh the natural numbers of the real  numbers are not the same size using that  definition of one-to-one correspondence  to introduce the diagonalization method  we use the diagonalization method to  show that atm is undecidable  we also showed that little theorem that  if the language and its complement are  recognizable then the language is  decidable  and from that we conclude that atm  complement is not recognizable  and then we showed at least by virtue of  an introduction to the method the  reducibility method to show that whole  tm is undecided  okay and that's that that was today's  lecture and we're and we're uh  at the end of the hour so why don't i um  you know we are finished uh you can uh  log out um and if you want i will stick  around  okay  okay this is kind of a good question  here  [Music]  so i'm getting a question about the  atm complement  which is uh you know since we have a  a recognizer for atm  uh if i'm doing justice to this uh  question uh we have a co we have a  recognizer for atm so why can't we just  invert the answer  you know  flip flip the answer around and now we  have a recognizer for  the complement of atm atm complement  so why doesn't that work  well the reason that doesn't work  is because  the recognizer for atm  might be rejecting some things by  looping  and now if you just flip  the accepting and rejecting  um  when it hits one of those uh holding  states it's going to give the reverse  answer  but the uh when it uh  rejects by looping it'll continue to  reject by looping so you won't get the  complementary language coming out  so you know if we want you know if we  would be helpful i can go back  to that uh slide here  um  which proves that atm complement is  unrecognizable  because  maybe we should start with the bottom  we know that atm  is recognizable and undecidable  right we already proved those two facts  atm is recognizable  from the um universal turing machine  and it's undecidable by the  diagonalization argument  those two things together  tell us that the complement has to be  unrecognizable  because  if a language and its complement are  both recognizable and we already know  the language itself is recognizable  so now if the complement is also  recognizable the language is going to be  decidable by the upper theorem  so it must be the case that either the  language itself is unrecognizable or its  complement is unrecognizable  we know the language is recognizable  that's what the universal turing machine  told us so the only thing left is for  the complement to be unrecognizable  you should review that if you didn't get  it um because  this is a kind of  you know  kind of reasoning we  you know we're going to be building on  things like that so i think it's good  good to make sure you understand  okay um  okay the diagram on the right so this is  just a venn diagram here  kind of threw this in at the last minute  here i was worried about it being  confusing  you know that part is um  you know so you know i'm trying to show  that the three classes that we've  already talked about  the languages which are decidable the  languages which are touring recognizable  and the languages whose compliments are  going recognizable those are three  separate classes of languages  and  those come up here in those three  regions  these are the decidable ones  here are the recognizable ones  and here are the ones whose compliments  are recognizable  now if a language  is in both  recognizable and its complement is  recognizable so it's in both of these  bigger regions here  then this theorem tells you it's  decidable  so that's why  the intersection of these two regions is  marked as being decidable because that  means you're in both  okay  but we know that atm is sitting out here  as recognizable but not decidable so atm  is in the recognizable side but it's not  on the complement of recognizable atm  itself um  the complement of atm is the complement  of a recognizable but itself is not  recognizable um  and uh  not decidable so you get this side of  nice  you know  [Music]  i hope it's you think it's nice but it's  a sort of uh trying to summarize things  in this in this field diagram  so i think i'm going to then uh  sign off  and um  i'll see you all on  tuesday and have a good weekend bye-bye

2
00:00:28,070 --> 00:00:28,080
okay why don't i get started um  so  okay what would what have we been doing  um so last time we considered a bunch of  uh procedures for testing properties of  various automata and grammars  the acceptance problem for dfas  for anaphase  the acceptance problem which is really  the generation problem for context-free  grammars  and emptiness problems for dfas and and  and context-free grammars  and also um  we looked we we showed that atm is  turning recognizable like there's a  question here in the chat already about  that yes we did show that that was the  universal turing machine that we  presented at the end that's what shows  that atm is turning recognizable  um  we mentioned that uh it's not atm is not  decidable uh which we promised we will  prove today and we will do so okay so  that is the plan  um proving atm is undecidable  and we'll introduce the method for doing  that called the diagonalization method  i will also show the complement of atm  is  uh turing on rec unrecognizable even  though atm itself is recognizable the  complement is not  and  then we will introduce another method  called the reducibility method for  showing other problems are not decidable  and give a one example of another  problem which is not decidable assuming  we have time to get to it if not we will  uh  uh delay that part until uh next  tuesday's lecture  all right acceptance problem for uh  touring machines uh so just um  as i mentioned we showed that atm um  which is the language of turing machines  and inputs where the machine accepts the  input  um  we showed that was recognizable we  claimed it was decidable today we're  going to prove it's not decidable  all right now the method  uh that  uh we're going to use um which is really  the only method out there um for proving  uh um  some pro you know a problem was  undecidable is the decoder  diagonalization method i mean ultimately  we're going to show the reducibility  method as well but it really depends on  having already shown some other problem  undecidable  via  the diagonalization method so ultimately  everything hinges on the diagonalization  method which is really all we have um  and uh so  to  uh introduce the diagonalization method  i'm going to  make a bit of a  digression into a  uh branch of mathematics called set  theory or  it's part of mathematical logic where  the method of diagonalization was first  uh  conceived of uh back in the late 19th  century by a mathematician called georg  cantor  and cantor was considering the problem  of how do you compare  the relative sizes of infinite sets  you know for finite sets um  the  uh  the problem of comparing somebody said  that the cantor went crazy that is that  is true um  and maybe i i i don't know why he went  crazy but  um he um he did go uh he had some mental  problems unfortunately um  and so  so how do we compare the sizes of sets  in general if they're finite sets we can  just count them up  we can say oh this set has  uh 11 elements and the other set has uh  10 elements so the 11 one with 11 is  bigger or if they both have 11 they're  the same size well that's not going to  work for infinite sets because you can't  count them up um  and so he had cantor had the following  idea for comparing the sizes of infinite  sets  um and that was  basically um to see whether you can have  a function  that would map  from one set to the other set with  certain properties  and those properties are um called  traditionally well i mean  in the past have been called the  one-to-one and onto properties for the  function i'll tell you what that means  um but the concept is very simple um so  a one-to-one function is one a function  that's mapping from a to b those are the  two sets whose sizes we're trying to  compare  and  uh the function being one to one just  means that there are no collisions if  you have two different elements of a  they're never going to map onto the same  element of b  so two different elements of a always  map onto two different elements of b  so that's the one-to-one property it's  also called injective um  and um the other property is called onto  or surjective um which is that the range  of f has to be all of b so you're not  allowed to miss any elements b you have  to hit everything  um  and when you have the both of those  properties it the function is called the  one-to-one correspondence or a bijection  also  okay um  now uh another way of looking at i don't  want to make this overly more  complicated than it needs to be it just  simply means that two sets are  considered to be the same size if we can  match up the elements with one set with  elements of the other set you just pair  them up  you know for example well  if you look have finite sets um that  into that idea that informal idea just  works exactly as you would expect you  know for example if we have two sets  here's a set of puppies here's a set of  kittens  um  now we want to show that those two sets  have the same size we could count them  up as i mentioned and see that there are  six elements in both  but it's counting up does not work for  infinite sets  so  um we can just match up the elements of  the the puppies with the kittens  and then we know they're we have the  same number of puppies as kittens  okay now that has the advantage of it  making sense when you have infinite sets  so we're just going to extend that idea  and apply it to infinite sets too and  then we'll have a notion of what it  means for two infinite sets to have the  same size  and you might wonder what do you get you  know are all infinite sets of the same  size when you use this notion or or not  what happens um well some strange things  do happen but there actually are quite  some interesting um  uh structure there that uh that emerges  so if um  so anyway  i don't want to rush on uh questions on  any of this if you want to uh  quick question this hopefully was not  too hard but i want to make sure  everybody's together with me on it so we  can pop in uh  i'll give a few seconds for a chat if  you have any uh questions  um  the rain the range of the set is all of  the elements that you hit as you look at  the different possible elements of a so  all of the things that f hits the  standard notion of range of a function  um  so the range of s f has to be equal to b  you have to hit everything  um right uh  can you think of a one-to-one  correspondent says relabeling yeah i'm  not sure that's helpful but yes you can  think of as a re-labeling of the  elements in a sense but uh yeah  i just think of it as a matching up  um all right so let's move on um  so uh  coming out of this notion of sets of  being of the same size there was this  notion of countable sets as we'll see in  a minute um  so  let's do an example  let's take the set of natural numbers  you know one two three four dot dot dot  and the set of integers  which includes the natural numbers but  but also the negative numbers in zero um  so the  natural numbers are typically referred  to as n the  integers are typically referred to as z  and  how do we  what do we think of the relative sizes  of um  n and z  well n is a subset of z it's a proper  subset of c so you might at first glance  think that z is larger and they're not  really going to be of the same size  but it actually it turns out that  there's a very simple way  you know the arithmetic and the  properties of infinite sensor can be a  little bit surprising and there is a way  of matching up all of the elements of z  with elements their own elements of n um  and so you can show that as uh  following that definition that these two  sets are in fact of the same size so  let's just quickly go that goes make  sure you see that  um  so here is n  here is z i'm going to write down a  table which shows how they match up and  here's the function f of n that i'm  going to be describing that's the um the  one-to-one correspondence  and so here are the natural numbers  dot one through seven dot dot dot and  here are the elements of z that i'm  gonna be matching up this is how the  function is working so one i'm gonna you  know f of one is gonna be zero f of two  is gonna be minus one f of three is  gonna be one  um and i'm just giving you a way to  match up each of the natural numbers  with with integers  so that every single integer has its own  natural number and vice versa um  [Music]  so four goes to minus two five goes to  two six goes to minus three seven goes  to three and then minus four and then  four minus five then five and so on  you're clearly going to cover all of the  integers in this way and each of the  natural numbers is going to have its own  integer and there's never going to be  any collisions there's never going to be  two natural numbers assigned to the same  integer so this is meets the uh the  conditions of a one-to-one  correspondence and shows that the  natural numbers and the um and the  integers have the same size  uh following this definition um  okay let's do one that's slightly  more  complicated um and perhaps slightly more  surprising  which is that if you consider all of the  rational numbers  and um then they have the same that is a  collection even though the rational  numbers seem to be much richer and  more numerous than the integers from  this perspective they have the same size  and for the simplicity of my uh  my presentation i'm going to consider  only the positive rational numbers which  i'm going to write as q plus  so those are all of the positive  rational numbers that can be expressed  as a ratio of two natural numbers  and um i'm going to show that there is a  one-to-one correspondence between the  rations between these positive rational  numbers and and the natural numbers  okay so  um  here i'm going to again make a table  just as i did up uh up above um  so comparing the natural numbers and the  positive rational numbers  and  to do that i'm going to write down over  here on the side just to help you see  how i'm getting this table  a table a separate table that can that  has all of the rational number positive  rational numbers appearing you know in  kind of a nicely organized way um here  are all the rational numbers here that  have one as a numerator that have two as  a numerator and and so on and going  through across the columns the different  denominators  um so it's the the numbers inside here  represent all of the different rational  numbers and so whatever rational number  you have  m over n  um  that's going to appear down the nth row  in the nth column  that number is going to appear so  they're all going to show up  and i'm going to use this  table here to fill out this function  um  so uh  here are all the natural numbers and the  way i'm going to assign  the  rational numbers to appear over here is  i'm just going to work my way in from  the corner  and i'm going to do that by kind of  doing layers so first i'll take the one  in this  this number here in this corner then  i'll do these three that surround it and  then these guys that's around that and  these guys sort of in shells going  around the previous ones that i've  already covered  okay so  let me illustrate that  so here's one over one my first rational  number that i'm going to enter then to  the table  appearing right over there so next i'm  going to go 2 over 1  that's going to appear in the table over  there  now we have 2 over 2. now that's  actually a little bit uh problematic  because 2 over 2 has already been done  um and if we put that in  uh because 2 over 2 equals 1 over 1  they're both the equal to the rational  number one  so if we put two over two in this table  over here then we would no longer have  the one-to-one property because both one  and three would be mapping to the same  point um so we're just going to simply  skip over two over two  um  i'll show that as kind of graying it out  so we're not gonna  we're not gonna add that one onto the  table onto my function  um  so but so we'll skip over that we'll go  to one over two which is um has not been  seen before  and then we're just going to continue  doing the same thing now going to this  next shell out here  three over one  three over two  three over three  same thing i'm going to skip over that  one  2 over 3  1 over 3. i hope you're getting the idea  um so i'm not going to fill this  together i ran out of room to  put fill out this table some more but  just to look at how the process is going  to continue here i would get 4 over 1.  now 4 over 2  again is the number we've previously  seen because that's the that's the  rational number 2. we saw that up here  when we had 2 over 1 so we're going to  have to skip that one  4 over 3 four over four  that was going to skip  three or four and so on  okay so by uh following this procedure  i'm going to be able to define this  function now this function is not  particularly nice in terms of having a  an elegant closed form but it is a  the total legitimate function in the  sense of being a mapping from  natural numbers to  the positive rational numbers  and it has the one-to-one correspondence  property  so it pairs up each of the  natural numbers with each of the um  uh positive rational numbers um they  each get their own  mate in a sense and so that shows that  the rational numbers despite the fact  that they're dense and they have all  sorts of very sort of more much bigger  seaming they really and from this  perspective of the sizes of the sets  they have the same size as the  natural numbers do and so with that it  suggested  the following definition that a set is  countable  if it has the same size as the natural  numbers or it's finite  from this perspective we're going to be  focusing on infinite sets uh but yeah  countable or countably infinite  sometimes people say uh if it has the  same size as the natural numbers or  otherwise you have to include the finite  sets as well and countable means you can  just sort of go through the the sets the  the elements of the set kind of  as a list  so you can count them the first one the  second one the third one the fourth one  dot dot dot and once you can do that and  that counting is going to hit everything  then you know um you can match them you  can pair them up with the natural  numbers and so therefore you have a  countable set okay um  [Music]  so as we've shown  both z  the integers and the positive rational  numbers are countable sets  okay now  you might think that well since we're  allowing ourselves to do something as  arbitrary in a way as this kind of a  function  to match up the natural numbers with  whatever set you're trying to um  to measure  that every set is going to be countable  if you think about it that way because  it seems like you're allowing two too  too many possibilities and that all the  infinite sets are going to end up being  the same size as the natural numbers  well that isn't in fact is not true  um  and i don't know i i i  can't or as the one who discovered that  um i don't know if that was surprising  or not um but uh it is kind of uh  interesting i think that there are  different sizes of infinities um  and uh so uh we're gonna now take a look  and see uh that but i want to again um  i want to uh stop and make sure we're  all together can we always find a closed  formula for f somebody's asking me um  i don't know  for this particular f uh  you probably could but it would probably  be very messy um  um but in general that's not a  requirement  having a closed form for the for the  mapping function any function is allowed  as long as it's a one-to-one  correspondence  um  are we all together on this is this are  we comfortable with the notion of  some infinite sets  having the same size as the natural  numbers and therefore we're going to  call them countable sets and we're going  to show some other sets are going to  have um more elements they're going to  be uncountable they're going to be  beyond  strictly speaking strictly larger sets  in the sense that we won't be able to  put them into a one-to-one  correspondence with the integers um so  then the smallest infinity yes n is the  smallest um  smallest one so  any infinity is going to have um  you know you can always i don't think  you even need it you need a special  you know you can always  and whenever you have an  internet collection you can always find  a subset which is going to be  a countable subset uh so it's uh  and is going to be the smallest of the  infinities but there are bigger ones  all right why don't we move on  okay so um  the example of a set that we will show  is not countable an uncountable set as  we call it um is the  uh set of real numbers which you i  you know  we all know what these are i hope uh  these are all of the numbers that you  can express by possibly infinite decimal  representations like pi or e square root  of two  um or on any of the other familiar ones  you know um rational numbers are also  members of uh  are also count as real numbers and  integers too um  and so  uh but you know there are these  additional numbers that you can get by  uh  decimal expansions which may not be  rational  um  and that collection even though in some  ways it looks somewhat similar to the  rational numbers um the real numbers i  hope i said that right the real numbers  um uh the the uh which is the set i'm  considering here the ones with the  infinite decimal expansions they  actually are much larger  um  so  um  the theorem is and this was discovered  by kantor um that uh r is an uncountable  set  and the reason why i'm introducing this  is um besides that i think it's  interesting um  uh  and has some some relation uh to uh the  kinds of things we're doing but it's  really for the purposes right now is to  introduce this method called  diagonalization  um  okay uh that's we're gonna use later on  again but this is the first time it  appeared  so we're going to  use a proof by contradiction in order to  show that r the collection of real  numbers  is uncountable and we'll assume for  contradiction that r is countable  okay  um  so  if we assume that r is countable it  means we have by definition a one to one  correspondence from the natural numbers  to the real numbers  okay so we can match up  all of the natural numbers with  uh the real numbers in a one-to-one and  onto fashion so we can pair up the  natural numbers with the real numbers  and we will cover all of the real  numbers by doing that and we can make a  table  just like i did before  here it is  um  and you can fill this out with all of  the real numbers  and um  that was what the assumption means and  i'm going to show you that that's  impossible something is going to go  terribly wrong if you do that  um now uh  you might disagree you might be  surprised you might think well  uh professor sipser is wrong um you know  that i'm gonna work on this overnight  and forget the rest of my classes and  i'm gonna come up with a list of  uh all the real numbers i'm gonna fill  them out here and show that that's  impossible um so let's say  hypothetically just for my example's  sake um here is the list that you came  up with um  so you know you had to match up  something with the one let's say e had  to that was a special case so you're  gonna stick that with one and then pi  came out to be the number that you you  connected up with uh two you wanna see  what i'm doing here i'm making a list  i'm trying to make my one my  correspondence my matching up between  the natural numbers and my real numbers  that i'm hypothesizing to exist for a  contradiction  so three  i i don't know three is gets connected  to zero i'm making this up obviously uh  not on the spot i wrote the slide you  know uh yesterday but uh here's a square  root of two showing up for whatever  reason here is one seventh  here is some other number which i'll be  interested if you recognize that one  that's a that's a subtle one um  this is one point two three four one  point yeah some some familiar looking  sequence here and whatever it is  whatever it is this is what you came up  with you claim that this is to work as  uh very good you somebody got it  it's i to the eighth power but let's not  get hung up on that please um  i to the either power oddly enough can  be seen as a real number under you know  if you define the uh  imaginary exponentiation  uh which is weird but anyway  let's uh let's not get too distracted um  so here's my list of numbers my real  numbers that i've matched up in my table  here with the natural numbers  now something's go i claim something  goes wrong what goes wrong i'm going to  show you that you actually  uh did not  do as you claimed  that there's actually um at least one  number that's missing from this list and  i'll exhibit that number i'm going to  show you what that number is i'm going  to explicitly come up with a number and  show you that there's that number it's  missing from the list um so here  it's going to be a number x  x is the x is the one that's missing  so how am i going to get x  so x well i'm going to start it off with  zero point and then i'm going to fill  out the rest of the places and how am i  going to get those places i'm going to  look at the table here  so i want to look at to get my first  digit after the decimal point of x  i'm going to look at the first digit  after the decimal point of the very  first number  so i take the first number look at the  first digit after the decimal point  and which happens to be a 7  and the number i'm going to put in for x  is not going to be 7 it's going to be  anything except 7.  let's say  8. um  for my next digit of x  i'm going to look at  so my second digit of x i'm going to  after the decimal everything's going to  be after the decimal point now uh so i'm  not going to keep saying that i'm going  to look at the second digit of the  second number uh which is a four  uh after the decimal point um  uh  there it is  and for the second digit of x i'm going  to use something which is  anything besides four five  i have some flexibility here um so i  could have used six i could have used  seven  i'm going for those of you who have seen  this before who are gonna nitpick on me  i'm gonna stay away from nine and zero  just because there are some little um  edge cases that arise there which i  don't want to get into because i don't  think it's interesting for this argument  um but since i have some flexibility i'm  going to avoid zeros and nines probably  just nine is all i really need and then  um  the argument is just going to work fine  okay  so uh the next digit is a zero  uh for the third digit of the third  number is a zero the third digit of x is  going to be anything except for zero be  a one  then i have a two here  anything except a two  six  uh then five anything except a five a  one a nine anything except a nine an  eight  and so on there's an eight  there's a two and dot dot dot i'm just  gonna keep doing that  and i'm gonna say  you missed that number whatever it is  but that number it's a that's a number  after i'm all done it's going to be the  decimal representation of something  and that number uh i claim  is absent from the table  and you might say well  you know it's really there  um it's just on the  um  23rd row  you just didn't get to it on your slide  but it's there well i'm going to say i  know it's not in the 23rd row because it  differs from the number in the 23rd row  at the 23rd digit  because i constructed it that way  this number is designed  explicitly to be different from each of  the numbers that's on the list  okay so it can't be on the list because  it's been constructed to be different  from each of them in at least one place  so it's i think this is a beautiful  argument and it shows that  uh no matter how you try to come up with  a one-to-one correspondence you're going  to fail you know you might say oh you  know like  you know just one number you know it did  so much hard work and missing just one  number can i get partial credit  you know and put this one on the list  now i fix it no obviously there are many  many numbers that are missing if you put  this one on the list i'm going to  construct another number that was  missing  so  um this is uh  you know  there's just not no possibility of  fixing this and in fact you know the um  the real numbers are  are uncountable cannot be matched up  with the natural numbers and there's  nothing  it can't even come it doesn't even come  close um  so um  here's summary what i just said  um f is not a one-to-one correspondence  no matter what you try to do you can't  come up with a one-to-one correspondence  so that's the contradiction  okay so that proves that  r is uncountable  okay and that's why by the way we call  this a diagonalization because we're  going down this diagonal here that's  where the term that's where the name has  come from  okay um  so i i'm happy to  okay that's it uh  somebody's asking me  i'm actually i have a  um  is it here i can't remember it's here i  have a uh check-in coming about this and  somebody is kind of um anticipating that  by asking uh the the actual rather  famous question about there being a  possible infinity in between  the natural numbers and the real numbers  we know the real numbers now are bigger  than the natural numbers but is there  something that's in between i mean this  is a very very famous problem um  uh which i'll talk about you know when  we get to our check-in which is coming  up  um  well somebody is objecting just the way  i've defined x using this procedure that  really really can't in a sense state  you know but it x is a number x is the  result of  what what this procedure is it's you  know following this procedure we're  converging on some particular value and  so that is the value um if you want you  know we can make a more precise way of  determining i mean i so i we don't have  the flexibility of choosing the way i  did in my example we can make a precise  procedure for coming up with these  digits but  i don't think there's anybody thinks  there's anything  that's um  there's any shortcoming in this argument  in terms of the way we're defining x  it's i i think it's worth understanding  this  because it's really going to set the  groundwork for our proof that atm is  undecidable which is a little i think  perhaps slightly more abstract in a way  um in the way it sort of comes across  i'm going to try to can make connect the  two  but uh i think it's helpful to  understand at least this argument  because this argument is kind of  diagonalization in its kind of most  raw form  all right i think we're good um so let  why don't we continue then um  so there are a number of corollaries  that follow from the statement that the  real numbers is uncountable um  uh  first of all if you let script l be the  collection of all languages if you want  to consider over some particular  alphabet that's fine but that's not  going to be really uh  you know important for this uh  point that i'm trying going to make so  uh l  uh script l is the collection of all  languages um so every subset  of sigma star  every subset of sigma star is a language  um so look at all those possible subsets  um so that includes you know 0 to the k  1 to the k plus every other language you  can ever think of and more all possible  languages  um so that  the collection of all languages is  uncountable  there's uncountably many different  languages out there  i don't want to belabor this point you  can just take this if you don't quite  follow the the quick argument i'm going  to make here but um  uh you can make a correspondence  one-to-one correspondence from all  languages to the reals  so that each language gets its own real  number  and the way i'm going to think about  that let's put the real numbers into  binary form  and if you imagine here being sigma star  all of the possible strings of sigma  star  you know written out in their standard  order  um and now if you have a language here a  it's just some arbitrary language so  that's going to have some of the strings  of um of sigma star appearing like zero  is appearing but one is not appearing  zero zero is appearing in zero one but  not these three  um and i'm gonna associate to a  my language  some real number in binary by putting in  a zero in the decimal representation or  the binary representation i should say  um  for that  string  if it's not there and a one if it is  there  um and so a real number because there's  infinite many infinitely many yes no  choices  in the binary representation can  represent a language because of each of  the yes no choices of a string being  present or not i'm going to put a one  for when the string is present the zero  when it's not present so each  uh language has its own real number and  each real number is going to be  associated to its own uh language here  i'm restricting myself to real numbers  between zero and 1  that's not going to be an essential  point so let's not get hung up on that  so  [Music]  the  the fact that  the  the languages can be  uh  put into one-to-one correspondence with  the real numbers  um  shows that the collection of all  languages is also uncountable  now another  observation here another point worth  noting is that if you look at sigma star  itself  the strings  uh all possible strings that's a  countable set  the collection of all possible languages  is uncountable but the collection of all  possible finite strings  is countable because i can just list  them  here is my list of all possible strings  which you can put into a table if you  like to think of it matching up with the  natural numbers in that way  now i'm get i'm trying to make a point  here which is that  if you take am which is all possible  turing machines script m is all possible  turing machines the collection of all  possible turing machines is countable  there are only countably many different  turing machines  and you can argue that in all sorts of  messy different ways but i think the  most simple way to see that  is to think about each turing machine as  having a description  which is a string  so the collection of all descriptions of  turing machines is just a subset of  sigma star which we already know is  countable  and the subset of any countable set is  going to be countable  so  anyway  i think it's worth  remembering  that  the collection of all turing machines is  countable  um whereas the collection of languages  is uncountable and that tells you right  there  that some language is not decided  because there are more languages than  touring machines  we have uncountably many language only  countably many turing machines so that's  fewer turing machines than languages  there's no way to map all the languages  onto turing machines so there's going to  always be some languages that got  unmapped  um and so in particular there are going  to be some languages which are  undecidable there are going to be some  languages which are not touring  recognizable  and anything based on some automata kind  of um  definite definition process is going to  be some languages that you're not going  to be not going to be defining  um  okay now what this corollary shows you  that there is some language out there  which is not decidable what we're going  to show next is that there is a specific  language atm which is not decidable  okay and but first i think we have a  check-in coming up  and  let me give you a little bit of  background here because this is relevant  to this question that i got  about intermediate sized sets so  the question of whether there is a set  of size between the natural numbers and  the real knit numbers  strictly in between so bigger than the  natural numbers not the same size as the  natural numbers but not the same size as  the real numbers either  um but in between uh in size  um  that was hilbert's question number one  out of his list of 23 that i talked  about a few lectures back  it's interesting that he put it as  number one in that very privileged  special place  because i know hilbert was very  he felt that the understanding infinity  was a really central issue in  mathematics and that if we can't answer  a question like this we don't really  understand infinity um  uh you want to understand what kind of  sizes of infinities are there um we know  there's the real numbers bigger than the  than the natural numbers is there  something in between so fundamental  really um  but uh it was shown uh during the course  of the 20th century really in two  separate steps one in the 1930s by  girdle one in the early 1970s by cohen  that we can't answer this question by  using the standard axioms of mathematics  you know it's  the the answer can go either way  and it's both of them are consistent  with the axis of mathematics so you're  never going to be able to prove  that there is a set whose size is in  between  or that you or that there is no such set  it's just impossible to prove either  direct either way  using the standard axiom in mathematics  which actually is kind of remarkable um  and so my question for you is and this  is really a philosophical question not  one that um is directly and you need to  know about material in the course just i  think it's just a matter of your own  interest i hope you find it interesting  if you don't you pick a wren you can  just answer it randomly um  but um  what's going on here that we can't  answer that question about whether there  is a set of intermediate sides is it  because our axioms for mathematics are  inadequate  or  maybe there is no such thing as a  mathematical reality you can talk about  you know you know what's what's real  here what what what's the reality either  there is a set in between or not  if you imagine all of these things have  their own reality to them well then  there's going to be an answer and then  you would expect well maybe we could  find better axioms which will actually  give us that answer or you can say well  there is no reality  and um  you know it  infinite sets are kind of human  constructs anyway so we can make them  kind of play out any way we like  mathematicians argue about that to this  day um  and um it is as i say really it's a  philosophical question but just out of  curiosity let's see how you guys end up  uh deciding on that one um so here's the  poll  five seconds to go please vote  and uh we're going to end the polling  one two three now  all right here we go  so there's no right answer  um  i think if most mathematicians were  to um  i think the instinct of most logicians  especially i'm not sure our general  mathematicians really even care about  this question but logicians um  would probably have an instinct that  probably there are sets in between  there's no reason that there shouldn't  be  um  you know it seems kind of strange that  there should be this sort of jump uh  from the  natural numbers to the real numbers and  why nothing in between um  but um  it's uh  i don't think that question is really  settled  so  all right let's continue on i think we  are  um okay so we're gonna  um  a coffee break is coming in case you're  wondering so this is on my last slide  before then but this is an important  slide so please uh hold hold out  um  so here is our  uh promised theorem of the day  i'm going to show that atm is not  decidable the acceptance problem for  turing machines  and it's all going to be contained on  this one slide we're going to give a  proof by contradiction using  diagonalization  and we're going to assume some turing  machine h decides atm  and we're going to get a contradiction  so let's first of all make sure we  understand what h is doing  so h gets an input a turing machine and  an  input and h is going to be a decider so  it always halts  with an accept or a reject  it's supposed to accept if m accepts w  and reject if it doesn't so in other  words it's going to reject if m rejects  w either by whole by halting or by  looping  that's the job of h  and we're assuming we can do that  but we will see a contradiction occur  so the way we're going to do that  is is really kind of just one step here  in a way and we're going to use h to  construct another turing machine d  h is going to be a subroutine to d  we've already seen us doing that in the  past  d is going to do something a little  strange  just to just to warn you um  these input is just a turing machine no  in no w  and  what  d is going to do  using its subroutine h  is going to simulate h  on input  m comma the description of m now what is  that  well the description of m is just some  string  so what h is trying what it's asking h  uh to tell to answer is does m  accept  the string representing m's own  description  it's as if we're feeding m into itself  which seems like a totally twisted thing  to do  um  you might say  uh  you know  why would you ever feed a program into  itself  somebody's written cannibalism here  yeah kind of uh i said it's it's worse  because it's  not eating somebody else it's eating  himself  okay but  um  i claim  that we actually there are actual cases  in practice  where we do this  we feed programs into themselves  and uh the example that i know of where  this is done  is when you're making a compiler  you might want to make a compiler and  then written in the same language that  it's compiling and then you feed the  compiler into itself  they may say why even bother because  it's already obviously if once it's  running you don't need to  compile it again um but actually you  know an example where this was really  used  was when there was an optimizing  compiler i think for c uh written on  early unix machines  and the optimizing compiler for c was  written in c  so you would feed the optimizing  compiler  into the regular compiler first of all  now you had the um  compiler running  but it was unoptimized  so but now that it's the optimizing  compiler is running  you can feed the optimizing compiler  into that which is itself now you have  an optimized optimizing compiler  so it really makes  some there is a at least one case where  this has actually been done uh in  practice  um not that we really care this is a  theory class but just for fun to observe  that  so here h is trying to say well does n a  m end up accepting when it's fed  the description of itself  you know at least mathematically  speaking that's a reasonable uh thing to  ask  and then what  d is going to do when it gets the answer  back from h  h as a decider don't forget  is d is going to do the opposite  whatever h does it's going to accept if  h rejects and rejective h accepts  um so let's in summary let's pull this  together some  you know it's easy to understand in the  end what is d doing  d is going to accept d is also going to  be decided by the way so d d is always  going to either accept or reject  just the opposite of what h tells it to  do so d is going to accept  m  exactly when m doesn't accept m because  you know when m doesn't accept m  h is going to reject  um and so then d is going to accept so d  accepts m if and only if m doesn't  accept that that's exactly the condition  in which d accepts it  i think it's important to just step back  and make sure you understand this line  because we have only one line left  to get our contradiction  right are we together d accepts m if and  only if m doesn't accept m that's just  by the that way we've defined setup d  now  what we're going to do is feed in  instead of m to d and not some arbitrary  fee  we're going to use feed in d into d  and that is going to be our  contradiction because d is now going to  accept d if and only if d doesn't accept  e and that's certainly impossible  okay  that's our contradiction which proves  that h cannot exist and therefore atm is  undecidable  okay so we're done  except for the one point which is that  um  why is this a  diagonalization  and i think you can get that from the  following picture  if you imagine here writing down all  possible time i'm making i'm going to  make a table here here is a list of all  turing machines  okay uh including d which is a machine  which i  built  under the assumption that h exists so d  appears here somewhere but here are the  all the other turing machines and here  are all these descriptions of the turing  machines along the uh labeling all of  the columns  okay so these are the rows labeled these  are the column labels and inside i'm  going to tell you  uh the answer for whether a given  machine  accepts a given input  so for example m1 accepts its own  description but rejects the description  of m2 but accepts the description of m3  i don't know you know i'm obviously  making this up i don't know what m1 is  but just hypothetically that's what the  machine m1 does  um so i'm just filling out this table  and you know this is  d  uh h could get the answer to any of the  elements in this table because it can  test whether m4  um accepts the description of m3 so it  could h could fill out this table  so maybe m2 is a machine that always  rejects it's a very unfriendly rejecting  machine  m3 is a very friendly machine it accepts  all inputs and for its reject sum and  accepts other dot dot dot  now i want to look and see what does d  do  um  now based on the information i've  already given you we can understand what  d does  so for example what does d do when i  feed it the description of m1  what does d do  well we can look over here d accepts m  if and only if m doesn't accept m so d  is going to accept  um  m1 if and only if m1 does not accept m1  well m1 does accept m1  so d  does the opposite d rejects  so okay i'm highlighting here  d rejects because it's going to d is  going to do the opposite of what the  machine does on its own it on input  um so m2 on so d on m2 you have to look  what m2 does on m2 it rejects so d does  the opposite of that it accepts  and similarly  uh  you know all each one of these things  these answer is going to be the opposite  of what the machine does on its own  description  um just by virtue of the definition of  date  okay and so on so far so good  but the problem is what happens when d  is fed itself  because as you can see  you know um we're we're heading for  we're heading for trouble because this  is a diagonal down here  d is just one of the rows that diagonal  is going to  intersect that row at this point  and d is defined to be going to be doing  the opposite of what that element is but  it can't be the opposite of itself  okay and so that's that's the  contradiction  so i think you know where um  uh  i i'm gonna call us give us a little  break here um and then you can also text  me in the meantime we'll be happy to  answer some questions during during that  a little over four minutes to go so  let's see let me see if i can  answer your questions  okay what's so special about atm that  enables us to do this why can't we do  this on adfa for example  um so that's a good question i i i  and  the answer is that um  you know  you know in a sense  you know we can do this on dfa i mean i  i think this is perhaps a bit bit of a  stretch but you know dfas could not  answer adfa i mean we could prove that  in other ways as well you know by uh  because  you know we could use things like the  pumping lima and it's not clear even how  you formulate adf8  but what's important here is that the  um it's really the model talking about  itself  um that really is where the problem  comes up  so if you try to push this argument  through to show that adfa is not  decidable by touring machines you're  gonna fail  um  because you know we're starting off with  a turing machine and um i mean  i think i'm gonna confuse myself if i  try to just repeat it but um you're you  won't get a contradiction because the  turing machine is not a find out  automaton  um  okay um  will this argument get into self loops i  don't see why there was there is some  self-reference perhaps we're going to  talk about that a little later because  we're going to come back and revisit  this argument um  you know in a  in a week or so when we talk about the  recursion theorem which talks about  machines that can refer to themselves  but this is a little bit of a head  getting ahead of ourselves so  uh somebody's commenting on this  reminding them of the barber paradox if  you remember that the  which has some similarity you know the  there's a town in which uh there is a  barber which shaves every man who  doesn't shave themselves  which seems you know he's a very good  barber so there's some people who shave  themselves  and  all the rest the barber shavers uh the  question is does the barber shave  himself because he shaves only those men  who don't shave themselves so you got a  same kind of a contradiction there is a  there is a relationship there  um  so somebody wants to know where did we  use the decidability so we used the  decidability to come up with h  um  you know once we know that atm is  decidable then we have that h function  and then we can build d  um so that's where that's the the the  chain of that's the chain of reasoning  um  so you assume atm is decidable then you  have the decider  and then  called h and then you can build d um  somebody wants to see the previous slide  well  uh what part of this one do you want  uh  so i'll leave that up there why can't we  why can't we apply the proof that all  touring machines are countable to all  languages well because turing machines  have descriptions  languages general languages don't have  descriptions  and so that's uh why okay the candle has  burned to the to the bottom and it's  time to move on um  so now let's look at the  uh acceptance problem for kuwatama  i'll give you a q automaton an input  and i want to know does it accept the  input is that going to be decidable  and you have you have your choices it's  either yes  it is decidable because these are  similar to put down automata and apda is  decidable  or no because yes would con contradicts  results that we know at this point or we  don't have enough information to answer  the question  okay let's put that up  one second  all right  that's it ready going gone  uh so  yes the answer is uh well no  the answer is the indeed the answer is b  um  uh true that uh cubitamina are similar  to push on automata but all these atomic  are kind of similar to each other and  that's not going to be good enough  uh  well the homework has asked you to do is  to show that you can simulate turing  machines with q automata  so if you can answer the question about  whether the queue automata uh will  accept their input that would allow you  to be able to answer questions about  whether turing machines accept their  input and we just proved that's not  possible  so um  uh  it would get it be a contradiction if we  could answer  uh if we could decide a qa  now we have an example of an undecidable  language let's look at an example of an  unrecognizable language  now atm is not going to serve  that purpose because atm  um  [Music]  is  um  recognizable is turning recognizable as  we pointed out by the universal turing  machine  so uh atm is undecidable however how  about an unrecognizable language  for that we will see that the complement  of atm  will serve so the complement of atm  is  neither decidable nor even recognizable  that's not turing recognizable  and that's going to follow from a pretty  basic theorem that connects  recognizability and decidability that i  put up here on the screen  which is that if you have a language  where it and its complement are both  recognizable then the language turnout  turns out to be decidable in fact the  language and its complement are decided  but but being decidable is closed under  complement so that's something you  should be aware of  um  but being uh okay  we'll get to that in a minute but  uh if um  uh  so anyway so we have a language and it's  complement both recognizable how do we  know the language is decidable so first  of all let's take the two turing  machines m1 and m2 that recognizes a and  a complement  and we're going to put those together  to get a decider for a  um  and that's going to work like this  it's going to be called t  so t says on input w what it's going to  do  it's going to feed w into m1 and m2 both  um a is a language by the way yes a is  when i'm telling you when i say it's  touring recognizable you know turing  recognizable only applies to languages  so so yes a um is often this symbol i'm  going to use for languages sometimes for  an automaton but  a is typically going to be a language  so um  [Music]  if uh so  now i'm trying to make t  be a decider for a  from the recognizers for a and a  complement  so i'm gonna  take an input to t  and feed it into both recognizers m1 and  m2  okay i'm going to run them in parallel  what's nice  is that because  um  m2 is a  recognizes the complement of what m1  recognizes  every string is going to be accepted  either by m1 or by m2  because every string is either an a or  an a complement  so if i run m1 and m2 on w until one of  them holds one of them accepts i know  i'm not going to run forever because  eventually one of the other ones have to  accept  so and then i got my answer because if  m1 accepts that i know i'm in the  language but if m2 accepts i know i'm in  the complement of the language no matter  the language so if m1 accepts then t  should accept if m2 accepts then t  should reject  um  now  so that proves that  nice little theorem uh written at the  top in blue  um so i got my decider for a  built out of the recognizers for a and a  complement  now immediately it follows that  the complement of atm is not touring  recognizable  because  we know  that atm itself  is recognizable but it's undecidable  if its complement were also on recognize  if the complement was also recognizable  then atm would be decidable but it isn't  so when something is  undecidable either it or its complement  have to be unrecognizable and in the  case for atm it has to be the compliment  because we already showed that it is  itself is recognizable  um  so that's the proof of that so here is a  little picture of the way the world  looks right now if you have here in the  middle of the decidable languages see  these are all languages here this venn  diagram of languages kind of we showed  earlier you know like the regular the  context free decidable recognizable  here i've got the recognizable and what  i'm calling the co  co code touring recognizable  this is the collection of all  complements  of recognizable languages so atm  bar atm complement is the complement of  a recognizable language this uh  region here is are all the complements  of the recognizable languages or the  so-called  co-turing recognizable languages  complement of  so atm is on this side atm complement is  on that side but if something's in both  by virtue of this theorem here then it's  decidable  okay  last check-in for the day  um from what we've learned so far  um which closure properties can we prove  for the class of  the touring recognizable languages  choose all that apply  well as i say  you don't have to get it right let's  let's not spend too much more time on  this because we'll we'll we'll talk a  little bit about it  um  almost all it's closed under almost all  of them but not all of them  because you know  are we done here i think we're done  five seconds  okay here we go ending polling  i'm not sure what the meaning of  the leading answer is here uh everybody  likes union i guess they're closed under  all of these operations except  complement so  um  but we just proved it's not closing the  confidence i'm a little  you know a little puzzled by why we have  so many votes for closure under  compliment  uh we have here atm  is touring recognizable but atm  complement is not touring recognizable  so right here on the slide  so i'm not trying to make you feel bad  but uh  um i'm trying to  just point out that you  think please um  so  um  now closure under union and intersection  i mean you could kind of get those  answers just by running things in  parallel the way we did the proof here  you just run both machines  and  if they both  give i mean it's a little tricky i  suppose you know if if if either one of  them accept um  then you can accept or if they both  accept you just wait until they both  have accepted otherwise you just keep  running um so the first two are pretty  straightforward um closure under  concatenation is also going to be  similar you just try every possible way  of cutting uh the string up into two  pieces  and run in parallel on and if you ever  find a way  of cutting it up and you run those two  and those two sides in parallel and if  they both um accept  um then uh then you can accept and star  is again very similar so there these are  not too bad um but i admit you know it's  not a whole lot of time to i have to  contend with something uh that you're  just getting uh used to  so let's um  uh  let's talk about the very last topic of  the day which is really going to be  setting ourselves up  for um tuesday's lecture next week um  and that's  how we are going to be showing other  languages are undecidable which is  something that  um i'm going to be expecting you guys to  be able to do um  this is um  the standard procedure for showing  languages are undecidable using what's  called the reducibility method  um  and what that does is it  takes as a starting point a language  that we already know is undecidable  typically atm  or it could be another one that you've  previously shown to be undecidable and  leverages that information to show other  languages are undecided  and um  it's using what's called reducibility  we're going to go into this  more carefully next time  but basically reducibility is a way of  using one problem to solve another  problem  and so we're going to show for example  uh let's take a look at the problem  called the holding the halting problem  which is like the famous problem for  turing machines um  uh you just want to know whether it  holds not necessarily whether it accepts  so it's very similar but not exactly the  same  and we're going to show that  this halting problem is similarly  undecidable now we could go back and do  the whole diagonalization but that seems  like  well that's more work than necessary now  that we already know atm is undecidable  because we're going to show that we can  reduce the atm  problem to the hold holding problem um  and we'll explain what that means again  uh later but um the idea is and as as  we'll show in an illustration uh shortly  that  by proving by contradiction um  if the whole thing if halt tm  were decidable then atm would be  decidable  and we know atm is not decidable and so  um  that's our contradiction  now  uh  the way we're going to show that if  whole team is decidable than atm is  decidable  is use a decider for whole tm to decide  atm with a suitable  um  you know uh  uh  modification  so basically we're gonna turn  and hold tm decider into an atm decider  and that's  how we're going to reduce the problem of  solving atm to the problem of solving  halt tm  let's just do an example like you know  if you've seen it before obviously this  is not going to be hard but for the many  of you who have not seen it before i it  i'm partly doing it this time just so we  can do it again next time and maybe  it'll sink in by virtue of repetition  so  um  so again so as i just said we're going  to assume the whole tm problem is  decidable and use that to show that atm  is decidable which we know is false we  showed it just earlier that it's not  so assume we have a decider for whole  team we'll call it r  and we're going to construct from our  decider for atm we'll call s  okay so we're again typical proof by  contradiction we're assuming the  opposite of what we're trying to prove  and then we're going to get something  crazy  okay so here my job now is i'm assuming  i have r which is a whole tm decider so  now i'm assuming i know how to  decide  if a turing machine and an input  eventually halts  not necessarily except just whether it  holds  you know it's conceivable you know you  have to bear with me here it's  conceivable that you could find a way to  test whether  you know turing machines halt on their  input even though we now know that  testing whether they accept their input  is not decidable  so you have to kind of be open-minded to  the possibility that we can  that the whole problem is decidable and  we're going to show that that's can't be  so we're going to show that  if we could decide the whole thing  problem then we can use that to decide  the uh the acceptance problem  okay so how do we how do we going to do  that so imagine now we can solve the  halting problem  so to solve the atm  which is what my job is  to do  so s is supposed to solve atm  i'm constructing two  machine as the site atm  i'm going to use first i'm given an mnw  i'm going to feed it into r since that's  really all i got  see if r  tells me  what happens  does m on w at least hold  well if r says no it doesn't hold  well then then i'm actually done  because if it m doesn't even hold on w  then it couldn't be accepting w so at  that point i know that m doesn't accept  w and i can reject right  off  so our you can see how it could  potentially be helpful but it's going to  be helpful in either way because if r if  r says m  does hold  well then i'm also good  because i don't know the answer yet but  what i do know is i can now simulate m  on w  until it holds because r has told me it  holds so i don't have to worry about  getting into a loop  um  uh so s can be confident in being a  decider for whatever it's doing um  because i'm running uh now m on w with a  guarantee that it holds  um  and now that going to tell me now  eventually the simulation of m w is  going to end up at an acceptor reject  and that's going to be the answer i need  so if m is accepted then accept and as m  is rejected then reject  and that's how s solves the atm using r  which which solves whole tia  but s can't exist  and so therefore r can't exist and  therefore whole tm can't be decidable  okay  so that quickly  um  okay  i'm not sure which diagram you wanted me  to show but anyway maybe we can do that  we're basically at the end of the hour  or end of that 90 minutes so let's do a  quick review and if you stick around i'm  happy to go back and look at any of the  other slides uh that you might have  missed something on  okay so just to recap we showed that  uh the natural numbers of the real  numbers are not the same size using that  definition of one-to-one correspondence  to introduce the diagonalization method  we use the diagonalization method to  show that atm is undecidable  we also showed that little theorem that  if the language and its complement are  recognizable then the language is  decidable  and from that we conclude that atm  complement is not recognizable  and then we showed at least by virtue of  an introduction to the method the  reducibility method to show that whole  tm is undecided  okay and that's that that was today's  lecture and we're and we're uh  at the end of the hour so why don't i um  you know we are finished uh you can uh  log out um and if you want i will stick  around  okay  okay this is kind of a good question  here  [Music]  so i'm getting a question about the  atm complement  which is uh you know since we have a  a recognizer for atm  uh if i'm doing justice to this uh  question uh we have a co we have a  recognizer for atm so why can't we just  invert the answer  you know  flip flip the answer around and now we  have a recognizer for  the complement of atm atm complement  so why doesn't that work  well the reason that doesn't work  is because  the recognizer for atm  might be rejecting some things by  looping  and now if you just flip  the accepting and rejecting  um  when it hits one of those uh holding  states it's going to give the reverse  answer  but the uh when it uh  rejects by looping it'll continue to  reject by looping so you won't get the  complementary language coming out  so you know if we want you know if we  would be helpful i can go back  to that uh slide here  um  which proves that atm complement is  unrecognizable  because  maybe we should start with the bottom  we know that atm  is recognizable and undecidable  right we already proved those two facts  atm is recognizable  from the um universal turing machine  and it's undecidable by the  diagonalization argument  those two things together  tell us that the complement has to be  unrecognizable  because  if a language and its complement are  both recognizable and we already know  the language itself is recognizable  so now if the complement is also  recognizable the language is going to be  decidable by the upper theorem  so it must be the case that either the  language itself is unrecognizable or its  complement is unrecognizable  we know the language is recognizable  that's what the universal turing machine  told us so the only thing left is for  the complement to be unrecognizable  you should review that if you didn't get  it um because  this is a kind of  you know  kind of reasoning we  you know we're going to be building on  things like that so i think it's good  good to make sure you understand  okay um  okay the diagram on the right so this is  just a venn diagram here  kind of threw this in at the last minute  here i was worried about it being  confusing  you know that part is um  you know so you know i'm trying to show  that the three classes that we've  already talked about  the languages which are decidable the  languages which are touring recognizable  and the languages whose compliments are  going recognizable those are three  separate classes of languages  and  those come up here in those three  regions  these are the decidable ones  here are the recognizable ones  and here are the ones whose compliments  are recognizable  now if a language  is in both  recognizable and its complement is  recognizable so it's in both of these  bigger regions here  then this theorem tells you it's  decidable  so that's why  the intersection of these two regions is  marked as being decidable because that  means you're in both  okay  but we know that atm is sitting out here  as recognizable but not decidable so atm  is in the recognizable side but it's not  on the complement of recognizable atm  itself um  the complement of atm is the complement  of a recognizable but itself is not  recognizable um  and uh  not decidable so you get this side of  nice  you know  [Music]  i hope it's you think it's nice but it's  a sort of uh trying to summarize things  in this in this field diagram  so i think i'm going to then uh  sign off  and um  i'll see you all on  tuesday and have a good weekend bye-bye
 

3
00:00:28,080 --> 00:00:31,750
okay why don't i get started um  so  okay what would what have we been doing  um so last time we considered a bunch of  uh procedures for testing properties of  various automata and grammars  the acceptance problem for dfas  for anaphase  the acceptance problem which is really  the generation problem for context-free  grammars  and emptiness problems for dfas and and  and context-free grammars  and also um  we looked we we showed that atm is  turning recognizable like there's a  question here in the chat already about  that yes we did show that that was the  universal turing machine that we  presented at the end that's what shows  that atm is turning recognizable  um  we mentioned that uh it's not atm is not  decidable uh which we promised we will  prove today and we will do so okay so  that is the plan  um proving atm is undecidable  and we'll introduce the method for doing  that called the diagonalization method  i will also show the complement of atm  is  uh turing on rec unrecognizable even  though atm itself is recognizable the  complement is not  and  then we will introduce another method  called the reducibility method for  showing other problems are not decidable  and give a one example of another  problem which is not decidable assuming  we have time to get to it if not we will  uh  uh delay that part until uh next  tuesday's lecture  all right acceptance problem for uh  touring machines uh so just um  as i mentioned we showed that atm um  which is the language of turing machines  and inputs where the machine accepts the  input  um  we showed that was recognizable we  claimed it was decidable today we're  going to prove it's not decidable  all right now the method  uh that  uh we're going to use um which is really  the only method out there um for proving  uh um  some pro you know a problem was  undecidable is the decoder  diagonalization method i mean ultimately  we're going to show the reducibility  method as well but it really depends on  having already shown some other problem  undecidable  via  the diagonalization method so ultimately  everything hinges on the diagonalization  method which is really all we have um  and uh so  to  uh introduce the diagonalization method  i'm going to  make a bit of a  digression into a  uh branch of mathematics called set  theory or  it's part of mathematical logic where  the method of diagonalization was first  uh  conceived of uh back in the late 19th  century by a mathematician called georg  cantor  and cantor was considering the problem  of how do you compare  the relative sizes of infinite sets  you know for finite sets um  the  uh  the problem of comparing somebody said  that the cantor went crazy that is that  is true um  and maybe i i i don't know why he went  crazy but  um he um he did go uh he had some mental  problems unfortunately um  and so  so how do we compare the sizes of sets  in general if they're finite sets we can  just count them up  we can say oh this set has  uh 11 elements and the other set has uh  10 elements so the 11 one with 11 is  bigger or if they both have 11 they're  the same size well that's not going to  work for infinite sets because you can't  count them up um  and so he had cantor had the following  idea for comparing the sizes of infinite  sets  um and that was  basically um to see whether you can have  a function  that would map  from one set to the other set with  certain properties  and those properties are um called  traditionally well i mean  in the past have been called the  one-to-one and onto properties for the  function i'll tell you what that means  um but the concept is very simple um so  a one-to-one function is one a function  that's mapping from a to b those are the  two sets whose sizes we're trying to  compare  and  uh the function being one to one just  means that there are no collisions if  you have two different elements of a  they're never going to map onto the same  element of b  so two different elements of a always  map onto two different elements of b  so that's the one-to-one property it's  also called injective um  and um the other property is called onto  or surjective um which is that the range  of f has to be all of b so you're not  allowed to miss any elements b you have  to hit everything  um  and when you have the both of those  properties it the function is called the  one-to-one correspondence or a bijection  also  okay um  now uh another way of looking at i don't  want to make this overly more  complicated than it needs to be it just  simply means that two sets are  considered to be the same size if we can  match up the elements with one set with  elements of the other set you just pair  them up  you know for example well  if you look have finite sets um that  into that idea that informal idea just  works exactly as you would expect you  know for example if we have two sets  here's a set of puppies here's a set of  kittens  um  now we want to show that those two sets  have the same size we could count them  up as i mentioned and see that there are  six elements in both  but it's counting up does not work for  infinite sets  so  um we can just match up the elements of  the the puppies with the kittens  and then we know they're we have the  same number of puppies as kittens  okay now that has the advantage of it  making sense when you have infinite sets  so we're just going to extend that idea  and apply it to infinite sets too and  then we'll have a notion of what it  means for two infinite sets to have the  same size  and you might wonder what do you get you  know are all infinite sets of the same  size when you use this notion or or not  what happens um well some strange things  do happen but there actually are quite  some interesting um  uh structure there that uh that emerges  so if um  so anyway  i don't want to rush on uh questions on  any of this if you want to uh  quick question this hopefully was not  too hard but i want to make sure  everybody's together with me on it so we  can pop in uh  i'll give a few seconds for a chat if  you have any uh questions  um  the rain the range of the set is all of  the elements that you hit as you look at  the different possible elements of a so  all of the things that f hits the  standard notion of range of a function  um  so the range of s f has to be equal to b  you have to hit everything  um right uh  can you think of a one-to-one  correspondent says relabeling yeah i'm  not sure that's helpful but yes you can  think of as a re-labeling of the  elements in a sense but uh yeah  i just think of it as a matching up  um all right so let's move on um  so uh  coming out of this notion of sets of  being of the same size there was this  notion of countable sets as we'll see in  a minute um  so  let's do an example  let's take the set of natural numbers  you know one two three four dot dot dot  and the set of integers  which includes the natural numbers but  but also the negative numbers in zero um  so the  natural numbers are typically referred  to as n the  integers are typically referred to as z  and  how do we  what do we think of the relative sizes  of um  n and z  well n is a subset of z it's a proper  subset of c so you might at first glance  think that z is larger and they're not  really going to be of the same size  but it actually it turns out that  there's a very simple way  you know the arithmetic and the  properties of infinite sensor can be a  little bit surprising and there is a way  of matching up all of the elements of z  with elements their own elements of n um  and so you can show that as uh  following that definition that these two  sets are in fact of the same size so  let's just quickly go that goes make  sure you see that  um  so here is n  here is z i'm going to write down a  table which shows how they match up and  here's the function f of n that i'm  going to be describing that's the um the  one-to-one correspondence  and so here are the natural numbers  dot one through seven dot dot dot and  here are the elements of z that i'm  gonna be matching up this is how the  function is working so one i'm gonna you  know f of one is gonna be zero f of two  is gonna be minus one f of three is  gonna be one  um and i'm just giving you a way to  match up each of the natural numbers  with with integers  so that every single integer has its own  natural number and vice versa um  [Music]  so four goes to minus two five goes to  two six goes to minus three seven goes  to three and then minus four and then  four minus five then five and so on  you're clearly going to cover all of the  integers in this way and each of the  natural numbers is going to have its own  integer and there's never going to be  any collisions there's never going to be  two natural numbers assigned to the same  integer so this is meets the uh the  conditions of a one-to-one  correspondence and shows that the  natural numbers and the um and the  integers have the same size  uh following this definition um  okay let's do one that's slightly  more  complicated um and perhaps slightly more  surprising  which is that if you consider all of the  rational numbers  and um then they have the same that is a  collection even though the rational  numbers seem to be much richer and  more numerous than the integers from  this perspective they have the same size  and for the simplicity of my uh  my presentation i'm going to consider  only the positive rational numbers which  i'm going to write as q plus  so those are all of the positive  rational numbers that can be expressed  as a ratio of two natural numbers  and um i'm going to show that there is a  one-to-one correspondence between the  rations between these positive rational  numbers and and the natural numbers  okay so  um  here i'm going to again make a table  just as i did up uh up above um  so comparing the natural numbers and the  positive rational numbers  and  to do that i'm going to write down over  here on the side just to help you see  how i'm getting this table  a table a separate table that can that  has all of the rational number positive  rational numbers appearing you know in  kind of a nicely organized way um here  are all the rational numbers here that  have one as a numerator that have two as  a numerator and and so on and going  through across the columns the different  denominators  um so it's the the numbers inside here  represent all of the different rational  numbers and so whatever rational number  you have  m over n  um  that's going to appear down the nth row  in the nth column  that number is going to appear so  they're all going to show up  and i'm going to use this  table here to fill out this function  um  so uh  here are all the natural numbers and the  way i'm going to assign  the  rational numbers to appear over here is  i'm just going to work my way in from  the corner  and i'm going to do that by kind of  doing layers so first i'll take the one  in this  this number here in this corner then  i'll do these three that surround it and  then these guys that's around that and  these guys sort of in shells going  around the previous ones that i've  already covered  okay so  let me illustrate that  so here's one over one my first rational  number that i'm going to enter then to  the table  appearing right over there so next i'm  going to go 2 over 1  that's going to appear in the table over  there  now we have 2 over 2. now that's  actually a little bit uh problematic  because 2 over 2 has already been done  um and if we put that in  uh because 2 over 2 equals 1 over 1  they're both the equal to the rational  number one  so if we put two over two in this table  over here then we would no longer have  the one-to-one property because both one  and three would be mapping to the same  point um so we're just going to simply  skip over two over two  um  i'll show that as kind of graying it out  so we're not gonna  we're not gonna add that one onto the  table onto my function  um  so but so we'll skip over that we'll go  to one over two which is um has not been  seen before  and then we're just going to continue  doing the same thing now going to this  next shell out here  three over one  three over two  three over three  same thing i'm going to skip over that  one  2 over 3  1 over 3. i hope you're getting the idea  um so i'm not going to fill this  together i ran out of room to  put fill out this table some more but  just to look at how the process is going  to continue here i would get 4 over 1.  now 4 over 2  again is the number we've previously  seen because that's the that's the  rational number 2. we saw that up here  when we had 2 over 1 so we're going to  have to skip that one  4 over 3 four over four  that was going to skip  three or four and so on  okay so by uh following this procedure  i'm going to be able to define this  function now this function is not  particularly nice in terms of having a  an elegant closed form but it is a  the total legitimate function in the  sense of being a mapping from  natural numbers to  the positive rational numbers  and it has the one-to-one correspondence  property  so it pairs up each of the  natural numbers with each of the um  uh positive rational numbers um they  each get their own  mate in a sense and so that shows that  the rational numbers despite the fact  that they're dense and they have all  sorts of very sort of more much bigger  seaming they really and from this  perspective of the sizes of the sets  they have the same size as the  natural numbers do and so with that it  suggested  the following definition that a set is  countable  if it has the same size as the natural  numbers or it's finite  from this perspective we're going to be  focusing on infinite sets uh but yeah  countable or countably infinite  sometimes people say uh if it has the  same size as the natural numbers or  otherwise you have to include the finite  sets as well and countable means you can  just sort of go through the the sets the  the elements of the set kind of  as a list  so you can count them the first one the  second one the third one the fourth one  dot dot dot and once you can do that and  that counting is going to hit everything  then you know um you can match them you  can pair them up with the natural  numbers and so therefore you have a  countable set okay um  [Music]  so as we've shown  both z  the integers and the positive rational  numbers are countable sets  okay now  you might think that well since we're  allowing ourselves to do something as  arbitrary in a way as this kind of a  function  to match up the natural numbers with  whatever set you're trying to um  to measure  that every set is going to be countable  if you think about it that way because  it seems like you're allowing two too  too many possibilities and that all the  infinite sets are going to end up being  the same size as the natural numbers  well that isn't in fact is not true  um  and i don't know i i i  can't or as the one who discovered that  um i don't know if that was surprising  or not um but uh it is kind of uh  interesting i think that there are  different sizes of infinities um  and uh so uh we're gonna now take a look  and see uh that but i want to again um  i want to uh stop and make sure we're  all together can we always find a closed  formula for f somebody's asking me um  i don't know  for this particular f uh  you probably could but it would probably  be very messy um  um but in general that's not a  requirement  having a closed form for the for the  mapping function any function is allowed  as long as it's a one-to-one  correspondence  um  are we all together on this is this are  we comfortable with the notion of  some infinite sets  having the same size as the natural  numbers and therefore we're going to  call them countable sets and we're going  to show some other sets are going to  have um more elements they're going to  be uncountable they're going to be  beyond  strictly speaking strictly larger sets  in the sense that we won't be able to  put them into a one-to-one  correspondence with the integers um so  then the smallest infinity yes n is the  smallest um  smallest one so  any infinity is going to have um  you know you can always i don't think  you even need it you need a special  you know you can always  and whenever you have an  internet collection you can always find  a subset which is going to be  a countable subset uh so it's uh  and is going to be the smallest of the  infinities but there are bigger ones  all right why don't we move on  okay so um  the example of a set that we will show  is not countable an uncountable set as  we call it um is the  uh set of real numbers which you i  you know  we all know what these are i hope uh  these are all of the numbers that you  can express by possibly infinite decimal  representations like pi or e square root  of two  um or on any of the other familiar ones  you know um rational numbers are also  members of uh  are also count as real numbers and  integers too um  and so  uh but you know there are these  additional numbers that you can get by  uh  decimal expansions which may not be  rational  um  and that collection even though in some  ways it looks somewhat similar to the  rational numbers um the real numbers i  hope i said that right the real numbers  um uh the the uh which is the set i'm  considering here the ones with the  infinite decimal expansions they  actually are much larger  um  so  um  the theorem is and this was discovered  by kantor um that uh r is an uncountable  set  and the reason why i'm introducing this  is um besides that i think it's  interesting um  uh  and has some some relation uh to uh the  kinds of things we're doing but it's  really for the purposes right now is to  introduce this method called  diagonalization  um  okay uh that's we're gonna use later on  again but this is the first time it  appeared  so we're going to  use a proof by contradiction in order to  show that r the collection of real  numbers  is uncountable and we'll assume for  contradiction that r is countable  okay  um  so  if we assume that r is countable it  means we have by definition a one to one  correspondence from the natural numbers  to the real numbers  okay so we can match up  all of the natural numbers with  uh the real numbers in a one-to-one and  onto fashion so we can pair up the  natural numbers with the real numbers  and we will cover all of the real  numbers by doing that and we can make a  table  just like i did before  here it is  um  and you can fill this out with all of  the real numbers  and um  that was what the assumption means and  i'm going to show you that that's  impossible something is going to go  terribly wrong if you do that  um now uh  you might disagree you might be  surprised you might think well  uh professor sipser is wrong um you know  that i'm gonna work on this overnight  and forget the rest of my classes and  i'm gonna come up with a list of  uh all the real numbers i'm gonna fill  them out here and show that that's  impossible um so let's say  hypothetically just for my example's  sake um here is the list that you came  up with um  so you know you had to match up  something with the one let's say e had  to that was a special case so you're  gonna stick that with one and then pi  came out to be the number that you you  connected up with uh two you wanna see  what i'm doing here i'm making a list  i'm trying to make my one my  correspondence my matching up between  the natural numbers and my real numbers  that i'm hypothesizing to exist for a  contradiction  so three  i i don't know three is gets connected  to zero i'm making this up obviously uh  not on the spot i wrote the slide you  know uh yesterday but uh here's a square  root of two showing up for whatever  reason here is one seventh  here is some other number which i'll be  interested if you recognize that one  that's a that's a subtle one um  this is one point two three four one  point yeah some some familiar looking  sequence here and whatever it is  whatever it is this is what you came up  with you claim that this is to work as  uh very good you somebody got it  it's i to the eighth power but let's not  get hung up on that please um  i to the either power oddly enough can  be seen as a real number under you know  if you define the uh  imaginary exponentiation  uh which is weird but anyway  let's uh let's not get too distracted um  so here's my list of numbers my real  numbers that i've matched up in my table  here with the natural numbers  now something's go i claim something  goes wrong what goes wrong i'm going to  show you that you actually  uh did not  do as you claimed  that there's actually um at least one  number that's missing from this list and  i'll exhibit that number i'm going to  show you what that number is i'm going  to explicitly come up with a number and  show you that there's that number it's  missing from the list um so here  it's going to be a number x  x is the x is the one that's missing  so how am i going to get x  so x well i'm going to start it off with  zero point and then i'm going to fill  out the rest of the places and how am i  going to get those places i'm going to  look at the table here  so i want to look at to get my first  digit after the decimal point of x  i'm going to look at the first digit  after the decimal point of the very  first number  so i take the first number look at the  first digit after the decimal point  and which happens to be a 7  and the number i'm going to put in for x  is not going to be 7 it's going to be  anything except 7.  let's say  8. um  for my next digit of x  i'm going to look at  so my second digit of x i'm going to  after the decimal everything's going to  be after the decimal point now uh so i'm  not going to keep saying that i'm going  to look at the second digit of the  second number uh which is a four  uh after the decimal point um  uh  there it is  and for the second digit of x i'm going  to use something which is  anything besides four five  i have some flexibility here um so i  could have used six i could have used  seven  i'm going for those of you who have seen  this before who are gonna nitpick on me  i'm gonna stay away from nine and zero  just because there are some little um  edge cases that arise there which i  don't want to get into because i don't  think it's interesting for this argument  um but since i have some flexibility i'm  going to avoid zeros and nines probably  just nine is all i really need and then  um  the argument is just going to work fine  okay  so uh the next digit is a zero  uh for the third digit of the third  number is a zero the third digit of x is  going to be anything except for zero be  a one  then i have a two here  anything except a two  six  uh then five anything except a five a  one a nine anything except a nine an  eight  and so on there's an eight  there's a two and dot dot dot i'm just  gonna keep doing that  and i'm gonna say  you missed that number whatever it is  but that number it's a that's a number  after i'm all done it's going to be the  decimal representation of something  and that number uh i claim  is absent from the table  and you might say well  you know it's really there  um it's just on the  um  23rd row  you just didn't get to it on your slide  but it's there well i'm going to say i  know it's not in the 23rd row because it  differs from the number in the 23rd row  at the 23rd digit  because i constructed it that way  this number is designed  explicitly to be different from each of  the numbers that's on the list  okay so it can't be on the list because  it's been constructed to be different  from each of them in at least one place  so it's i think this is a beautiful  argument and it shows that  uh no matter how you try to come up with  a one-to-one correspondence you're going  to fail you know you might say oh you  know like  you know just one number you know it did  so much hard work and missing just one  number can i get partial credit  you know and put this one on the list  now i fix it no obviously there are many  many numbers that are missing if you put  this one on the list i'm going to  construct another number that was  missing  so  um this is uh  you know  there's just not no possibility of  fixing this and in fact you know the um  the real numbers are  are uncountable cannot be matched up  with the natural numbers and there's  nothing  it can't even come it doesn't even come  close um  so um  here's summary what i just said  um f is not a one-to-one correspondence  no matter what you try to do you can't  come up with a one-to-one correspondence  so that's the contradiction  okay so that proves that  r is uncountable  okay and that's why by the way we call  this a diagonalization because we're  going down this diagonal here that's  where the term that's where the name has  come from  okay um  so i i'm happy to  okay that's it uh  somebody's asking me  i'm actually i have a  um  is it here i can't remember it's here i  have a uh check-in coming about this and  somebody is kind of um anticipating that  by asking uh the the actual rather  famous question about there being a  possible infinity in between  the natural numbers and the real numbers  we know the real numbers now are bigger  than the natural numbers but is there  something that's in between i mean this  is a very very famous problem um  uh which i'll talk about you know when  we get to our check-in which is coming  up  um  well somebody is objecting just the way  i've defined x using this procedure that  really really can't in a sense state  you know but it x is a number x is the  result of  what what this procedure is it's you  know following this procedure we're  converging on some particular value and  so that is the value um if you want you  know we can make a more precise way of  determining i mean i so i we don't have  the flexibility of choosing the way i  did in my example we can make a precise  procedure for coming up with these  digits but  i don't think there's anybody thinks  there's anything  that's um  there's any shortcoming in this argument  in terms of the way we're defining x  it's i i think it's worth understanding  this  because it's really going to set the  groundwork for our proof that atm is  undecidable which is a little i think  perhaps slightly more abstract in a way  um in the way it sort of comes across  i'm going to try to can make connect the  two  but uh i think it's helpful to  understand at least this argument  because this argument is kind of  diagonalization in its kind of most  raw form  all right i think we're good um so let  why don't we continue then um  so there are a number of corollaries  that follow from the statement that the  real numbers is uncountable um  uh  first of all if you let script l be the  collection of all languages if you want  to consider over some particular  alphabet that's fine but that's not  going to be really uh  you know important for this uh  point that i'm trying going to make so  uh l  uh script l is the collection of all  languages um so every subset  of sigma star  every subset of sigma star is a language  um so look at all those possible subsets  um so that includes you know 0 to the k  1 to the k plus every other language you  can ever think of and more all possible  languages  um so that  the collection of all languages is  uncountable  there's uncountably many different  languages out there  i don't want to belabor this point you  can just take this if you don't quite  follow the the quick argument i'm going  to make here but um  uh you can make a correspondence  one-to-one correspondence from all  languages to the reals  so that each language gets its own real  number  and the way i'm going to think about  that let's put the real numbers into  binary form  and if you imagine here being sigma star  all of the possible strings of sigma  star  you know written out in their standard  order  um and now if you have a language here a  it's just some arbitrary language so  that's going to have some of the strings  of um of sigma star appearing like zero  is appearing but one is not appearing  zero zero is appearing in zero one but  not these three  um and i'm gonna associate to a  my language  some real number in binary by putting in  a zero in the decimal representation or  the binary representation i should say  um  for that  string  if it's not there and a one if it is  there  um and so a real number because there's  infinite many infinitely many yes no  choices  in the binary representation can  represent a language because of each of  the yes no choices of a string being  present or not i'm going to put a one  for when the string is present the zero  when it's not present so each  uh language has its own real number and  each real number is going to be  associated to its own uh language here  i'm restricting myself to real numbers  between zero and 1  that's not going to be an essential  point so let's not get hung up on that  so  [Music]  the  the fact that  the  the languages can be  uh  put into one-to-one correspondence with  the real numbers  um  shows that the collection of all  languages is also uncountable  now another  observation here another point worth  noting is that if you look at sigma star  itself  the strings  uh all possible strings that's a  countable set  the collection of all possible languages  is uncountable but the collection of all  possible finite strings  is countable because i can just list  them  here is my list of all possible strings  which you can put into a table if you  like to think of it matching up with the  natural numbers in that way  now i'm get i'm trying to make a point  here which is that  if you take am which is all possible  turing machines script m is all possible  turing machines the collection of all  possible turing machines is countable  there are only countably many different  turing machines  and you can argue that in all sorts of  messy different ways but i think the  most simple way to see that  is to think about each turing machine as  having a description  which is a string  so the collection of all descriptions of  turing machines is just a subset of  sigma star which we already know is  countable  and the subset of any countable set is  going to be countable  so  anyway  i think it's worth  remembering  that  the collection of all turing machines is  countable  um whereas the collection of languages  is uncountable and that tells you right  there  that some language is not decided  because there are more languages than  touring machines  we have uncountably many language only  countably many turing machines so that's  fewer turing machines than languages  there's no way to map all the languages  onto turing machines so there's going to  always be some languages that got  unmapped  um and so in particular there are going  to be some languages which are  undecidable there are going to be some  languages which are not touring  recognizable  and anything based on some automata kind  of um  definite definition process is going to  be some languages that you're not going  to be not going to be defining  um  okay now what this corollary shows you  that there is some language out there  which is not decidable what we're going  to show next is that there is a specific  language atm which is not decidable  okay and but first i think we have a  check-in coming up  and  let me give you a little bit of  background here because this is relevant  to this question that i got  about intermediate sized sets so  the question of whether there is a set  of size between the natural numbers and  the real knit numbers  strictly in between so bigger than the  natural numbers not the same size as the  natural numbers but not the same size as  the real numbers either  um but in between uh in size  um  that was hilbert's question number one  out of his list of 23 that i talked  about a few lectures back  it's interesting that he put it as  number one in that very privileged  special place  because i know hilbert was very  he felt that the understanding infinity  was a really central issue in  mathematics and that if we can't answer  a question like this we don't really  understand infinity um  uh you want to understand what kind of  sizes of infinities are there um we know  there's the real numbers bigger than the  than the natural numbers is there  something in between so fundamental  really um  but uh it was shown uh during the course  of the 20th century really in two  separate steps one in the 1930s by  girdle one in the early 1970s by cohen  that we can't answer this question by  using the standard axioms of mathematics  you know it's  the the answer can go either way  and it's both of them are consistent  with the axis of mathematics so you're  never going to be able to prove  that there is a set whose size is in  between  or that you or that there is no such set  it's just impossible to prove either  direct either way  using the standard axiom in mathematics  which actually is kind of remarkable um  and so my question for you is and this  is really a philosophical question not  one that um is directly and you need to  know about material in the course just i  think it's just a matter of your own  interest i hope you find it interesting  if you don't you pick a wren you can  just answer it randomly um  but um  what's going on here that we can't  answer that question about whether there  is a set of intermediate sides is it  because our axioms for mathematics are  inadequate  or  maybe there is no such thing as a  mathematical reality you can talk about  you know you know what's what's real  here what what what's the reality either  there is a set in between or not  if you imagine all of these things have  their own reality to them well then  there's going to be an answer and then  you would expect well maybe we could  find better axioms which will actually  give us that answer or you can say well  there is no reality  and um  you know it  infinite sets are kind of human  constructs anyway so we can make them  kind of play out any way we like  mathematicians argue about that to this  day um  and um it is as i say really it's a  philosophical question but just out of  curiosity let's see how you guys end up  uh deciding on that one um so here's the  poll  five seconds to go please vote  and uh we're going to end the polling  one two three now  all right here we go  so there's no right answer  um  i think if most mathematicians were  to um  i think the instinct of most logicians  especially i'm not sure our general  mathematicians really even care about  this question but logicians um  would probably have an instinct that  probably there are sets in between  there's no reason that there shouldn't  be  um  you know it seems kind of strange that  there should be this sort of jump uh  from the  natural numbers to the real numbers and  why nothing in between um  but um  it's uh  i don't think that question is really  settled  so  all right let's continue on i think we  are  um okay so we're gonna  um  a coffee break is coming in case you're  wondering so this is on my last slide  before then but this is an important  slide so please uh hold hold out  um  so here is our  uh promised theorem of the day  i'm going to show that atm is not  decidable the acceptance problem for  turing machines  and it's all going to be contained on  this one slide we're going to give a  proof by contradiction using  diagonalization  and we're going to assume some turing  machine h decides atm  and we're going to get a contradiction  so let's first of all make sure we  understand what h is doing  so h gets an input a turing machine and  an  input and h is going to be a decider so  it always halts  with an accept or a reject  it's supposed to accept if m accepts w  and reject if it doesn't so in other  words it's going to reject if m rejects  w either by whole by halting or by  looping  that's the job of h  and we're assuming we can do that  but we will see a contradiction occur  so the way we're going to do that  is is really kind of just one step here  in a way and we're going to use h to  construct another turing machine d  h is going to be a subroutine to d  we've already seen us doing that in the  past  d is going to do something a little  strange  just to just to warn you um  these input is just a turing machine no  in no w  and  what  d is going to do  using its subroutine h  is going to simulate h  on input  m comma the description of m now what is  that  well the description of m is just some  string  so what h is trying what it's asking h  uh to tell to answer is does m  accept  the string representing m's own  description  it's as if we're feeding m into itself  which seems like a totally twisted thing  to do  um  you might say  uh  you know  why would you ever feed a program into  itself  somebody's written cannibalism here  yeah kind of uh i said it's it's worse  because it's  not eating somebody else it's eating  himself  okay but  um  i claim  that we actually there are actual cases  in practice  where we do this  we feed programs into themselves  and uh the example that i know of where  this is done  is when you're making a compiler  you might want to make a compiler and  then written in the same language that  it's compiling and then you feed the  compiler into itself  they may say why even bother because  it's already obviously if once it's  running you don't need to  compile it again um but actually you  know an example where this was really  used  was when there was an optimizing  compiler i think for c uh written on  early unix machines  and the optimizing compiler for c was  written in c  so you would feed the optimizing  compiler  into the regular compiler first of all  now you had the um  compiler running  but it was unoptimized  so but now that it's the optimizing  compiler is running  you can feed the optimizing compiler  into that which is itself now you have  an optimized optimizing compiler  so it really makes  some there is a at least one case where  this has actually been done uh in  practice  um not that we really care this is a  theory class but just for fun to observe  that  so here h is trying to say well does n a  m end up accepting when it's fed  the description of itself  you know at least mathematically  speaking that's a reasonable uh thing to  ask  and then what  d is going to do when it gets the answer  back from h  h as a decider don't forget  is d is going to do the opposite  whatever h does it's going to accept if  h rejects and rejective h accepts  um so let's in summary let's pull this  together some  you know it's easy to understand in the  end what is d doing  d is going to accept d is also going to  be decided by the way so d d is always  going to either accept or reject  just the opposite of what h tells it to  do so d is going to accept  m  exactly when m doesn't accept m because  you know when m doesn't accept m  h is going to reject  um and so then d is going to accept so d  accepts m if and only if m doesn't  accept that that's exactly the condition  in which d accepts it  i think it's important to just step back  and make sure you understand this line  because we have only one line left  to get our contradiction  right are we together d accepts m if and  only if m doesn't accept m that's just  by the that way we've defined setup d  now  what we're going to do is feed in  instead of m to d and not some arbitrary  fee  we're going to use feed in d into d  and that is going to be our  contradiction because d is now going to  accept d if and only if d doesn't accept  e and that's certainly impossible  okay  that's our contradiction which proves  that h cannot exist and therefore atm is  undecidable  okay so we're done  except for the one point which is that  um  why is this a  diagonalization  and i think you can get that from the  following picture  if you imagine here writing down all  possible time i'm making i'm going to  make a table here here is a list of all  turing machines  okay uh including d which is a machine  which i  built  under the assumption that h exists so d  appears here somewhere but here are the  all the other turing machines and here  are all these descriptions of the turing  machines along the uh labeling all of  the columns  okay so these are the rows labeled these  are the column labels and inside i'm  going to tell you  uh the answer for whether a given  machine  accepts a given input  so for example m1 accepts its own  description but rejects the description  of m2 but accepts the description of m3  i don't know you know i'm obviously  making this up i don't know what m1 is  but just hypothetically that's what the  machine m1 does  um so i'm just filling out this table  and you know this is  d  uh h could get the answer to any of the  elements in this table because it can  test whether m4  um accepts the description of m3 so it  could h could fill out this table  so maybe m2 is a machine that always  rejects it's a very unfriendly rejecting  machine  m3 is a very friendly machine it accepts  all inputs and for its reject sum and  accepts other dot dot dot  now i want to look and see what does d  do  um  now based on the information i've  already given you we can understand what  d does  so for example what does d do when i  feed it the description of m1  what does d do  well we can look over here d accepts m  if and only if m doesn't accept m so d  is going to accept  um  m1 if and only if m1 does not accept m1  well m1 does accept m1  so d  does the opposite d rejects  so okay i'm highlighting here  d rejects because it's going to d is  going to do the opposite of what the  machine does on its own it on input  um so m2 on so d on m2 you have to look  what m2 does on m2 it rejects so d does  the opposite of that it accepts  and similarly  uh  you know all each one of these things  these answer is going to be the opposite  of what the machine does on its own  description  um just by virtue of the definition of  date  okay and so on so far so good  but the problem is what happens when d  is fed itself  because as you can see  you know um we're we're heading for  we're heading for trouble because this  is a diagonal down here  d is just one of the rows that diagonal  is going to  intersect that row at this point  and d is defined to be going to be doing  the opposite of what that element is but  it can't be the opposite of itself  okay and so that's that's the  contradiction  so i think you know where um  uh  i i'm gonna call us give us a little  break here um and then you can also text  me in the meantime we'll be happy to  answer some questions during during that  a little over four minutes to go so  let's see let me see if i can  answer your questions  okay what's so special about atm that  enables us to do this why can't we do  this on adfa for example  um so that's a good question i i i  and  the answer is that um  you know  you know in a sense  you know we can do this on dfa i mean i  i think this is perhaps a bit bit of a  stretch but you know dfas could not  answer adfa i mean we could prove that  in other ways as well you know by uh  because  you know we could use things like the  pumping lima and it's not clear even how  you formulate adf8  but what's important here is that the  um it's really the model talking about  itself  um that really is where the problem  comes up  so if you try to push this argument  through to show that adfa is not  decidable by touring machines you're  gonna fail  um  because you know we're starting off with  a turing machine and um i mean  i think i'm gonna confuse myself if i  try to just repeat it but um you're you  won't get a contradiction because the  turing machine is not a find out  automaton  um  okay um  will this argument get into self loops i  don't see why there was there is some  self-reference perhaps we're going to  talk about that a little later because  we're going to come back and revisit  this argument um  you know in a  in a week or so when we talk about the  recursion theorem which talks about  machines that can refer to themselves  but this is a little bit of a head  getting ahead of ourselves so  uh somebody's commenting on this  reminding them of the barber paradox if  you remember that the  which has some similarity you know the  there's a town in which uh there is a  barber which shaves every man who  doesn't shave themselves  which seems you know he's a very good  barber so there's some people who shave  themselves  and  all the rest the barber shavers uh the  question is does the barber shave  himself because he shaves only those men  who don't shave themselves so you got a  same kind of a contradiction there is a  there is a relationship there  um  so somebody wants to know where did we  use the decidability so we used the  decidability to come up with h  um  you know once we know that atm is  decidable then we have that h function  and then we can build d  um so that's where that's the the the  chain of that's the chain of reasoning  um  so you assume atm is decidable then you  have the decider  and then  called h and then you can build d um  somebody wants to see the previous slide  well  uh what part of this one do you want  uh  so i'll leave that up there why can't we  why can't we apply the proof that all  touring machines are countable to all  languages well because turing machines  have descriptions  languages general languages don't have  descriptions  and so that's uh why okay the candle has  burned to the to the bottom and it's  time to move on um  so now let's look at the  uh acceptance problem for kuwatama  i'll give you a q automaton an input  and i want to know does it accept the  input is that going to be decidable  and you have you have your choices it's  either yes  it is decidable because these are  similar to put down automata and apda is  decidable  or no because yes would con contradicts  results that we know at this point or we  don't have enough information to answer  the question  okay let's put that up  one second  all right  that's it ready going gone  uh so  yes the answer is uh well no  the answer is the indeed the answer is b  um  uh true that uh cubitamina are similar  to push on automata but all these atomic  are kind of similar to each other and  that's not going to be good enough  uh  well the homework has asked you to do is  to show that you can simulate turing  machines with q automata  so if you can answer the question about  whether the queue automata uh will  accept their input that would allow you  to be able to answer questions about  whether turing machines accept their  input and we just proved that's not  possible  so um  uh  it would get it be a contradiction if we  could answer  uh if we could decide a qa  now we have an example of an undecidable  language let's look at an example of an  unrecognizable language  now atm is not going to serve  that purpose because atm  um  [Music]  is  um  recognizable is turning recognizable as  we pointed out by the universal turing  machine  so uh atm is undecidable however how  about an unrecognizable language  for that we will see that the complement  of atm  will serve so the complement of atm  is  neither decidable nor even recognizable  that's not turing recognizable  and that's going to follow from a pretty  basic theorem that connects  recognizability and decidability that i  put up here on the screen  which is that if you have a language  where it and its complement are both  recognizable then the language turnout  turns out to be decidable in fact the  language and its complement are decided  but but being decidable is closed under  complement so that's something you  should be aware of  um  but being uh okay  we'll get to that in a minute but  uh if um  uh  so anyway so we have a language and it's  complement both recognizable how do we  know the language is decidable so first  of all let's take the two turing  machines m1 and m2 that recognizes a and  a complement  and we're going to put those together  to get a decider for a  um  and that's going to work like this  it's going to be called t  so t says on input w what it's going to  do  it's going to feed w into m1 and m2 both  um a is a language by the way yes a is  when i'm telling you when i say it's  touring recognizable you know turing  recognizable only applies to languages  so so yes a um is often this symbol i'm  going to use for languages sometimes for  an automaton but  a is typically going to be a language  so um  [Music]  if uh so  now i'm trying to make t  be a decider for a  from the recognizers for a and a  complement  so i'm gonna  take an input to t  and feed it into both recognizers m1 and  m2  okay i'm going to run them in parallel  what's nice  is that because  um  m2 is a  recognizes the complement of what m1  recognizes  every string is going to be accepted  either by m1 or by m2  because every string is either an a or  an a complement  so if i run m1 and m2 on w until one of  them holds one of them accepts i know  i'm not going to run forever because  eventually one of the other ones have to  accept  so and then i got my answer because if  m1 accepts that i know i'm in the  language but if m2 accepts i know i'm in  the complement of the language no matter  the language so if m1 accepts then t  should accept if m2 accepts then t  should reject  um  now  so that proves that  nice little theorem uh written at the  top in blue  um so i got my decider for a  built out of the recognizers for a and a  complement  now immediately it follows that  the complement of atm is not touring  recognizable  because  we know  that atm itself  is recognizable but it's undecidable  if its complement were also on recognize  if the complement was also recognizable  then atm would be decidable but it isn't  so when something is  undecidable either it or its complement  have to be unrecognizable and in the  case for atm it has to be the compliment  because we already showed that it is  itself is recognizable  um  so that's the proof of that so here is a  little picture of the way the world  looks right now if you have here in the  middle of the decidable languages see  these are all languages here this venn  diagram of languages kind of we showed  earlier you know like the regular the  context free decidable recognizable  here i've got the recognizable and what  i'm calling the co  co code touring recognizable  this is the collection of all  complements  of recognizable languages so atm  bar atm complement is the complement of  a recognizable language this uh  region here is are all the complements  of the recognizable languages or the  so-called  co-turing recognizable languages  complement of  so atm is on this side atm complement is  on that side but if something's in both  by virtue of this theorem here then it's  decidable  okay  last check-in for the day  um from what we've learned so far  um which closure properties can we prove  for the class of  the touring recognizable languages  choose all that apply  well as i say  you don't have to get it right let's  let's not spend too much more time on  this because we'll we'll we'll talk a  little bit about it  um  almost all it's closed under almost all  of them but not all of them  because you know  are we done here i think we're done  five seconds  okay here we go ending polling  i'm not sure what the meaning of  the leading answer is here uh everybody  likes union i guess they're closed under  all of these operations except  complement so  um  but we just proved it's not closing the  confidence i'm a little  you know a little puzzled by why we have  so many votes for closure under  compliment  uh we have here atm  is touring recognizable but atm  complement is not touring recognizable  so right here on the slide  so i'm not trying to make you feel bad  but uh  um i'm trying to  just point out that you  think please um  so  um  now closure under union and intersection  i mean you could kind of get those  answers just by running things in  parallel the way we did the proof here  you just run both machines  and  if they both  give i mean it's a little tricky i  suppose you know if if if either one of  them accept um  then you can accept or if they both  accept you just wait until they both  have accepted otherwise you just keep  running um so the first two are pretty  straightforward um closure under  concatenation is also going to be  similar you just try every possible way  of cutting uh the string up into two  pieces  and run in parallel on and if you ever  find a way  of cutting it up and you run those two  and those two sides in parallel and if  they both um accept  um then uh then you can accept and star  is again very similar so there these are  not too bad um but i admit you know it's  not a whole lot of time to i have to  contend with something uh that you're  just getting uh used to  so let's um  uh  let's talk about the very last topic of  the day which is really going to be  setting ourselves up  for um tuesday's lecture next week um  and that's  how we are going to be showing other  languages are undecidable which is  something that  um i'm going to be expecting you guys to  be able to do um  this is um  the standard procedure for showing  languages are undecidable using what's  called the reducibility method  um  and what that does is it  takes as a starting point a language  that we already know is undecidable  typically atm  or it could be another one that you've  previously shown to be undecidable and  leverages that information to show other  languages are undecided  and um  it's using what's called reducibility  we're going to go into this  more carefully next time  but basically reducibility is a way of  using one problem to solve another  problem  and so we're going to show for example  uh let's take a look at the problem  called the holding the halting problem  which is like the famous problem for  turing machines um  uh you just want to know whether it  holds not necessarily whether it accepts  so it's very similar but not exactly the  same  and we're going to show that  this halting problem is similarly  undecidable now we could go back and do  the whole diagonalization but that seems  like  well that's more work than necessary now  that we already know atm is undecidable  because we're going to show that we can  reduce the atm  problem to the hold holding problem um  and we'll explain what that means again  uh later but um the idea is and as as  we'll show in an illustration uh shortly  that  by proving by contradiction um  if the whole thing if halt tm  were decidable then atm would be  decidable  and we know atm is not decidable and so  um  that's our contradiction  now  uh  the way we're going to show that if  whole team is decidable than atm is  decidable  is use a decider for whole tm to decide  atm with a suitable  um  you know uh  uh  modification  so basically we're gonna turn  and hold tm decider into an atm decider  and that's  how we're going to reduce the problem of  solving atm to the problem of solving  halt tm  let's just do an example like you know  if you've seen it before obviously this  is not going to be hard but for the many  of you who have not seen it before i it  i'm partly doing it this time just so we  can do it again next time and maybe  it'll sink in by virtue of repetition  so  um  so again so as i just said we're going  to assume the whole tm problem is  decidable and use that to show that atm  is decidable which we know is false we  showed it just earlier that it's not  so assume we have a decider for whole  team we'll call it r  and we're going to construct from our  decider for atm we'll call s  okay so we're again typical proof by  contradiction we're assuming the  opposite of what we're trying to prove  and then we're going to get something  crazy  okay so here my job now is i'm assuming  i have r which is a whole tm decider so  now i'm assuming i know how to  decide  if a turing machine and an input  eventually halts  not necessarily except just whether it  holds  you know it's conceivable you know you  have to bear with me here it's  conceivable that you could find a way to  test whether  you know turing machines halt on their  input even though we now know that  testing whether they accept their input  is not decidable  so you have to kind of be open-minded to  the possibility that we can  that the whole problem is decidable and  we're going to show that that's can't be  so we're going to show that  if we could decide the whole thing  problem then we can use that to decide  the uh the acceptance problem  okay so how do we how do we going to do  that so imagine now we can solve the  halting problem  so to solve the atm  which is what my job is  to do  so s is supposed to solve atm  i'm constructing two  machine as the site atm  i'm going to use first i'm given an mnw  i'm going to feed it into r since that's  really all i got  see if r  tells me  what happens  does m on w at least hold  well if r says no it doesn't hold  well then then i'm actually done  because if it m doesn't even hold on w  then it couldn't be accepting w so at  that point i know that m doesn't accept  w and i can reject right  off  so our you can see how it could  potentially be helpful but it's going to  be helpful in either way because if r if  r says m  does hold  well then i'm also good  because i don't know the answer yet but  what i do know is i can now simulate m  on w  until it holds because r has told me it  holds so i don't have to worry about  getting into a loop  um  uh so s can be confident in being a  decider for whatever it's doing um  because i'm running uh now m on w with a  guarantee that it holds  um  and now that going to tell me now  eventually the simulation of m w is  going to end up at an acceptor reject  and that's going to be the answer i need  so if m is accepted then accept and as m  is rejected then reject  and that's how s solves the atm using r  which which solves whole tia  but s can't exist  and so therefore r can't exist and  therefore whole tm can't be decidable  okay  so that quickly  um  okay  i'm not sure which diagram you wanted me  to show but anyway maybe we can do that  we're basically at the end of the hour  or end of that 90 minutes so let's do a  quick review and if you stick around i'm  happy to go back and look at any of the  other slides uh that you might have  missed something on  okay so just to recap we showed that  uh the natural numbers of the real  numbers are not the same size using that  definition of one-to-one correspondence  to introduce the diagonalization method  we use the diagonalization method to  show that atm is undecidable  we also showed that little theorem that  if the language and its complement are  recognizable then the language is  decidable  and from that we conclude that atm  complement is not recognizable  and then we showed at least by virtue of  an introduction to the method the  reducibility method to show that whole  tm is undecided  okay and that's that that was today's  lecture and we're and we're uh  at the end of the hour so why don't i um  you know we are finished uh you can uh  log out um and if you want i will stick  around  okay  okay this is kind of a good question  here  [Music]  so i'm getting a question about the  atm complement  which is uh you know since we have a  a recognizer for atm  uh if i'm doing justice to this uh  question uh we have a co we have a  recognizer for atm so why can't we just  invert the answer  you know  flip flip the answer around and now we  have a recognizer for  the complement of atm atm complement  so why doesn't that work  well the reason that doesn't work  is because  the recognizer for atm  might be rejecting some things by  looping  and now if you just flip  the accepting and rejecting  um  when it hits one of those uh holding  states it's going to give the reverse  answer  but the uh when it uh  rejects by looping it'll continue to  reject by looping so you won't get the  complementary language coming out  so you know if we want you know if we  would be helpful i can go back  to that uh slide here  um  which proves that atm complement is  unrecognizable  because  maybe we should start with the bottom  we know that atm  is recognizable and undecidable  right we already proved those two facts  atm is recognizable  from the um universal turing machine  and it's undecidable by the  diagonalization argument  those two things together  tell us that the complement has to be  unrecognizable  because  if a language and its complement are  both recognizable and we already know  the language itself is recognizable  so now if the complement is also  recognizable the language is going to be  decidable by the upper theorem  so it must be the case that either the  language itself is unrecognizable or its  complement is unrecognizable  we know the language is recognizable  that's what the universal turing machine  told us so the only thing left is for  the complement to be unrecognizable  you should review that if you didn't get  it um because  this is a kind of  you know  kind of reasoning we  you know we're going to be building on  things like that so i think it's good  good to make sure you understand  okay um  okay the diagram on the right so this is  just a venn diagram here  kind of threw this in at the last minute  here i was worried about it being  confusing  you know that part is um  you know so you know i'm trying to show  that the three classes that we've  already talked about  the languages which are decidable the  languages which are touring recognizable  and the languages whose compliments are  going recognizable those are three  separate classes of languages  and  those come up here in those three  regions  these are the decidable ones  here are the recognizable ones  and here are the ones whose compliments  are recognizable  now if a language  is in both  recognizable and its complement is  recognizable so it's in both of these  bigger regions here  then this theorem tells you it's  decidable  so that's why  the intersection of these two regions is  marked as being decidable because that  means you're in both  okay  but we know that atm is sitting out here  as recognizable but not decidable so atm  is in the recognizable side but it's not  on the complement of recognizable atm  itself um  the complement of atm is the complement  of a recognizable but itself is not  recognizable um  and uh  not decidable so you get this side of  nice  you know  [Music]  i hope it's you think it's nice but it's  a sort of uh trying to summarize things  in this in this field diagram  so i think i'm going to then uh  sign off  and um  i'll see you all on  tuesday and have a good weekend bye-bye

4
00:00:31,750 --> 00:00:33,910

 

5
00:00:33,910 --> 00:00:37,270

 

6
00:00:37,270 --> 00:00:40,549

 

7
00:00:40,549 --> 00:00:43,030

 

8
00:00:43,030 --> 00:00:46,549

 

9
00:00:46,549 --> 00:00:50,389

 

10
00:00:50,389 --> 00:00:52,310

 

11
00:00:52,310 --> 00:00:54,310

 

12
00:00:54,310 --> 00:00:54,320

 

13
00:00:54,320 --> 00:00:55,510


14
00:00:55,510 --> 00:00:58,470

 

15
00:00:58,470 --> 00:01:00,470

 

16
00:01:00,470 --> 00:01:02,790

 

17
00:01:02,790 --> 00:01:05,030

 

18
00:01:05,030 --> 00:01:06,870

 

19
00:01:06,870 --> 00:01:08,390

 

20
00:01:08,390 --> 00:01:10,469

 

21
00:01:10,469 --> 00:01:11,750

 

22
00:01:11,750 --> 00:01:13,590

 

23
00:01:13,590 --> 00:01:16,070

 

24
00:01:16,070 --> 00:01:16,080

 

25
00:01:16,080 --> 00:01:17,030


26
00:01:17,030 --> 00:01:20,149

 

27
00:01:20,149 --> 00:01:22,310

 

28
00:01:22,310 --> 00:01:25,670

 

29
00:01:25,670 --> 00:01:27,190

 

30
00:01:27,190 --> 00:01:30,149

 

31
00:01:30,149 --> 00:01:31,749

 

32
00:01:31,749 --> 00:01:34,230

 

33
00:01:34,230 --> 00:01:37,510

 

34
00:01:37,510 --> 00:01:37,520

 

35
00:01:37,520 --> 00:01:38,230


36
00:01:38,230 --> 00:01:41,190

 

37
00:01:41,190 --> 00:01:43,670

 

38
00:01:43,670 --> 00:01:45,670

 

39
00:01:45,670 --> 00:01:45,680

 

40
00:01:45,680 --> 00:01:46,870


41
00:01:46,870 --> 00:01:49,030

 

42
00:01:49,030 --> 00:01:51,109

 

43
00:01:51,109 --> 00:01:54,149

 

44
00:01:54,149 --> 00:01:55,990

 

45
00:01:55,990 --> 00:01:57,830

 

46
00:01:57,830 --> 00:01:59,670

 

47
00:01:59,670 --> 00:01:59,680

 

48
00:01:59,680 --> 00:02:00,469


49
00:02:00,469 --> 00:02:03,109

 

50
00:02:03,109 --> 00:02:05,270

 

51
00:02:05,270 --> 00:02:07,510

 

52
00:02:07,510 --> 00:02:09,990

 

53
00:02:09,990 --> 00:02:13,430

 

54
00:02:13,430 --> 00:02:15,910

 

55
00:02:15,910 --> 00:02:17,670

 

56
00:02:17,670 --> 00:02:17,680

 

57
00:02:17,680 --> 00:02:18,550


58
00:02:18,550 --> 00:02:18,560

 

59
00:02:18,560 --> 00:02:19,670


60
00:02:19,670 --> 00:02:21,430

 

61
00:02:21,430 --> 00:02:22,869

 

62
00:02:22,869 --> 00:02:24,949

 

63
00:02:24,949 --> 00:02:27,030

 

64
00:02:27,030 --> 00:02:28,309

 

65
00:02:28,309 --> 00:02:30,869

 

66
00:02:30,869 --> 00:02:33,750

 

67
00:02:33,750 --> 00:02:36,390

 

68
00:02:36,390 --> 00:02:38,070

 

69
00:02:38,070 --> 00:02:39,990

 

70
00:02:39,990 --> 00:02:41,910

 

71
00:02:41,910 --> 00:02:43,509

 

72
00:02:43,509 --> 00:02:46,229

 

73
00:02:46,229 --> 00:02:47,990

 

74
00:02:47,990 --> 00:02:48,000

 

75
00:02:48,000 --> 00:02:49,430


76
00:02:49,430 --> 00:02:49,440

 

77
00:02:49,440 --> 00:02:51,430


78
00:02:51,430 --> 00:02:53,509

 

79
00:02:53,509 --> 00:02:55,270

 

80
00:02:55,270 --> 00:02:58,790

 

81
00:02:58,790 --> 00:03:02,229

 

82
00:03:02,229 --> 00:03:02,239

 

83
00:03:02,239 --> 00:03:03,350


84
00:03:03,350 --> 00:03:05,670

 

85
00:03:05,670 --> 00:03:06,790

 

86
00:03:06,790 --> 00:03:08,390

 

87
00:03:08,390 --> 00:03:10,710

 

88
00:03:10,710 --> 00:03:12,790

 

89
00:03:12,790 --> 00:03:14,390

 

90
00:03:14,390 --> 00:03:16,630

 

91
00:03:16,630 --> 00:03:19,110

 

92
00:03:19,110 --> 00:03:19,120

 

93
00:03:19,120 --> 00:03:19,910


94
00:03:19,910 --> 00:03:22,869

 

95
00:03:22,869 --> 00:03:26,070

 

96
00:03:26,070 --> 00:03:26,080

 

97
00:03:26,080 --> 00:03:27,670


98
00:03:27,670 --> 00:03:30,789

 

99
00:03:30,789 --> 00:03:32,390

 

100
00:03:32,390 --> 00:03:36,309

 

101
00:03:36,309 --> 00:03:39,110

 

102
00:03:39,110 --> 00:03:39,120

 

103
00:03:39,120 --> 00:03:40,070


104
00:03:40,070 --> 00:03:40,080

 

105
00:03:40,080 --> 00:03:40,949


106
00:03:40,949 --> 00:03:43,589

 

107
00:03:43,589 --> 00:03:45,750

 

108
00:03:45,750 --> 00:03:47,509

 

109
00:03:47,509 --> 00:03:50,070

 

110
00:03:50,070 --> 00:03:51,190

 

111
00:03:51,190 --> 00:03:54,869

 

112
00:03:54,869 --> 00:03:58,149

 

113
00:03:58,149 --> 00:04:00,949

 

114
00:04:00,949 --> 00:04:02,789

 

115
00:04:02,789 --> 00:04:04,470

 

116
00:04:04,470 --> 00:04:06,070

 

117
00:04:06,070 --> 00:04:08,149

 

118
00:04:08,149 --> 00:04:11,750

 

119
00:04:11,750 --> 00:04:13,990

 

120
00:04:13,990 --> 00:04:15,589

 

121
00:04:15,589 --> 00:04:17,509

 

122
00:04:17,509 --> 00:04:18,949

 

123
00:04:18,949 --> 00:04:21,110

 

124
00:04:21,110 --> 00:04:23,670

 

125
00:04:23,670 --> 00:04:25,909

 

126
00:04:25,909 --> 00:04:25,919

 

127
00:04:25,919 --> 00:04:26,870


128
00:04:26,870 --> 00:04:29,270

 

129
00:04:29,270 --> 00:04:32,150

 

130
00:04:32,150 --> 00:04:33,749

 

131
00:04:33,749 --> 00:04:35,270

 

132
00:04:35,270 --> 00:04:37,670

 

133
00:04:37,670 --> 00:04:39,510

 

134
00:04:39,510 --> 00:04:42,710

 

135
00:04:42,710 --> 00:04:45,110

 

136
00:04:45,110 --> 00:04:46,310

 

137
00:04:46,310 --> 00:04:48,790

 

138
00:04:48,790 --> 00:04:50,790

 

139
00:04:50,790 --> 00:04:54,310

 

140
00:04:54,310 --> 00:04:56,710

 

141
00:04:56,710 --> 00:04:58,790

 

142
00:04:58,790 --> 00:05:01,029

 

143
00:05:01,029 --> 00:05:01,039

 

144
00:05:01,039 --> 00:05:03,189


145
00:05:03,189 --> 00:05:03,199

 

146
00:05:03,199 --> 00:05:04,070


147
00:05:04,070 --> 00:05:06,629

 

148
00:05:06,629 --> 00:05:08,469

 

149
00:05:08,469 --> 00:05:10,629

 

150
00:05:10,629 --> 00:05:12,150

 

151
00:05:12,150 --> 00:05:13,350

 

152
00:05:13,350 --> 00:05:15,029

 

153
00:05:15,029 --> 00:05:17,189

 

154
00:05:17,189 --> 00:05:19,590

 

155
00:05:19,590 --> 00:05:22,469

 

156
00:05:22,469 --> 00:05:26,629

 

157
00:05:26,629 --> 00:05:29,830

 

158
00:05:29,830 --> 00:05:31,830

 

159
00:05:31,830 --> 00:05:33,350

 

160
00:05:33,350 --> 00:05:34,710

 

161
00:05:34,710 --> 00:05:34,720

 

162
00:05:34,720 --> 00:05:35,590


163
00:05:35,590 --> 00:05:36,950

 

164
00:05:36,950 --> 00:05:39,430

 

165
00:05:39,430 --> 00:05:42,469

 

166
00:05:42,469 --> 00:05:42,479

 

167
00:05:42,479 --> 00:05:44,230


168
00:05:44,230 --> 00:05:45,909

 

169
00:05:45,909 --> 00:05:48,550

 

170
00:05:48,550 --> 00:05:49,749

 

171
00:05:49,749 --> 00:05:51,670

 

172
00:05:51,670 --> 00:05:53,830

 

173
00:05:53,830 --> 00:05:56,469

 

174
00:05:56,469 --> 00:05:58,550

 

175
00:05:58,550 --> 00:06:00,390

 

176
00:06:00,390 --> 00:06:01,590

 

177
00:06:01,590 --> 00:06:03,830

 

178
00:06:03,830 --> 00:06:07,189

 

179
00:06:07,189 --> 00:06:09,670

 

180
00:06:09,670 --> 00:06:11,909

 

181
00:06:11,909 --> 00:06:13,430

 

182
00:06:13,430 --> 00:06:16,150

 

183
00:06:16,150 --> 00:06:16,160

 

184
00:06:16,160 --> 00:06:17,430


185
00:06:17,430 --> 00:06:17,440

 

186
00:06:17,440 --> 00:06:18,830


187
00:06:18,830 --> 00:06:21,830

 

188
00:06:21,830 --> 00:06:24,070

 

189
00:06:24,070 --> 00:06:26,070

 

190
00:06:26,070 --> 00:06:27,990

 

191
00:06:27,990 --> 00:06:30,309

 

192
00:06:30,309 --> 00:06:31,670

 

193
00:06:31,670 --> 00:06:31,680

 

194
00:06:31,680 --> 00:06:33,270


195
00:06:33,270 --> 00:06:36,070

 

196
00:06:36,070 --> 00:06:38,629

 

197
00:06:38,629 --> 00:06:40,070

 

198
00:06:40,070 --> 00:06:42,390

 

199
00:06:42,390 --> 00:06:46,070

 

200
00:06:46,070 --> 00:06:48,469

 

201
00:06:48,469 --> 00:06:50,309

 

202
00:06:50,309 --> 00:06:51,830

 

203
00:06:51,830 --> 00:06:53,430

 

204
00:06:53,430 --> 00:06:55,830

 

205
00:06:55,830 --> 00:06:57,189

 

206
00:06:57,189 --> 00:06:59,029

 

207
00:06:59,029 --> 00:07:01,110

 

208
00:07:01,110 --> 00:07:04,309

 

209
00:07:04,309 --> 00:07:07,110

 

210
00:07:07,110 --> 00:07:09,589

 

211
00:07:09,589 --> 00:07:11,670

 

212
00:07:11,670 --> 00:07:14,550

 

213
00:07:14,550 --> 00:07:16,550

 

214
00:07:16,550 --> 00:07:18,150

 

215
00:07:18,150 --> 00:07:20,150

 

216
00:07:20,150 --> 00:07:22,309

 

217
00:07:22,309 --> 00:07:23,749

 

218
00:07:23,749 --> 00:07:24,790

 

219
00:07:24,790 --> 00:07:26,469

 

220
00:07:26,469 --> 00:07:28,629

 

221
00:07:28,629 --> 00:07:30,550

 

222
00:07:30,550 --> 00:07:34,469

 

223
00:07:34,469 --> 00:07:34,479

 

224
00:07:34,479 --> 00:07:38,390


225
00:07:38,390 --> 00:07:40,390

 

226
00:07:40,390 --> 00:07:42,950

 

227
00:07:42,950 --> 00:07:45,029

 

228
00:07:45,029 --> 00:07:46,309

 

229
00:07:46,309 --> 00:07:48,790

 

230
00:07:48,790 --> 00:07:48,800

 

231
00:07:48,800 --> 00:07:50,950


232
00:07:50,950 --> 00:07:53,189

 

233
00:07:53,189 --> 00:07:56,830

 

234
00:07:56,830 --> 00:08:00,309

 

235
00:08:00,309 --> 00:08:01,270

 

236
00:08:01,270 --> 00:08:03,430

 

237
00:08:03,430 --> 00:08:05,029

 

238
00:08:05,029 --> 00:08:06,869

 

239
00:08:06,869 --> 00:08:09,510

 

240
00:08:09,510 --> 00:08:12,309

 

241
00:08:12,309 --> 00:08:15,189

 

242
00:08:15,189 --> 00:08:17,510

 

243
00:08:17,510 --> 00:08:19,990

 

244
00:08:19,990 --> 00:08:22,150

 

245
00:08:22,150 --> 00:08:23,830

 

246
00:08:23,830 --> 00:08:25,430

 

247
00:08:25,430 --> 00:08:25,440

 

248
00:08:25,440 --> 00:08:26,230


249
00:08:26,230 --> 00:08:28,150

 

250
00:08:28,150 --> 00:08:30,550

 

251
00:08:30,550 --> 00:08:32,790

 

252
00:08:32,790 --> 00:08:34,469

 

253
00:08:34,469 --> 00:08:36,790

 

254
00:08:36,790 --> 00:08:42,070

 

255
00:08:42,070 --> 00:08:43,190

 

256
00:08:43,190 --> 00:08:44,949

 

257
00:08:44,949 --> 00:08:46,870

 

258
00:08:46,870 --> 00:08:49,509

 

259
00:08:49,509 --> 00:08:49,519

 

260
00:08:49,519 --> 00:08:50,710


261
00:08:50,710 --> 00:08:52,470

 

262
00:08:52,470 --> 00:08:54,470

 

263
00:08:54,470 --> 00:08:56,870

 

264
00:08:56,870 --> 00:08:58,070

 

265
00:08:58,070 --> 00:09:00,550

 

266
00:09:00,550 --> 00:09:02,790

 

267
00:09:02,790 --> 00:09:04,949

 

268
00:09:04,949 --> 00:09:07,190

 

269
00:09:07,190 --> 00:09:09,110

 

270
00:09:09,110 --> 00:09:10,790

 

271
00:09:10,790 --> 00:09:12,870

 

272
00:09:12,870 --> 00:09:14,710

 

273
00:09:14,710 --> 00:09:17,030

 

274
00:09:17,030 --> 00:09:19,509

 

275
00:09:19,509 --> 00:09:22,790

 

276
00:09:22,790 --> 00:09:25,590

 

277
00:09:25,590 --> 00:09:27,990

 

278
00:09:27,990 --> 00:09:29,829

 

279
00:09:29,829 --> 00:09:31,590

 

280
00:09:31,590 --> 00:09:33,269

 

281
00:09:33,269 --> 00:09:33,279

 

282
00:09:33,279 --> 00:09:34,710


283
00:09:34,710 --> 00:09:36,389

 

284
00:09:36,389 --> 00:09:37,829

 

285
00:09:37,829 --> 00:09:40,310

 

286
00:09:40,310 --> 00:09:42,310

 

287
00:09:42,310 --> 00:09:44,710

 

288
00:09:44,710 --> 00:09:46,949

 

289
00:09:46,949 --> 00:09:49,269

 

290
00:09:49,269 --> 00:09:52,230

 

291
00:09:52,230 --> 00:09:53,670

 

292
00:09:53,670 --> 00:09:55,030

 

293
00:09:55,030 --> 00:09:57,509

 

294
00:09:57,509 --> 00:10:00,230

 

295
00:10:00,230 --> 00:10:02,630

 

296
00:10:02,630 --> 00:10:04,470

 

297
00:10:04,470 --> 00:10:07,670

 

298
00:10:07,670 --> 00:10:10,310

 

299
00:10:10,310 --> 00:10:12,630

 

300
00:10:12,630 --> 00:10:15,670

 

301
00:10:15,670 --> 00:10:18,380

 

302
00:10:18,380 --> 00:10:18,390

 

303
00:10:18,390 --> 00:10:19,829


304
00:10:19,829 --> 00:10:22,069

 

305
00:10:22,069 --> 00:10:24,550

 

306
00:10:24,550 --> 00:10:26,710

 

307
00:10:26,710 --> 00:10:29,509

 

308
00:10:29,509 --> 00:10:31,190

 

309
00:10:31,190 --> 00:10:33,030

 

310
00:10:33,030 --> 00:10:34,870

 

311
00:10:34,870 --> 00:10:36,389

 

312
00:10:36,389 --> 00:10:37,750

 

313
00:10:37,750 --> 00:10:39,350

 

314
00:10:39,350 --> 00:10:42,310

 

315
00:10:42,310 --> 00:10:43,990

 

316
00:10:43,990 --> 00:10:46,310

 

317
00:10:46,310 --> 00:10:48,550

 

318
00:10:48,550 --> 00:10:51,350

 

319
00:10:51,350 --> 00:10:55,190

 

320
00:10:55,190 --> 00:10:58,230

 

321
00:10:58,230 --> 00:10:58,240

 

322
00:10:58,240 --> 00:10:59,670


323
00:10:59,670 --> 00:11:02,389

 

324
00:11:02,389 --> 00:11:02,399

 

325
00:11:02,399 --> 00:11:03,910


326
00:11:03,910 --> 00:11:07,030

 

327
00:11:07,030 --> 00:11:08,630

 

328
00:11:08,630 --> 00:11:11,990

 

329
00:11:11,990 --> 00:11:13,829

 

330
00:11:13,829 --> 00:11:17,269

 

331
00:11:17,269 --> 00:11:19,269

 

332
00:11:19,269 --> 00:11:21,430

 

333
00:11:21,430 --> 00:11:23,990

 

334
00:11:23,990 --> 00:11:25,670

 

335
00:11:25,670 --> 00:11:27,670

 

336
00:11:27,670 --> 00:11:30,069

 

337
00:11:30,069 --> 00:11:32,150

 

338
00:11:32,150 --> 00:11:33,509

 

339
00:11:33,509 --> 00:11:36,550

 

340
00:11:36,550 --> 00:11:39,430

 

341
00:11:39,430 --> 00:11:41,990

 

342
00:11:41,990 --> 00:11:43,670

 

343
00:11:43,670 --> 00:11:46,630

 

344
00:11:46,630 --> 00:11:47,990

 

345
00:11:47,990 --> 00:11:48,000

 

346
00:11:48,000 --> 00:11:48,949


347
00:11:48,949 --> 00:11:50,470

 

348
00:11:50,470 --> 00:11:53,430

 

349
00:11:53,430 --> 00:11:55,590

 

350
00:11:55,590 --> 00:11:57,590

 

351
00:11:57,590 --> 00:11:57,600

 

352
00:11:57,600 --> 00:11:58,470


353
00:11:58,470 --> 00:12:00,629

 

354
00:12:00,629 --> 00:12:02,790

 

355
00:12:02,790 --> 00:12:04,790

 

356
00:12:04,790 --> 00:12:08,069

 

357
00:12:08,069 --> 00:12:10,230

 

358
00:12:10,230 --> 00:12:12,069

 

359
00:12:12,069 --> 00:12:15,430

 

360
00:12:15,430 --> 00:12:17,670

 

361
00:12:17,670 --> 00:12:19,590

 

362
00:12:19,590 --> 00:12:22,150

 

363
00:12:22,150 --> 00:12:24,310

 

364
00:12:24,310 --> 00:12:24,320

 

365
00:12:24,320 --> 00:12:25,670


366
00:12:25,670 --> 00:12:28,710

 

367
00:12:28,710 --> 00:12:30,389

 

368
00:12:30,389 --> 00:12:32,069

 

369
00:12:32,069 --> 00:12:32,949

 

370
00:12:32,949 --> 00:12:34,310

 

371
00:12:34,310 --> 00:12:34,320

 

372
00:12:34,320 --> 00:12:35,590


373
00:12:35,590 --> 00:12:37,430

 

374
00:12:37,430 --> 00:12:38,949

 

375
00:12:38,949 --> 00:12:40,389

 

376
00:12:40,389 --> 00:12:42,150

 

377
00:12:42,150 --> 00:12:44,310

 

378
00:12:44,310 --> 00:12:48,150

 

379
00:12:48,150 --> 00:12:48,160

 

380
00:12:48,160 --> 00:12:49,030


381
00:12:49,030 --> 00:12:50,629

 

382
00:12:50,629 --> 00:12:52,470

 

383
00:12:52,470 --> 00:12:54,629

 

384
00:12:54,629 --> 00:12:54,639

 

385
00:12:54,639 --> 00:12:55,509


386
00:12:55,509 --> 00:12:57,750

 

387
00:12:57,750 --> 00:12:59,990

 

388
00:12:59,990 --> 00:13:02,550

 

389
00:13:02,550 --> 00:13:04,550

 

390
00:13:04,550 --> 00:13:07,269

 

391
00:13:07,269 --> 00:13:08,629

 

392
00:13:08,629 --> 00:13:10,470

 

393
00:13:10,470 --> 00:13:13,190

 

394
00:13:13,190 --> 00:13:15,670

 

395
00:13:15,670 --> 00:13:17,509

 

396
00:13:17,509 --> 00:13:19,030

 

397
00:13:19,030 --> 00:13:20,629

 

398
00:13:20,629 --> 00:13:21,670

 

399
00:13:21,670 --> 00:13:23,590

 

400
00:13:23,590 --> 00:13:26,069

 

401
00:13:26,069 --> 00:13:27,350

 

402
00:13:27,350 --> 00:13:28,389

 

403
00:13:28,389 --> 00:13:30,310

 

404
00:13:30,310 --> 00:13:32,389

 

405
00:13:32,389 --> 00:13:33,750

 

406
00:13:33,750 --> 00:13:33,760

 

407
00:13:33,760 --> 00:13:35,110


408
00:13:35,110 --> 00:13:36,949

 

409
00:13:36,949 --> 00:13:39,670

 

410
00:13:39,670 --> 00:13:42,790

 

411
00:13:42,790 --> 00:13:45,030

 

412
00:13:45,030 --> 00:13:46,870

 

413
00:13:46,870 --> 00:13:48,470

 

414
00:13:48,470 --> 00:13:50,150

 

415
00:13:50,150 --> 00:13:52,069

 

416
00:13:52,069 --> 00:13:53,990

 

417
00:13:53,990 --> 00:13:56,550

 

418
00:13:56,550 --> 00:13:58,629

 

419
00:13:58,629 --> 00:14:01,189

 

420
00:14:01,189 --> 00:14:03,269

 

421
00:14:03,269 --> 00:14:03,279

 

422
00:14:03,279 --> 00:14:04,629


423
00:14:04,629 --> 00:14:06,710

 

424
00:14:06,710 --> 00:14:08,069

 

425
00:14:08,069 --> 00:14:09,509

 

426
00:14:09,509 --> 00:14:11,189

 

427
00:14:11,189 --> 00:14:11,199

 

428
00:14:11,199 --> 00:14:12,150


429
00:14:12,150 --> 00:14:14,310

 

430
00:14:14,310 --> 00:14:17,590

 

431
00:14:17,590 --> 00:14:18,870

 

432
00:14:18,870 --> 00:14:20,150

 

433
00:14:20,150 --> 00:14:21,670

 

434
00:14:21,670 --> 00:14:23,509

 

435
00:14:23,509 --> 00:14:25,269

 

436
00:14:25,269 --> 00:14:27,189

 

437
00:14:27,189 --> 00:14:28,710

 

438
00:14:28,710 --> 00:14:30,230

 

439
00:14:30,230 --> 00:14:30,240

 

440
00:14:30,240 --> 00:14:31,670


441
00:14:31,670 --> 00:14:33,189

 

442
00:14:33,189 --> 00:14:35,990

 

443
00:14:35,990 --> 00:14:37,670

 

444
00:14:37,670 --> 00:14:39,590

 

445
00:14:39,590 --> 00:14:41,430

 

446
00:14:41,430 --> 00:14:43,350

 

447
00:14:43,350 --> 00:14:45,430

 

448
00:14:45,430 --> 00:14:47,189

 

449
00:14:47,189 --> 00:14:49,110

 

450
00:14:49,110 --> 00:14:50,949

 

451
00:14:50,949 --> 00:14:53,110

 

452
00:14:53,110 --> 00:14:54,550

 

453
00:14:54,550 --> 00:14:56,069

 

454
00:14:56,069 --> 00:14:58,389

 

455
00:14:58,389 --> 00:14:59,990

 

456
00:14:59,990 --> 00:15:02,629

 

457
00:15:02,629 --> 00:15:06,629

 

458
00:15:06,629 --> 00:15:08,310

 

459
00:15:08,310 --> 00:15:09,829

 

460
00:15:09,829 --> 00:15:12,069

 

461
00:15:12,069 --> 00:15:15,269

 

462
00:15:15,269 --> 00:15:16,870

 

463
00:15:16,870 --> 00:15:18,949

 

464
00:15:18,949 --> 00:15:20,710

 

465
00:15:20,710 --> 00:15:23,509

 

466
00:15:23,509 --> 00:15:26,230

 

467
00:15:26,230 --> 00:15:26,240

 

468
00:15:26,240 --> 00:15:27,430


469
00:15:27,430 --> 00:15:29,990

 

470
00:15:29,990 --> 00:15:33,829

 

471
00:15:33,829 --> 00:15:36,790

 

472
00:15:36,790 --> 00:15:38,629

 

473
00:15:38,629 --> 00:15:40,949

 

474
00:15:40,949 --> 00:15:42,949

 

475
00:15:42,949 --> 00:15:44,629

 

476
00:15:44,629 --> 00:15:47,269

 

477
00:15:47,269 --> 00:15:49,350

 

478
00:15:49,350 --> 00:15:51,829

 

479
00:15:51,829 --> 00:15:54,790

 

480
00:15:54,790 --> 00:15:57,749

 

481
00:15:57,749 --> 00:15:57,759

 

482
00:15:57,759 --> 00:15:58,790


483
00:15:58,790 --> 00:16:00,470

 

484
00:16:00,470 --> 00:16:00,480

 

485
00:16:00,480 --> 00:16:01,829


486
00:16:01,829 --> 00:16:04,550

 

487
00:16:04,550 --> 00:16:06,629

 

488
00:16:06,629 --> 00:16:07,990

 

489
00:16:07,990 --> 00:16:10,710

 

490
00:16:10,710 --> 00:16:12,150

 

491
00:16:12,150 --> 00:16:14,230

 

492
00:16:14,230 --> 00:16:16,150

 

493
00:16:16,150 --> 00:16:17,590

 

494
00:16:17,590 --> 00:16:19,829

 

495
00:16:19,829 --> 00:16:22,710

 

496
00:16:22,710 --> 00:16:25,189

 

497
00:16:25,189 --> 00:16:27,269

 

498
00:16:27,269 --> 00:16:28,870

 

499
00:16:28,870 --> 00:16:31,030

 

500
00:16:31,030 --> 00:16:33,990

 

501
00:16:33,990 --> 00:16:36,150

 

502
00:16:36,150 --> 00:16:38,550

 

503
00:16:38,550 --> 00:16:39,829

 

504
00:16:39,829 --> 00:16:41,509

 

505
00:16:41,509 --> 00:16:43,760

 

506
00:16:43,760 --> 00:16:43,770

 

507
00:16:43,770 --> 00:16:45,110


508
00:16:45,110 --> 00:16:46,870

 

509
00:16:46,870 --> 00:16:48,790

 

510
00:16:48,790 --> 00:16:50,550

 

511
00:16:50,550 --> 00:16:53,670

 

512
00:16:53,670 --> 00:16:55,350

 

513
00:16:55,350 --> 00:16:57,670

 

514
00:16:57,670 --> 00:17:01,670

 

515
00:17:01,670 --> 00:17:05,429

 

516
00:17:05,429 --> 00:17:05,439

 

517
00:17:05,439 --> 00:17:06,470


518
00:17:06,470 --> 00:17:09,429

 

519
00:17:09,429 --> 00:17:12,470

 

520
00:17:12,470 --> 00:17:14,069

 

521
00:17:14,069 --> 00:17:15,829

 

522
00:17:15,829 --> 00:17:17,189

 

523
00:17:17,189 --> 00:17:19,189

 

524
00:17:19,189 --> 00:17:21,029

 

525
00:17:21,029 --> 00:17:22,390

 

526
00:17:22,390 --> 00:17:24,390

 

527
00:17:24,390 --> 00:17:26,710

 

528
00:17:26,710 --> 00:17:26,720

 

529
00:17:26,720 --> 00:17:27,909


530
00:17:27,909 --> 00:17:29,909

 

531
00:17:29,909 --> 00:17:31,990

 

532
00:17:31,990 --> 00:17:33,990

 

533
00:17:33,990 --> 00:17:37,270

 

534
00:17:37,270 --> 00:17:39,270

 

535
00:17:39,270 --> 00:17:41,990

 

536
00:17:41,990 --> 00:17:45,350

 

537
00:17:45,350 --> 00:17:48,950

 

538
00:17:48,950 --> 00:17:51,830

 

539
00:17:51,830 --> 00:17:54,070

 

540
00:17:54,070 --> 00:17:56,710

 

541
00:17:56,710 --> 00:17:57,990

 

542
00:17:57,990 --> 00:18:02,230

 

543
00:18:02,230 --> 00:18:04,310

 

544
00:18:04,310 --> 00:18:07,029

 

545
00:18:07,029 --> 00:18:08,630

 

546
00:18:08,630 --> 00:18:08,640

 

547
00:18:08,640 --> 00:18:09,750


548
00:18:09,750 --> 00:18:12,710

 

549
00:18:12,710 --> 00:18:15,110

 

550
00:18:15,110 --> 00:18:16,150

 

551
00:18:16,150 --> 00:18:16,160

 

552
00:18:16,160 --> 00:18:19,190


553
00:18:19,190 --> 00:18:19,200

 

554
00:18:19,200 --> 00:18:20,230


555
00:18:20,230 --> 00:18:22,150

 

556
00:18:22,150 --> 00:18:25,029

 

557
00:18:25,029 --> 00:18:26,789

 

558
00:18:26,789 --> 00:18:28,710

 

559
00:18:28,710 --> 00:18:29,909

 

560
00:18:29,909 --> 00:18:31,830

 

561
00:18:31,830 --> 00:18:34,070

 

562
00:18:34,070 --> 00:18:36,710

 

563
00:18:36,710 --> 00:18:38,470

 

564
00:18:38,470 --> 00:18:38,480

 

565
00:18:38,480 --> 00:18:39,430


566
00:18:39,430 --> 00:18:42,630

 

567
00:18:42,630 --> 00:18:44,230

 

568
00:18:44,230 --> 00:18:45,430

 

569
00:18:45,430 --> 00:18:48,310

 

570
00:18:48,310 --> 00:18:50,150

 

571
00:18:50,150 --> 00:18:51,830

 

572
00:18:51,830 --> 00:18:53,590

 

573
00:18:53,590 --> 00:18:56,470

 

574
00:18:56,470 --> 00:18:58,390

 

575
00:18:58,390 --> 00:19:00,870

 

576
00:19:00,870 --> 00:19:02,230

 

577
00:19:02,230 --> 00:19:03,669

 

578
00:19:03,669 --> 00:19:05,430

 

579
00:19:05,430 --> 00:19:09,110

 

580
00:19:09,110 --> 00:19:12,310

 

581
00:19:12,310 --> 00:19:13,750

 

582
00:19:13,750 --> 00:19:16,549

 

583
00:19:16,549 --> 00:19:20,470

 

584
00:19:20,470 --> 00:19:22,710

 

585
00:19:22,710 --> 00:19:26,150

 

586
00:19:26,150 --> 00:19:28,470

 

587
00:19:28,470 --> 00:19:32,310

 

588
00:19:32,310 --> 00:19:35,190

 

589
00:19:35,190 --> 00:19:36,310

 

590
00:19:36,310 --> 00:19:38,549

 

591
00:19:38,549 --> 00:19:40,789

 

592
00:19:40,789 --> 00:19:43,669

 

593
00:19:43,669 --> 00:19:46,230

 

594
00:19:46,230 --> 00:19:47,270

 

595
00:19:47,270 --> 00:19:49,750

 

596
00:19:49,750 --> 00:19:53,110

 

597
00:19:53,110 --> 00:19:55,669

 

598
00:19:55,669 --> 00:19:57,190

 

599
00:19:57,190 --> 00:19:59,430

 

600
00:19:59,430 --> 00:20:01,029

 

601
00:20:01,029 --> 00:20:02,950

 

602
00:20:02,950 --> 00:20:05,190

 

603
00:20:05,190 --> 00:20:05,200

 

604
00:20:05,200 --> 00:20:05,909


605
00:20:05,909 --> 00:20:07,510

 

606
00:20:07,510 --> 00:20:07,520

 

607
00:20:07,520 --> 00:20:08,549


608
00:20:08,549 --> 00:20:08,559

 

609
00:20:08,559 --> 00:20:09,510


610
00:20:09,510 --> 00:20:11,669

 

611
00:20:11,669 --> 00:20:14,070

 

612
00:20:14,070 --> 00:20:17,350

 

613
00:20:17,350 --> 00:20:19,190

 

614
00:20:19,190 --> 00:20:22,870

 

615
00:20:22,870 --> 00:20:24,390

 

616
00:20:24,390 --> 00:20:26,630

 

617
00:20:26,630 --> 00:20:28,710

 

618
00:20:28,710 --> 00:20:28,720

 

619
00:20:28,720 --> 00:20:30,149


620
00:20:30,149 --> 00:20:30,159

 

621
00:20:30,159 --> 00:20:31,029


622
00:20:31,029 --> 00:20:31,039

 

623
00:20:31,039 --> 00:20:33,029


624
00:20:33,029 --> 00:20:35,110

 

625
00:20:35,110 --> 00:20:38,870

 

626
00:20:38,870 --> 00:20:38,880

 

627
00:20:38,880 --> 00:20:39,669


628
00:20:39,669 --> 00:20:42,549

 

629
00:20:42,549 --> 00:20:44,549

 

630
00:20:44,549 --> 00:20:46,070

 

631
00:20:46,070 --> 00:20:46,080

 

632
00:20:46,080 --> 00:20:47,190


633
00:20:47,190 --> 00:20:50,070

 

634
00:20:50,070 --> 00:20:51,669

 

635
00:20:51,669 --> 00:20:53,669

 

636
00:20:53,669 --> 00:20:54,870

 

637
00:20:54,870 --> 00:20:54,880

 

638
00:20:54,880 --> 00:20:56,710


639
00:20:56,710 --> 00:20:56,720

 

640
00:20:56,720 --> 00:20:58,950


641
00:20:58,950 --> 00:21:01,270

 

642
00:21:01,270 --> 00:21:02,950

 

643
00:21:02,950 --> 00:21:02,960

 

644
00:21:02,960 --> 00:21:04,470


645
00:21:04,470 --> 00:21:06,070

 

646
00:21:06,070 --> 00:21:08,230

 

647
00:21:08,230 --> 00:21:11,110

 

648
00:21:11,110 --> 00:21:11,120

 

649
00:21:11,120 --> 00:21:12,149


650
00:21:12,149 --> 00:21:14,870

 

651
00:21:14,870 --> 00:21:17,669

 

652
00:21:17,669 --> 00:21:17,679

 

653
00:21:17,679 --> 00:21:18,630


654
00:21:18,630 --> 00:21:18,640

 

655
00:21:18,640 --> 00:21:20,149


656
00:21:20,149 --> 00:21:20,159

 

657
00:21:20,159 --> 00:21:21,430


658
00:21:21,430 --> 00:21:23,270

 

659
00:21:23,270 --> 00:21:25,669

 

660
00:21:25,669 --> 00:21:27,350

 

661
00:21:27,350 --> 00:21:29,270

 

662
00:21:29,270 --> 00:21:30,950

 

663
00:21:30,950 --> 00:21:33,350

 

664
00:21:33,350 --> 00:21:36,230

 

665
00:21:36,230 --> 00:21:38,950

 

666
00:21:38,950 --> 00:21:40,549

 

667
00:21:40,549 --> 00:21:42,390

 

668
00:21:42,390 --> 00:21:44,630

 

669
00:21:44,630 --> 00:21:44,640

 

670
00:21:44,640 --> 00:21:45,990


671
00:21:45,990 --> 00:21:47,510

 

672
00:21:47,510 --> 00:21:49,830

 

673
00:21:49,830 --> 00:21:49,840

 

674
00:21:49,840 --> 00:21:50,710


675
00:21:50,710 --> 00:21:53,029

 

676
00:21:53,029 --> 00:21:54,710

 

677
00:21:54,710 --> 00:21:56,230

 

678
00:21:56,230 --> 00:21:57,990

 

679
00:21:57,990 --> 00:21:59,190

 

680
00:21:59,190 --> 00:22:01,270

 

681
00:22:01,270 --> 00:22:03,909

 

682
00:22:03,909 --> 00:22:06,070

 

683
00:22:06,070 --> 00:22:07,590

 

684
00:22:07,590 --> 00:22:10,830

 

685
00:22:10,830 --> 00:22:15,029

 

686
00:22:15,029 --> 00:22:17,430

 

687
00:22:17,430 --> 00:22:19,029

 

688
00:22:19,029 --> 00:22:22,470

 

689
00:22:22,470 --> 00:22:24,230

 

690
00:22:24,230 --> 00:22:26,390

 

691
00:22:26,390 --> 00:22:28,549

 

692
00:22:28,549 --> 00:22:30,310

 

693
00:22:30,310 --> 00:22:32,950

 

694
00:22:32,950 --> 00:22:34,630

 

695
00:22:34,630 --> 00:22:35,830

 

696
00:22:35,830 --> 00:22:38,149

 

697
00:22:38,149 --> 00:22:39,590

 

698
00:22:39,590 --> 00:22:42,149

 

699
00:22:42,149 --> 00:22:43,830

 

700
00:22:43,830 --> 00:22:46,230

 

701
00:22:46,230 --> 00:22:48,149

 

702
00:22:48,149 --> 00:22:49,590

 

703
00:22:49,590 --> 00:22:51,830

 

704
00:22:51,830 --> 00:22:54,789

 

705
00:22:54,789 --> 00:22:57,590

 

706
00:22:57,590 --> 00:22:57,600

 

707
00:22:57,600 --> 00:22:59,270


708
00:22:59,270 --> 00:23:00,390

 

709
00:23:00,390 --> 00:23:02,390

 

710
00:23:02,390 --> 00:23:05,669

 

711
00:23:05,669 --> 00:23:07,350

 

712
00:23:07,350 --> 00:23:10,710

 

713
00:23:10,710 --> 00:23:12,470

 

714
00:23:12,470 --> 00:23:15,750

 

715
00:23:15,750 --> 00:23:18,070

 

716
00:23:18,070 --> 00:23:19,590

 

717
00:23:19,590 --> 00:23:23,750

 

718
00:23:23,750 --> 00:23:26,630

 

719
00:23:26,630 --> 00:23:28,789

 

720
00:23:28,789 --> 00:23:31,510

 

721
00:23:31,510 --> 00:23:33,270

 

722
00:23:33,270 --> 00:23:36,470

 

723
00:23:36,470 --> 00:23:38,950

 

724
00:23:38,950 --> 00:23:41,510

 

725
00:23:41,510 --> 00:23:44,390

 

726
00:23:44,390 --> 00:23:46,070

 

727
00:23:46,070 --> 00:23:49,190

 

728
00:23:49,190 --> 00:23:51,990

 

729
00:23:51,990 --> 00:23:54,070

 

730
00:23:54,070 --> 00:23:56,950

 

731
00:23:56,950 --> 00:23:59,669

 

732
00:23:59,669 --> 00:24:02,710

 

733
00:24:02,710 --> 00:24:04,630

 

734
00:24:04,630 --> 00:24:07,669

 

735
00:24:07,669 --> 00:24:08,950

 

736
00:24:08,950 --> 00:24:10,950

 

737
00:24:10,950 --> 00:24:13,990

 

738
00:24:13,990 --> 00:24:15,750

 

739
00:24:15,750 --> 00:24:17,269

 

740
00:24:17,269 --> 00:24:20,230

 

741
00:24:20,230 --> 00:24:23,029

 

742
00:24:23,029 --> 00:24:24,310

 

743
00:24:24,310 --> 00:24:25,909

 

744
00:24:25,909 --> 00:24:27,990

 

745
00:24:27,990 --> 00:24:29,510

 

746
00:24:29,510 --> 00:24:32,630

 

747
00:24:32,630 --> 00:24:34,230

 

748
00:24:34,230 --> 00:24:36,630

 

749
00:24:36,630 --> 00:24:38,390

 

750
00:24:38,390 --> 00:24:40,310

 

751
00:24:40,310 --> 00:24:41,830

 

752
00:24:41,830 --> 00:24:43,909

 

753
00:24:43,909 --> 00:24:45,029

 

754
00:24:45,029 --> 00:24:48,710

 

755
00:24:48,710 --> 00:24:51,029

 

756
00:24:51,029 --> 00:24:53,510

 

757
00:24:53,510 --> 00:24:54,950

 

758
00:24:54,950 --> 00:24:56,870

 

759
00:24:56,870 --> 00:24:58,950

 

760
00:24:58,950 --> 00:25:00,710

 

761
00:25:00,710 --> 00:25:03,110

 

762
00:25:03,110 --> 00:25:05,350

 

763
00:25:05,350 --> 00:25:07,350

 

764
00:25:07,350 --> 00:25:09,190

 

765
00:25:09,190 --> 00:25:11,590

 

766
00:25:11,590 --> 00:25:12,830

 

767
00:25:12,830 --> 00:25:15,190

 

768
00:25:15,190 --> 00:25:17,110

 

769
00:25:17,110 --> 00:25:18,470

 

770
00:25:18,470 --> 00:25:20,549

 

771
00:25:20,549 --> 00:25:21,510

 

772
00:25:21,510 --> 00:25:23,430

 

773
00:25:23,430 --> 00:25:24,950

 

774
00:25:24,950 --> 00:25:26,710

 

775
00:25:26,710 --> 00:25:30,390

 

776
00:25:30,390 --> 00:25:33,350

 

777
00:25:33,350 --> 00:25:33,360

 

778
00:25:33,360 --> 00:25:34,310


779
00:25:34,310 --> 00:25:36,070

 

780
00:25:36,070 --> 00:25:38,230

 

781
00:25:38,230 --> 00:25:40,390

 

782
00:25:40,390 --> 00:25:43,830

 

783
00:25:43,830 --> 00:25:46,470

 

784
00:25:46,470 --> 00:25:47,830

 

785
00:25:47,830 --> 00:25:47,840

 

786
00:25:47,840 --> 00:25:49,110


787
00:25:49,110 --> 00:25:50,950

 

788
00:25:50,950 --> 00:25:53,830

 

789
00:25:53,830 --> 00:25:56,230

 

790
00:25:56,230 --> 00:25:59,190

 

791
00:25:59,190 --> 00:26:01,029

 

792
00:26:01,029 --> 00:26:02,230

 

793
00:26:02,230 --> 00:26:04,230

 

794
00:26:04,230 --> 00:26:06,549

 

795
00:26:06,549 --> 00:26:08,390

 

796
00:26:08,390 --> 00:26:10,710

 

797
00:26:10,710 --> 00:26:10,720

 

798
00:26:10,720 --> 00:26:11,990


799
00:26:11,990 --> 00:26:14,470

 

800
00:26:14,470 --> 00:26:14,480

 

801
00:26:14,480 --> 00:26:15,830


802
00:26:15,830 --> 00:26:19,430

 

803
00:26:19,430 --> 00:26:21,590

 

804
00:26:21,590 --> 00:26:23,990

 

805
00:26:23,990 --> 00:26:25,830

 

806
00:26:25,830 --> 00:26:27,190

 

807
00:26:27,190 --> 00:26:30,549

 

808
00:26:30,549 --> 00:26:33,190

 

809
00:26:33,190 --> 00:26:33,200

 

810
00:26:33,200 --> 00:26:35,430


811
00:26:35,430 --> 00:26:38,310

 

812
00:26:38,310 --> 00:26:41,590

 

813
00:26:41,590 --> 00:26:41,600

 

814
00:26:41,600 --> 00:26:42,789


815
00:26:42,789 --> 00:26:45,190

 

816
00:26:45,190 --> 00:26:47,269

 

817
00:26:47,269 --> 00:26:48,950

 

818
00:26:48,950 --> 00:26:51,029

 

819
00:26:51,029 --> 00:26:54,149

 

820
00:26:54,149 --> 00:26:55,830

 

821
00:26:55,830 --> 00:26:57,669

 

822
00:26:57,669 --> 00:27:00,230

 

823
00:27:00,230 --> 00:27:03,590

 

824
00:27:03,590 --> 00:27:06,390

 

825
00:27:06,390 --> 00:27:09,190

 

826
00:27:09,190 --> 00:27:11,669

 

827
00:27:11,669 --> 00:27:13,990

 

828
00:27:13,990 --> 00:27:14,000

 

829
00:27:14,000 --> 00:27:15,190


830
00:27:15,190 --> 00:27:17,190

 

831
00:27:17,190 --> 00:27:19,909

 

832
00:27:19,909 --> 00:27:22,149

 

833
00:27:22,149 --> 00:27:24,710

 

834
00:27:24,710 --> 00:27:27,269

 

835
00:27:27,269 --> 00:27:29,590

 

836
00:27:29,590 --> 00:27:31,750

 

837
00:27:31,750 --> 00:27:33,510

 

838
00:27:33,510 --> 00:27:36,230

 

839
00:27:36,230 --> 00:27:41,110

 

840
00:27:41,110 --> 00:27:42,549

 

841
00:27:42,549 --> 00:27:43,750

 

842
00:27:43,750 --> 00:27:48,070

 

843
00:27:48,070 --> 00:27:49,669

 

844
00:27:49,669 --> 00:27:52,310

 

845
00:27:52,310 --> 00:27:55,510

 

846
00:27:55,510 --> 00:27:57,669

 

847
00:27:57,669 --> 00:27:59,750

 

848
00:27:59,750 --> 00:28:00,630

 

849
00:28:00,630 --> 00:28:03,830

 

850
00:28:03,830 --> 00:28:05,510

 

851
00:28:05,510 --> 00:28:07,750

 

852
00:28:07,750 --> 00:28:09,350

 

853
00:28:09,350 --> 00:28:11,430

 

854
00:28:11,430 --> 00:28:12,870

 

855
00:28:12,870 --> 00:28:14,310

 

856
00:28:14,310 --> 00:28:15,590

 

857
00:28:15,590 --> 00:28:15,600

 

858
00:28:15,600 --> 00:28:16,630


859
00:28:16,630 --> 00:28:16,640

 

860
00:28:16,640 --> 00:28:17,909


861
00:28:17,909 --> 00:28:20,470

 

862
00:28:20,470 --> 00:28:21,990

 

863
00:28:21,990 --> 00:28:23,590

 

864
00:28:23,590 --> 00:28:26,630

 

865
00:28:26,630 --> 00:28:28,470

 

866
00:28:28,470 --> 00:28:30,230

 

867
00:28:30,230 --> 00:28:31,350

 

868
00:28:31,350 --> 00:28:31,360

 

869
00:28:31,360 --> 00:28:32,230


870
00:28:32,230 --> 00:28:33,750

 

871
00:28:33,750 --> 00:28:36,470

 

872
00:28:36,470 --> 00:28:38,230

 

873
00:28:38,230 --> 00:28:40,310

 

874
00:28:40,310 --> 00:28:42,549

 

875
00:28:42,549 --> 00:28:44,070

 

876
00:28:44,070 --> 00:28:45,510

 

877
00:28:45,510 --> 00:28:48,230

 

878
00:28:48,230 --> 00:28:50,710

 

879
00:28:50,710 --> 00:28:52,789

 

880
00:28:52,789 --> 00:28:54,710

 

881
00:28:54,710 --> 00:28:57,190

 

882
00:28:57,190 --> 00:28:58,870

 

883
00:28:58,870 --> 00:29:00,149

 

884
00:29:00,149 --> 00:29:02,789

 

885
00:29:02,789 --> 00:29:05,669

 

886
00:29:05,669 --> 00:29:10,230

 

887
00:29:10,230 --> 00:29:14,070

 

888
00:29:14,070 --> 00:29:16,149

 

889
00:29:16,149 --> 00:29:19,110

 

890
00:29:19,110 --> 00:29:19,120

 

891
00:29:19,120 --> 00:29:20,070


892
00:29:20,070 --> 00:29:21,909

 

893
00:29:21,909 --> 00:29:25,190

 

894
00:29:25,190 --> 00:29:27,430

 

895
00:29:27,430 --> 00:29:30,070

 

896
00:29:30,070 --> 00:29:32,230

 

897
00:29:32,230 --> 00:29:35,110

 

898
00:29:35,110 --> 00:29:37,830

 

899
00:29:37,830 --> 00:29:39,350

 

900
00:29:39,350 --> 00:29:41,110

 

901
00:29:41,110 --> 00:29:42,710

 

902
00:29:42,710 --> 00:29:45,590

 

903
00:29:45,590 --> 00:29:47,269

 

904
00:29:47,269 --> 00:29:49,350

 

905
00:29:49,350 --> 00:29:49,360

 

906
00:29:49,360 --> 00:29:50,149


907
00:29:50,149 --> 00:29:50,159

 

908
00:29:50,159 --> 00:29:54,630


909
00:29:54,630 --> 00:29:56,710

 

910
00:29:56,710 --> 00:29:59,430

 

911
00:29:59,430 --> 00:30:02,230

 

912
00:30:02,230 --> 00:30:04,230

 

913
00:30:04,230 --> 00:30:05,269

 

914
00:30:05,269 --> 00:30:07,669

 

915
00:30:07,669 --> 00:30:08,950

 

916
00:30:08,950 --> 00:30:11,350

 

917
00:30:11,350 --> 00:30:14,230

 

918
00:30:14,230 --> 00:30:16,950

 

919
00:30:16,950 --> 00:30:18,710

 

920
00:30:18,710 --> 00:30:20,230

 

921
00:30:20,230 --> 00:30:23,350

 

922
00:30:23,350 --> 00:30:24,950

 

923
00:30:24,950 --> 00:30:26,630

 

924
00:30:26,630 --> 00:30:28,070

 

925
00:30:28,070 --> 00:30:29,190

 

926
00:30:29,190 --> 00:30:32,230

 

927
00:30:32,230 --> 00:30:35,110

 

928
00:30:35,110 --> 00:30:37,029

 

929
00:30:37,029 --> 00:30:38,789

 

930
00:30:38,789 --> 00:30:38,799

 

931
00:30:38,799 --> 00:30:39,830


932
00:30:39,830 --> 00:30:42,870

 

933
00:30:42,870 --> 00:30:46,149

 

934
00:30:46,149 --> 00:30:48,470

 

935
00:30:48,470 --> 00:30:50,389

 

936
00:30:50,389 --> 00:30:53,029

 

937
00:30:53,029 --> 00:30:55,350

 

938
00:30:55,350 --> 00:30:55,360

 

939
00:30:55,360 --> 00:30:56,230


940
00:30:56,230 --> 00:30:57,750

 

941
00:30:57,750 --> 00:30:58,950

 

942
00:30:58,950 --> 00:31:00,310

 

943
00:31:00,310 --> 00:31:03,350

 

944
00:31:03,350 --> 00:31:09,350

 

945
00:31:09,350 --> 00:31:11,430

 

946
00:31:11,430 --> 00:31:14,070

 

947
00:31:14,070 --> 00:31:16,470

 

948
00:31:16,470 --> 00:31:18,789

 

949
00:31:18,789 --> 00:31:21,509

 

950
00:31:21,509 --> 00:31:21,519

 

951
00:31:21,519 --> 00:31:23,830


952
00:31:23,830 --> 00:31:27,430

 

953
00:31:27,430 --> 00:31:29,750

 

954
00:31:29,750 --> 00:31:31,269

 

955
00:31:31,269 --> 00:31:32,710

 

956
00:31:32,710 --> 00:31:35,269

 

957
00:31:35,269 --> 00:31:38,549

 

958
00:31:38,549 --> 00:31:40,950

 

959
00:31:40,950 --> 00:31:42,070

 

960
00:31:42,070 --> 00:31:44,830

 

961
00:31:44,830 --> 00:31:48,230

 

962
00:31:48,230 --> 00:31:50,070

 

963
00:31:50,070 --> 00:31:52,630

 

964
00:31:52,630 --> 00:31:55,830

 

965
00:31:55,830 --> 00:31:58,230

 

966
00:31:58,230 --> 00:31:59,990

 

967
00:31:59,990 --> 00:32:02,470

 

968
00:32:02,470 --> 00:32:02,480

 

969
00:32:02,480 --> 00:32:03,830


970
00:32:03,830 --> 00:32:05,669

 

971
00:32:05,669 --> 00:32:07,430

 

972
00:32:07,430 --> 00:32:07,440

 

973
00:32:07,440 --> 00:32:08,870


974
00:32:08,870 --> 00:32:10,230

 

975
00:32:10,230 --> 00:32:12,070

 

976
00:32:12,070 --> 00:32:14,070

 

977
00:32:14,070 --> 00:32:15,509

 

978
00:32:15,509 --> 00:32:17,750

 

979
00:32:17,750 --> 00:32:19,830

 

980
00:32:19,830 --> 00:32:22,149

 

981
00:32:22,149 --> 00:32:23,669

 

982
00:32:23,669 --> 00:32:25,909

 

983
00:32:25,909 --> 00:32:28,470

 

984
00:32:28,470 --> 00:32:28,480

 

985
00:32:28,480 --> 00:32:30,310


986
00:32:30,310 --> 00:32:31,430

 

987
00:32:31,430 --> 00:32:33,509

 

988
00:32:33,509 --> 00:32:35,190

 

989
00:32:35,190 --> 00:32:37,430

 

990
00:32:37,430 --> 00:32:39,110

 

991
00:32:39,110 --> 00:32:39,120

 

992
00:32:39,120 --> 00:32:40,230


993
00:32:40,230 --> 00:32:41,750

 

994
00:32:41,750 --> 00:32:41,760

 

995
00:32:41,760 --> 00:32:42,710


996
00:32:42,710 --> 00:32:45,909

 

997
00:32:45,909 --> 00:32:47,909

 

998
00:32:47,909 --> 00:32:50,389

 

999
00:32:50,389 --> 00:32:53,110

 

1000
00:32:53,110 --> 00:32:55,269

 

1001
00:32:55,269 --> 00:32:57,350

 

1002
00:32:57,350 --> 00:33:00,470

 

1003
00:33:00,470 --> 00:33:03,430

 

1004
00:33:03,430 --> 00:33:04,630

 

1005
00:33:04,630 --> 00:33:09,190

 

1006
00:33:09,190 --> 00:33:12,389

 

1007
00:33:12,389 --> 00:33:14,789

 

1008
00:33:14,789 --> 00:33:14,799

 

1009
00:33:14,799 --> 00:33:15,669


1010
00:33:15,669 --> 00:33:17,029

 

1011
00:33:17,029 --> 00:33:17,039

 

1012
00:33:17,039 --> 00:33:18,149


1013
00:33:18,149 --> 00:33:20,230

 

1014
00:33:20,230 --> 00:33:20,240

 

1015
00:33:20,240 --> 00:33:23,509


1016
00:33:23,509 --> 00:33:26,549

 

1017
00:33:26,549 --> 00:33:29,029

 

1018
00:33:29,029 --> 00:33:29,039

 

1019
00:33:29,039 --> 00:33:30,070


1020
00:33:30,070 --> 00:33:32,149

 

1021
00:33:32,149 --> 00:33:34,950

 

1022
00:33:34,950 --> 00:33:37,110

 

1023
00:33:37,110 --> 00:33:39,029

 

1024
00:33:39,029 --> 00:33:40,470

 

1025
00:33:40,470 --> 00:33:42,870

 

1026
00:33:42,870 --> 00:33:45,029

 

1027
00:33:45,029 --> 00:33:46,070

 

1028
00:33:46,070 --> 00:33:48,549

 

1029
00:33:48,549 --> 00:33:50,470

 

1030
00:33:50,470 --> 00:33:52,389

 

1031
00:33:52,389 --> 00:33:53,669

 

1032
00:33:53,669 --> 00:33:57,669

 

1033
00:33:57,669 --> 00:33:57,679

 

1034
00:33:57,679 --> 00:33:58,530


1035
00:33:58,530 --> 00:33:58,540

 

1036
00:33:58,540 --> 00:33:59,990


1037
00:33:59,990 --> 00:34:00,000

 

1038
00:34:00,000 --> 00:34:01,509


1039
00:34:01,509 --> 00:34:02,789

 

1040
00:34:02,789 --> 00:34:02,799

 

1041
00:34:02,799 --> 00:34:04,389


1042
00:34:04,389 --> 00:34:07,590

 

1043
00:34:07,590 --> 00:34:07,600

 

1044
00:34:07,600 --> 00:34:10,149


1045
00:34:10,149 --> 00:34:11,990

 

1046
00:34:11,990 --> 00:34:13,190

 

1047
00:34:13,190 --> 00:34:13,200

 

1048
00:34:13,200 --> 00:34:14,310


1049
00:34:14,310 --> 00:34:16,069

 

1050
00:34:16,069 --> 00:34:19,109

 

1051
00:34:19,109 --> 00:34:20,470

 

1052
00:34:20,470 --> 00:34:22,550

 

1053
00:34:22,550 --> 00:34:24,950

 

1054
00:34:24,950 --> 00:34:24,960

 

1055
00:34:24,960 --> 00:34:26,470


1056
00:34:26,470 --> 00:34:28,470

 

1057
00:34:28,470 --> 00:34:30,790

 

1058
00:34:30,790 --> 00:34:32,550

 

1059
00:34:32,550 --> 00:34:34,310

 

1060
00:34:34,310 --> 00:34:36,149

 

1061
00:34:36,149 --> 00:34:38,310

 

1062
00:34:38,310 --> 00:34:39,990

 

1063
00:34:39,990 --> 00:34:40,000

 

1064
00:34:40,000 --> 00:34:41,109


1065
00:34:41,109 --> 00:34:43,109

 

1066
00:34:43,109 --> 00:34:44,550

 

1067
00:34:44,550 --> 00:34:46,149

 

1068
00:34:46,149 --> 00:34:49,349

 

1069
00:34:49,349 --> 00:34:51,270

 

1070
00:34:51,270 --> 00:34:53,030

 

1071
00:34:53,030 --> 00:34:55,190

 

1072
00:34:55,190 --> 00:34:57,589

 

1073
00:34:57,589 --> 00:34:59,589

 

1074
00:34:59,589 --> 00:35:02,230

 

1075
00:35:02,230 --> 00:35:04,470

 

1076
00:35:04,470 --> 00:35:06,390

 

1077
00:35:06,390 --> 00:35:07,990

 

1078
00:35:07,990 --> 00:35:09,510

 

1079
00:35:09,510 --> 00:35:11,430

 

1080
00:35:11,430 --> 00:35:14,150

 

1081
00:35:14,150 --> 00:35:17,349

 

1082
00:35:17,349 --> 00:35:19,190

 

1083
00:35:19,190 --> 00:35:21,349

 

1084
00:35:21,349 --> 00:35:23,589

 

1085
00:35:23,589 --> 00:35:25,510

 

1086
00:35:25,510 --> 00:35:25,520

 

1087
00:35:25,520 --> 00:35:26,630


1088
00:35:26,630 --> 00:35:28,390

 

1089
00:35:28,390 --> 00:35:32,230

 

1090
00:35:32,230 --> 00:35:32,240

 

1091
00:35:32,240 --> 00:35:34,390


1092
00:35:34,390 --> 00:35:34,400

 

1093
00:35:34,400 --> 00:35:37,829


1094
00:35:37,829 --> 00:35:39,510

 

1095
00:35:39,510 --> 00:35:39,520

 

1096
00:35:39,520 --> 00:35:41,190


1097
00:35:41,190 --> 00:35:41,200

 

1098
00:35:41,200 --> 00:35:43,190


1099
00:35:43,190 --> 00:35:44,950

 

1100
00:35:44,950 --> 00:35:44,960

 

1101
00:35:44,960 --> 00:35:46,310


1102
00:35:46,310 --> 00:35:48,150

 

1103
00:35:48,150 --> 00:35:50,470

 

1104
00:35:50,470 --> 00:35:50,480

 

1105
00:35:50,480 --> 00:35:51,349


1106
00:35:51,349 --> 00:35:55,430

 

1107
00:35:55,430 --> 00:35:57,589

 

1108
00:35:57,589 --> 00:35:59,589

 

1109
00:35:59,589 --> 00:36:01,910

 

1110
00:36:01,910 --> 00:36:04,310

 

1111
00:36:04,310 --> 00:36:06,390

 

1112
00:36:06,390 --> 00:36:07,990

 

1113
00:36:07,990 --> 00:36:09,990

 

1114
00:36:09,990 --> 00:36:11,510

 

1115
00:36:11,510 --> 00:36:11,520

 

1116
00:36:11,520 --> 00:36:12,710


1117
00:36:12,710 --> 00:36:15,109

 

1118
00:36:15,109 --> 00:36:16,230

 

1119
00:36:16,230 --> 00:36:17,510

 

1120
00:36:17,510 --> 00:36:18,710

 

1121
00:36:18,710 --> 00:36:18,720

 

1122
00:36:18,720 --> 00:36:20,069


1123
00:36:20,069 --> 00:36:22,710

 

1124
00:36:22,710 --> 00:36:24,230

 

1125
00:36:24,230 --> 00:36:26,710

 

1126
00:36:26,710 --> 00:36:27,990

 

1127
00:36:27,990 --> 00:36:29,910

 

1128
00:36:29,910 --> 00:36:29,920

 

1129
00:36:29,920 --> 00:36:31,990


1130
00:36:31,990 --> 00:36:34,550

 

1131
00:36:34,550 --> 00:36:36,470

 

1132
00:36:36,470 --> 00:36:38,390

 

1133
00:36:38,390 --> 00:36:40,790

 

1134
00:36:40,790 --> 00:36:44,150

 

1135
00:36:44,150 --> 00:36:46,150

 

1136
00:36:46,150 --> 00:36:47,990

 

1137
00:36:47,990 --> 00:36:48,000

 

1138
00:36:48,000 --> 00:36:49,270


1139
00:36:49,270 --> 00:36:50,230

 

1140
00:36:50,230 --> 00:36:51,589

 

1141
00:36:51,589 --> 00:36:53,349

 

1142
00:36:53,349 --> 00:36:56,630

 

1143
00:36:56,630 --> 00:36:58,710

 

1144
00:36:58,710 --> 00:37:01,270

 

1145
00:37:01,270 --> 00:37:02,950

 

1146
00:37:02,950 --> 00:37:05,190

 

1147
00:37:05,190 --> 00:37:07,109

 

1148
00:37:07,109 --> 00:37:09,190

 

1149
00:37:09,190 --> 00:37:10,870

 

1150
00:37:10,870 --> 00:37:13,670

 

1151
00:37:13,670 --> 00:37:13,680

 

1152
00:37:13,680 --> 00:37:14,870


1153
00:37:14,870 --> 00:37:16,950

 

1154
00:37:16,950 --> 00:37:18,870

 

1155
00:37:18,870 --> 00:37:21,829

 

1156
00:37:21,829 --> 00:37:23,030

 

1157
00:37:23,030 --> 00:37:24,390

 

1158
00:37:24,390 --> 00:37:25,589

 

1159
00:37:25,589 --> 00:37:28,790

 

1160
00:37:28,790 --> 00:37:30,790

 

1161
00:37:30,790 --> 00:37:32,069

 

1162
00:37:32,069 --> 00:37:34,310

 

1163
00:37:34,310 --> 00:37:35,589

 

1164
00:37:35,589 --> 00:37:38,230

 

1165
00:37:38,230 --> 00:37:39,589

 

1166
00:37:39,589 --> 00:37:41,829

 

1167
00:37:41,829 --> 00:37:43,670

 

1168
00:37:43,670 --> 00:37:45,030

 

1169
00:37:45,030 --> 00:37:47,109

 

1170
00:37:47,109 --> 00:37:48,710

 

1171
00:37:48,710 --> 00:37:51,030

 

1172
00:37:51,030 --> 00:37:52,630

 

1173
00:37:52,630 --> 00:37:54,470

 

1174
00:37:54,470 --> 00:37:57,750

 

1175
00:37:57,750 --> 00:37:59,910

 

1176
00:37:59,910 --> 00:38:03,349

 

1177
00:38:03,349 --> 00:38:04,390

 

1178
00:38:04,390 --> 00:38:07,510

 

1179
00:38:07,510 --> 00:38:09,430

 

1180
00:38:09,430 --> 00:38:11,349

 

1181
00:38:11,349 --> 00:38:13,190

 

1182
00:38:13,190 --> 00:38:16,390

 

1183
00:38:16,390 --> 00:38:16,400

 

1184
00:38:16,400 --> 00:38:17,510


1185
00:38:17,510 --> 00:38:20,069

 

1186
00:38:20,069 --> 00:38:22,150

 

1187
00:38:22,150 --> 00:38:23,589

 

1188
00:38:23,589 --> 00:38:25,430

 

1189
00:38:25,430 --> 00:38:29,030

 

1190
00:38:29,030 --> 00:38:30,710

 

1191
00:38:30,710 --> 00:38:32,630

 

1192
00:38:32,630 --> 00:38:35,430

 

1193
00:38:35,430 --> 00:38:36,950

 

1194
00:38:36,950 --> 00:38:39,190

 

1195
00:38:39,190 --> 00:38:40,630

 

1196
00:38:40,630 --> 00:38:42,230

 

1197
00:38:42,230 --> 00:38:44,870

 

1198
00:38:44,870 --> 00:38:48,069

 

1199
00:38:48,069 --> 00:38:49,829

 

1200
00:38:49,829 --> 00:38:51,910

 

1201
00:38:51,910 --> 00:38:54,230

 

1202
00:38:54,230 --> 00:38:56,630

 

1203
00:38:56,630 --> 00:38:56,640

 

1204
00:38:56,640 --> 00:38:57,910


1205
00:38:57,910 --> 00:38:57,920

 

1206
00:38:57,920 --> 00:38:58,790


1207
00:38:58,790 --> 00:39:01,030

 

1208
00:39:01,030 --> 00:39:03,109

 

1209
00:39:03,109 --> 00:39:04,950

 

1210
00:39:04,950 --> 00:39:07,190

 

1211
00:39:07,190 --> 00:39:09,910

 

1212
00:39:09,910 --> 00:39:11,510

 

1213
00:39:11,510 --> 00:39:13,990

 

1214
00:39:13,990 --> 00:39:15,750

 

1215
00:39:15,750 --> 00:39:17,109

 

1216
00:39:17,109 --> 00:39:18,630

 

1217
00:39:18,630 --> 00:39:20,790

 

1218
00:39:20,790 --> 00:39:22,550

 

1219
00:39:22,550 --> 00:39:23,910

 

1220
00:39:23,910 --> 00:39:25,190

 

1221
00:39:25,190 --> 00:39:26,550

 

1222
00:39:26,550 --> 00:39:28,230

 

1223
00:39:28,230 --> 00:39:30,069

 

1224
00:39:30,069 --> 00:39:32,630

 

1225
00:39:32,630 --> 00:39:34,630

 

1226
00:39:34,630 --> 00:39:37,190

 

1227
00:39:37,190 --> 00:39:38,630

 

1228
00:39:38,630 --> 00:39:41,030

 

1229
00:39:41,030 --> 00:39:44,710

 

1230
00:39:44,710 --> 00:39:44,720

 

1231
00:39:44,720 --> 00:39:46,150


1232
00:39:46,150 --> 00:39:48,870

 

1233
00:39:48,870 --> 00:39:51,109

 

1234
00:39:51,109 --> 00:39:54,950

 

1235
00:39:54,950 --> 00:39:56,790

 

1236
00:39:56,790 --> 00:39:58,550

 

1237
00:39:58,550 --> 00:39:58,560

 

1238
00:39:58,560 --> 00:39:59,910


1239
00:39:59,910 --> 00:40:02,950

 

1240
00:40:02,950 --> 00:40:04,710

 

1241
00:40:04,710 --> 00:40:06,790

 

1242
00:40:06,790 --> 00:40:08,790

 

1243
00:40:08,790 --> 00:40:10,230

 

1244
00:40:10,230 --> 00:40:12,790

 

1245
00:40:12,790 --> 00:40:15,030

 

1246
00:40:15,030 --> 00:40:16,710

 

1247
00:40:16,710 --> 00:40:17,910

 

1248
00:40:17,910 --> 00:40:17,920

 

1249
00:40:17,920 --> 00:40:18,790


1250
00:40:18,790 --> 00:40:18,800

 

1251
00:40:18,800 --> 00:40:19,910


1252
00:40:19,910 --> 00:40:21,510

 

1253
00:40:21,510 --> 00:40:24,230

 

1254
00:40:24,230 --> 00:40:25,430

 

1255
00:40:25,430 --> 00:40:27,750

 

1256
00:40:27,750 --> 00:40:31,030

 

1257
00:40:31,030 --> 00:40:32,870

 

1258
00:40:32,870 --> 00:40:34,230

 

1259
00:40:34,230 --> 00:40:36,150

 

1260
00:40:36,150 --> 00:40:36,160

 

1261
00:40:36,160 --> 00:40:38,710


1262
00:40:38,710 --> 00:40:38,720

 

1263
00:40:38,720 --> 00:40:39,750


1264
00:40:39,750 --> 00:40:41,670

 

1265
00:40:41,670 --> 00:40:41,680

 

1266
00:40:41,680 --> 00:40:43,030


1267
00:40:43,030 --> 00:40:45,510

 

1268
00:40:45,510 --> 00:40:45,520

 

1269
00:40:45,520 --> 00:40:47,910


1270
00:40:47,910 --> 00:40:49,510

 

1271
00:40:49,510 --> 00:40:51,190

 

1272
00:40:51,190 --> 00:40:52,550

 

1273
00:40:52,550 --> 00:40:56,230

 

1274
00:40:56,230 --> 00:40:56,240

 

1275
00:40:56,240 --> 00:40:57,829


1276
00:40:57,829 --> 00:40:59,349

 

1277
00:40:59,349 --> 00:41:01,829

 

1278
00:41:01,829 --> 00:41:03,670

 

1279
00:41:03,670 --> 00:41:05,349

 

1280
00:41:05,349 --> 00:41:07,190

 

1281
00:41:07,190 --> 00:41:09,109

 

1282
00:41:09,109 --> 00:41:10,790

 

1283
00:41:10,790 --> 00:41:12,150

 

1284
00:41:12,150 --> 00:41:12,160

 

1285
00:41:12,160 --> 00:41:14,870


1286
00:41:14,870 --> 00:41:17,030

 

1287
00:41:17,030 --> 00:41:21,109

 

1288
00:41:21,109 --> 00:41:24,230

 

1289
00:41:24,230 --> 00:41:25,670

 

1290
00:41:25,670 --> 00:41:28,630

 

1291
00:41:28,630 --> 00:41:31,030

 

1292
00:41:31,030 --> 00:41:31,040

 

1293
00:41:31,040 --> 00:41:32,589


1294
00:41:32,589 --> 00:41:36,309

 

1295
00:41:36,309 --> 00:41:37,910

 

1296
00:41:37,910 --> 00:41:40,630

 

1297
00:41:40,630 --> 00:41:44,069

 

1298
00:41:44,069 --> 00:41:47,030

 

1299
00:41:47,030 --> 00:41:49,750

 

1300
00:41:49,750 --> 00:41:52,710

 

1301
00:41:52,710 --> 00:41:52,720

 

1302
00:41:52,720 --> 00:41:56,150


1303
00:41:56,150 --> 00:41:58,870

 

1304
00:41:58,870 --> 00:42:02,230

 

1305
00:42:02,230 --> 00:42:06,710

 

1306
00:42:06,710 --> 00:42:08,790

 

1307
00:42:08,790 --> 00:42:12,230

 

1308
00:42:12,230 --> 00:42:15,030

 

1309
00:42:15,030 --> 00:42:17,910

 

1310
00:42:17,910 --> 00:42:20,150

 

1311
00:42:20,150 --> 00:42:22,069

 

1312
00:42:22,069 --> 00:42:22,079

 

1313
00:42:22,079 --> 00:42:24,950


1314
00:42:24,950 --> 00:42:26,309

 

1315
00:42:26,309 --> 00:42:26,319

 

1316
00:42:26,319 --> 00:42:27,589


1317
00:42:27,589 --> 00:42:30,790

 

1318
00:42:30,790 --> 00:42:32,950

 

1319
00:42:32,950 --> 00:42:36,069

 

1320
00:42:36,069 --> 00:42:36,079

 

1321
00:42:36,079 --> 00:42:37,349


1322
00:42:37,349 --> 00:42:37,359

 

1323
00:42:37,359 --> 00:42:38,470


1324
00:42:38,470 --> 00:42:40,309

 

1325
00:42:40,309 --> 00:42:42,390

 

1326
00:42:42,390 --> 00:42:44,470

 

1327
00:42:44,470 --> 00:42:46,470

 

1328
00:42:46,470 --> 00:42:49,109

 

1329
00:42:49,109 --> 00:42:49,119

 

1330
00:42:49,119 --> 00:42:51,670


1331
00:42:51,670 --> 00:42:53,190

 

1332
00:42:53,190 --> 00:42:53,200

 

1333
00:42:53,200 --> 00:42:55,109


1334
00:42:55,109 --> 00:42:58,390

 

1335
00:42:58,390 --> 00:43:02,309

 

1336
00:43:02,309 --> 00:43:02,319

 

1337
00:43:02,319 --> 00:43:05,190


1338
00:43:05,190 --> 00:43:07,670

 

1339
00:43:07,670 --> 00:43:07,680

 

1340
00:43:07,680 --> 00:43:10,309


1341
00:43:10,309 --> 00:43:13,910

 

1342
00:43:13,910 --> 00:43:16,150

 

1343
00:43:16,150 --> 00:43:17,910

 

1344
00:43:17,910 --> 00:43:17,920

 

1345
00:43:17,920 --> 00:43:20,550


1346
00:43:20,550 --> 00:43:21,990

 

1347
00:43:21,990 --> 00:43:22,000

 

1348
00:43:22,000 --> 00:43:23,109


1349
00:43:23,109 --> 00:43:25,190

 

1350
00:43:25,190 --> 00:43:27,270

 

1351
00:43:27,270 --> 00:43:27,280

 

1352
00:43:27,280 --> 00:43:30,150


1353
00:43:30,150 --> 00:43:32,630

 

1354
00:43:32,630 --> 00:43:36,550

 

1355
00:43:36,550 --> 00:43:37,589

 

1356
00:43:37,589 --> 00:43:39,510

 

1357
00:43:39,510 --> 00:43:39,520

 

1358
00:43:39,520 --> 00:43:41,750


1359
00:43:41,750 --> 00:43:42,950

 

1360
00:43:42,950 --> 00:43:42,960

 

1361
00:43:42,960 --> 00:43:44,069


1362
00:43:44,069 --> 00:43:45,190

 

1363
00:43:45,190 --> 00:43:47,829

 

1364
00:43:47,829 --> 00:43:49,349

 

1365
00:43:49,349 --> 00:43:51,670

 

1366
00:43:51,670 --> 00:43:56,470

 

1367
00:43:56,470 --> 00:43:59,510

 

1368
00:43:59,510 --> 00:44:00,710

 

1369
00:44:00,710 --> 00:44:03,990

 

1370
00:44:03,990 --> 00:44:06,230

 

1371
00:44:06,230 --> 00:44:08,230

 

1372
00:44:08,230 --> 00:44:10,150

 

1373
00:44:10,150 --> 00:44:12,630

 

1374
00:44:12,630 --> 00:44:14,710

 

1375
00:44:14,710 --> 00:44:16,150

 

1376
00:44:16,150 --> 00:44:19,910

 

1377
00:44:19,910 --> 00:44:22,470

 

1378
00:44:22,470 --> 00:44:24,230

 

1379
00:44:24,230 --> 00:44:24,240

 

1380
00:44:24,240 --> 00:44:25,190


1381
00:44:25,190 --> 00:44:27,030

 

1382
00:44:27,030 --> 00:44:29,990

 

1383
00:44:29,990 --> 00:44:31,910

 

1384
00:44:31,910 --> 00:44:34,470

 

1385
00:44:34,470 --> 00:44:36,950

 

1386
00:44:36,950 --> 00:44:39,510

 

1387
00:44:39,510 --> 00:44:39,520

 

1388
00:44:39,520 --> 00:44:41,109


1389
00:44:41,109 --> 00:44:43,910

 

1390
00:44:43,910 --> 00:44:46,870

 

1391
00:44:46,870 --> 00:44:48,790

 

1392
00:44:48,790 --> 00:44:51,190

 

1393
00:44:51,190 --> 00:44:52,870

 

1394
00:44:52,870 --> 00:44:54,390

 

1395
00:44:54,390 --> 00:44:56,150

 

1396
00:44:56,150 --> 00:44:58,309

 

1397
00:44:58,309 --> 00:45:01,109

 

1398
00:45:01,109 --> 00:45:02,790

 

1399
00:45:02,790 --> 00:45:05,270

 

1400
00:45:05,270 --> 00:45:07,349

 

1401
00:45:07,349 --> 00:45:07,359

 

1402
00:45:07,359 --> 00:45:08,790


1403
00:45:08,790 --> 00:45:10,870

 

1404
00:45:10,870 --> 00:45:13,030

 

1405
00:45:13,030 --> 00:45:13,040

 

1406
00:45:13,040 --> 00:45:14,630


1407
00:45:14,630 --> 00:45:18,150

 

1408
00:45:18,150 --> 00:45:21,349

 

1409
00:45:21,349 --> 00:45:23,190

 

1410
00:45:23,190 --> 00:45:24,550

 

1411
00:45:24,550 --> 00:45:26,630

 

1412
00:45:26,630 --> 00:45:26,640

 

1413
00:45:26,640 --> 00:45:27,589


1414
00:45:27,589 --> 00:45:29,030

 

1415
00:45:29,030 --> 00:45:30,950

 

1416
00:45:30,950 --> 00:45:32,390

 

1417
00:45:32,390 --> 00:45:34,230

 

1418
00:45:34,230 --> 00:45:35,670

 

1419
00:45:35,670 --> 00:45:37,670

 

1420
00:45:37,670 --> 00:45:41,270

 

1421
00:45:41,270 --> 00:45:43,670

 

1422
00:45:43,670 --> 00:45:45,750

 

1423
00:45:45,750 --> 00:45:48,470

 

1424
00:45:48,470 --> 00:45:51,109

 

1425
00:45:51,109 --> 00:45:53,910

 

1426
00:45:53,910 --> 00:45:55,829

 

1427
00:45:55,829 --> 00:45:57,829

 

1428
00:45:57,829 --> 00:45:59,430

 

1429
00:45:59,430 --> 00:46:02,470

 

1430
00:46:02,470 --> 00:46:02,480

 

1431
00:46:02,480 --> 00:46:04,069


1432
00:46:04,069 --> 00:46:06,710

 

1433
00:46:06,710 --> 00:46:09,430

 

1434
00:46:09,430 --> 00:46:11,829

 

1435
00:46:11,829 --> 00:46:14,630

 

1436
00:46:14,630 --> 00:46:17,030

 

1437
00:46:17,030 --> 00:46:19,030

 

1438
00:46:19,030 --> 00:46:20,950

 

1439
00:46:20,950 --> 00:46:23,589

 

1440
00:46:23,589 --> 00:46:25,270

 

1441
00:46:25,270 --> 00:46:28,230

 

1442
00:46:28,230 --> 00:46:31,589

 

1443
00:46:31,589 --> 00:46:33,829

 

1444
00:46:33,829 --> 00:46:35,750

 

1445
00:46:35,750 --> 00:46:38,630

 

1446
00:46:38,630 --> 00:46:38,640

 

1447
00:46:38,640 --> 00:46:39,990


1448
00:46:39,990 --> 00:46:42,150

 

1449
00:46:42,150 --> 00:46:44,550

 

1450
00:46:44,550 --> 00:46:44,560

 

1451
00:46:44,560 --> 00:46:45,270


1452
00:46:45,270 --> 00:46:48,230

 

1453
00:46:48,230 --> 00:46:49,829

 

1454
00:46:49,829 --> 00:46:51,910

 

1455
00:46:51,910 --> 00:46:54,390

 

1456
00:46:54,390 --> 00:46:58,550

 

1457
00:46:58,550 --> 00:46:58,560

 

1458
00:46:58,560 --> 00:46:59,349


1459
00:46:59,349 --> 00:47:01,589

 

1460
00:47:01,589 --> 00:47:05,109

 

1461
00:47:05,109 --> 00:47:05,119

 

1462
00:47:05,119 --> 00:47:07,030


1463
00:47:07,030 --> 00:47:08,870

 

1464
00:47:08,870 --> 00:47:11,430

 

1465
00:47:11,430 --> 00:47:11,440

 

1466
00:47:11,440 --> 00:47:12,309


1467
00:47:12,309 --> 00:47:14,470

 

1468
00:47:14,470 --> 00:47:14,480

 

1469
00:47:14,480 --> 00:47:15,990


1470
00:47:15,990 --> 00:47:17,510

 

1471
00:47:17,510 --> 00:47:20,630

 

1472
00:47:20,630 --> 00:47:22,790

 

1473
00:47:22,790 --> 00:47:24,390

 

1474
00:47:24,390 --> 00:47:27,030

 

1475
00:47:27,030 --> 00:47:29,349

 

1476
00:47:29,349 --> 00:47:32,470

 

1477
00:47:32,470 --> 00:47:34,150

 

1478
00:47:34,150 --> 00:47:34,160

 

1479
00:47:34,160 --> 00:47:35,030


1480
00:47:35,030 --> 00:47:38,630

 

1481
00:47:38,630 --> 00:47:40,150

 

1482
00:47:40,150 --> 00:47:41,750

 

1483
00:47:41,750 --> 00:47:43,510

 

1484
00:47:43,510 --> 00:47:45,750

 

1485
00:47:45,750 --> 00:47:47,589

 

1486
00:47:47,589 --> 00:47:49,349

 

1487
00:47:49,349 --> 00:47:52,150

 

1488
00:47:52,150 --> 00:47:53,430

 

1489
00:47:53,430 --> 00:47:55,910

 

1490
00:47:55,910 --> 00:47:55,920

 

1491
00:47:55,920 --> 00:47:56,870


1492
00:47:56,870 --> 00:48:00,950

 

1493
00:48:00,950 --> 00:48:03,589

 

1494
00:48:03,589 --> 00:48:05,829

 

1495
00:48:05,829 --> 00:48:08,790

 

1496
00:48:08,790 --> 00:48:10,230

 

1497
00:48:10,230 --> 00:48:11,589

 

1498
00:48:11,589 --> 00:48:13,349

 

1499
00:48:13,349 --> 00:48:15,510

 

1500
00:48:15,510 --> 00:48:17,750

 

1501
00:48:17,750 --> 00:48:19,349

 

1502
00:48:19,349 --> 00:48:19,359

 

1503
00:48:19,359 --> 00:48:20,870


1504
00:48:20,870 --> 00:48:23,349

 

1505
00:48:23,349 --> 00:48:25,109

 

1506
00:48:25,109 --> 00:48:27,270

 

1507
00:48:27,270 --> 00:48:30,470

 

1508
00:48:30,470 --> 00:48:32,950

 

1509
00:48:32,950 --> 00:48:34,870

 

1510
00:48:34,870 --> 00:48:37,430

 

1511
00:48:37,430 --> 00:48:37,440

 

1512
00:48:37,440 --> 00:48:38,390


1513
00:48:38,390 --> 00:48:40,390

 

1514
00:48:40,390 --> 00:48:43,109

 

1515
00:48:43,109 --> 00:48:46,390

 

1516
00:48:46,390 --> 00:48:48,230

 

1517
00:48:48,230 --> 00:48:48,240

 

1518
00:48:48,240 --> 00:48:50,150


1519
00:48:50,150 --> 00:48:50,160

 

1520
00:48:50,160 --> 00:48:51,030


1521
00:48:51,030 --> 00:48:52,870

 

1522
00:48:52,870 --> 00:48:55,349

 

1523
00:48:55,349 --> 00:48:57,030

 

1524
00:48:57,030 --> 00:48:59,270

 

1525
00:48:59,270 --> 00:49:03,670

 

1526
00:49:03,670 --> 00:49:05,190

 

1527
00:49:05,190 --> 00:49:07,510

 

1528
00:49:07,510 --> 00:49:10,950

 

1529
00:49:10,950 --> 00:49:13,270

 

1530
00:49:13,270 --> 00:49:13,280

 

1531
00:49:13,280 --> 00:49:14,150


1532
00:49:14,150 --> 00:49:17,910

 

1533
00:49:17,910 --> 00:49:20,470

 

1534
00:49:20,470 --> 00:49:21,829

 

1535
00:49:21,829 --> 00:49:24,069

 

1536
00:49:24,069 --> 00:49:26,150

 

1537
00:49:26,150 --> 00:49:28,710

 

1538
00:49:28,710 --> 00:49:30,309

 

1539
00:49:30,309 --> 00:49:33,510

 

1540
00:49:33,510 --> 00:49:37,430

 

1541
00:49:37,430 --> 00:49:40,390

 

1542
00:49:40,390 --> 00:49:43,030

 

1543
00:49:43,030 --> 00:49:44,710

 

1544
00:49:44,710 --> 00:49:44,720

 

1545
00:49:44,720 --> 00:49:46,470


1546
00:49:46,470 --> 00:49:48,950

 

1547
00:49:48,950 --> 00:49:51,430

 

1548
00:49:51,430 --> 00:49:53,190

 

1549
00:49:53,190 --> 00:49:53,200

 

1550
00:49:53,200 --> 00:49:54,230


1551
00:49:54,230 --> 00:49:56,390

 

1552
00:49:56,390 --> 00:49:56,400

 

1553
00:49:56,400 --> 00:49:58,790


1554
00:49:58,790 --> 00:50:01,349

 

1555
00:50:01,349 --> 00:50:03,910

 

1556
00:50:03,910 --> 00:50:06,309

 

1557
00:50:06,309 --> 00:50:08,230

 

1558
00:50:08,230 --> 00:50:10,230

 

1559
00:50:10,230 --> 00:50:11,829

 

1560
00:50:11,829 --> 00:50:13,910

 

1561
00:50:13,910 --> 00:50:15,750

 

1562
00:50:15,750 --> 00:50:16,710

 

1563
00:50:16,710 --> 00:50:19,270

 

1564
00:50:19,270 --> 00:50:21,750

 

1565
00:50:21,750 --> 00:50:23,750

 

1566
00:50:23,750 --> 00:50:27,349

 

1567
00:50:27,349 --> 00:50:29,030

 

1568
00:50:29,030 --> 00:50:29,040

 

1569
00:50:29,040 --> 00:50:31,109


1570
00:50:31,109 --> 00:50:33,750

 

1571
00:50:33,750 --> 00:50:33,760

 

1572
00:50:33,760 --> 00:50:34,549


1573
00:50:34,549 --> 00:50:37,430

 

1574
00:50:37,430 --> 00:50:40,150

 

1575
00:50:40,150 --> 00:50:41,430

 

1576
00:50:41,430 --> 00:50:43,750

 

1577
00:50:43,750 --> 00:50:45,510

 

1578
00:50:45,510 --> 00:50:47,349

 

1579
00:50:47,349 --> 00:50:49,589

 

1580
00:50:49,589 --> 00:50:51,510

 

1581
00:50:51,510 --> 00:50:53,270

 

1582
00:50:53,270 --> 00:50:56,150

 

1583
00:50:56,150 --> 00:50:59,430

 

1584
00:50:59,430 --> 00:50:59,440

 

1585
00:50:59,440 --> 00:51:00,630


1586
00:51:00,630 --> 00:51:09,030

 

1587
00:51:09,030 --> 00:51:11,430

 

1588
00:51:11,430 --> 00:51:12,950

 

1589
00:51:12,950 --> 00:51:15,109

 

1590
00:51:15,109 --> 00:51:17,349

 

1591
00:51:17,349 --> 00:51:20,069

 

1592
00:51:20,069 --> 00:51:23,190

 

1593
00:51:23,190 --> 00:51:25,750

 

1594
00:51:25,750 --> 00:51:25,760

 

1595
00:51:25,760 --> 00:51:26,630


1596
00:51:26,630 --> 00:51:27,670

 

1597
00:51:27,670 --> 00:51:29,270

 

1598
00:51:29,270 --> 00:51:31,190

 

1599
00:51:31,190 --> 00:51:34,829

 

1600
00:51:34,829 --> 00:51:37,829

 

1601
00:51:37,829 --> 00:51:37,839

 

1602
00:51:37,839 --> 00:51:39,030


1603
00:51:39,030 --> 00:51:40,870

 

1604
00:51:40,870 --> 00:51:42,549

 

1605
00:51:42,549 --> 00:51:44,790

 

1606
00:51:44,790 --> 00:51:46,870

 

1607
00:51:46,870 --> 00:51:49,430

 

1608
00:51:49,430 --> 00:51:50,549

 

1609
00:51:50,549 --> 00:51:50,559

 

1610
00:51:50,559 --> 00:51:52,870


1611
00:51:52,870 --> 00:51:54,790

 

1612
00:51:54,790 --> 00:51:58,549

 

1613
00:51:58,549 --> 00:52:00,230

 

1614
00:52:00,230 --> 00:52:03,109

 

1615
00:52:03,109 --> 00:52:04,710

 

1616
00:52:04,710 --> 00:52:05,910

 

1617
00:52:05,910 --> 00:52:05,920

 

1618
00:52:05,920 --> 00:52:07,270


1619
00:52:07,270 --> 00:52:07,280

 

1620
00:52:07,280 --> 00:52:10,309


1621
00:52:10,309 --> 00:52:13,670

 

1622
00:52:13,670 --> 00:52:15,750

 

1623
00:52:15,750 --> 00:52:17,910

 

1624
00:52:17,910 --> 00:52:19,990

 

1625
00:52:19,990 --> 00:52:21,589

 

1626
00:52:21,589 --> 00:52:22,790

 

1627
00:52:22,790 --> 00:52:24,950

 

1628
00:52:24,950 --> 00:52:26,150

 

1629
00:52:26,150 --> 00:52:27,750

 

1630
00:52:27,750 --> 00:52:29,829

 

1631
00:52:29,829 --> 00:52:32,630

 

1632
00:52:32,630 --> 00:52:35,270

 

1633
00:52:35,270 --> 00:52:37,270

 

1634
00:52:37,270 --> 00:52:39,349

 

1635
00:52:39,349 --> 00:52:42,309

 

1636
00:52:42,309 --> 00:52:44,790

 

1637
00:52:44,790 --> 00:52:48,150

 

1638
00:52:48,150 --> 00:52:50,790

 

1639
00:52:50,790 --> 00:52:52,710

 

1640
00:52:52,710 --> 00:52:54,309

 

1641
00:52:54,309 --> 00:52:55,829

 

1642
00:52:55,829 --> 00:52:57,349

 

1643
00:52:57,349 --> 00:52:57,359

 

1644
00:52:57,359 --> 00:52:58,710


1645
00:52:58,710 --> 00:52:58,720

 

1646
00:52:58,720 --> 00:52:59,589


1647
00:52:59,589 --> 00:53:01,910

 

1648
00:53:01,910 --> 00:53:03,670

 

1649
00:53:03,670 --> 00:53:05,910

 

1650
00:53:05,910 --> 00:53:08,309

 

1651
00:53:08,309 --> 00:53:10,150

 

1652
00:53:10,150 --> 00:53:12,829

 

1653
00:53:12,829 --> 00:53:12,839

 

1654
00:53:12,839 --> 00:53:14,390


1655
00:53:14,390 --> 00:53:15,990

 

1656
00:53:15,990 --> 00:53:17,910

 

1657
00:53:17,910 --> 00:53:21,670

 

1658
00:53:21,670 --> 00:53:21,680

 

1659
00:53:21,680 --> 00:53:22,790


1660
00:53:22,790 --> 00:53:24,309

 

1661
00:53:24,309 --> 00:53:26,549

 

1662
00:53:26,549 --> 00:53:28,470

 

1663
00:53:28,470 --> 00:53:31,670

 

1664
00:53:31,670 --> 00:53:34,390

 

1665
00:53:34,390 --> 00:53:34,400

 

1666
00:53:34,400 --> 00:53:35,270


1667
00:53:35,270 --> 00:53:37,430

 

1668
00:53:37,430 --> 00:53:38,950

 

1669
00:53:38,950 --> 00:53:39,829

 

1670
00:53:39,829 --> 00:53:43,510

 

1671
00:53:43,510 --> 00:53:45,109

 

1672
00:53:45,109 --> 00:53:45,119

 

1673
00:53:45,119 --> 00:53:46,470


1674
00:53:46,470 --> 00:53:50,630

 

1675
00:53:50,630 --> 00:53:50,640

 

1676
00:53:50,640 --> 00:53:52,549


1677
00:53:52,549 --> 00:53:55,190

 

1678
00:53:55,190 --> 00:53:56,549

 

1679
00:53:56,549 --> 00:53:58,069

 

1680
00:53:58,069 --> 00:53:59,829

 

1681
00:53:59,829 --> 00:54:01,190

 

1682
00:54:01,190 --> 00:54:03,109

 

1683
00:54:03,109 --> 00:54:03,119

 

1684
00:54:03,119 --> 00:54:04,710


1685
00:54:04,710 --> 00:54:07,349

 

1686
00:54:07,349 --> 00:54:10,549

 

1687
00:54:10,549 --> 00:54:13,990

 

1688
00:54:13,990 --> 00:54:15,750

 

1689
00:54:15,750 --> 00:54:20,069

 

1690
00:54:20,069 --> 00:54:22,710

 

1691
00:54:22,710 --> 00:54:24,630

 

1692
00:54:24,630 --> 00:54:27,750

 

1693
00:54:27,750 --> 00:54:29,270

 

1694
00:54:29,270 --> 00:54:30,870

 

1695
00:54:30,870 --> 00:54:32,710

 

1696
00:54:32,710 --> 00:54:34,950

 

1697
00:54:34,950 --> 00:54:34,960

 

1698
00:54:34,960 --> 00:54:36,870


1699
00:54:36,870 --> 00:54:40,069

 

1700
00:54:40,069 --> 00:54:42,309

 

1701
00:54:42,309 --> 00:54:43,750

 

1702
00:54:43,750 --> 00:54:45,109

 

1703
00:54:45,109 --> 00:54:48,950

 

1704
00:54:48,950 --> 00:54:52,870

 

1705
00:54:52,870 --> 00:54:54,390

 

1706
00:54:54,390 --> 00:54:59,349

 

1707
00:54:59,349 --> 00:55:01,750

 

1708
00:55:01,750 --> 00:55:04,950

 

1709
00:55:04,950 --> 00:55:08,470

 

1710
00:55:08,470 --> 00:55:08,480

 

1711
00:55:08,480 --> 00:55:09,910


1712
00:55:09,910 --> 00:55:12,710

 

1713
00:55:12,710 --> 00:55:14,470

 

1714
00:55:14,470 --> 00:55:16,069

 

1715
00:55:16,069 --> 00:55:18,829

 

1716
00:55:18,829 --> 00:55:18,839

 

1717
00:55:18,839 --> 00:55:20,470


1718
00:55:20,470 --> 00:55:22,549

 

1719
00:55:22,549 --> 00:55:24,069

 

1720
00:55:24,069 --> 00:55:26,230

 

1721
00:55:26,230 --> 00:55:27,750

 

1722
00:55:27,750 --> 00:55:30,150

 

1723
00:55:30,150 --> 00:55:31,910

 

1724
00:55:31,910 --> 00:55:33,430

 

1725
00:55:33,430 --> 00:55:35,349

 

1726
00:55:35,349 --> 00:55:36,789

 

1727
00:55:36,789 --> 00:55:36,799

 

1728
00:55:36,799 --> 00:55:38,630


1729
00:55:38,630 --> 00:55:41,190

 

1730
00:55:41,190 --> 00:55:41,200

 

1731
00:55:41,200 --> 00:55:42,710


1732
00:55:42,710 --> 00:55:44,789

 

1733
00:55:44,789 --> 00:55:46,230

 

1734
00:55:46,230 --> 00:55:50,309

 

1735
00:55:50,309 --> 00:55:52,150

 

1736
00:55:52,150 --> 00:55:54,069

 

1737
00:55:54,069 --> 00:55:56,069

 

1738
00:55:56,069 --> 00:55:58,789

 

1739
00:55:58,789 --> 00:56:02,150

 

1740
00:56:02,150 --> 00:56:02,160

 

1741
00:56:02,160 --> 00:56:02,580


1742
00:56:02,580 --> 00:56:02,590

 

1743
00:56:02,590 --> 00:56:04,390


1744
00:56:04,390 --> 00:56:04,400

 

1745
00:56:04,400 --> 00:56:05,829


1746
00:56:05,829 --> 00:56:05,839

 

1747
00:56:05,839 --> 00:56:07,190


1748
00:56:07,190 --> 00:56:09,430

 

1749
00:56:09,430 --> 00:56:11,030

 

1750
00:56:11,030 --> 00:56:11,040

 

1751
00:56:11,040 --> 00:56:12,309


1752
00:56:12,309 --> 00:56:15,270

 

1753
00:56:15,270 --> 00:56:18,470

 

1754
00:56:18,470 --> 00:56:21,829

 

1755
00:56:21,829 --> 00:56:23,030

 

1756
00:56:23,030 --> 00:56:25,829

 

1757
00:56:25,829 --> 00:56:25,839

 

1758
00:56:25,839 --> 00:56:26,710


1759
00:56:26,710 --> 00:56:30,470

 

1760
00:56:30,470 --> 00:56:32,789

 

1761
00:56:32,789 --> 00:56:34,230

 

1762
00:56:34,230 --> 00:56:36,150

 

1763
00:56:36,150 --> 00:56:38,630

 

1764
00:56:38,630 --> 00:56:40,470

 

1765
00:56:40,470 --> 00:56:42,470

 

1766
00:56:42,470 --> 00:56:44,390

 

1767
00:56:44,390 --> 00:56:46,870

 

1768
00:56:46,870 --> 00:56:48,390

 

1769
00:56:48,390 --> 00:56:49,990

 

1770
00:56:49,990 --> 00:56:52,390

 

1771
00:56:52,390 --> 00:56:53,430

 

1772
00:56:53,430 --> 00:56:55,109

 

1773
00:56:55,109 --> 00:56:55,119

 

1774
00:56:55,119 --> 00:56:56,150


1775
00:56:56,150 --> 00:56:59,750

 

1776
00:56:59,750 --> 00:57:01,430

 

1777
00:57:01,430 --> 00:57:04,870

 

1778
00:57:04,870 --> 00:57:04,880

 

1779
00:57:04,880 --> 00:57:05,670


1780
00:57:05,670 --> 00:57:07,670

 

1781
00:57:07,670 --> 00:57:09,829

 

1782
00:57:09,829 --> 00:57:12,630

 

1783
00:57:12,630 --> 00:57:14,309

 

1784
00:57:14,309 --> 00:57:16,950

 

1785
00:57:16,950 --> 00:57:20,150

 

1786
00:57:20,150 --> 00:57:22,069

 

1787
00:57:22,069 --> 00:57:24,829

 

1788
00:57:24,829 --> 00:57:24,839

 

1789
00:57:24,839 --> 00:57:26,470


1790
00:57:26,470 --> 00:57:28,390

 

1791
00:57:28,390 --> 00:57:30,710

 

1792
00:57:30,710 --> 00:57:32,870

 

1793
00:57:32,870 --> 00:57:32,880

 

1794
00:57:32,880 --> 00:57:33,990


1795
00:57:33,990 --> 00:57:39,829

 

1796
00:57:39,829 --> 00:57:43,109

 

1797
00:57:43,109 --> 00:57:44,150

 

1798
00:57:44,150 --> 00:57:46,069

 

1799
00:57:46,069 --> 00:57:47,750

 

1800
00:57:47,750 --> 00:57:51,030

 

1801
00:57:51,030 --> 00:57:52,789

 

1802
00:57:52,789 --> 00:57:54,630

 

1803
00:57:54,630 --> 00:57:57,430

 

1804
00:57:57,430 --> 00:57:58,350

 

1805
00:57:58,350 --> 00:57:58,360

 

1806
00:57:58,360 --> 00:58:00,309


1807
00:58:00,309 --> 00:58:02,549

 

1808
00:58:02,549 --> 00:58:04,150

 

1809
00:58:04,150 --> 00:58:06,950

 

1810
00:58:06,950 --> 00:58:08,870

 

1811
00:58:08,870 --> 00:58:08,880

 

1812
00:58:08,880 --> 00:58:10,230


1813
00:58:10,230 --> 00:58:12,069

 

1814
00:58:12,069 --> 00:58:13,910

 

1815
00:58:13,910 --> 00:58:16,710

 

1816
00:58:16,710 --> 00:58:16,720

 

1817
00:58:16,720 --> 00:58:20,710


1818
00:58:20,710 --> 00:58:24,150

 

1819
00:58:24,150 --> 00:58:25,750

 

1820
00:58:25,750 --> 00:58:27,589

 

1821
00:58:27,589 --> 00:58:27,599

 

1822
00:58:27,599 --> 00:58:28,710


1823
00:58:28,710 --> 00:58:31,030

 

1824
00:58:31,030 --> 00:58:33,349

 

1825
00:58:33,349 --> 00:58:33,359

 

1826
00:58:33,359 --> 00:58:34,789


1827
00:58:34,789 --> 00:58:37,349

 

1828
00:58:37,349 --> 00:58:39,750

 

1829
00:58:39,750 --> 00:58:41,430

 

1830
00:58:41,430 --> 00:58:43,750

 

1831
00:58:43,750 --> 00:58:47,430

 

1832
00:58:47,430 --> 00:58:50,230

 

1833
00:58:50,230 --> 00:58:51,430

 

1834
00:58:51,430 --> 00:58:53,109

 

1835
00:58:53,109 --> 00:58:53,119

 

1836
00:58:53,119 --> 00:58:55,750


1837
00:58:55,750 --> 00:58:57,990

 

1838
00:58:57,990 --> 00:58:59,510

 

1839
00:58:59,510 --> 00:59:01,990

 

1840
00:59:01,990 --> 00:59:03,510

 

1841
00:59:03,510 --> 00:59:06,150

 

1842
00:59:06,150 --> 00:59:08,470

 

1843
00:59:08,470 --> 00:59:10,710

 

1844
00:59:10,710 --> 00:59:10,720

 

1845
00:59:10,720 --> 00:59:13,589


1846
00:59:13,589 --> 00:59:13,599

 

1847
00:59:13,599 --> 00:59:14,470


1848
00:59:14,470 --> 00:59:17,510

 

1849
00:59:17,510 --> 00:59:19,910

 

1850
00:59:19,910 --> 00:59:21,750

 

1851
00:59:21,750 --> 00:59:25,030

 

1852
00:59:25,030 --> 00:59:27,430

 

1853
00:59:27,430 --> 00:59:27,440

 

1854
00:59:27,440 --> 00:59:28,789


1855
00:59:28,789 --> 00:59:31,750

 

1856
00:59:31,750 --> 00:59:34,309

 

1857
00:59:34,309 --> 00:59:34,319

 

1858
00:59:34,319 --> 00:59:36,470


1859
00:59:36,470 --> 00:59:36,480

 

1860
00:59:36,480 --> 00:59:37,670


1861
00:59:37,670 --> 00:59:39,270

 

1862
00:59:39,270 --> 00:59:41,190

 

1863
00:59:41,190 --> 00:59:45,109

 

1864
00:59:45,109 --> 00:59:47,430

 

1865
00:59:47,430 --> 00:59:50,150

 

1866
00:59:50,150 --> 00:59:54,069

 

1867
00:59:54,069 --> 00:59:55,670

 

1868
00:59:55,670 --> 00:59:58,069

 

1869
00:59:58,069 --> 00:59:59,990

 

1870
00:59:59,990 --> 01:00:01,829

 

1871
01:00:01,829 --> 01:00:03,670

 

1872
01:00:03,670 --> 01:00:06,630

 

1873
01:00:06,630 --> 01:00:06,640

 

1874
01:00:06,640 --> 01:00:08,950


1875
01:00:08,950 --> 01:00:11,190

 

1876
01:00:11,190 --> 01:00:12,549

 

1877
01:00:12,549 --> 01:00:14,309

 

1878
01:00:14,309 --> 01:00:16,549

 

1879
01:00:16,549 --> 01:00:18,150

 

1880
01:00:18,150 --> 01:00:20,069

 

1881
01:00:20,069 --> 01:00:21,829

 

1882
01:00:21,829 --> 01:00:25,910

 

1883
01:00:25,910 --> 01:00:28,309

 

1884
01:00:28,309 --> 01:00:30,390

 

1885
01:00:30,390 --> 01:00:33,109

 

1886
01:00:33,109 --> 01:00:35,030

 

1887
01:00:35,030 --> 01:00:35,040

 

1888
01:00:35,040 --> 01:00:36,309


1889
01:00:36,309 --> 01:00:39,109

 

1890
01:00:39,109 --> 01:00:41,510

 

1891
01:00:41,510 --> 01:00:45,510

 

1892
01:00:45,510 --> 01:00:48,230

 

1893
01:00:48,230 --> 01:00:50,390

 

1894
01:00:50,390 --> 01:00:50,400

 

1895
01:00:50,400 --> 01:00:51,870


1896
01:00:51,870 --> 01:00:53,990

 

1897
01:00:53,990 --> 01:00:57,030

 

1898
01:00:57,030 --> 01:00:59,829

 

1899
01:00:59,829 --> 01:01:03,030

 

1900
01:01:03,030 --> 01:01:04,710

 

1901
01:01:04,710 --> 01:01:04,720

 

1902
01:01:04,720 --> 01:01:08,390


1903
01:01:08,390 --> 01:01:08,400

 

1904
01:01:08,400 --> 01:01:09,349


1905
01:01:09,349 --> 01:01:11,109

 

1906
01:01:11,109 --> 01:01:13,990

 

1907
01:01:13,990 --> 01:01:16,309

 

1908
01:01:16,309 --> 01:01:17,510

 

1909
01:01:17,510 --> 01:01:20,549

 

1910
01:01:20,549 --> 01:01:24,390

 

1911
01:01:24,390 --> 01:01:26,309

 

1912
01:01:26,309 --> 01:01:28,470

 

1913
01:01:28,470 --> 01:01:29,829

 

1914
01:01:29,829 --> 01:01:31,430

 

1915
01:01:31,430 --> 01:01:33,190

 

1916
01:01:33,190 --> 01:01:33,200

 

1917
01:01:33,200 --> 01:01:34,549


1918
01:01:34,549 --> 01:01:36,549

 

1919
01:01:36,549 --> 01:01:45,190

 

1920
01:01:45,190 --> 01:01:48,150

 

1921
01:01:48,150 --> 01:01:51,270

 

1922
01:01:51,270 --> 01:01:54,390

 

1923
01:01:54,390 --> 01:01:59,910

 

1924
01:01:59,910 --> 01:02:02,710

 

1925
01:02:02,710 --> 01:02:05,430

 

1926
01:02:05,430 --> 01:02:07,910

 

1927
01:02:07,910 --> 01:02:09,349

 

1928
01:02:09,349 --> 01:02:11,109

 

1929
01:02:11,109 --> 01:02:11,119

 

1930
01:02:11,119 --> 01:02:13,750


1931
01:02:13,750 --> 01:02:15,270

 

1932
01:02:15,270 --> 01:02:17,750

 

1933
01:02:17,750 --> 01:02:19,670

 

1934
01:02:19,670 --> 01:02:21,430

 

1935
01:02:21,430 --> 01:02:21,440

 

1936
01:02:21,440 --> 01:02:22,710


1937
01:02:22,710 --> 01:02:25,589

 

1938
01:02:25,589 --> 01:02:27,430

 

1939
01:02:27,430 --> 01:02:29,109

 

1940
01:02:29,109 --> 01:02:31,670

 

1941
01:02:31,670 --> 01:02:33,589

 

1942
01:02:33,589 --> 01:02:35,109

 

1943
01:02:35,109 --> 01:02:36,789

 

1944
01:02:36,789 --> 01:02:39,430

 

1945
01:02:39,430 --> 01:02:41,750

 

1946
01:02:41,750 --> 01:02:41,760

 

1947
01:02:41,760 --> 01:02:42,549


1948
01:02:42,549 --> 01:02:42,559

 

1949
01:02:42,559 --> 01:02:44,549


1950
01:02:44,549 --> 01:02:47,430

 

1951
01:02:47,430 --> 01:02:49,029

 

1952
01:02:49,029 --> 01:02:50,470

 

1953
01:02:50,470 --> 01:02:52,630

 

1954
01:02:52,630 --> 01:02:56,309

 

1955
01:02:56,309 --> 01:02:56,319

 

1956
01:02:56,319 --> 01:02:59,750


1957
01:02:59,750 --> 01:03:01,670

 

1958
01:03:01,670 --> 01:03:03,029

 

1959
01:03:03,029 --> 01:03:05,190

 

1960
01:03:05,190 --> 01:03:07,670

 

1961
01:03:07,670 --> 01:03:09,270

 

1962
01:03:09,270 --> 01:03:10,789

 

1963
01:03:10,789 --> 01:03:12,230

 

1964
01:03:12,230 --> 01:03:14,309

 

1965
01:03:14,309 --> 01:03:16,470

 

1966
01:03:16,470 --> 01:03:17,829

 

1967
01:03:17,829 --> 01:03:19,910

 

1968
01:03:19,910 --> 01:03:22,069

 

1969
01:03:22,069 --> 01:03:22,079

 

1970
01:03:22,079 --> 01:03:23,029


1971
01:03:23,029 --> 01:03:24,710

 

1972
01:03:24,710 --> 01:03:25,990

 

1973
01:03:25,990 --> 01:03:27,589

 

1974
01:03:27,589 --> 01:03:29,510

 

1975
01:03:29,510 --> 01:03:31,510

 

1976
01:03:31,510 --> 01:03:34,870

 

1977
01:03:34,870 --> 01:03:37,510

 

1978
01:03:37,510 --> 01:03:40,630

 

1979
01:03:40,630 --> 01:03:42,789

 

1980
01:03:42,789 --> 01:03:44,390

 

1981
01:03:44,390 --> 01:03:46,230

 

1982
01:03:46,230 --> 01:03:48,390

 

1983
01:03:48,390 --> 01:03:48,400

 

1984
01:03:48,400 --> 01:03:50,470


1985
01:03:50,470 --> 01:03:52,549

 

1986
01:03:52,549 --> 01:03:53,829

 

1987
01:03:53,829 --> 01:03:55,589

 

1988
01:03:55,589 --> 01:03:58,870

 

1989
01:03:58,870 --> 01:04:00,069

 

1990
01:04:00,069 --> 01:04:02,069

 

1991
01:04:02,069 --> 01:04:03,990

 

1992
01:04:03,990 --> 01:04:05,270

 

1993
01:04:05,270 --> 01:04:08,390

 

1994
01:04:08,390 --> 01:04:10,789

 

1995
01:04:10,789 --> 01:04:13,270

 

1996
01:04:13,270 --> 01:04:15,829

 

1997
01:04:15,829 --> 01:04:18,470

 

1998
01:04:18,470 --> 01:04:20,390

 

1999
01:04:20,390 --> 01:04:20,400

 

2000
01:04:20,400 --> 01:04:21,270


2001
01:04:21,270 --> 01:04:23,430

 

2002
01:04:23,430 --> 01:04:25,589

 

2003
01:04:25,589 --> 01:04:28,870

 

2004
01:04:28,870 --> 01:04:31,029

 

2005
01:04:31,029 --> 01:04:32,710

 

2006
01:04:32,710 --> 01:04:35,029

 

2007
01:04:35,029 --> 01:04:37,270

 

2008
01:04:37,270 --> 01:04:39,990

 

2009
01:04:39,990 --> 01:04:42,950

 

2010
01:04:42,950 --> 01:04:44,549

 

2011
01:04:44,549 --> 01:04:46,710

 

2012
01:04:46,710 --> 01:04:48,549

 

2013
01:04:48,549 --> 01:04:50,870

 

2014
01:04:50,870 --> 01:04:52,630

 

2015
01:04:52,630 --> 01:04:52,640

 

2016
01:04:52,640 --> 01:04:54,549


2017
01:04:54,549 --> 01:04:57,109

 

2018
01:04:57,109 --> 01:04:59,190

 

2019
01:04:59,190 --> 01:05:01,029

 

2020
01:05:01,029 --> 01:05:02,549

 

2021
01:05:02,549 --> 01:05:04,549

 

2022
01:05:04,549 --> 01:05:06,309

 

2023
01:05:06,309 --> 01:05:09,589

 

2024
01:05:09,589 --> 01:05:11,349

 

2025
01:05:11,349 --> 01:05:11,359

 

2026
01:05:11,359 --> 01:05:14,309


2027
01:05:14,309 --> 01:05:16,390

 

2028
01:05:16,390 --> 01:05:19,109

 

2029
01:05:19,109 --> 01:05:21,109

 

2030
01:05:21,109 --> 01:05:22,950

 

2031
01:05:22,950 --> 01:05:22,960

 

2032
01:05:22,960 --> 01:05:23,750


2033
01:05:23,750 --> 01:05:25,829

 

2034
01:05:25,829 --> 01:05:28,069

 

2035
01:05:28,069 --> 01:05:30,630

 

2036
01:05:30,630 --> 01:05:32,549

 

2037
01:05:32,549 --> 01:05:36,710

 

2038
01:05:36,710 --> 01:05:38,470

 

2039
01:05:38,470 --> 01:05:42,150

 

2040
01:05:42,150 --> 01:05:45,349

 

2041
01:05:45,349 --> 01:05:45,359

 

2042
01:05:45,359 --> 01:05:46,870


2043
01:05:46,870 --> 01:05:50,470

 

2044
01:05:50,470 --> 01:05:53,270

 

2045
01:05:53,270 --> 01:05:55,750

 

2046
01:05:55,750 --> 01:05:55,760

 

2047
01:05:55,760 --> 01:05:57,270


2048
01:05:57,270 --> 01:06:00,390

 

2049
01:06:00,390 --> 01:06:00,400

 

2050
01:06:00,400 --> 01:06:01,349


2051
01:06:01,349 --> 01:06:04,470

 

2052
01:06:04,470 --> 01:06:04,480

 

2053
01:06:04,480 --> 01:06:06,309


2054
01:06:06,309 --> 01:06:06,319

 

2055
01:06:06,319 --> 01:06:09,589


2056
01:06:09,589 --> 01:06:11,270

 

2057
01:06:11,270 --> 01:06:13,510

 

2058
01:06:13,510 --> 01:06:13,520

 

2059
01:06:13,520 --> 01:06:14,710


2060
01:06:14,710 --> 01:06:18,069

 

2061
01:06:18,069 --> 01:06:20,950

 

2062
01:06:20,950 --> 01:06:20,960

 

2063
01:06:20,960 --> 01:06:21,990


2064
01:06:21,990 --> 01:06:24,150

 

2065
01:06:24,150 --> 01:06:24,160

 

2066
01:06:24,160 --> 01:06:26,789


2067
01:06:26,789 --> 01:06:26,799

 

2068
01:06:26,799 --> 01:06:28,710


2069
01:06:28,710 --> 01:06:32,870

 

2070
01:06:32,870 --> 01:06:36,470

 

2071
01:06:36,470 --> 01:06:37,990

 

2072
01:06:37,990 --> 01:06:40,470

 

2073
01:06:40,470 --> 01:06:42,390

 

2074
01:06:42,390 --> 01:06:44,069

 

2075
01:06:44,069 --> 01:06:45,990

 

2076
01:06:45,990 --> 01:06:47,510

 

2077
01:06:47,510 --> 01:06:49,670

 

2078
01:06:49,670 --> 01:06:52,710

 

2079
01:06:52,710 --> 01:06:54,390

 

2080
01:06:54,390 --> 01:06:56,470

 

2081
01:06:56,470 --> 01:07:00,150

 

2082
01:07:00,150 --> 01:07:00,160

 

2083
01:07:00,160 --> 01:07:01,190


2084
01:07:01,190 --> 01:07:01,200

 

2085
01:07:01,200 --> 01:07:03,430


2086
01:07:03,430 --> 01:07:05,430

 

2087
01:07:05,430 --> 01:07:06,870

 

2088
01:07:06,870 --> 01:07:09,029

 

2089
01:07:09,029 --> 01:07:11,109

 

2090
01:07:11,109 --> 01:07:14,309

 

2091
01:07:14,309 --> 01:07:15,990

 

2092
01:07:15,990 --> 01:07:18,950

 

2093
01:07:18,950 --> 01:07:22,710

 

2094
01:07:22,710 --> 01:07:27,990

 

2095
01:07:27,990 --> 01:07:29,829

 

2096
01:07:29,829 --> 01:07:31,270

 

2097
01:07:31,270 --> 01:07:33,990

 

2098
01:07:33,990 --> 01:07:35,270

 

2099
01:07:35,270 --> 01:07:35,280

 

2100
01:07:35,280 --> 01:07:37,430


2101
01:07:37,430 --> 01:07:40,230

 

2102
01:07:40,230 --> 01:07:43,349

 

2103
01:07:43,349 --> 01:07:48,230

 

2104
01:07:48,230 --> 01:07:48,240

 

2105
01:07:48,240 --> 01:07:49,589


2106
01:07:49,589 --> 01:07:51,670

 

2107
01:07:51,670 --> 01:07:54,069

 

2108
01:07:54,069 --> 01:07:55,829

 

2109
01:07:55,829 --> 01:07:55,839

 

2110
01:07:55,839 --> 01:07:57,510


2111
01:07:57,510 --> 01:08:00,150

 

2112
01:08:00,150 --> 01:08:01,349

 

2113
01:08:01,349 --> 01:08:03,670

 

2114
01:08:03,670 --> 01:08:05,029

 

2115
01:08:05,029 --> 01:08:06,950

 

2116
01:08:06,950 --> 01:08:08,470

 

2117
01:08:08,470 --> 01:08:11,510

 

2118
01:08:11,510 --> 01:08:15,670

 

2119
01:08:15,670 --> 01:08:17,430

 

2120
01:08:17,430 --> 01:08:19,669

 

2121
01:08:19,669 --> 01:08:21,749

 

2122
01:08:21,749 --> 01:08:23,749

 

2123
01:08:23,749 --> 01:08:25,430

 

2124
01:08:25,430 --> 01:08:27,030

 

2125
01:08:27,030 --> 01:08:29,110

 

2126
01:08:29,110 --> 01:08:32,229

 

2127
01:08:32,229 --> 01:08:33,749

 

2128
01:08:33,749 --> 01:08:35,749

 

2129
01:08:35,749 --> 01:08:37,030

 

2130
01:08:37,030 --> 01:08:40,470

 

2131
01:08:40,470 --> 01:08:42,309

 

2132
01:08:42,309 --> 01:08:43,189

 

2133
01:08:43,189 --> 01:08:45,990

 

2134
01:08:45,990 --> 01:08:47,430

 

2135
01:08:47,430 --> 01:08:49,669

 

2136
01:08:49,669 --> 01:08:52,229

 

2137
01:08:52,229 --> 01:08:53,910

 

2138
01:08:53,910 --> 01:08:55,669

 

2139
01:08:55,669 --> 01:08:58,149

 

2140
01:08:58,149 --> 01:08:59,269

 

2141
01:08:59,269 --> 01:09:00,630

 

2142
01:09:00,630 --> 01:09:04,550

 

2143
01:09:04,550 --> 01:09:08,229

 

2144
01:09:08,229 --> 01:09:10,390

 

2145
01:09:10,390 --> 01:09:12,630

 

2146
01:09:12,630 --> 01:09:14,630

 

2147
01:09:14,630 --> 01:09:16,870

 

2148
01:09:16,870 --> 01:09:18,829

 

2149
01:09:18,829 --> 01:09:18,839

 

2150
01:09:18,839 --> 01:09:20,789


2151
01:09:20,789 --> 01:09:22,470

 

2152
01:09:22,470 --> 01:09:24,229

 

2153
01:09:24,229 --> 01:09:27,030

 

2154
01:09:27,030 --> 01:09:28,789

 

2155
01:09:28,789 --> 01:09:30,149

 

2156
01:09:30,149 --> 01:09:32,070

 

2157
01:09:32,070 --> 01:09:34,149

 

2158
01:09:34,149 --> 01:09:36,709

 

2159
01:09:36,709 --> 01:09:38,470

 

2160
01:09:38,470 --> 01:09:41,189

 

2161
01:09:41,189 --> 01:09:43,669

 

2162
01:09:43,669 --> 01:09:45,030

 

2163
01:09:45,030 --> 01:09:45,040

 

2164
01:09:45,040 --> 01:09:46,309


2165
01:09:46,309 --> 01:09:49,269

 

2166
01:09:49,269 --> 01:09:52,789

 

2167
01:09:52,789 --> 01:09:56,070

 

2168
01:09:56,070 --> 01:09:59,030

 

2169
01:09:59,030 --> 01:09:59,040

 

2170
01:09:59,040 --> 01:10:00,229


2171
01:10:00,229 --> 01:10:02,229

 

2172
01:10:02,229 --> 01:10:04,470

 

2173
01:10:04,470 --> 01:10:05,990

 

2174
01:10:05,990 --> 01:10:07,510

 

2175
01:10:07,510 --> 01:10:09,830

 

2176
01:10:09,830 --> 01:10:12,790

 

2177
01:10:12,790 --> 01:10:16,790

 

2178
01:10:16,790 --> 01:10:19,830

 

2179
01:10:19,830 --> 01:10:22,390

 

2180
01:10:22,390 --> 01:10:24,070

 

2181
01:10:24,070 --> 01:10:28,149

 

2182
01:10:28,149 --> 01:10:28,159

 

2183
01:10:28,159 --> 01:10:29,110


2184
01:10:29,110 --> 01:10:30,790

 

2185
01:10:30,790 --> 01:10:30,800

 

2186
01:10:30,800 --> 01:10:35,430


2187
01:10:35,430 --> 01:10:35,440

 

2188
01:10:35,440 --> 01:10:37,830


2189
01:10:37,830 --> 01:10:39,430

 

2190
01:10:39,430 --> 01:10:41,350

 

2191
01:10:41,350 --> 01:10:43,030

 

2192
01:10:43,030 --> 01:10:45,750

 

2193
01:10:45,750 --> 01:10:47,510

 

2194
01:10:47,510 --> 01:10:49,270

 

2195
01:10:49,270 --> 01:10:50,790

 

2196
01:10:50,790 --> 01:10:52,310

 

2197
01:10:52,310 --> 01:10:56,709

 

2198
01:10:56,709 --> 01:10:58,070

 

2199
01:10:58,070 --> 01:11:00,149

 

2200
01:11:00,149 --> 01:11:02,070

 

2201
01:11:02,070 --> 01:11:04,390

 

2202
01:11:04,390 --> 01:11:05,910

 

2203
01:11:05,910 --> 01:11:08,070

 

2204
01:11:08,070 --> 01:11:10,470

 

2205
01:11:10,470 --> 01:11:11,910

 

2206
01:11:11,910 --> 01:11:13,590

 

2207
01:11:13,590 --> 01:11:13,600

 

2208
01:11:13,600 --> 01:11:15,030


2209
01:11:15,030 --> 01:11:17,350

 

2210
01:11:17,350 --> 01:11:20,149

 

2211
01:11:20,149 --> 01:11:22,390

 

2212
01:11:22,390 --> 01:11:23,910

 

2213
01:11:23,910 --> 01:11:25,590

 

2214
01:11:25,590 --> 01:11:27,350

 

2215
01:11:27,350 --> 01:11:28,870

 

2216
01:11:28,870 --> 01:11:31,430

 

2217
01:11:31,430 --> 01:11:35,430

 

2218
01:11:35,430 --> 01:11:37,590

 

2219
01:11:37,590 --> 01:11:41,350

 

2220
01:11:41,350 --> 01:11:41,360

 

2221
01:11:41,360 --> 01:11:43,350


2222
01:11:43,350 --> 01:11:43,360

 

2223
01:11:43,360 --> 01:11:44,310


2224
01:11:44,310 --> 01:11:45,910

 

2225
01:11:45,910 --> 01:11:45,920

 

2226
01:11:45,920 --> 01:11:46,880


2227
01:11:46,880 --> 01:11:46,890

 

2228
01:11:46,890 --> 01:11:49,910


2229
01:11:49,910 --> 01:11:53,350

 

2230
01:11:53,350 --> 01:11:59,030

 

2231
01:11:59,030 --> 01:12:02,550

 

2232
01:12:02,550 --> 01:12:06,390

 

2233
01:12:06,390 --> 01:12:10,470

 

2234
01:12:10,470 --> 01:12:12,390

 

2235
01:12:12,390 --> 01:12:14,470

 

2236
01:12:14,470 --> 01:12:17,750

 

2237
01:12:17,750 --> 01:12:19,430

 

2238
01:12:19,430 --> 01:12:21,910

 

2239
01:12:21,910 --> 01:12:24,070

 

2240
01:12:24,070 --> 01:12:27,669

 

2241
01:12:27,669 --> 01:12:30,149

 

2242
01:12:30,149 --> 01:12:32,709

 

2243
01:12:32,709 --> 01:12:35,110

 

2244
01:12:35,110 --> 01:12:37,910

 

2245
01:12:37,910 --> 01:12:39,430

 

2246
01:12:39,430 --> 01:12:39,440

 

2247
01:12:39,440 --> 01:12:41,830


2248
01:12:41,830 --> 01:12:43,750

 

2249
01:12:43,750 --> 01:12:46,310

 

2250
01:12:46,310 --> 01:12:46,320

 

2251
01:12:46,320 --> 01:12:48,310


2252
01:12:48,310 --> 01:12:50,790

 

2253
01:12:50,790 --> 01:12:52,550

 

2254
01:12:52,550 --> 01:12:52,560

 

2255
01:12:52,560 --> 01:12:53,590


2256
01:12:53,590 --> 01:12:56,390

 

2257
01:12:56,390 --> 01:12:58,470

 

2258
01:12:58,470 --> 01:13:00,709

 

2259
01:13:00,709 --> 01:13:05,110

 

2260
01:13:05,110 --> 01:13:07,270

 

2261
01:13:07,270 --> 01:13:09,270

 

2262
01:13:09,270 --> 01:13:12,149

 

2263
01:13:12,149 --> 01:13:12,159

 

2264
01:13:12,159 --> 01:13:15,510


2265
01:13:15,510 --> 01:13:18,070

 

2266
01:13:18,070 --> 01:13:18,080

 

2267
01:13:18,080 --> 01:13:21,270


2268
01:13:21,270 --> 01:13:21,280

 

2269
01:13:21,280 --> 01:13:22,870


2270
01:13:22,870 --> 01:13:26,070

 

2271
01:13:26,070 --> 01:13:29,030

 

2272
01:13:29,030 --> 01:13:33,110

 

2273
01:13:33,110 --> 01:13:34,950

 

2274
01:13:34,950 --> 01:13:37,270

 

2275
01:13:37,270 --> 01:13:41,030

 

2276
01:13:41,030 --> 01:13:42,550

 

2277
01:13:42,550 --> 01:13:45,270

 

2278
01:13:45,270 --> 01:13:47,110

 

2279
01:13:47,110 --> 01:13:49,990

 

2280
01:13:49,990 --> 01:13:50,000

 

2281
01:13:50,000 --> 01:13:52,070


2282
01:13:52,070 --> 01:13:52,080

 

2283
01:13:52,080 --> 01:13:53,430


2284
01:13:53,430 --> 01:13:55,350

 

2285
01:13:55,350 --> 01:13:57,110

 

2286
01:13:57,110 --> 01:13:59,350

 

2287
01:13:59,350 --> 01:14:00,870

 

2288
01:14:00,870 --> 01:14:02,390

 

2289
01:14:02,390 --> 01:14:10,470

 

2290
01:14:10,470 --> 01:14:11,990

 

2291
01:14:11,990 --> 01:14:13,910

 

2292
01:14:13,910 --> 01:14:16,709

 

2293
01:14:16,709 --> 01:14:18,310

 

2294
01:14:18,310 --> 01:14:19,669

 

2295
01:14:19,669 --> 01:14:21,830

 

2296
01:14:21,830 --> 01:14:25,510

 

2297
01:14:25,510 --> 01:14:27,510

 

2298
01:14:27,510 --> 01:14:29,510

 

2299
01:14:29,510 --> 01:14:30,709

 

2300
01:14:30,709 --> 01:14:31,669

 

2301
01:14:31,669 --> 01:14:33,510

 

2302
01:14:33,510 --> 01:14:35,030

 

2303
01:14:35,030 --> 01:14:37,830

 

2304
01:14:37,830 --> 01:14:40,830

 

2305
01:14:40,830 --> 01:14:43,990

 

2306
01:14:43,990 --> 01:14:45,590

 

2307
01:14:45,590 --> 01:14:47,590

 

2308
01:14:47,590 --> 01:14:49,110

 

2309
01:14:49,110 --> 01:14:50,470

 

2310
01:14:50,470 --> 01:14:50,480

 

2311
01:14:50,480 --> 01:14:53,189


2312
01:14:53,189 --> 01:14:59,030

 

2313
01:14:59,030 --> 01:15:01,350

 

2314
01:15:01,350 --> 01:15:03,030

 

2315
01:15:03,030 --> 01:15:04,470

 

2316
01:15:04,470 --> 01:15:06,790

 

2317
01:15:06,790 --> 01:15:09,189

 

2318
01:15:09,189 --> 01:15:11,270

 

2319
01:15:11,270 --> 01:15:13,750

 

2320
01:15:13,750 --> 01:15:17,189

 

2321
01:15:17,189 --> 01:15:17,199

 

2322
01:15:17,199 --> 01:15:18,229


2323
01:15:18,229 --> 01:15:20,550

 

2324
01:15:20,550 --> 01:15:20,560

 

2325
01:15:20,560 --> 01:15:22,310


2326
01:15:22,310 --> 01:15:24,390

 

2327
01:15:24,390 --> 01:15:27,030

 

2328
01:15:27,030 --> 01:15:28,709

 

2329
01:15:28,709 --> 01:15:31,750

 

2330
01:15:31,750 --> 01:15:34,149

 

2331
01:15:34,149 --> 01:15:35,830

 

2332
01:15:35,830 --> 01:15:37,510

 

2333
01:15:37,510 --> 01:15:39,430

 

2334
01:15:39,430 --> 01:15:41,350

 

2335
01:15:41,350 --> 01:15:42,950

 

2336
01:15:42,950 --> 01:15:42,960

 

2337
01:15:42,960 --> 01:15:45,750


2338
01:15:45,750 --> 01:15:47,030

 

2339
01:15:47,030 --> 01:15:49,750

 

2340
01:15:49,750 --> 01:15:51,750

 

2341
01:15:51,750 --> 01:15:57,270

 

2342
01:15:57,270 --> 01:15:57,280

 

2343
01:15:57,280 --> 01:15:59,350


2344
01:15:59,350 --> 01:16:01,910

 

2345
01:16:01,910 --> 01:16:05,110

 

2346
01:16:05,110 --> 01:16:07,110

 

2347
01:16:07,110 --> 01:16:10,070

 

2348
01:16:10,070 --> 01:16:12,310

 

2349
01:16:12,310 --> 01:16:14,550

 

2350
01:16:14,550 --> 01:16:16,630

 

2351
01:16:16,630 --> 01:16:19,030

 

2352
01:16:19,030 --> 01:16:21,030

 

2353
01:16:21,030 --> 01:16:22,870

 

2354
01:16:22,870 --> 01:16:22,880

 

2355
01:16:22,880 --> 01:16:24,390


2356
01:16:24,390 --> 01:16:24,710

 

2357
01:16:24,710 --> 01:16:24,720

 

2358
01:16:24,720 --> 01:16:25,990


2359
01:16:25,990 --> 01:16:27,590

 

2360
01:16:27,590 --> 01:16:30,550

 

2361
01:16:30,550 --> 01:16:35,030

 

2362
01:16:35,030 --> 01:16:38,229

 

2363
01:16:38,229 --> 01:16:40,550

 

2364
01:16:40,550 --> 01:16:42,470

 

2365
01:16:42,470 --> 01:16:44,790

 

2366
01:16:44,790 --> 01:16:49,840