Trascrizione
00:00:01Today we discuss more details parametrizzato what we
00:00:08starting starting yesterday just to give you beat of.
00:00:17The following you start from
00:00:20a given program and for us programs are
00:00:23numbers could but ok we write I which is the number,
00:00:30but the internet refer to the program,
00:00:33which is gamma gamma is
00:00:35the encoding of programs in numbers gamma to the minus one
00:00:38of you and we consider the computer functions.
00:00:44We need to fix a number of arguments.
00:00:46This is not embedded program so for this specific introduction,
00:00:52we fix e function of
00:00:54two arguments and is that we want to Consider the function
00:01:00that you from dysfunction by hard coding
00:01:05one of the argument the first so in any way,
00:01:09you fix the first argument you have still the second argument,
00:01:12which is free so you get the function of one argument why?
00:01:17So for the function map
00:01:22into the value of the general function apply to.
00:01:28One you get the function,
00:01:30which is an argument,
00:01:32which is potential in typically different maps into
00:01:37the image of the function of
00:01:39the original function with the first argument fixed to
00:01:42one and so so you get
00:01:45the sequence of functions with the ex we are you
00:01:49and that it is that all functions
00:01:53are compatible because they are
00:01:54just the composition function with the constant.
00:01:57composition stability original functions
00:02:01compatible the constant compatible.
00:02:04This means that each dysfunction his computer by
00:02:08a program and the theorem essential says that given
00:02:13the original program and fixed argument
00:02:18you can algoritmica computer the program.
00:02:24The code of the program,
00:02:26which computer the function where
00:02:28the argument is fixed so the function,
00:02:31which maps way to pay off and I think that it right to convince
00:02:39you yesterday that the conceptual content
00:02:44is very much expected so this is not surprise,
00:02:48because what we are saying is that you a program
00:02:52arguments and I want to show that given this program,
00:02:57it is possible to the one of the argument,
00:03:01which is what you could do in any of
00:03:04your favorite languages essential.
00:03:06If you think of an imperative language and you want to
00:03:09fix ex people to some of the show must go
00:03:12through the code and whatever it is this is not
00:03:17exactly true because this could be
00:03:19used to the variable, but mirrorless.
00:03:22This is the point you can easily imaging how to do it,
00:03:25but you want to show it normally in
00:03:29setting with double mathematical process
00:03:35and this is what we are going to do today actually the form
00:03:40to be extremely long and full
00:03:44of details so actually what going to do it just to start the proof
00:03:48trying to get that it could be back to the end and we will stop.
00:03:54But the theorem is not specific for two arguments.
00:03:59There is nothing special about two arguments to
00:04:01the general theory is as follows.
00:04:08You again a program which is
00:04:12fixed considered function computer by program I.
00:04:18But with the number of arguments,
00:04:21which you write as m plus
00:04:24where are the argument what you want to fix and and play
00:04:29the role of the way are you want to be free so this is
00:04:35the function which goes from plus and arguments to a single value.
00:04:42What we want to show is that. The function.
00:04:51Applied to the full size of arguments can
00:04:57be seen as the function computers over only and arguments.
00:05:06By fixing and the program,
00:05:09which is computing dysfunction is algoritmica from I.
00:05:16And from ex. So what you have here.
00:05:21This is is actually the program,
00:05:25which is by from I by fixing
00:05:29the arguments and so the content of the theorem will
00:05:34be that this function is a total compatible function.
00:05:39Now. This is just general.
00:05:47And the reason why the theorem is Man is not really
00:05:52deep only in the original formula on the function,
00:05:56which transform the program by fixing
00:05:58the argument as and the arguments,
00:06:02which are fixed are m and those
00:06:04who are and so this is this is the reason why?
00:06:11Not but it should be expected.
00:06:19So this is the parametrizzazione or.
00:06:26As follows given.
00:06:31Two sets of the numbers,
00:06:34which express the arts and then.
00:06:39There is a total compatible function.
00:06:54Per cui di notte by. Which takes en
00:07:02plus and arguments the program is the one and that is the input,
00:07:11which fixed and gives back and other program.
00:07:16So this is the program transformer how that. For all.
00:07:26Program. And possible inputs that we split into which is that.
00:07:37Which is that.
00:07:42The function computer by over and plus and Arguments applied to XP.
00:07:52Is the function computer by program SMN.
00:08:04X with an arguments which are.
00:08:12Ok. Maybe seen directly it could be a bit cryptic,
00:08:19but I know it is what is as.
00:08:35Is the following we start with an intuitive view of
00:08:41the proof and then we go to
00:08:44the part And intuition is that it again quite easy.
00:08:52Because you from the given program.
00:08:55I.
00:09:01AM sa input
00:09:07ex which is an Apple.
00:09:10And from the code you can recover the program.
00:09:18Poi.
00:09:23Vai ad encoding program is in the following.
00:09:36IT is the program computing function Fai I
00:09:39with and arguments so if you start.
00:09:45from a memory where in the first.
00:09:53Register you have x and in the successive and register.
00:10:07You want you execute?
00:10:13And at the end if there is an and the program also.
00:10:22You will find in register on the value of function.
00:10:37This is what you have the program e and what you want is.
00:10:42Contract Program.
00:10:47Different function.
00:10:50SMM. Must construct Program.
00:11:03I. Primi with the pants.
00:11:15On I ex.
00:11:22This is because function just.
00:11:26Our intuition as that we want construction
00:11:29effective that starting just from way.
00:11:36From the input while.
00:11:45Il register one two.
00:11:49To execute prime are you want to reach.
00:11:58Of the function, which is the same as before.
00:12:10You. And I think
00:12:19that it is quite clear what is to do.
00:12:30Program. Will need to.
00:12:38Move forward right here and execute program.
00:12:55To.
00:13:03Write ex in
00:13:08one time and finally execute.
00:13:20This sede you are translation of art Coding value.
00:13:27Ex. And this is this program prime we can write it.
00:13:37Moving forward is transfer.
00:13:45Register and to.
00:13:50We start from the last of things.
00:13:55And then transfer register one to one.
00:14:00So here we are moving.
00:14:05One to one.
00:14:13Then we have to write ex.
00:14:18Register one register for this we
00:14:24need to be programming for writing one to one.
00:14:36Zero register one and then incremento one times.
00:14:52And to the same for the other so.
00:14:58Writing access to register.
00:15:23And now da setup is ready and we just need to execute.
00:15:32So we CONCATENATE All this
00:15:35with the program that we can construct by
00:15:38starting from. This is program.
00:16:04Program.
00:16:08And. The function
00:16:16s. Of X is the code of this program.
00:16:35Now the book say says well common.
00:16:44Writing this instructions and
00:16:47the code of this instructions can be down.
00:16:52Free fixing the program with
00:16:55this sequence of instructions is something that is
00:16:58effective intuitive effective given
00:17:02you can recover by the top gamma,
00:17:05which is effective that you need to
00:17:08concatenate all this and apply which is
00:17:11effective and so this is intuitive effective
00:17:14effective and so this is this is computer,
00:17:20which is kind of except
00:17:23able Bat Ye'or left I think with the impression that seeing on.
00:17:30This must be able to see you can say for
00:17:35everything so at like to you that you
00:17:39can completely avoid any reference to
00:17:42the intuitive computational to the intuitive notion of
00:17:45effectiveness and just used
00:17:47formal computer and to the result function is computer.
00:17:53This is just long and boring,
00:17:56but it is not difficult or it is not avoid able to
00:18:01this or to the fact among concatenate things must be effective.
00:18:07You can bring everything to
00:18:09the mathematical levels and that the right to
00:18:11convince you in venti minutes.
00:18:16Because this is it any clear is it their any. Questions or.
00:18:33If not to convince you that you can do
00:18:36this in a completely formal way.
00:18:47And essential Le prime
00:18:52the first time to have to do as
00:18:54a basic cooperation is CONCATENATE in things.
00:18:58CONCATENATE. Think. Different parts with the program and
00:19:07so what we to address is how to show that the program is able.
00:19:21To the first to observer.
00:19:25IT will be the only thing is that
00:19:28sequential composition of progress is computer.
00:19:48By this I mean that the function that given one and the
00:19:56two as code of progress and map this to the code of.
00:20:06Program. P one followed by program to this is computer,
00:20:16but I want to do this without reference to the.
00:20:22Function which is just Informali
00:20:26effective I want to do this is it completely formal levels.
00:20:31So this will go through several steps.
00:20:38The first observation is that in order to concatenate to
00:20:42you need to update the jump instructions
00:20:45on the second program to take care of the facts
00:20:48that is absolute and so you need to
00:20:51increase the destination of the jump of the second
00:20:54by the land of the first so we need an update operation.
00:21:03Which takes to arguments.
00:21:11È program could and the displacement and
00:21:17products the program code of the program.
00:21:30From so from the program is by update jump instructions.
00:21:41Each.
00:21:54And jump instruction
00:21:56of this kind we want to transform it.
00:22:02In this way.
00:22:11Queste poche volte
00:22:14without words without calm and actually in order to get this.
00:22:23With an intermediate function
00:22:26which is updated e single instruction.
00:22:30Because it update child.
00:22:35Which takes as instruction codes and
00:22:40a displacement and gives the encoding of instructions.
00:22:46Which is obtaining. From instruction.
00:22:58By the target if it is a jump.
00:23:20Okay. And not to this function we have to remember.
00:23:32How instructions are encoding and
00:23:37in particular the jump instruction is
00:23:40encode as a multiple of four plus three.
00:23:48To take. The encoding of the triple of the arguments.
00:23:59Times for this is what we did so in order to understand whether.
00:24:08His jump instructions just need to get the reminder of the science
00:24:15of it is three or not Ottimo weekend Translate this is this check.
00:24:23So what? If the reminder of divided for.
00:24:33Is not the end of dating I will remain and tagged.
00:24:43Because it is not a jump instructions it
00:24:46instead the reminder three is a jump instructions.
00:24:52So we need to computer.
00:25:02And. Now we can.
00:25:07Update to take the original.
00:25:14Arguments of the.
00:25:16Out of.
00:25:21The first to remains and changed while the first to be increase it.
00:25:29IT is a triple.
00:25:35Multiply by for.
00:25:53This is just the point,
00:25:55if you understand this.
00:25:59We want too much more than this
00:26:01understand is the end of the rest is totally clear.
00:26:04I think you can really get rid of this This is it by just using
00:26:13the encoding coin Into the encoding argument
00:26:17that what you are using just functions like
00:26:22reminder conscience encoding of
00:26:26tribes projection product some of functions should be
00:26:31able to this that you can avoid
00:26:35it we know how to encode e conditional as a single functions.
00:26:42Because this is just need to write times quantity,
00:26:48which is one when the conditions through and other wise.
00:26:52This is the science of this condition.
00:27:05Is the times. Of the conditions.
00:27:29No dysfunction is a completely form function
00:27:36using only products reminder of
00:27:40the action some encoding types
00:27:44projection everything computer so
00:27:49you see that this function is computer.
00:27:51IT is not intuitive effective yes.
00:27:55Some where is one of it is the second thanks.
00:28:07To this is not just intuitive effective
00:28:12And actually you can see you are never using minimal action.
00:28:17This will be the KEE until the end we're more than this primitive.
00:28:25Given this you can get back to the update function.
00:28:33And use this update to
00:28:37the update function because now
00:28:40the update function you remember you want to.
00:28:45Update not only a single instruction,
00:28:48but a full program so you need
00:28:52to do the following you need to remember how we encode?
00:29:00Sequence is. The encoding of the sequence one way and.
00:29:10Vedi The Strange Things taking the product of the prime number one
00:29:16to one frame number to the eye.
00:29:24And then the last special by in order to get back to the land.
00:29:31So the last is an one everything.
00:29:38IT is the encoding is not really important.
00:29:41What is this is what we choose
00:29:44and given encoding of time in this way,
00:29:49you can get back to the land.
00:29:53This will in this way.
00:29:57To this is the land of the included sequence.
00:30:10Expression what we don't recall?
00:30:13We don't want you can get back to the components so this is the.
00:30:24Component.
00:30:35Which must be
00:30:37included between one and the land of.
00:30:41This specific encoding is not
00:30:44important just need to know that there
00:30:46are this functions and so on this functions.
00:30:50You can update. On the program because this is
00:30:56a list of the encoding of the least of codes of instructions,
00:31:02you get back to the codes of the single instructions.
00:31:09Code of the first destruction code,
00:31:14the second destruction, code of the last instruction.
00:31:21And what you do with. You have to update it
00:31:26single instructions with the function update
00:31:29till the best we defined bob.
00:31:47And how you have to this sequence.
00:31:56Of this is not completely formal because.
00:32:03This Which is just effective
00:32:07because this domain is sequence number.
00:32:10IT is not the domain where we have.
00:32:14You can avoid any reference to by using the definition of
00:32:19this becomes using this is this becomes.
00:32:28Product from which goes from one to.
00:32:39One off to the corrisponde in component,
00:32:46which is update field
00:32:49e. Everything is the last component,
00:32:57which is lost.
00:33:01Component. Art of the component.
00:33:10Plus one everything is.
00:33:16What this expression is not really important to
00:33:19just need to know is that we used
00:33:22encoding with defined before and here every reference to
00:33:27effective function is completely this appeared
00:33:30this function by using numbers update,
00:33:34which is just to be computer.
00:33:36This functions computer product is this product,
00:33:41which is computer and so on which is computer.
00:33:45Everything is computer also this is for computer.
00:33:49This is just small step
00:33:52out of our home because we are just concatenati
00:33:57so update program by age to
00:34:01the destination of the jump instruction small step for.
00:34:11All and remember was a small.
00:34:17Step for human kind that.
00:34:22We know how to do some other steps for instance.
00:34:27CONCATENATE to sequence.
00:34:38One and two sequence as you want to produce the court.
00:34:48Of the concatenazione.
00:35:00Of the sequence,
00:35:03corrispondendo one and the sequence, corrispondendo to.
00:35:09So what I mean is
00:35:13to take all the components of one by using function.
00:35:25At the last component,
00:35:27which is the one and you concatenate with the components
00:35:32of sequence to component up to the last component,
00:35:38which is land of.
00:35:43This is not yet formal because you have this reference to
00:35:48do what you can avoid by
00:35:51expanded the definition here we don't do it.
00:35:58After that this is no longer too anything intuitive,
00:36:03it is just computer and finally you can define what we
00:36:08want that the beginning the sequential composition of the programs.
00:36:15This is not yet sequential composition
00:36:17because you are just concatenate.
00:36:19This is what you are not update
00:36:21the second one in order to have
00:36:24a defined sequential composition of programs.
00:36:28What I mean by this is given.
00:36:32I want to know how interprete as program codes I want
00:36:39what I want to get the beginning you want
00:36:42follow up to update it instructions,
00:36:46which is it back,
00:36:50this is just take program one.
00:36:57The program to update its dump instructions by using the land.
00:37:10Of hope and then the nation of this is.
00:37:20Program composition sequential composition.
00:37:30And you can continue.
00:37:39Because maybe now you for God,
00:37:43We are going to do we want to the time.
00:37:51We want it to construct this program.
00:38:04We started working on composition.
00:38:14Now this program will be.
00:38:17The composition of this part.
00:38:26Per composition of this is what is.
00:38:36The single parts we don't do that because it would be with long,
00:38:42but it suggest could do it.
00:38:45And then the end of the details is this first part.
00:38:52We can col transfert Transfer transfer and it is a function.
00:39:04Of two argument transfer of an is the code of the program,
00:39:14which is the transfer of two.
00:39:19Transfer of one to.
00:39:26This includes a reference to the gamma,
00:39:31but you can avoid it by the definition.
00:39:34We don't do that what if you
00:39:36expand full definition as you will have
00:39:38only computer functions same for
00:39:41the second part setting a register to some specific value.
00:39:51This is again a function of two arguments.
00:39:57Set Register.
00:40:00Register to x it will be the court of the program,
00:40:07which first register and then take of register x times.
00:40:20At means that you have to do it by
00:40:23primitive to this take a little bit more what you can do it.
00:40:29And once everything is set up to just
00:40:32need to take the composition of this parts.
00:40:42Program is the code of the prime.
00:40:47This is what we wanted.
00:40:58Posted. By saying that it is the sequential composition.
00:41:08Of this part. So transfer.
00:41:15Of. Sequential composition with setting register
00:41:24one to one sequential composition
00:41:29with setting register two to.
00:41:41Sequential composition of setting register.
00:41:48To exam with execution.
00:41:54And you need to close a lot of parentesi and this function
00:41:59as which is composition compatible functions
00:42:02and so it is compatible.
00:42:29And actually if you look back to see what we never used
00:42:33minimal so it is most specific.
00:42:37Primitive ricorsive.
00:42:50This is not the last,
00:42:52but not be able to the idea that the fool proof would be
00:42:58as easy as the single we need only it is a bit full of details.
00:43:09Ehm, okay. Theorem sm
00:43:13in itself is not very powerful you can do very much.
00:43:16IT. IT will be instead the powerful tool combined with
00:43:21the universal function for produce reduction to problems,
00:43:26which are known to be able or get.
00:43:30Sold out of other problems,
00:43:34which are reduced but for now.
00:43:35IT is just single what we can use very
00:43:39much and what we will actually most Mostly used is not the.
00:43:48Basic form, but rather simple corollari.
00:43:56Which is similar that very often I will not to mention that it
00:44:01is a corollari will it is and that.
00:44:09If you start from the computer function of m. Plus and arguments.
00:44:37Then there is a total computer function as.
00:44:49Arguments.
00:44:57That For
00:45:02all ex ex.
00:45:07Typekit way.
00:45:16Of ex what is?
00:45:27IT is almost the same as the only the program,
00:45:32which is computing is this appearing but
00:45:35the proof is just an application of the room.
00:45:43Just that it is computer.
00:45:54IT is the function computer by some program.
00:46:05And therefore.
00:46:10By. This is.
00:46:22IT is nothing. You know that.
00:46:27Fai in place of.
00:46:34Is fai sm of X.
00:46:43For all. And this is.
00:47:00This is what we want.
00:47:14By function has to be sm with coded.
00:47:26Pazienza is total incompiuto also as is total in computer.
00:47:41Lo stesso. Similar to the same.
00:47:47Very often semplicemente not corolla of.
00:47:59Also may be something to the observer is that
00:48:03the content is not says.
00:48:07There is the functions,
00:48:09but the functions as is
00:48:11built step by step so if you want to programming,
00:48:15especially if you know any functional language or
00:48:18any language with pattern matching like like
00:48:22encoding the function into
00:48:27the language is immediate just
00:48:29take that we developed with your language.
00:48:34So it is not just there is what we exhibit IT is so with
00:48:41the universal function you will get yours
00:48:45personal implementation of the machine
00:48:48in your language, if you like.
00:48:53Good any question or mark or.
00:49:02Not.
00:49:05So.
00:49:17Much with
00:49:19something can be time is the following proof.
00:49:24That their exists.
00:49:30È tutto il computer function.
00:49:44KEE.
00:49:55Oro Natural numbers and.
00:50:03Input. Function fichi and
00:50:11ex it is not the square root ex.
00:50:19Integer part.
00:50:28And if you look superficiali to this is the result might Surprise.
00:50:35Because of this function we have.
00:50:41The case computer so you have the program machine,
00:50:47which is computer is this is the
00:50:50following it is taking in input value and.
00:50:57And it is produce in output program so this is
00:51:02a program generator KEE and this is the program,
00:51:07which is computing the end of a number.
00:51:19And its look something really clever spend some time in
00:51:25the elementary school to understand how to
00:51:28computer it was difficult quite difficult.
00:51:32I think will learn also to the truth and even more
00:51:38difficult and how we have a program with
00:51:42you and provides as an output program,
00:51:47which is the truth so this looks
00:51:51like a incredible clever incredible clever.
00:51:56Program which is a program generator,
00:52:00but actually this is something,
00:52:03which is very very trivial
00:52:07because you can think of it as following this is the way it.
00:52:16Inside program KEE.
00:52:20You have the program chiamata you have.
00:52:25The general program which is computing
00:52:28the end of hex for any given.
00:52:33And so you have a program inside you have a program to arguments.
00:52:50Using and it is using x and finally it returns.
00:52:56The integer part of the Square Enix again look difficult,
00:53:02but what is difficult to get and efficient for computer square or
00:53:07the art of order for but if you are happy with anything,
00:53:16then it is very easy you just try and iterate multiplier
00:53:22until you break even bound
00:53:25so what is difficult is to be efficient to the.
00:53:29Human beings can you without getting mad so writing.
00:53:35This is easy and KEE as just in
00:53:38interior copy of this program and when never it.
00:53:44IT. IT has an input some e produce
00:53:49output which is a program yes this looks something clever,
00:53:56but actually the only thing doing is providing as an output.
00:54:01The same program which is embedded in to KEE.
00:54:07Only it codes value.
00:54:14Sei Specific value is it
00:54:20specific value in place of it, that's it.
00:54:26IT is really doing something stupid,
00:54:28it's not a clever program.
00:54:32This is it intuition and we have
00:54:36to make it formal and the making it is the.
00:54:42First with this.
00:54:47Is that this is able.
00:54:57To arguments. Which given
00:55:06and produced the integer part of the.
00:55:12End of arts and this is it before is easy to
00:55:19computer because if you are not married
00:55:21about efficiency you just take that maximum.
00:55:27Such that set the end is moller X.
00:55:36This is not something what we can claim to be
00:55:40compatible because we are good finding minimum things,
00:55:46but the maximum is that this is that is the minimum.
00:55:52Set if you go beyond.
00:56:01And we are good because this is
00:56:07the minimum set and here we have to write not boolean condition,
00:56:12but the function, which becomes and
00:56:14the conditions through this can be.
00:56:20Just the attraction of the
00:56:23first minus the second and you take that.
00:56:34We have the difference is positive,
00:56:38which means that the first is better than the second.
00:56:43This is okay for this computer this would be ok,
00:56:50but we can observer,
00:56:52you don't have the power of minimal section because
00:56:55you know how to stop you should never go beyond.
00:57:03The wounded or not this is computer.
00:57:18But this is not what you want we want the function.
00:57:21KEE which takes as an input and and producers.
00:57:27The program which is computing this function fixed.
00:57:31This is the application of
00:57:33the theorem so by the role of the theorem.
00:57:50KEE total black.
00:58:06Out that. Is to as is for the next.
00:58:19For all in.
00:58:28This is by definition the square,
00:58:32not the end of the third party.
00:58:37So this is what we want.
00:58:43And you see you think that is this several times.
00:58:48The point is to have a clear intuition what you are doing which is
00:58:54this and then transform it is to the form,
00:58:59which is this and the night of the two is alternate between the
00:59:05two doing only form is in
00:59:08my view impossible after while if you just bright symbols.
00:59:12You don't understand anything you have to be very
00:59:16much into the Intuition which is behind its impossible.
00:59:25Eh eh.
00:59:28Eh. Eh. Eh. Eh.
00:59:40Eh.
00:59:48Eh.
00:59:50Eh. Eh. No.
00:59:54Eh.
00:59:55Ok. Yes! We don't
01:00:00want it is true that we have
01:00:02also another function, which escape room.
01:00:06Total computer. Which is the argument that you want to use as
01:00:12a parameter so you can say function KEE,
01:00:17which is total computer such that.
01:00:22Is. Key of.
01:00:28This is it is possible the order of ok strictly for.
01:00:40The first. Argument and fix on the first argument,
01:00:47but the order of arguments total material you can change then
01:00:52without any problem only this
01:00:55is not what you want because this is computing.
01:00:59For argument.
01:01:03And where is not the the input so you fix.
01:01:12For and you can computer.
01:01:17Fai KEE prime of four is a function that given input one of
01:01:26the one of it is for if
01:01:31you do you get the square for which is to go.
01:01:38To this is not what you want what you can do it.
01:01:50IT.
01:01:58Is not we
01:02:01can do it different exercise.
01:02:11Which is that there is a total compatible function.
01:02:17When you here total computer often it has to do it.
01:02:43For all and.
01:02:48Fai KEE is the function of an argument,
01:02:53which is to find.
01:02:58Only.
01:03:04On. Powers by
01:03:09this is that it is the only
01:03:13on elements of the way to the end for some.
01:03:19Way in wise this interesting for reason it is just
01:03:25an exercise so I want that the domain of this function,
01:03:31but not the symbol.
01:03:36Of the elements such.
01:03:44As is the power.
01:03:57And the trick. Is always first define function
01:04:04were not only ex also And is an argument.
01:04:13A functional argument.
01:04:29Ready since the beginning we think that later this will be
01:04:34fixed by using the theory
01:04:37of it is playing different roll in our mind,
01:04:40but not in the mind.
01:04:44And we want dysfunction to be defined
01:04:48only one to one way to the so we want
01:04:53the function defined if there is such as is what we.
01:05:03Are we want the function undefined otherwise.
01:05:15And here we do not the side at.
01:05:20The value we could put zero to twenty seven two,
01:05:27but it is more convenient not to say what
01:05:32we are because we can do it on the basis of the one,
01:05:37which is more convenient when we trying to this function.
01:05:41I mean. Can we check whether it is the way to the end for some.
01:05:51We trust search for search is minimal.
01:05:58We search some way that way to the end are the same.
01:06:10This way as usual.
01:06:14We don't search for the condition to become true and
01:06:17so on this into the function which becomes.
01:06:23When the conditions you.
01:06:28Also here you could beyond.
01:06:32The search because you will never go beyond ex but this is
01:06:39not needed to claim that the function this is
01:06:42computer because it is the minimal of the function,
01:06:45which is computer visit compatible because it is the composition of
01:06:49absolute value with the power to the end expansion to be able.
01:06:56To this is compatible.
01:07:04By the fact, but it is compatible.
01:07:08We can used to say that it is compatible and.
01:07:18Given, but not the function is there is defined.
01:07:22We can understand this
01:07:24is what you get by searching for the way that
01:07:29the end is it is the end of as.
01:07:38We put zero their instead you would be forced to
01:07:45the place some of
01:07:47the zero air force to compose with the zero function.
01:07:53IT is as we decide what you to get back to the the most convenient.
01:08:07Good we have a function of the argument.
01:08:11This is not what we want you want.
01:08:14That. The function of KEE of
01:08:20an was the only on and powers,
01:08:25which is this function where and his fixed and so we used theorem.
01:08:33Poi corollari of this.
01:08:52Is KEE total computer.
01:08:59And the only inventive Part.
01:09:03Time for you just used.
01:09:07This kind of automatic.
01:09:15Total computer. For all inputs.
01:09:26Fai che i Queen.
01:09:31Of ex.
01:09:35An ex which is what?
01:09:43If ex one to the end for some.
01:09:51And it is undefined.
01:09:57So are we don't yes,
01:10:00we are bird, but.
01:10:04To remember that we want.
01:10:08This we want our function to be defined only on
01:10:15the end of powers and we did everything to get.
01:10:22The function with features clear it is
01:10:25the case in this pacific case.
01:10:28IT is completely, but in general this kind of exercise as
01:10:34well as follows you have
01:10:37some intuition how to see you do everything to get the property,
01:10:42but finally you have to get the property is this in this case,
01:10:48it would be really needed,
01:10:50but the try to this is the pattern.
01:10:54The pattern is that now observer that
01:10:57the function At the property which for.
01:11:04So. What indeed?
01:11:16Del domain of the function with index KEE with
01:11:20program key is the power of.
01:11:32Why? Because this is in the domain of the function computer
01:11:42by program key if non if
01:11:47fai of KEE of ex defined by definition of domain.
01:11:54But this is fx Ex is
01:11:59defined if only if as is the power of an.
01:12:14In this is this is that.
01:12:18IT is just a sequence of this,
01:12:22but in general will be the pattern to follow exercise is this.
01:12:35And that. Is not a.
01:12:53Exercise is about the.
01:12:56technical typically their conceptual content is not proof.
01:13:00Tu sei ok understand something muore is just to play with
01:13:04the show that there is a total computer function.
01:13:30That. The domain of
01:13:36the function of key arguments the sky and this time.
01:13:42Is the place.
01:13:51Of the components.
01:13:58If. You can try,
01:14:08anzi if you manage and see Ok,
01:14:11but this is super trivial am very happy if if you know.
01:14:28How will be a function where?
01:14:32Are parameters and then you used This is the general idea.
01:14:45Okay. I hope is kind of understand.
01:14:52Parameter n program is what you can do effective and we
01:14:59move to the next technical pillar of computer theory.
01:15:06We want be able to finish today
01:15:08so it is just an introduction and it is the universal function.
01:15:21Which is where is everything
01:15:24started where computer science started.
01:15:27So it is a large title for.
01:15:35The universal function it is an object,
01:15:39which is very easy to define.
01:15:45IT is a function save the arguments in this case.
01:15:51Where you in the first argument?
01:15:59As a program. The second argument as an input
01:16:04the program and you want to
01:16:07know what is the result of executive program.
01:16:11I over. This is a function.
01:16:15This is what if you can it.
01:16:17IT.
01:16:25Is is it computer.
01:16:33If you have universal machine now.
01:16:38IT is clear what we have universal machine here.
01:16:40IT is what is the time,
01:16:42where this is it was last clear as it computer.
01:16:49Is clear yes for us,
01:16:52we are living in the first.
01:16:57If you have a machine get the program.
01:17:03You it takes in input program and then input for program.
01:17:12I simulati program I x.
01:17:18So this is executive.
01:17:23Program I program for the encoding gamma is over input x.
01:17:37So as is said before this is completely clear it is interpreta.
01:17:43IT is the machine,
01:17:45which is able to execute Program not really surprise and for
01:17:48us what if you like it from a different perspective.
01:17:54IT is a big surprise because when i
01:17:57range over all possible natural numbers.
01:18:13And you consider the universal functions.
01:18:18Where you fix the first parameter to say first?
01:18:24Then want?
01:18:29To. What you
01:18:37get is a function of the second argument,
01:18:39which is the function computer by program
01:18:42five zero zero the function Computer Program.
01:18:47Function computer program to a single function
01:18:51the universal function which bodies all other computer functions.
01:18:57By just changing the first parameter.
01:19:01And so on Ok, but then.
01:19:06We can get very rich.
01:19:09We can found the Turing.
01:19:14Company. Where we sell
01:19:22software but actually we are not writing.
01:19:25A single line of the beginning we program
01:19:28as well as we will do next time.
01:19:31The universal function then
01:19:35we close the universal function into a box with some
01:19:41of caption just avoid that the other people discover
01:19:47our secret and when the same customer client and ask safe for.
01:19:57A program for training with mathematical dates.
01:20:08Ok. Ok.
01:20:13I. Think it is program.
01:20:20Thousand. Twenty five with
01:20:27this input to our universal machine kind
01:20:31and we keep open only the real input,
01:20:36which is the query and his will
01:20:39produce in output the response to the query.
01:20:43A lot of money for this.
01:20:49Is for one billion dollars and then another customer and I want
01:20:57a web service for something with
01:21:01some quality guarantee response time of some kind it.
01:21:07I can. IT for you but write a single line of God,
01:21:11we just take our universal machines.
01:21:14We know that this is program.
01:21:23Or for for twenty thousand and one
01:21:30with the number into the wild it into the machine.
01:21:35We offuscate bit and this is the program of service.
01:21:43Solving it single with given political without a lot of
01:21:49money and we become very very
01:21:52very rich without writing a single line of God.
01:21:57We don't we do this.
01:22:12Is exactly because at least I fortunati otherwise I would be.
01:22:18Able to find this number without writing
01:22:21the code this number is the code the only way,
01:22:24we have to to get to this number
01:22:27is to write the program and used to get to
01:22:31the number so actually the number
01:22:34is the program so we can Not in this way,
01:22:40you can eat rich, but not in this way.
01:22:45And yes we can through the theorem about the universal function.
01:23:02Which is in general you have
01:23:06the universal function for any given it so we fix a given parity.
01:23:15Universal function.
01:23:18Of which is actually KEE because this is the program.
01:23:33Si, ok, go Anche i plug in to find by.
01:23:42Sai che i ex KEE ex X computer?
01:24:01And look at the book the proof is mirrorless as follows.
01:24:09You fix you are.
01:24:17Given. Program and the input ex
01:24:24what you want is
01:24:26a program più di universal program which starting from.
01:24:38Program in register and program and
01:24:42input register to up to keep calm.
01:24:51And eventuali terminate if that the case
01:24:55for this function simulation.
01:24:59In register on fire I k of.
01:25:07And the proof is like this.
01:25:12Is working.
01:25:19IT can. The. Program which
01:25:26is computer how by using the effective encoding reverse.
01:25:34And then use this program as follows you initial memory.
01:25:56Simulate program.
01:26:00And this is it because finally you will find in register one.
01:26:09If the program Terminate i KEE of.
01:26:15Everything is affected by church during this is this is computer.
01:26:42With find factory because especially saying why should
01:26:51be student why should should
01:26:55be possible to simulate a program over the input.
01:27:00This is exactly what we want to know how.
01:27:03To find this factory.
01:27:17Will sometimes not long time to you in a similar way as we need for
01:27:24the theorem and su start
01:27:28up proof what actually everything can be made in Italy,
01:27:32formal way and stop some point because this is
01:27:36the complete proof would be a bit too long,
01:27:40but most of this details because this is not is not complex.
01:27:46Only is it is a bit because
01:27:49you have a lot of index a lot of subscription,
01:27:52but it will take something like of our lives
01:27:56and we will to this next time in the next lesson.
01:28:06And this is it for me,
01:28:09if you have questions to answer.
01:28:26No.