Transcript
00:00:00Today we talk about the proof techniques,
00:00:03which actually we are ready use without giving
00:00:06a name will appear very often
00:00:11during our discussion and it is
00:00:13diagonal so we talk about diagonal section.
00:00:26And very the idea of the technique is to
00:00:32try through the existence of an element given set of elements,
00:00:39which common nature existence of an elements,
00:00:42which is different from all elements.
00:00:45We are given. And more formal,
00:00:50but only then some examples the idea which
00:00:54is behind is the following your given a collection of elements.
00:00:59Sexy high ranking in some index and
00:01:05typically for the index it will be the natural number of
00:01:09the year with the new global collections.
00:01:13So we will have something like.
00:01:15XXX2X3 and so on x.
00:01:24There is the idea this will appear in several history is
00:01:28that for the end of the elements.
00:01:33We can that it is elements as internal structure and we can talk
00:01:37about the value to the features.
00:01:43This element has at position KEE where is again number.
00:01:50IT is a function if the element is
00:01:53a function could be the value by the function as
00:01:56an argument KEE so we can talk about this position KEE.
00:02:02And then the technique consiste in
00:02:07building an element which is now with respect to this collection.
00:02:13Construct but not always the will be construction.
00:02:18And which is the same,
00:02:21but which is different from the axis.
00:02:30È un how do we do as we try to
00:02:36make sure that different from at position.
00:02:54La UE See a number of examples and the main example,
00:03:02which is also at the origin of this is
00:03:05the counter and it is about the Cardinals of
00:03:10the power of the power of the is the state
00:03:13of subjects of the net and the observation,
00:03:18which has been made by country,
00:03:19which is the power of modern theory is that
00:03:22given and that it is the city of the power.
00:03:26IT is always larger than the cardinal city of the set
00:03:30itself and this has been
00:03:35closing some troubles to counter essential
00:03:39because this is you can take
00:03:42infinite that actually it was clear and the time.
00:03:45Whether you have really taken and infinite set
00:03:48because this is that you can have a infinite process clear,
00:03:52but instead you can consider the total of the elements,
00:03:57which this process was something not
00:04:00completely accepted that country as you can take the set
00:04:04of all natural numbers for
00:04:07this infinite and this was choosing some problems to counter
00:04:12because infinite was a property which was considered only
00:04:17of God so there
00:04:20where some criticism not only from from mathematics from colleges,
00:04:23but also from people from
00:04:25the religious side and so we have a lot of trouble,
00:04:29but likely we don't have this kind of trouble and we can
00:04:33try and to the techniques in the specific instance.
00:04:39Which is that of the natural numbers so we want to that class.
00:04:47Of the state of natural numbers.
00:04:53Has a cardinalità which is strictly smaller than the set.
00:05:00Of subset of the natural numbers by this symbols by two in general.
00:05:10Tutto di ADCs effect.
00:05:13Why not the state of subset of ex?
00:05:22And then we want to that.
00:05:27In this is true for any set,
00:05:30but it in particular for the natural numbers because this is
00:05:33my view more interesting filling.
00:05:39By the way you see that in particular this is nothing new for
00:05:44this time is in particular if you can get it,
00:05:50which is Infinite But larger the city of
00:05:55the sets of natural numbers
00:05:58is infinite as the city of natural numbers,
00:06:01but also something which is very
00:06:04difficult to accept when country forward this theory,
00:06:09but as it is fine to it by the.
00:06:16End is the following where you can go to ways.
00:06:21We are completely equivalent with take the one,
00:06:24which is more by tradition and we assume this is not true.
00:06:29So it is not that numbers smaller cardinalità so we
00:06:34that the converse and so numbers as a cardinale,
00:06:40which is better than the cardinal city
00:06:44of the city of natural numbers and.
00:06:50We have a notion of two two
00:06:55cardinali larger than and this would mean that you have suggestion.
00:07:11Function. From the natural numbers
00:07:20to the sets of numbers.
00:07:24Which we are ready so this kind of
00:07:28corrispondenze means that essential you can
00:07:30enumerate least the state of
00:07:33natural number one after the others so we take
00:07:36this more intuitive view we have as
00:07:39a consequence that we can
00:07:41consider the first set of natural numbers,
00:07:43second set number first and so
00:07:47on and in this least we find all subjects of natural numbers.
00:07:52So this is the complete enumerazioni of two to the end.
00:08:00Up to know this looks completely fine now we look at each set as
00:08:08its characteristic functions so we list on this side
00:08:12instead possible element one to one two and so on.
00:08:18And on the columns we wright the characteristic function so
00:08:25be wright yes in case element zero is in.
00:08:33This is the science or know if it is not imaging
00:08:38what is that you do the same
00:08:42for all the other This could be this could be yes and
00:08:46save for this could be could be no.
00:08:52Yes. Yes. Yes!
00:08:59Oh! Yes. IT is
00:09:09this are not numbers and here we will have a list of yes.
00:09:15We don't know this is just by chance.
00:09:19You character the element is or
00:09:23not for instance image that for all the rest.
00:09:29All air news from the road then this means that it is zero in to.
00:09:42This Ok, so so good now,
00:09:50what you can do is to take the diagonal.
00:10:03Which is still as a set it contains zero it does not
00:10:10contain expand it does not contain and so on this is not a problem,
00:10:18but what you can do it you can change systematic diagonal
00:10:23find the yes you know when you know how put yes.
00:10:31This is again a set subset of natural numbers,
00:10:36but it has a property which is what we can.
00:10:40IT. IT is different from the year.
00:10:45Old sets of natural numbers
00:10:49you have a problem because of natural numbers,
00:10:52which is different from the sets of natural numbers.
00:10:56This is the then we try make it more precise so what I did take.
00:11:06That they are change in systematic can be by the final set di
00:11:13the diagonal set the change diagonal set
00:11:17which contains an element natural number.
00:11:23When never eye is not an element of this is what we did it.
00:11:35This is a subset of natural numbers.
00:11:39Problem now because this is different from
00:11:42all the success subjects of natural numbers,
00:11:45but images that we don't see immediately this problem just see.
00:11:50This is that number so it must be one of this.
00:11:57Must exists some index KEE.
00:12:03Such that is to.
00:12:10Know what you can ask our self.
00:12:16That's belong.
00:12:21To be the question is it can.
00:12:28Can have the answers.
00:12:30IT can be yes or it can be now,
00:12:36but you can easily see that
00:12:38both answers are contraddittori because this is yes.
00:12:45Man che basta this is the property which is KEE belong to xk so.
00:12:58Che is and. Then chiama the defined property,
00:13:05which is KEE does not belong to.
00:13:09What is? This is.
00:13:15This is an introduction.
00:13:24To. Clear also the other possibility is contraddittori because
00:13:31it is not and then in false field The condition.
00:13:41Must belong to which is the so again, we have tradition.
00:13:48So it was was contraddittori,
00:13:52which is that the natural numbers were unable to the problem
00:14:01of this existence of
00:14:03this enumerazione and so
00:14:06it must be that the state of numbers is not the numerabile.
00:14:21As you have some of this kind similar
00:14:28the beginning of the course and but also in analysis of calculus.
00:14:35We have The proof of the real numbers
00:14:37are more than the real numbers
00:14:40and the profits very similar to
00:14:42this we will be using a lot kind of techniques.
00:14:48Ok.
00:14:59Doubt we can
00:15:01continue with other examples this technique by number of examples.
00:15:10Exercise is actually.
00:15:15Also because this is typical one of
00:15:19the typical example exercise that this is
00:15:22not accountable that is accountable this properties so.
00:15:28And so on software and also it
00:15:31is a place to computabilità and non computabili.
00:15:34This is the second another thing what we are ready
00:15:39so is that the class of functions of the natural numbers.
00:15:47Is not accountable is not the new variable.
00:15:59We are ready proof of this,
00:16:01but we can review the proof review of our new understanding of
00:16:07diagonal and we can it actually it was.
00:16:15The first. Time in
00:16:21using but we are ready showing second to go and observer
00:16:26actually you can identifying
00:16:30the set of natural sets of natural numbers the power set
00:16:35with special functions which are the characteristic functions
00:16:40so let's take that set of functions,
00:16:46which can have only two possible values.
00:16:49I main function from end to end,
00:16:53but where the domain is actually just zero or one.
00:17:01Of the function only one and it is total.
00:17:07So in our terminologia.
00:17:10This is the characteristic function of some set.
00:17:14So if you have to this function.
00:17:22Which is that this is a subset of f. Beh,
00:17:33io subset of an as you can see this is one to one with
00:17:43by corrispondenze with the state
00:17:47of subset of natural numbers because where you
00:17:49put zero you can element is not
00:17:52there when you want you can think element is their.
00:17:57So what is the city of this functions.
00:18:08Is the same as the cardinalità
00:18:11of the subset of the natural numbers and.
00:18:20To this would need to action
00:18:24action from two to the power of.
00:18:36So you need to identifying function of
00:18:39this kind subset of you before.
00:18:42This can be you map it function.
00:18:46If you map it to the numbers.
00:18:52Such that the function of it is one,
00:18:57it is the element is in the set.
00:19:01You can easily see that this is.
00:19:06Now. AM da or functions.
00:19:19IT is clear larger than the set special functions, which are two.
00:19:26With this because this is motivati by that is just the subset of.
00:19:42Formulato to claim that it is that which is that
00:19:48we would need an injection and injection function from it.
00:19:54To. You can easily
00:20:03see what is this injection function mapping where.
00:20:19You want to get function from the first to the second.
00:20:24Every element to help.
00:20:31You find the other side so you need to get anything.
00:20:37From different you get different tips.
00:20:48And then we are ready know that the city of
00:20:52the power is larger than the city of
00:20:55time and so by taking
00:20:58this chain of equality equality as you get that.
00:21:06The sort of the class
00:21:11of all function is strictly larger than the quality of two to the.
00:21:22Okay possible using what we need before? And the question.
00:21:43Okay, is not we go to a second proof.
00:21:51Which is a direct group,
00:21:53which is that we are ready did only it change it
00:21:57to make it more similar to what we
00:22:00need what we do in the second about.
00:22:04The second directly that as which is larger.
00:22:13Than and this is larger than an.
00:22:26Ehm. I due diagonali.
00:22:35We just take a slide different perspective
00:22:38with respect to before before we said
00:22:41assume this is not KEE so we have
00:22:44an enumerazione of all possible in this case functions.
00:22:49One two three and
00:22:54so on and then we are you that is the existence of this.
00:23:00Is in the tradition.
00:23:03We take different route,
00:23:07which is we consider an enumerazione of functions,
00:23:11which is possible not the number of
00:23:14functions just one enumerazioni where you and you
00:23:18can find functions We consider any possible end of functions.
00:23:38And we shall that it is not fool
00:23:41that there is one missing function at least.
00:23:45So finally that the functions is not the new black.
00:23:51Is the same as before only the
00:23:56only different one possible enumerazione of functions.
00:24:02We constructor function, which is not here we do
00:24:07exactly as before so what the time,
00:24:11we write the possible arguments of the functions.
00:24:15And it functions can be identifier List of its values zero zero.
00:24:24Zero zero and similar one
00:24:31can be identifying white list of its values.
00:24:36E so.
00:24:46You can
00:24:47take the diagonal.
00:25:01Diagonal. And you can view as a function.
00:25:09Which is this value of zero.
00:25:12This way of this way of two and so You
00:25:17change it sistematica you change
00:25:20that value systematic is that you constructor function,
00:25:23which is different from all the functions, which are.
00:25:27You can't have fun. So we define function.
00:25:44Function from end to end as follows.
00:25:52When you find some value.
00:26:01If you find some value.
00:26:06Function defined then you
00:26:09want to get the different value and if the function is.
00:26:14Undefined. Thank you give
00:26:18fixed values this is that you take off ex.
00:26:30And in order to decide what is the voice over ex you
00:26:36check fx over ex if this is to find when you.
00:26:46And if instead it is
00:26:51undefined and to make it different to give a specific value,
00:26:55which could be any, but it was zero.
00:27:00Okay. And you see probably already
00:27:07where we are going because this function is by construction
00:27:11different from Functions and.
00:27:16Path imaging that we don't know that.
00:27:20We want to you.
00:27:27Want to show that f.
00:27:35D is different from FX for.
00:27:42IT is not in the nation.
00:27:48And the point is that.
00:27:54We can put in this way, this total.
00:28:06And. If if.
00:28:15Then di is different from fx.
00:28:20Questo fix together says that is different from.
00:28:26That.
00:28:31Because.
00:28:40This is
00:28:42that it is defined over.
00:28:44X x x. X x x x plus.
00:28:57Which is different from fx.
00:29:10Think simple, but not.
00:29:14Totally trivial so.
00:29:21We will be using the kind of argument several several times.
00:29:27Defined total because this is defined everywhere.
00:29:30These defined in this case.
00:29:34And we want to it is different from
00:29:37all fx and so if it is not total to
00:29:43because of this is it is different if instead fx
00:29:47total when it is different because it is effects of.
00:29:53KEE. And so.
00:29:59On and we construct function,
00:30:02which is not that it means that there is
00:30:05no animation of the entire set f.
00:30:24Enzo è is not accountable.
00:30:31Which is what we wanted?
00:30:36Good.
00:30:44Introduce This is
00:30:48this point because now we can
00:30:50use it to you that there is the function,
00:30:52which is total and not
00:30:54compatible actually this is something that we already know
00:30:59because we are already know that the total functions are
00:31:03more than the natural numbers and so
00:31:06their more than the algorithm and so they are total functions,
00:31:09which cannot be compatible.
00:31:11This is that we know the last,
00:31:14but not we can exhibit,
00:31:17we can write it and say this is
00:31:19total it is completely defined functions,
00:31:23but it is not computer.
00:31:38So the statement is there is a total computer functions.
00:31:55This is not now, this is something reading
00:31:58now actually what is now is that we can do it now.
00:32:04And it is defined in the way,
00:32:06which is very much remains finding what we need before.
00:32:14How do we construct dysfunction essential we
00:32:17consider the list of all you computabile functions.
00:32:28This is what we considered
00:32:31last lessons if you fix encoding program,
00:32:36you have the end of progress and you have and functions.
00:32:43And then we need by diagonal and constructor function,
00:32:48which is different from
00:32:49the computer functions and so it must be not
00:32:53compatible and we do exactly as we need
00:32:57before so here we put fai zero zero.
00:33:03Zero zero. And so on.
00:33:19The Diagonal.
00:33:30Changed systematic.
00:33:37So you get whether.
00:33:42Ex of ex his
00:33:45defined according to the notation between the last time
00:33:51means checking whether x belong or not
00:33:55to the domain of X not by double x.
00:34:01This is just. In case we want.
00:34:15And if instead.
00:34:19Ex of ex his undefined which means that is not and.
00:34:29That we put some specific value to make it.
00:34:35What we want ex with the same.
00:34:46Argument is the same as before effect total.
00:34:58And he for any x. X total.
00:35:16Ex different from f. F is different from
00:35:24total computer functions and its total so it is not
00:35:28compatible argument is exactly the same as before so this because.
00:35:39Of this is different from effects. In the way.
00:35:47IT. Is defined da.
00:35:55Soli? No. I need to make this dysfunction.
00:36:04Infant since total.
00:36:21Total functions defined where. And their for.
00:36:28Life of. His physics of X plus one which is different from physics.
00:36:49Total and different from
00:36:52total compatible functions so it is not compatible.
00:37:12Out. Of this is
00:37:19not really satisfaction because you construct something,
00:37:23which is not compatible just by making different from
00:37:28all the computer things so you are left
00:37:32with the impression that you still to know why
00:37:35this is not computer and in particular
00:37:40think that there are two reasons when
00:37:44reason is that in order to say takes
00:37:49interpreti this program considered
00:37:52corrisponde in computer functions and apply to
00:37:56simulate the program over
00:37:59the input ex that this is a problem cannot be cannot be.
00:38:07As people living in the first century.
00:38:10We know that taking something
00:38:13which is the code of program and asking
00:38:16a machine to simulate the program
00:38:19is that can be on the other point,
00:38:23which could be critical might be the one,
00:38:25which is better the machine over
00:38:29minutes and we know that really the problem,
00:38:33but we need some to make it precise.
00:38:42Okay, is the question.
00:38:49Is not to make it is
00:39:06Building a function which is maybe total or
00:39:10not but not computabile with constraints in this case.
00:39:14We want to be total.
00:39:18We see the following.
00:39:23Let.
00:39:33MP. Be given function.
00:39:51And then you want to you.
00:39:56That there is a non computabile function.
00:40:09Which size with up to value computer.
00:40:21You have the constraint that.
00:40:27G. F for all smaller and.
00:40:46That this is not great problem.
00:40:50having this constraint because you can do essential the same,
00:40:55but before you list of the computer functions.
00:41:03And now have additional problem,
00:41:06which is for values smaller than so to.
00:41:19You cannot decide nothing about your function it must be.
00:41:26What you are completely free to from?
00:41:35You have more than of space to make
00:41:39your function not computer by making it different from Fai zero.
00:41:48Over. So you make
00:41:55your starting from from one.
00:42:00Over one from two over en place to and so.
00:42:11So you define your function we can it again.
00:42:16IT is this time. As follows.
00:42:23If ex is more than you have not choice.
00:42:32For this values you are constraints to be the same as.
00:42:45You can choose and so if.
00:42:52You look at.
00:42:57Fai.
00:43:04Fare. Fai. Minus is
00:43:08doing over. And if.
00:43:24You make your function.
00:43:28The same value plus so that it is different.
00:43:40Instead it is undefined.
00:44:05Eh? Again you know your function to be
00:44:12the same sex and different from all total computer functions.
00:44:22To this is not computer.
00:44:25IT is the properties that we want.
00:44:33By the construction of the same.
00:44:40Or. Ex. Ante. O ex.
00:44:57G Ex Why?
00:45:05Since. Your shift that so of ex plus.
00:45:16Is different from ex of ex.
00:45:23Can you need is.
00:45:33What you want to see the.
00:45:36For the details you just take?
00:45:41Infect. E fai x
00:45:52x x. X x
00:45:59x x x plus plus one. To it is different.
00:46:16And if instead fai x plus is undefined.
00:46:25Then. If zero which
00:46:33is different from x x plus.
00:46:41In this case, we didn't show that the function is
00:46:46total and different from
00:46:49all total computer functions because this principle is not total.
00:46:53Total total.
00:47:06Okay.
00:47:18And informal argument
00:47:21is that con training your function on
00:47:26a amount of values doesn't change the point you
00:47:31you have also always infinity many other points where to make
00:47:36your function different from
00:47:37al computer functions so this is something.
00:47:43Which is typically he advertiser vulgaris
00:47:50as the Hilbert hotel
00:47:53if somebody told about to you about the Hilbert hotel.
00:48:02Hilbert hotel is an hotel,
00:48:04which is luxury hotel.
00:48:12Purchase infinity many rooms accountable.
00:48:17Many rooms. Room zero room one.
00:48:25Two. Room free so.
00:48:35Imagine that it is fully boot. So every room.
00:48:45In every room there is a guest.
00:48:49Said some very important guest
00:48:53appear and you can't say news. Donald Trump.
00:49:07Be nice to say, but difficult and so.
00:49:15And so you have to find a way to accomodate.
00:49:19Donald Trump, which is the additional guests so you have then
00:49:23additional guests what you have to insert your you
00:49:28do what you need to it is a bit convenient for the space
00:49:33are But you need to let it guest to move nine rooms forward,
00:49:40then rooms forward to the guest in room.
00:49:46Zero to room.
00:50:06Guest room one more to room eleven.
00:50:14And then you have a way of accommodation.
00:50:22Ventennio guest. In Room zero.
00:50:39Maybe it would be much better to say no tales for.
00:50:52And the point is that you can you can do this for the people,
00:50:57but you can do also this the same for.
00:51:02People count many people imagine that you have
00:51:07some super guests and we
00:51:11the people at like to find a place
00:51:15and what you do to you take your other which is again fully but.
00:51:48And you want to free infinite many rooms what can you do?
00:51:55Know how to get are we are accountable many are all the rooms,
00:52:00you can move all of them and.
00:52:05Even rooms. So what you can is what the best one.
00:52:14Of the room to get the move to room for.
00:52:26You can put the new guys in the room,
00:52:29which are not free.
00:52:34So when you dealing with.
00:52:38Yes, we are infinite
00:52:42typically you can can be to have consequences,
00:52:50which are not very intuitive.
00:52:51You have to find little better than you get it is that.
00:52:57IT is not difficult.
00:53:02And we see the second example,
00:53:05where you need to accomodate Infinite jest,
00:53:08but for the time being we have only one.
00:53:12And we need we the problem by moving the other guests forward.
00:53:23But not like to observer That it was not necessary.
00:53:31In our case we alternative.
00:53:37Which was the following defined function g. As follows ok for.
00:53:50IT is for which is more than we are not choice.
00:53:56IT must be f. F instead ex.
00:54:05End of ex we make it different by.
00:54:16And that is what?
00:54:21Is undefined we make it different by the function to be.
00:54:29And this is correct might be that it
00:54:36is not because if you take
00:54:39the list of all functions al computer functions.
00:54:57What we do here is to make different from the functions,
00:55:06which are of index or larger.
00:55:12Than or we make our function different
00:55:16so what we are sure of is that is different from.
00:55:22Plos one pay to.
00:55:35Be that is computer and it is one of the functions.
00:55:40Fai zero, fai one to one,
00:55:44but this cannot be the case
00:55:46so we can really so that is not compatible.
00:55:57I don't know if you can see you.
00:56:08Get back to the outlet for
00:56:12the same guests booking Infinity rooms so
00:56:16the same function same computer function is computer by infiniti
00:56:20many programs so it appears in Italy of in this list.
00:56:31And so yes it is through that missing
00:56:35this functions all functions will appear also here.
00:56:39This is not in my name.
00:56:43Is now write it more precise The point is that for
00:56:47all computer functions and this is very
00:56:49important there infinite many programs.
00:57:03So in particular why great?
00:57:10Exist.
00:57:20That. IT is
00:57:27to ex can can you see is.
00:57:35The reason for this is that.
00:57:38This. Is this there are infinite.
00:57:54Many of currencies.
00:58:02Currencies. Of its computer functions.
00:58:21And so even if a function is
00:58:24appearing here it will be appearing also here and
00:58:27later and later su computer function you
00:58:32take it will appear after em. And so.
00:58:50Which to be different from.
00:58:55For Enzo G. Is different from.
00:59:03Ex. From, etc.
00:59:12If you skip the intermediate step for
00:59:16computer Function G is different from each so is not compatible.
01:00:06If you write your function g in this way,
01:00:10you have to explain you can just say Ok.
01:00:15IT is not computer, it is clear explain we have to explain,
01:00:19we have to make the argument so this is it simple definition,
01:00:24but with more sofisticate argument about compatibility.
01:00:41We make one last exercise about this kind of diagonal stuff.
01:00:53And you want to show a function,
01:00:56which is total not compatible
01:00:58e. But this is which is constraint on.
01:01:12Show that there is.
01:01:17IT again
01:01:19G. Total.
01:01:31Not computer. And so.
01:01:42On the number it is zero.
01:01:52Il. Fatto che it is not so difficult to
01:02:02construct dysfunction with just need to use
01:02:06the Hilbert hotel in the wind
01:02:08Infinite jest which now are the event numbers.
01:02:21Is the possible.
01:02:24To make it restricted to the tree of life sex.
01:02:36And so on the even number
01:02:42you are not choice your function must be zero.
01:02:50Your completely free infinite many inputs which are
01:02:54the numbers and so what you can do is to make
01:02:58your function different from zero over one different from one.
01:03:07Over three different from two.
01:03:11Over and so.
01:03:16On. This is the idea.
01:03:25And exercise most exercise
01:03:30is the structure you need to thinking normally for.
01:03:36When you have in mind this picture
01:03:40exercise all the rest is just a little bit informalità,
01:03:45but you have to do also the formalizzazione,
01:03:47but first you need some intuition intuition is typically.
01:03:52Simple. There is nothing really super deep out,
01:03:57but to have to have the interaction is not what is just writing and
01:04:02just write symbols because if you
01:04:05don't start from intuition could be very difficult.
01:04:09Your function it like this.
01:04:14Is over all the event numbers.
01:04:23No choice their. Then on the old number.
01:04:31IT is that you take.
01:04:37The function fai ex minus divided by two and you check,
01:04:44which is the value over if it is defined.
01:04:56If instead is not.
01:05:00And function is undefined you make it different by Given some.
01:05:17This is that we need
01:05:21everything to make dysfunction not compatible and the constraints,
01:05:24but finally you to a double check the function G is total.
01:05:33Yes, it is always defined
01:05:36zero zero here and here IT is this function.
01:05:40This is defined.
01:05:46And it. Is zero for each.
01:05:55And this is by construction again nothing.
01:06:01And finally G is not compatible.
01:06:17G. Has been construct to be from.
01:06:27From used ex.
01:06:32How. Because if you take over the.
01:06:46Old number to which is to.
01:06:52This is different from ex over to one.
01:07:01And the argument. Effect is
01:07:08defined and otherwise it is undefined IT is.
01:07:13The consideration to be here the first one is that.
01:07:20The function is zero not only on the even numbers,
01:07:25but also on the numbers where the function is undefined.
01:07:32But this is fine. We didn't ask to be only on
01:07:39the even numbers so you should never over
01:07:43interprete the specification if we go to be where doesn't mean,
01:07:48but otherwise it is different from zero.
01:07:51So this is fine and the other consideration is
01:07:56that in this case the plain definition.
01:08:10If you just defined g x x zero x x
01:08:18x. X
01:08:23x. X x. X x.
01:08:36Zero. X x. X x.
01:08:48That it is very hard to you that this
01:08:55is working file I can't really say whether
01:08:58this is a good Definition and it is clear not compatible,
01:09:02but for sure there is not not a simple argument.
01:09:16Because this case you are infinite many functions
01:09:21and so you think computer function has only.
01:09:27Even index of only progress,
01:09:31which compute function whose encoding is number of.
01:09:52This is not compatible.
01:10:05Clear this is not.
01:10:09Working by the one is in the final case,
01:10:13when you have you will not only the amount
01:10:20of programs and so any computer function
01:10:24as infinite many program will find the same functions beyond,
01:10:27but the year of
01:10:28the event index in principal programs for the same functions.
01:10:39And you to do last exercise,
01:10:44but by yourself. Which is by.
01:10:50In this case I give you accountable list of functions
01:10:55not necessario Computer zero one two and so on.
01:11:03Function from end to end so you have a fine.
01:11:13And you to define function again from.
01:11:21Such that the domain of is different from the domain is for.
01:11:36How by diagonal?
01:12:03This is for less is
01:12:07more than that like to introduce what we will be doing tomorrow.
01:12:14Which is the second parametrizzato or.
01:12:22Which is one of the two pillars together with
01:12:26the universal functions of compatibility theory.
01:12:44And it is something which is kind of.
01:12:50Expected for as well with computers.
01:12:58And essential in the very essence,
01:13:01it's given a program with several arguments
01:13:05and coding some of the argument is effective operation.
01:13:09You can do it with an algorithm so not really very an expected.
01:13:16But we want to it.
01:13:21IT has follows you start from the given program and for use
01:13:29a given program is that it will be
01:13:34just a number because this number is code,
01:13:38which is the last of us,
01:13:41which we can see as program so let it B for now say program code,
01:13:50but it To say could take number
01:13:54and it is a program B e program code.
01:14:04And consider the function computer by the program.
01:14:14The function of two arguments.
01:14:21By the program you remember is that we take over encoding by
01:14:32and we have to take the inverse image
01:14:35this function we decided to give a name
01:14:38within the function by KEE to this is the function,
01:14:44which takes two natural numbers gives you as a output If it is.
01:14:56To this will be applied.
01:15:00To the arguments that we call to action why?
01:15:06And we want to do some manipulation.
01:15:09We give a different name to this function we can it.
01:15:18IT is the saint just different time for the same function.
01:15:24To you fix the first argument to some value.
01:15:37So that the function becomes the function only of.
01:15:42This function by fx.
01:15:47No effect of what is
01:15:53just a different name for effect of which is fi too.
01:16:01For the time being is this just manipulation of
01:16:05symbols at the first observations
01:16:08that for any which is fixed. This is computer.
01:16:16Can you see why this is computer?
01:16:28Intuitive as. IT is.
01:16:36For you can think of this as a function,
01:16:42which is this which is compatible By using it with
01:16:47the constant ex ex constant program,
01:16:53which constant ex is.
01:16:58Zero x times to the constant ex computer with dysfunction you get.
01:17:09IT is computer yes,
01:17:13maybe as we do some times,
01:17:17it is good to our hands on a specific example.
01:17:20Imaging that the function is way to the x.
01:17:26What we called if zero?
01:17:31For the way to the zero the constant one.
01:17:37Of one would be one to one the identity. Two would be.
01:17:48Way to the two taking square of the input and so all functions are
01:17:54compatible not by chance
01:17:57because the composition of compatible functions.
01:18:02And since the functions for your compatible.
01:18:20Program, which is computer dysfunction.
01:18:24FX is the function of one argument computer by program.
01:18:30D.
01:18:41And what does
01:18:42this did it on the original function,
01:18:45which is in the pending on the program.
01:19:02And then on the input, which is fixed.
01:19:09So given the regional program and there is such a program di.
01:19:18We have given to things to the numbers to numbers.
01:19:23You get the number for all choices of
01:19:25the first number you get the number what you get is a function,
01:19:29which is the two numbers into the number saying is that.
01:19:37There is a function,
01:19:40which is by
01:19:40the way
01:19:49IT is.
01:19:52Which given index.
01:19:56Give you the value above.
01:20:03The index.
01:20:12So this function is this is.
01:20:22What is that this function
01:20:26is not only a total, but also compatible.
01:20:33And today we don't see the proof,
01:20:37but it like to
01:20:38this last minute to you that this is completely expected.
01:20:46Because we start from the program.
01:20:50I programmi is a program of
01:20:52two arguments so write it in Python it is
01:20:56the pics and then it is now and then it is a value.
01:21:10This is our original program.
01:21:16And we want to fix to
01:21:20some specific value and get the program for the function,
01:21:23which is computer by fixing this value.
01:21:27But. If you have to some value to two.
01:21:39Transforming this program in the program which compute the same,
01:21:44but with fixed value this is.
01:21:51What if you have a functional language
01:21:55with partial evaluation or with
01:21:57the carrying than there
01:21:59is nothing to do you just partial apply your function,
01:22:01but even in imperative language to you take your program,
01:22:07you make it the program of one argument
01:22:11and when you find ex you replace it by the way to.
01:22:17This is something really what you can expect to be
01:22:21double effective with an other program.
01:22:25So what this is what the function as is
01:22:28doing that the program I take x and the program
01:22:34which where is fixed The output is a program of the function as
01:22:40is a program transformer only this is quite clear intuitive,
01:22:47but we want to make it formal.
01:22:51In our setting we are dealing with our primitive model,
01:22:54which is the machine,
01:22:55but also it that setting the proof want be
01:22:59difficult the full proof is long and boring.
01:23:04We want to see the full proof,
01:23:05but also saying so we don't see it idea so we will it for today.
01:23:15I just try to suggest undergoing extremely simple
01:23:20because what you are given at the beginning is the program.
01:23:26I. So you have the code,
01:23:32but actually what you think of
01:23:34is The program is the program of two arguments.
01:23:41That starting from exit register
01:23:45one way in register two and the rest is.
01:23:50The some computational.
01:23:54And diverge,
01:23:57but it is it converge it is an output the value of.
01:24:04Function over.
01:24:08This is what you find the register when.
01:24:13IT is one that it is.
01:24:23What you want?
01:24:34Is that
01:24:35given some fixed as fixed as.
01:24:45You want. To the.
01:24:59Program. Could be più di sx
01:25:06so actually what is computing is
01:25:09the functions and this program starting from a single argument,
01:25:13which is now why because this is fixed.
01:25:19In register one. IT is
01:25:23the computer and finally product the same value as before.
01:25:29Here you want to buy?
01:25:36And how can you do that?
01:25:53You don't understand how you want you get the general,
01:25:59which is also the good good side is
01:26:02that even If you are not very good after you get that.
01:26:08You can you do that. You from here.
01:26:17You just move with the register hardcore sex in the register one.
01:26:34So you from the place we? Can register what?
01:26:46You move it register to.
01:26:56Which is able to the program.
01:27:01Which is not so you are you write in one.
01:27:21Way of us and finally you execute programmi.
01:27:37Qui ci sgama tutte. Minus one of.
01:27:44This is a program,
01:27:46which is the essential on index.
01:27:56And this is what you want to computer your function s
01:28:01s X is nothing more than game of this red star.
01:28:12So you want to start from X and to
01:28:17this manipulation transform the program to get this that is back.
01:28:24A suppose that it is
01:28:27that it is essential trivial that this is computer.
01:28:34And this is the argument of the book.
01:28:38IT is trivial that this is computabile that we don't need a proof,
01:28:42but this is because.
01:28:46This is clear computer should be that you
01:28:50can do the same for every what we do in discourse and so.
01:28:56Loose beat the formal content
01:29:00and so altri to give you some it's not
01:29:03the full proof of
01:29:05our more some it's that if
01:29:08you really want you can form up to the last,
01:29:11but this is completely we don't do
01:29:16all the proof just a little bit a bit just to convinse
01:29:20that it could be done in principle and we will do this tomorrow.