Trascrizione
00:00:04È questo.
00:00:09Quello. Che da un certo punto di.
00:00:21Vista.
00:00:24Della.
00:00:55Popolazione.
00:00:57Ok, fin qui Can start.
00:01:22We start from where is the time.
00:01:27I remember that we introduce the class of partial functions.
00:01:34This is intended to be a different model of
00:01:36computational different from the machine with
00:01:39different with defined IT is the
00:01:41least which classe which means the least class of functions,
00:01:44including basic functions and closed under
00:01:46three combinator composition primitive recognition
00:01:49and wounded minimal section and the idea to
00:01:53view it as computational model is that
00:01:56it is a sort of functional language where you have
00:01:58basic set of functions and build functions by using the combinator.
00:02:04This is the so different from the machine,
00:02:08but we are expect all models of
00:02:09computational to give the same class of
00:02:11compatible functions and we are this is
00:02:14the case for this to you are here.
00:02:19We are in the middle of the proof because we
00:02:24already observer that this inclusion is clear what we
00:02:29already did we need that the
00:02:32computer computers functions and so it is included in this is.
00:02:39For the inclusion, we started in the following way.
00:02:46With a function, which is compatible using the machine for this.
00:02:52You have in order to be computer you need to have a program,
00:02:56which is computer the function
00:02:59and then we define to functions what we can see.
00:03:02J.P. which is the content of
00:03:05the first register and the next instructions to be
00:03:09execute after the steps of
00:03:13computational the second argument starting from input.
00:03:18And execution program.
00:03:22With the idea that when the program finish is it will be
00:03:27the final result and JP gives which is on
00:03:32existence instructions and the observation was
00:03:36okay dysfunction whether their computer or not we don't
00:03:39know anything about this functions, but.
00:03:44We can observer the function can be defined by
00:03:49using this functions because if you search for a number of steps,
00:03:53which determined JP to become zero.
00:03:57This is the number of steps required for the program.
00:04:01Terminate on input x it
00:04:05might be non exists because this is this case the functions is
00:04:11undefined but if then
00:04:14the content of register one after this number of steps is
00:04:18the result and so it is the way of the functions
00:04:21of the written in this way and.
00:04:25As it all the before we don't know how
00:04:28many very much about this to functions,
00:04:31but if you are able to show that are partial functions.
00:04:37Then we can conclude because this function which is generic
00:04:41you are not compatible functions will be by
00:04:45by using the the operator of
00:04:48partial functions Io sento functions which are not
00:04:53to be ADCs effect so we just need to this fact just because it.
00:05:01IT is the core of the proof.
00:05:05And today we try to do this and it will be not super easy,
00:05:13but neither is difficult one could thing because the facts that
00:05:19after any possible super
00:05:25sofisticati language your favorite language after ask.
00:05:30If you are you can be execution
00:05:34on the machine and its execution reduced something,
00:05:38which is just some bank of
00:05:40operations is something should be expected the program in
00:05:44the memory is a list of these number and
00:05:49Your machine computing machine calculator machine
00:05:53is able to do only the basic level only some some shift.
00:05:58Maybe some moltiplicazione switching memories from one place
00:06:03to the other and that's it and jumping between instructions.
00:06:09So what you can transform.
00:06:11This is to any execution program
00:06:13into a series of algebra operations
00:06:15is expected what is it is that
00:06:20this can be formalista until
00:06:23almost the last time in the time and so we
00:06:27trying to this is not until the last which would
00:06:30be would be to to long,
00:06:34but up to a good level of rigor so we have our program,
00:06:42which is the program for function if.
00:06:53This program as usual is in standard form so when it is that it is
00:06:59nothing at the last instruction plus
00:07:01one and the execution of this program,
00:07:05which is the least of instructions will
00:07:08start from instruction what.
00:07:13If it is not jump move to to this might be or
00:07:19not and and the conditions
00:07:24might be true or not so could not to
00:07:28the next instructions or jump somewhere and
00:07:31so and we want to keep track by means of
00:07:35function JP of the number of instruction to be execute next.
00:07:40This is our first time and
00:07:43the second time is to Take that we have the memory.
00:07:50Which is influence and execution and
00:07:54this memory of the last register,
00:07:57which is in principle and infinite which is a bit boring.
00:08:03Because you remember our memory is in
00:08:06principle and infinite memory world
00:08:10register register to register three and so.
00:08:19This is working because we want to take into account step after
00:08:26step of the content of the memory and keeping
00:08:30with infinite amount of information might be bit difficult,
00:08:34but we have to remember that actually our programs
00:08:39are using the direct address so.
00:08:48Will be greatest index of register,
00:08:53which is by the program and
00:08:55after the register the content of the memory totally
00:08:58relevant and so it will be
00:09:01changed with respect to the initial state, which is an.
00:09:06So we have the last but not least is a bit programmatic
00:09:11for us because we have only functions,
00:09:16which can the end of on fixed art of
00:09:21input e fixed list of inputs
00:09:24so we want to encode the content of memory as a single number.
00:09:30This will be our idea to reduce to remove
00:09:36the dependence on the land of the least so memory.
00:09:42is single number exploit in
00:09:44the unique of the composition of a number factors.
00:09:49We take that product for
00:09:54possible register of the number function that we the last time.
00:10:01At the power, which is the content of register.
00:10:06This might lucas as an infinite product,
00:10:10but it is not because after indexing.
00:10:15The content is zero by
00:10:17the air one you
00:10:20can remove this factor so this is essential the same
00:10:23as product from which cause from one to some of the.
00:10:34Memory encoder as a single number and given
00:10:38this number you can get back to the content of register
00:10:42because you need to see what is
00:10:46the end of the prime number in the prime the composition of.
00:10:52This is also a function introduce. Just to give an example.
00:11:02Imaging what you have the memory which contains.
00:11:07This is your memory,
00:11:10which contains in register on the value to in register
00:11:15to the value zero in register try the value one and.
00:11:25You encode this is the number, which is.
00:11:29You will have the first tree prime numbers.
00:11:36Because of the rest will be the zero
00:11:40and register one to the content.
00:11:48For register to the register,
00:11:52three experiment is one and then all the others are one.
00:12:01Of this is what. The count
00:12:06so this is the number that we can compiute in case.
00:12:09We want to it is to the two times,
00:12:13three to the zero times five to the one,
00:12:17which is for times,
00:12:19which is twenty so.
00:12:22This content of the memories.
00:12:27And given twenty we can ask,
00:12:31which is the content of register three.
00:12:34IT is the point of prime numbers tree of the composition so it is
00:12:40what we can go back to the
00:12:44between the representation the explicit content of the register.
00:12:57And then we get back to our name,
00:13:02which is this to functions are compatible
00:13:05not computabile primitive partial ricorsive. There are.
00:13:24But only since this function will be defined by
00:13:30primitive recursion essentials su Resort ad
00:13:35each step on the content of the memory and on the instruction,
00:13:39which has been selected
00:13:40previous step with the only the content of register one,
00:13:45but we need the content of the memory so actually.
00:13:50Not only of register one of memory.
00:13:54This is the only change.
00:13:59On register and we show that is the functions
00:14:04are in the air partial and we do this by
00:14:10showing that we can defined by
00:14:12primitive regression using only functions
00:14:15that we have been provided
00:14:16to be partial how because this is the composition and
00:14:27iframe number and like We have
00:14:30the end of time started from the basic functions by using
00:14:33primitive regression and composition
00:14:37so they are in if using this by primitive.
00:14:42We can define J.P. functions are in our.
00:14:49And what we do is with defined.
00:14:59By mutual primitive regression
00:15:04This is not exactly primitive recursion
00:15:07and so this is not this is the point.
00:15:09We are not totally formal what we
00:15:13should we should take the power of this to values.
00:15:18This function in a single number of this pairing,
00:15:22but would be only complex without anything conceptual level
00:15:28so we the functions at the same time by
00:15:30using the two for the shining,
00:15:34the other and you can can be transform in
00:15:37a PROpel primo step by the primitive reaction,
00:15:42but it will be a mutual primitive.
00:15:53From the case. So. The value
00:16:04of the content of the memory starting
00:16:08from input x after execution zero steps of competition.
00:16:13Is the content of memory.
00:16:17With only the input.
00:16:22So if start from this.
00:16:26Input. And perform having
00:16:33this content memory and this can be defined as a number.
00:16:38Yes, it is the product from one to k of the.
00:16:49And which is the next instruction to be
00:16:52execute after zero steps of competition as.
00:16:57IT is the first instructions to be executives for the program,
00:17:01which is the instruction number one.
00:17:11Of the cases.
00:17:19Where we want to define?
00:17:23The value of the functions IP over x
00:17:30step plus one JP x one.
00:17:37We want to do this by using the values at the previous interaction.
00:17:54With the only since we have to repeat
00:17:59several times JP XT with
00:18:02just use shortcut and we can this just
00:18:06si in the definition because this just.
00:18:17Because we have to repeat several times good
00:18:22and this is easy Is because.
00:18:29This is the content of the memory.
00:18:34After the one steps of competition.
00:18:42And so it will be the content of the memory,
00:18:48which had that step the
00:18:51modified by the instructions, which execute before,
00:18:56but instruction which execution before is the instruction of
00:19:01index j j p t and so I just.
00:19:12Before which is see
00:19:15and modified according to the instruction execute,
00:19:19which is instruction J Understand how it has been modified.
00:19:24I need a case on the nature of destruction,
00:19:28which a executives so distinguished several cases.
00:19:33If the instruction J is a PROpel instructions,
00:19:40which means that the index between one and the land of the program.
00:19:47Because this is finished J is what if you and something.
00:20:00Is a instruction.
00:20:04Then I want to put zero in register and.
00:20:12You have to remember. So I want to take.
00:20:19Si and I want to.
00:20:23Know how to remember search è presente
00:20:26Content of the memory and the following way.
00:20:37This is the content of the memory and in position and you have
00:20:46some value are you present
00:20:51This is the content register
00:20:53on air one your present this with the number,
00:20:56which is one to the air one path to the air to the end to the air.
00:21:04And you don't want to have and
00:21:08their longer you want you want to get zero,
00:21:12which means that you want pn as it zero and given number si.
00:21:21Were in the composition as.
00:21:26An and you know what are is yes, we know.
00:21:33What? Is the moment
00:21:39of the composition of if we want to put zero.
00:21:47There we need to divide see by the are we need to see.
00:21:58And take the end of see divided by pin to the air one, but is an.
00:22:17In the register is. The king.
00:22:31Is clear because this is clear then all the rest will
00:22:35be applied to other instructions doubt about this.
00:22:49Is not than the rest should be clear because.
00:22:55If you are execution PROpel instructions.
00:23:03And this instructions is a success.
00:23:13That you want to put in register
00:23:17and the value before you want to incrementate
00:23:22so you want to increase the point
00:23:26of the point of you need to multiply by.
00:23:40The planet and if.
00:23:49Instructions a transfer.
00:24:00What this is just a combination of things and then
00:24:04at the value of art and so you from see
00:24:10you take the science OCSE Divided by
00:24:15the end to the end of this point we have zero in Iran,
00:24:21but you don't want to have you want to have
00:24:25the content of register M and so you multiply by.
00:24:31With the content of register and.
00:24:47Other ways. And other wise
00:24:52included several things it include the facts,
00:24:55but it might be that j is equal zero.
00:25:00So the program is finished.
00:25:04Or. J is the end of the PROpel instruction.
00:25:15Instructions Jump.
00:25:24Jump I don't modified the memory when the program is finish.
00:25:30I don't want to this is.
00:25:49This. The content of the memory and the effect of
00:25:56the next instructions to be
00:25:59execute the program counter is capture in a similar way.
00:26:08Because again this build up and execute
00:26:12before the content memories and so.
00:26:18We have to distinguished cases
00:26:21before we execute instruction J which is
00:26:26not the last of the program is not the last of
00:26:30the program and this instructions is not a jump.
00:26:43Or it is a jump.
00:26:47With condition force.
00:26:56Condition fault means that the content of
00:26:59register and the content of register are different.
00:27:05To Gli osservatori of the function previous interaction different.
00:27:16Time. To the next instructions.
00:27:34If you are execution PROpel instructions
00:27:39to the index J is between one of the program.
00:27:44And. The instructions jump.
00:27:53And the conditions of the.
00:28:00Content register is the same as content of register
00:28:05and the point we are jumping is a PROpel instruction.
00:28:14Destination is an instruction
00:28:17because could also jump out of the program.
00:28:24When it jump go to.
00:28:29IT is not good choices because it is the same as
00:28:34it changed the argument of jumping because this is the same stesse.
00:28:42Bene, jump to the destination,
00:28:45which is in the structure. And otherwise.
00:28:58World is otherwise included several things.
00:29:03Ed include i jump but jump outside program it includes the facts.
00:29:10I might have the last instruction
00:29:15and that like to move to the next one,
00:29:17but it doesn't exist just finish or
00:29:21the facts that JBoss already zero the ready terminator.
00:29:27In this is.
00:29:38The. End back this
00:29:46is not completely formal because
00:29:48this is this is that we know how to transform.
00:29:53This is in the PROpel function,
00:29:57which is not using Charlie break and like this several times.
00:30:02but we are just using the value of the relations functions product.
00:30:10Where is it esponente of a number.
00:30:16The number of functions which has been a ready to
00:30:21be in here we are defined JP
00:30:25by primitive recursion mutual primitive regression
00:30:28and so we conclude that they are themselves primitive regards.
00:30:44Fece what we want because now.
00:30:49We just remember that the function was defined as
00:30:57the Possible number of steps you
00:31:01need to let the program terminate on input which is this.
00:31:08Make the functions becomes.
00:31:12And then the mind the content
00:31:15of the memory after the number of steps.
00:31:21But we don't want a full of memory.
00:31:24We want the content of register register one
00:31:29is one of the first frame number
00:31:33in the prime the composition of the content of memory.
00:31:40Which is by minimal section.
00:31:46Composition by using CP e JP.
00:31:49We are in our itself and given that generic functions. Si conclude.
00:32:05Okay. And this is the end of love.
00:32:28And that.
00:32:39Is not
00:32:42a continue with the creation with the rest of
00:32:48the last sort of
00:32:49the creation for introduce another class of functions,
00:32:54which will be of interest situations
00:32:58and some consideration about this class of functions.
00:33:03And this is the place of primitive functions.
00:33:28Which is very much related to
00:33:32the place of functions partial functions.
00:33:35IT is not by the way of it is that it is similar to the way,
00:33:42we defined partial functions.
00:33:46This is the least class of functions.
00:33:58With the basic functions.
00:34:18And which is closed under composition.
00:34:29General light composition. Primitive.
00:34:44But you don't have.
00:34:48Minimal.
00:35:01Ok, so if you
00:35:04to the partial records functions as is
00:35:08a language programming language,
00:35:11then this is the same language,
00:35:12where you can't use minimal section to the things.
00:35:16You can use this combinator,
00:35:19which I think immediately suggest that the class of
00:35:24partial functions is smaller than the class of functions of.
00:35:32Ok. Here you can you
00:35:36see you want one to see you can only you want to.
00:35:43The inclusion is strict. Can you Way.
00:35:52IT is clear strict.
00:36:02This is intuitive must be,
00:36:05but this is not a proof and the science that we have the function,
00:36:11which is year, but not here.
00:36:14There is one, which is clear here,
00:36:16but not here to many one in particular.
00:36:41Left size which consistent in classe of functions that you can time
00:36:47From the basic functions by using
00:36:50only composition and primitive are total.
00:36:55White instead in which just
00:36:58proof to be equal to see you have functions,
00:37:00which are not total for the function, which is always.
00:37:03Undefined. So this
00:37:12is this is easy,
00:37:14but actually if minimalismo was were useful only to define
00:37:22function which can be undefined at
00:37:25least in sequential setting it would be very interesting because.
00:37:32This sequential setting for sequential programming function,
00:37:36which is always which is Non terminate on some points
00:37:40wrong account think of anything useful in sequential setting,
00:37:46Which is partial saliti in a setting is a mistake is back.
00:37:52I don't want a function,
00:37:54which is the products,
00:37:56but only sometimes some other time.
00:37:57IT is a function,
00:37:59which is the some of
00:38:01the number one of the two numbers is the function.
00:38:04This is no interest setting that different story.
00:38:11If you programma server you want to server it principal to continue
00:38:14forever so it is not only accepted,
00:38:18but it is the expected expected behavior,
00:38:22but it sequential setting
00:38:24personality and so the real question is do it really need.
00:38:33Minimal action to generate.
00:38:39Functions with total.
00:38:45And this is not
00:38:48an immediate answer and actually
00:38:52Hilbert was convince that answer was now,
00:38:56but this is not strict,
00:38:59but later on Ackerman student,
00:39:02but actually this is the case the inclusion strict and you
00:39:07think that this is just very artificial curiosity,
00:39:13but it is not it is not really at the basis
00:39:16of computational because this is
00:39:19probably several times primitive recursion is bound interaction,
00:39:27you fix and we can do it
00:39:30times so this is the for loop in programming language terms.
00:39:38Bound it. IT was listed minimal Minimalista continue until.
00:39:46While their function is not zero There is this condition,
00:39:51but to meet to there is not bound on the number
00:39:54of this is a sort of while loop.
00:40:00And. The can be made for you can consider
00:40:11other languages less than you are machine or
00:40:15you can make the machine less primitive allow
00:40:20for structured programming in a way that you have the for
00:40:23loop loop rather than jump and the class of functions.
00:40:31You can can only using
00:40:33for the class of functions that we can computer using for
00:40:36while and you can see that this
00:40:40is the same as the class of primitive functions that you can
00:40:46can win for what is the class of partial functions and so if the
00:40:55minimal we are not useful to get any total computer function
00:41:00then it will be very interesting to know
00:41:03because you could remove while loops from your languages.
00:41:08That we have experience that getting the right is much more
00:41:13difficult than the thing for loop write and
00:41:17in particular if everything was
00:41:19terminate lot of things would be you could
00:41:22generate programs employment given specific life much,
00:41:28but it is not because.
00:41:32This is what you need to find it
00:41:36everywhere while love and the reason is that you have functions,
00:41:41which are here, but not here and we see
00:41:46an example e full proof of this function is on the right and side,
00:41:51but not least and side a lot of
00:41:53time so with just see some intuition
00:41:56some ideas fully understand
00:42:00able and this function is the Ackermann function.
00:42:04What is typically di biopsie di function IT is not here it is it.
00:42:17Is not. The definition.
00:42:34IT comes in different flavour with the binary version.
00:42:39IT is a function to arguments.
00:42:48And it is defined in the following way.
00:42:55Over zero.
00:42:58What if the first argument zero.
00:43:01IT is the success.
00:43:05If the first argument is better than zero,
00:43:08but the second zero.
00:43:11Than. IT is defined as.
00:43:22And if arguments better than zero.
00:43:27That you have nested recursion.
00:43:33Which is the forum. This is
00:43:40the definition and what we want to do is that this is the function,
00:43:46which is not here by proving that.
00:44:02Is to. Say is computer.
00:44:13So it is. That it is not primitive.
00:44:29But before about to this only about this three things.
00:44:37May be first point is to stress something,
00:44:42which a typically under the situation say.
00:44:49Something by. Definition by Richardson is
00:44:56on the same function year and
00:44:58year typically with the problem by sei Ok,
00:45:02but we are not matematici your computer scientists
00:45:05and so we are happy to the function is
00:45:09defined on by using the way of the same function
00:45:12smaller arguments and so this is a good recursion and it is the.
00:45:19Case this is not so.
00:45:24Because you see that for the final.
00:45:29Four instance the function on X0XX0.
00:45:38You on expand is this is this is one is better than one.
00:45:49And year the situation even more complex.
00:45:54So the fact that we are carrying on smaller argument is
00:45:59clear unless which is the order by your consider.
00:46:09Are you familiar with the lessicografico order.
00:46:16Not familiar, but about it.
00:46:19IT is the alfabetico order when you order strings in.
00:46:26You typically used lexicon Geographical Order
00:46:29of the first letter count more than
00:46:32the first letter to the second hand and so here we have to letters.
00:46:40To the order is over pearls of natural.
00:46:48And to say that appear of natural way of life,
00:46:55geographical to explain prime if.
00:47:01Ex smaller explain and is
00:47:07the first component order in
00:47:08this way than the second component doesn't count anything.
00:47:15Or if the first components inside than you go look the second.
00:47:32Okay. This is the geographical order
00:47:42to give an example if you take.
00:47:49One one thousand this is
00:47:55smaller geographical than to zero to heaven.
00:48:02If the second component is decreased quite
00:48:05a lot is the first component increase the second this large.
00:48:11White instead if the first component remains the
00:48:15same then the second component count.
00:48:38Ok. Now we go
00:48:46back to the function that.
00:48:51According to this order year the first component is.
00:48:57So we the evaluation of air one zero over one.
00:49:07So we are in the final order.
00:49:13In the second case it is not clear,
00:49:16but we first observer that. This per.
00:49:24Is smaller this per so ex plus
00:49:29one plus one is greater lessicografica than ex plus one way.
00:49:41So we can imagine that.
00:49:47This provides some value say you.
00:49:54Which might be large as we want,
00:50:01but then when we go and computers over as you
00:50:05also you is smaller lessicografico than the start and argument.
00:50:20Sono We are happy before because we need
00:50:25computing function is always carry
00:50:29over smaller arguments in the lessicografico order,
00:50:34but recording smaller argument is not sufficiente.
00:50:40Because.
00:50:58Give an example.
00:51:06As you function from the integer to the integer,
00:51:11which is the find and the following way.
00:51:15Given an integer that it is better Zero.
00:51:22Zero. And it is
00:51:31one if said is more than zero.
00:51:38And the question is.
00:51:43What is the one?
00:51:59If you resort your computational interpretation.
00:52:03This is the one is the same as the mind,
00:52:09which is the same as the three and you never produce a value.
00:52:23So what? Is possible answer
00:52:35but if you read This is
00:52:38the question time to think about the fact that
00:52:42you can put any value for the numbers three the question is the.
00:52:49Way we put undefined because we like it,
00:52:54but this is a different story.
00:52:56If the computational we will talk about this.
00:53:00This is a story if you think the computational interpretation.
00:53:03Yes, we expected to be undefined if you
00:53:07programma in Python you get undefined you get Risolto.
00:53:12But this is the thing on the order.
00:53:16I reduce every time to argument,
00:53:20but so this is not sufficiente what's
00:53:24bad about that and not bad about this.
00:53:32What is good about the lessicografi order and bad about
00:53:39zed in this context is that if I start decrease in the argument.
00:53:46In order some point need to stop instead for this is not a case.
00:53:54I think that it is
00:53:58your computer scientists and you are using sometimes recursion.
00:54:02IT is good to have more interpretation of this not to regulus,
00:54:08this too much time.
00:54:10But you need to think.
00:54:14About this and to be precise about what is good and what is
00:54:20bad for said lessicografico order Respect
00:54:25you need to know what the order if you know.
00:54:29How.
00:54:45About it is
00:54:48you know what order that is a set
00:54:52with the relations, which is reflection.
00:54:59Antisimmetrica? And transitiva.
00:55:08Which means that every element reflect means
00:55:13every element equalizer antisimmetrica means that
00:55:18it is what we are the same.
00:55:25And transit means that it is an ed ex smaller set.
00:55:37Ok about the partial order that's not important we
00:55:42need just a little intuition about that the point is
00:55:46that this properties allows you to think of the relation
00:55:52as intuitive one element being below and other so.
00:56:02If you hopes.
00:56:11E Drew Bullets.
00:56:16You must have one element which is above the
00:56:20other then above you have another that's smaller.
00:56:28Another one which is this is more than this.
00:56:32This is this is that the order in
00:56:36this direction so going up elements becomes
00:56:41larger but different from what
00:56:45you are typically used to elements might be in comparable.
00:56:51So for this two non of the two is larger than the other
00:56:56they are comparable. And you can.
00:57:07One on this side.
00:57:12And go to this might be
00:57:18with one two three four five six smaller ten elements.
00:57:29The central concept for our.
00:57:34For our discussion is that we were funded partial order.
00:57:56Purchase partial order.
00:58:00In which you can't go down unbundling.
00:58:04This is the general idea and for explain this I
00:58:08need the idea of minimal element.
00:58:14So minimal element in an order is an element,
00:58:20which is nothing below.
00:58:23For this is.
00:58:27Minimal.
00:58:39Under this element.
00:58:42IT is not minimum.
00:58:44IT is not the least element because it is not below
00:58:48everything this element is not below the road,
00:58:52but there is nothing below
00:58:54the minimal means this there is nothing below.
00:59:01When you defined minimal element is
00:59:04that if you have something below it is the same.
00:59:10This is like to this is nothing below the only thing,
00:59:17which is below the element itself.
00:59:22Good and now, we can say what is a world funded order.
00:59:32Our personal order is funded if.
00:59:41Every non empty set as minimal element.
01:00:11E i take. That full.
01:00:22As it takes the full order everything.
01:00:28This is our ex.
01:00:33When the red element is a minimal.
01:00:37But also this is minimal you can
01:00:43have many minimal elements different and also this ones minimal.
01:00:56Draw one of them minimal Good.
01:01:06We do I care about this, but before saying.
01:01:11I care about this is an example in case.
01:01:16You are not very familiar with partial order of the staff.
01:01:20Is very simple example,
01:01:25which is to the Italian what we say in Italian
01:01:31you can't mix Apple and peace and other countries.
01:01:36You to see you cannot mix
01:01:38things little to do it with the other italian.
01:01:42We see you can't compare Apple and pears and so it is this and
01:01:50I consider a partial order in which you can
01:01:54have either some amount of Apple or some amount of pears.
01:02:01And I wright saying that I have an element can be
01:02:07pears and indicate the number of elements or it can be Apple.
01:02:14And I have a given number of elements where and can be any number.
01:02:21But since I can can per Apple with pears yes.
01:02:26Trying to this is that are not found because.
01:02:32Integer not because of you take exactly if
01:02:35you take the negative numbers.
01:02:38There is no minimal and their exactly this will be the final.
01:02:45And I don't expect everything is totally clear.
01:02:48If you have been this trying to get some
01:02:51because this is really fundamental.
01:02:56Eppure Spears and so
01:03:01you can't compare which means that if I have to Naples,
01:03:04this is not comparable,
01:03:06but if instead have to Naples
01:03:08or three Naples three Naples is larger
01:03:10than two Naples Ok, so having.
01:03:18Zero pears is smaller than heaven.
01:03:24One pear which is more than even to pears.
01:03:36Assimilarli even zero Apple.
01:03:41Is more than one Apple.
01:03:47Which is more than heaven to Naples and so.
01:03:57Apple is not smaller one is not smaller tanto Apple their not
01:04:02comparable so if I want to for this relation given type of the.
01:04:11Same amount of this is only to
01:04:16the same same tipo fruit with say amount.
01:04:27IT is to the prime.
01:04:31Hand and is.
01:04:35This would be the forum definition,
01:04:38but it is clear.
01:04:42This is not for our understanding and again.
01:04:46This is to minimal elements.
01:04:54So just to the point here
01:04:57would have been to whether to see you have
01:05:00a good understanding of intuitive understanding of this is
01:05:04that the state of integer numbers or found
01:05:08your league already it is
01:05:11not to take the negative numbers that is not minimal element.
01:05:24Heart of natural numbers found.
01:05:29As it is and actually in
01:05:33that case whatever non empty take least element.
01:05:47An minimal elements is
01:05:53not directly what we want for termination recursion,
01:05:59but you can through the following.
01:06:04Not you, but it has been brought you don't need
01:06:08to that partial order is found.
01:06:16Even only it.
01:06:21IT does not meet the sound changes.
01:06:44È un buon testo in infinite sentence is from
01:06:48element then go to small air one to
01:06:53one and continue forever I can't I can't go down
01:06:58infinity longer this cannot be the KEE.
01:07:02If if if.
01:07:10If if if there is.
01:07:16No because if you take that is very seriously the equivalent.
01:07:23In one direction requires something,
01:07:26which is related to the actions of choice.
01:07:29These delicate point, but this is not to
01:07:34this foundations issues and.
01:07:38The point is that when you want to should be the love and
01:07:46about Terminato il typically
01:07:50even if you don't know how typically having some partial orders,
01:07:55which is funded and you know that you are you for your functions.
01:08:04It's time going to
01:08:05a smaller element and their not the infinite changes,
01:08:09you know what point this.
01:08:13Is what about the state of integer without zero zero.
01:08:22But would be able to go.
01:08:27Take that it is not found you need to stop the point. If you stop.
01:08:34Sai mai this is what if you continue for going down,
01:08:39this will never be found.
01:08:43But So. You to think about this?
01:08:49When you have a procedere what you want to show a
01:08:53determinate independent you want
01:08:57you or not you have to think of
01:09:00war found partial order to
01:09:03you that you are procedure is going down.
01:09:06This order for Ackermann function.
01:09:11This is the lessicografico order on
01:09:13the square on part of natural numbers.
01:09:19This is not found.
01:09:28To it is what you can do in different ways
01:09:33for you can do the following you take it.
01:09:41And you can use that the natural numbers
01:09:45are actually they are even better when
01:09:48orders non empty set minimum element
01:09:52and then you take the first components.
01:10:04You project on the first component. And you take that minimum.
01:10:13KEE man in the first components and you take that minimum.
01:10:20And that is the second component among the element,
01:10:24which is minimum first component minimum is the second.
01:10:31The minimum such that is the next,
01:10:37this is the formal what is In the first and the second.
01:10:44Hand if you do this then.
01:10:49Y zero is what is the minimum fax in the order.
01:11:03To this is not found. This is what.
01:11:08You can you what the function is total because
01:11:12this is in the recursion found in order.
01:11:25And this is if you like infinite things to think about infinite
01:11:31think it is quite peculiare if you want to be super formal.
01:11:36We should introduce.
01:11:39Induction principle which is associated
01:11:42funded orders, but we don't want.
01:11:46To think of this partial order is
01:11:50shaped because you start from zero zero.
01:11:55IT is the minimum of everything that you can go one step up,
01:12:02another step up to and you can continue forever
01:12:06going without breaking one in the first component.
01:12:11If you go to one of this is above everything of the shape.
01:12:17Zero KEE. You can Continue reading.
01:12:22One one one two also thank you can
01:12:27make up and go to zero to one two two.
01:12:35So essential it of this.
01:12:42Is a copy from the name of the element that is a copy of
01:12:47the natural numbers with the order of.
01:12:52This is another copy of natural numbers.
01:12:56This is another copy of natural numbers.
01:12:59So infiniti many copy of the natural number one after the
01:13:04other this is and we are the geographical order.
01:13:11Which means that if you start climbing this.
01:13:18IT is very very that it is infinite many times infinity,
01:13:25but if if you do if you go the other way of your up somewhere.
01:13:33And start going down.
01:13:37From time to time you need to take infinite jump because where to
01:13:42zero there is now predecessore you have to make an infinite jump.
01:13:50Venti Continue to make
01:13:52another infinite jump which
01:13:55means what if you from any element and you go
01:13:57down the night stand up is infinite many times infinite.
01:14:09And it is strange thing.
01:14:17Ok. Let's go so we are kind of convince,
01:14:26but the functions size total.
01:14:36With like to you like this computer.
01:14:43Is. Which is the same same,
01:14:49which is your computer and for you about this.
01:14:59We can used to see in the future,
01:15:04but we don't need strictly that we can also
01:15:09intuitive and observation is the following.
01:15:14If you want to computer Ackermann function
01:15:18over the value of inputs.
01:15:25At the definition so that you can. Che.
01:15:54Questo computer sia one to
01:15:59one one piece of arguments Scritto da zero So this is.
01:16:08Over zero.
01:16:12Sei uno zero.
01:16:17We focus on this which is
01:16:21this is this is the first in the second so
01:16:27this is Sai over zero
01:16:30one and we are in this case and this is the success of this is.
01:16:39An so here. This is one of. Which is three.
01:16:53And you see that in order to computer the value of
01:16:59the function over one one and you were three.
01:17:06We need to consider value of the function over zero to.
01:17:17Zero. Two and three.
01:17:26But in order to get to this point.
01:17:29We need to the value of the function when zero and result.
01:17:42And for this is the way of the function over zero one and the.
01:17:54Long but steel.
01:17:59As we are also before you need only a finite amount of steps.
01:18:06So you need to understand value
01:18:10to the function of the function one point.
01:18:13You need value of the function on a finite amount of
01:18:18other points and you can character as in a.
01:18:23Better way. which is the state of
01:18:28tribes of you need to the right to get the way of
01:18:32the function of the one triple of air one and for this you
01:18:37can introduce the notion of valid set of trials.
01:18:49Which is intuitive of trials like this you from this and then
01:18:53you want you need to the other trips to get to the final results.
01:19:01This is the place of this is.
01:19:08Where the intuition is that in its
01:19:11triple the first element is the way of the function.
01:19:19And. The set.
01:19:28Contains old triple needed to computer.
01:19:46Side of. This is intuition.
01:19:55You can make this a little bit formal.
01:20:13And the water tribe is.
01:20:19IT is valid If you have to remember the function is it.
01:20:39If you have a triple of the king.
01:20:42Zero sette zero sette.
01:20:47Your thinking of this is the argument and is to the result.
01:20:58You want this is what. You are in this case?
01:21:11If you have one zero sette in this.
01:21:21Senza in order to get the value
01:21:25for this function you need to get this is to
01:21:28input you want to see the triple X one in us.
01:21:43And is a little bit more complex because if you
01:21:51have the triple of the kind x plus one way plus one as.
01:22:02You need a triple which compute this value.
01:22:09And you know it will be some you and it is over input x. Ho.
01:22:24Fatto nota Only you have you for this input?
01:22:30Thank you want the result for you.
01:22:34And it must be used. As it kind of.
01:22:43Understand you want a function,
01:22:47which is need to the value of all the point that you list of this.
01:22:54Is the. Way and you.
01:23:01Must be. Exactly here taking this
01:23:08thank you very much taking this which
01:23:11is to this is it must be one way.
01:23:14Yes. Pensa che thank you very much.
01:23:25Ok. Now the observation has that.
01:23:36We can prove that.
01:23:47The function over input is what if if I
01:23:54can find the state of which is this is it.
01:24:06Is he finite?
01:24:11Valid. Set of trials.
01:24:19As. Such as we.
01:24:29Are as.
01:24:34Which means that in order to the function you
01:24:40need to search for a fine set of trials,
01:24:45which is valid which contains this trip search is minimal.
01:24:54Clear. You can't search for the use
01:24:57of you need to the city of trials for
01:25:00the memory as a single number you need to search for
01:25:03the number for this require a lot of effort.
01:25:06We don't do it, but it is intuitive to
01:25:10you that if write that to computer
01:25:13say I search with
01:25:17a minimal action for the asset as which is finite.
01:25:25And for used such.
01:25:29As is a fine set point of trials.
01:25:42And over the result set.
01:25:49This is informal but I could.
01:25:54Encode this as a single number and then translate
01:26:01the national bullet for a number of tribes as a predicate,
01:26:09which is not and so on.
01:26:10A could really do this form.
01:26:17We don't do it. IT a lot of effort.
01:26:22We could to this.
01:26:27So this is it, but it can be made
01:26:30form and how the point is that yes,
01:26:36we can computer Ackermann function
01:26:38probably the same education really
01:26:42willing to do it a could write this formali it is computer,
01:26:46but it is computer by using a minimal session.
01:26:50The facts that here I'm searching this number.
01:26:56Of the triple with the minimal session
01:27:02doesn't mean that it is needed to use
01:27:05minimal session so this is not in indicativo.
01:27:09Ackermann function needs minimal action to be computer.
01:27:14This for the time being is just in education
01:27:17that the Ackermann function is compatible.
01:27:26To. Ackermann function is
01:27:33not primitive recursion primitive ricorsive while this again.
01:27:43Probably lessons what we are happy with just little intuition,
01:27:50which is the following the short short short giustificazionista
01:27:55Ackermann function is to is going to fast to be primitive.
01:28:02And more.
01:28:06Ehm informative Argument is the following you
01:28:12remember that we started the final by the
01:28:17same using the success of the same
01:28:21is it ratings in the success within.
01:28:34Ex and you want.
01:28:43To the product.
01:28:47Which is better waiting the same times.
01:29:01Quei primi.
01:29:10The move
01:29:12to the financial time it rating the product names.
01:29:32And we could be continued making
01:29:36a colon tower of nations each time you
01:29:41need a primitive regression what if you think in terms of
01:29:46bound it in a language you need testing for loops.
01:29:52For this you need a single for
01:29:55you need for loops for the next three for
01:30:00loops of the function is
01:30:03to this process to the stream to the limit.
01:30:24In the way that you need to
01:30:27computer infinite many nested for loops.
01:30:33Again. This is.
01:30:37Our function.
01:30:42And. Let's change the notation for while instead of writing.
01:30:54Stop working. È stato writing.
01:31:01Sai. Sai. Let's consider
01:31:10ADCs effect parameters to write function as.
01:31:19Then if write this by using this notation you get that.
01:31:26Sei zero.
01:31:33Sei. Zero sei.
01:31:40Sei. Sei Plus one of.
01:31:49His six of sei x plus one of.
01:32:05Ehm. No. Typekit express one of some way,
01:32:15which is better than zero.
01:32:17By using this. This is
01:32:20just a different way of light in the function,
01:32:22but it is the same this is.
01:32:27This time.
01:32:30Is increase one you have to apply the function at
01:32:35the previous six to express,
01:32:40one of way to you decrease way and you six in front.
01:32:48This is say ex six Plos one way minus one.
01:32:59IT is still greater da zero.
01:33:05This is ex PCI, ex PCI express,
01:33:10one of two and so on until the argument year becomes zero.
01:33:27So you need to get it six times.
01:33:39And then six plus one of.
01:33:46Which is say.
01:33:53So this is psi ex applied one times.
01:34:04Of you. And this
01:34:13is very very informal,
01:34:15but in the parameter by one corrispondono hit rating the functions
01:34:24with parameter ex within in order to decrease
01:34:31it is time you increase
01:34:34the parameter as you have to the interaction.
01:34:39Of the previous function within the.
01:34:44Increase ex increase the number
01:34:48of nested for loops what you need to the function.
01:34:53This makes sense to you,
01:34:56but the idea is that increase.
01:35:06By one. Increase by
01:35:11on the number of nested loops what you need to the functions.
01:35:31Or primitive if you like.
01:35:54Ok, If you accept this time is bound.
01:36:01There is no program, which is using only for
01:36:04loops because if you used only for
01:36:06loops the number of nested for loops
01:36:10should be infinity because this is not found.
01:36:16I don't expect this is really convince or for clear.
01:36:23This is not rigorose,
01:36:24but not least some intuition essential Ackermann function
01:36:29is using the parameter as a way of
01:36:34increase the number of it is that you need
01:36:39further external interaction to the functions
01:36:42and so the number of for you need is infinite.
01:36:46If you want to use only for love and so you have
01:36:50to need also what you have to use also windows.
01:37:14This is the intuition,
01:37:16if you want for this is much longer. I can give some points.
01:37:26Ok. I think this is it for for today.
01:37:35Next time we go back to our main track.