Trascrizione
00:00:00In the previous lesson we discuss
00:00:03a bit more detail about the notion of effective trying to give
00:00:08some more details essential trying to say what we mean by
00:00:12an algorithm didn't give a definition,
00:00:17but only classified which are the features of the machine where
00:00:24the algorithm should be execution and only by fixing.
00:00:33This natural options.
00:00:36We were able to understand that whatever
00:00:39models computational We take there will be always some function,
00:00:43which is not computabile actually and that
00:00:45the majority of functions will be not compatible and.
00:00:50This was still a bit general informal there was not really great.
00:01:00definition of the computer function is because
00:01:07this really defined computer function is not to make proof about
00:01:10that to characteristic of computer functions in a PROpel way.
00:01:14We need to say what is the model
00:01:18of computational working in and we are the program
00:01:22is execute execution and
00:01:24that we have a number of choices number of choices.
00:01:31And this at the beginning might look like a problem
00:01:36because if you look at the history of
00:01:39the computer science and the theory of science.
00:01:42You see lot of people have been
00:01:44posing some model of computational for
00:01:47character and algorithm is
00:01:50a list of model of computational what we want to consider is long.
00:01:59And we can start with the most classical one,
00:02:03which is you to Turing and
00:02:07you have already at least it so Turing machines.
00:02:12This is a elementary model.
00:02:17Where the machine where the algorithm
00:02:21is execution is a sort of state machine,
00:02:26which is which is the capability of reading and writing
00:02:29symbols over at the state of the memory.
00:02:32The memory is that you can write read
00:02:36and how the computational wolves guided by
00:02:40the sort of program is not really program competition
00:02:45can start from some initial configuration and when it.
00:02:49Eventuali termini di output is
00:02:52what you find on the tape at the end of the computational.
00:02:55This is possible, this is not the only one.
00:02:59Also take away the lambda calculus also have heard about.
00:03:08This is the two Alonso church around the same time.
00:03:16This is the last century.
00:03:19This is completely different while
00:03:22the machine is what you
00:03:24understand is the machine that the calculus,
00:03:26which is not been inverted of competition,
00:03:29but rather which is field of found mathematics on the
00:03:33based on the national function
00:03:36is kind of the core of a functional language,
00:03:39where you have only to primitive
00:03:41it is very simple one for the finding function,
00:03:43which is one for playing function to an argument.
00:03:48This is another possibility and then with you could take something,
00:03:54which is instead you to itself himself,
00:03:59which are the partial functions.
00:04:05This is very abstract.
00:04:13Essential it is again a sort of functional language.
00:04:21But in this case we have
00:04:24the basic library of very very basic library of functions.
00:04:28What you combine Some combinator is in the state
00:04:32of some of you have heard about that is
00:04:36this is kind of similar to lisp and then
00:04:40you can radar different
00:04:44the canonical detection system you to e-mail post.
00:04:51Little bit later this is again quite different.
00:04:55The state of the competition is a string and
00:04:59competition step is perform by a playing writing rules.
00:05:04If you have mind context free gamers similar to
00:05:08the very little constraints about rules.
00:05:14You rewrite it until you know is it until you have no rule,
00:05:21which is applicabile and that is the
00:05:24final eight or you have something,
00:05:28which is closer to what we think of when we mention
00:05:33the world computers something which is in
00:05:36the movement style the unlimited Register machine.
00:05:44What you have a memory, which is of register
00:05:49and the Dr. Roper Program may be very elementary language,
00:05:53but program with assignment and jump
00:05:58and like this is quite different and
00:06:03the list is very very partial could be very
00:06:06long you could insert also your favorite model
00:06:09Java or C++ and like this are also computational models and
00:06:15so on might be married because this is the last of lessons.
00:06:22The first lessons to say we are going to face the problem,
00:06:26which is super fundamental,
00:06:27which is totally general independent of any option and
00:06:32then end up in choosing
00:06:33a specific model and developing for that model,
00:06:37which might be it will be doing effort
00:06:42and doing social network for understanding something
00:06:47which is specific to lambda calculus might be interesting,
00:06:52but instead to alleviate our.
00:06:56Our world is there is an experimental result.
00:07:02This probably never a result,
00:07:06but there is an experimental consideration.
00:07:10If you take the clash of compatible function for any
00:07:13of the models listed year and actually for all the models,
00:07:18but you could not the
00:07:21computer exactly the same class
00:07:24of functions apparenti the notion of
00:07:27compatible function when you
00:07:29some ability criteria for the model of computational so you can't
00:07:35say modified the infinite memory or
00:07:39the infinite memory with
00:07:41the single computational step or you don't have operations,
00:07:44which you don't know how to employment say PD versus
00:07:48ANPI Discount alimentari action but if you some some
00:07:53criteria as we did it is this model is
00:07:57reasonable than the class of computer function is the
00:08:02same which led also in the beginning of
00:08:07the theory of the ability to what is called the church during this.
00:08:15Which is that.
00:08:19The function is.
00:08:22Intuitive computer se is computer.
00:08:30By some sort of machine of so by side.
00:08:44Event only E IT is your favorite con it model.
00:08:56Machine. This is not a theorem.
00:09:05Because it is to
00:09:08the intuitive informal notion of an effective procedures,
00:09:12but it is some of support by
00:09:15a sequence of results with all the models,
00:09:19which has been considered to know how in
00:09:22variabili character the same class of compatible function which
00:09:26therefore looks like very fundamental and central notion
00:09:33which is independent then on the specific way to
00:09:37it and so we just choose one of the models and following the book
00:09:45with the last which is simple and may be close to
00:09:50our closer than the other to
00:09:52our intuition that we will understand that for making process.
00:09:56This is still a bit too much details.
00:09:59We need something which is more abstract and we
00:10:02will sort of basic form church Turing This is
00:10:07that this is this are actually
00:10:11equivalent and then we will use this
00:10:13for proof what we start from the time.
00:10:18And we do this today the introduction to
00:10:21the unlimited register machine and of
00:10:24the notion of computational different from.
00:10:28What we did yesterday will be very concrete habit.
00:10:34Not very much conceptual. We do it.
00:10:44So what is unlimited register machine is a machine,
00:10:50which is a memory program and
00:10:54the program is execution by modified the memory guided by
00:10:58some control flow instructions
00:11:02the memory system of a sequence of register.
00:11:08What we can address directly with
00:11:10an explicit address, which is a number.
00:11:14So you can think of it something like this.
00:11:21Register. Register to register try and so.
00:11:31On this register can contain a single type which is
00:11:37a number number so il register you will find a number.
00:11:48That we are which is not a number of.
00:11:55The memory is funded which means
00:11:59that we have has many register as we want you will
00:12:03see every program users only a part
00:12:05of the memory has describe by the general rules.
00:12:09We so yesterday is that.
00:12:20You should work also with the bound memory because this is
00:12:24the content of memory is bound have general number.
00:12:29This would be but it becomes here we
00:12:32do like this and then you have the program,
00:12:37which is execute by the machine to the machine execute the program.
00:12:45Which is a sort of assembly program very very
00:12:48basic instructions for types
00:12:52of instructions general program consistent
00:12:56with the list of instructions.
00:13:06That are numbers from the first you have
00:13:10the first instruction the second instruction and the last,
00:13:13but we typically numbers
00:13:16by as well to be consistent with this typically
00:13:19the last instruction will be
00:13:20the instruction and this taken from an instruction set.
00:13:28Which is very limited.
00:13:40You have the possibility of modified the register
00:13:44with the aritmetiche instructions.
00:13:51You can put zero in a register?
00:13:57Zero. Zero in register.
00:14:07You can by one.
00:14:17Of this is to register the content of their previous.
00:14:27And then you can transfer.
00:14:32This is a sort of assignment.
00:14:35Transfer the content of register to register
00:14:39and transfer my suggest to take at the content of
00:14:44this is not the case and remains the same and you copy to end
00:14:50to the result is the following in and you put.
00:15:06This are the instructions,
00:15:09but we have to modified the memory
00:15:12what you need clear some way of controlling,
00:15:17the flow of execution and
00:15:19for this we have a single instruction which is a conditional jump.
00:15:31Which is the following form you compero register
00:15:36register and if they are the
00:15:39same you jump to the instruction index,
00:15:42but this is the semantic you check
00:15:47is register and register and content the same.
00:15:55ANSWER can be yes and so
00:15:59you Continue execution with instruction it.
00:16:07Out and you continue with the next instructions.
00:16:20Onestà ed execution.
00:16:23These instructions execute the instructions
00:16:26move to the next execute sequential.
00:16:30I think we don't need to be borders about this this is.
00:16:36Reading. Description about and the computational seeds as.
00:16:45You have some initial configuration of the memory.
00:16:57Views from some content of the register.
00:17:08Given your program you start by execution the first instructions.
00:17:16This is not very surprise.
00:17:21Execute in aritmetica instruction move to the next on
00:17:25this jump possible jump are you to the next instructions
00:17:29and Execution Terminate possible that's not the case.
00:17:40For when you to execute and non existing instructions.
00:17:53This jump to our you and with an index,
00:17:58which is not an existing instructions.
00:18:04To this for two reasons
00:18:08either because you execute the last instruction of.
00:18:17The program. And this
00:18:22is not a jump or if it is a jump on the condition.
00:18:27The jumping condition is false Or because we
00:18:30are jumping and instructions,
00:18:32which is not in the program.
00:18:36Ok, description is really.
00:18:42The model itself is really easy,
00:18:44but less with an example.
00:18:49Or thoughts about some specific issues.
00:18:53Just talmente tanto che
00:18:57everything is super simple and it will be or.
00:19:04So you consider a program of four instructions.
00:19:14The first one is a jump.
00:19:17We don't care what the program is doing if it is doing anything,
00:19:20we just blind and just with execute
00:19:27IT Comparse register to entry and their equal jump to
00:19:32five five is existing instructions to this determine.
00:19:36The end of the program it register it register
00:19:42three and then it compared register
00:19:46on and register what if they are the same.
00:19:51Jump to instruction wait and you see
00:19:55that our language element only conditional jump,
00:20:01but if you want to jump and conditional you can mimic this fact
00:20:05by comparing two to the same and so if you register,
00:20:10we are the same clear will always all the same
00:20:13belief so this is a sort of.
00:20:17Instance of our job instruction where you make conditional jump.
00:20:30Ma ho due take primitive language and
00:20:35not C++ which is nice and you can write progress in
00:20:40much easy way because then you make a proof you should consider
00:20:45all the instructions of
00:20:46the soul less instructions
00:20:49you have the better it is and the more primitive.
00:20:51The language is for the better it is.
00:20:56Possible reputation of this will start from.
00:21:01The configuration of register in
00:21:05principle register are infinite many,
00:21:08but you see that as a mission before the program
00:21:12can use only a part of the memory by construction.
00:21:18You can this is using only the register one two and entri.
00:21:25So that's the only relevant part of memory,
00:21:28whatever it is in the rest of memory totally
00:21:30relevant because this we don't have in
00:21:35direct address so we can't refer to the cell number is
00:21:40the content of register and so on the part of memory,
00:21:44where is that is.
00:21:49The only important register are air
00:21:52one two and three and concentrate on the.
00:22:02Passion start from one two zero the rest this is relevant.
00:22:09Which simulate execution here compared
00:22:13content they are different so we don't jump move to it to.
00:22:18The register one So.
00:22:33Two. Step with three.
00:22:44Which becomes. The week the last instruction.
00:22:51But always jump back to instruction one.
00:22:59Week end to end they are still different.
00:23:04To one so we need to one and
00:23:10incremento register to execute at
00:23:13the same time to steps in a single.
00:23:24Register to find three in register three.
00:23:29We have to jump back again.
00:23:36Compare to know their the same jump to instruction five,
00:23:41which does not exist.
00:23:43This is the final States of
00:23:45computational the computational terminati.
00:23:49I understand that this is not
00:23:52the case it might happen computational continuous forever.
00:24:05This competition. But this is not always the case.
00:24:14And can you provide a program
00:24:17which Performance competition which is non terminati.
00:24:28Competition does not we save it diverge.
00:24:41For an experience of program which are not
00:24:44terminati are you have very simple one for
00:24:48the program consistent of
00:24:49a single instruction and just jumping back to the instruction.
00:24:57This is a program it is not to anything very interesting,
00:25:01but it is a program and
00:25:03you are the computational you continue for ever just jumping.
00:25:11Good. And then we In order to do it
00:25:19means for the function to be computabile we need to
00:25:22fix some notation function will be computer by the program.
00:25:25If starting from the input produce output
00:25:29somewhere in the canonical register for use will be register one,
00:25:33but for the PROpel this we need some notation.
00:25:41Against nothing really death,
00:25:45but we need to introduce it.
00:25:48Given a configuration of the memory,
00:25:51which will be a potential infinite sequence of register content.
00:25:57Even to the only infinite part
00:26:00of it will be interesting for has given
00:26:03a sequence infinite potential infinite sequence
00:26:05of natural numbers and the program.
00:26:15Why write P One way to do do not to indicate.
00:26:30The computational program P
00:26:33starting from an initial configuration register,
00:26:36which contains one e two.
00:26:45And in order to indicate that this competition eventuali terminate
00:26:54write it in this way and to say that instead it to write the arrow.
00:27:04This means the computational event terminate.
00:27:13And this is that means that it has never.
00:27:19Say. The infinite but we will always use just a part of it.
00:27:29IT will be useful to say these are the register that they
00:27:35of up to KEE and then we write not least,
00:27:41but only the least up to write
00:27:45it to do not configuration of
00:27:47register at the beginning of the computational,
00:27:50which is one in register,
00:27:53one again register KEE and the rest of the memory is terror.
00:28:01And then as a mentioned.
00:28:06We need to decide where to the result in principle
00:28:11of the register are fine, But since.
00:28:16IT is more natural to look at the beginning of the
00:28:20least we assume that the output if any will be
00:28:23put in register one and so we have notation for
00:28:27that we say that the computational one.
00:28:33Of one key terminate and producers
00:28:38as output if the competition terminate.
00:28:47And at the end the computational register one contains.
00:29:00Okay. If there is an it out, please ask,
00:29:04but it is that everything is quite simple.
00:29:13And finally with set up.
00:29:16We are the possibility of introduce in
00:29:19what you are compatible function
00:29:22is this is a good definition
00:29:27only we will soon understand that it is not very managed,
00:29:31but it is a good definition function.
00:29:40Of it. Takes KEE
00:29:50natural numbers and our functions will be young so they
00:29:54were only one output this functions.
00:29:59This time is mansion something for good
00:30:01are by default to be partial unless something different.
00:30:09And partial means possible partial.
00:30:17ITS function is called you are stable.
00:30:26If there is a program, which is computing the function so
00:30:29if there is you are an program.
00:30:39Such that. Is possible inputs.
00:30:51And for potential output.
00:30:58The program P starting from the input
00:31:03is to output e. e only if.
00:31:12The key elements key
00:31:16is in the domain of the functions of the functions defined.
00:31:20And the way of the function is.
00:31:29This is this definition would have expected so must
00:31:37compiute terminate and the output for
00:31:41every possible input and
00:31:44if the function is the find the program must.
00:31:51Have a symbol for the class.
00:31:55Of functions, which are compatible with rtk.
00:32:04Tiscali Graphics with super script KEE This is
00:32:10the state of functions. Of the KEE.
00:32:18Computer. E you are computabile,
00:32:24but it will forget about
00:32:26the qualification since it is the only notion of computer that we
00:32:31have by now and then if you want to consider
00:32:34all the possible compatible functions independent of the art.
00:32:40We have the union of the computer functions of RTK for all keys.
00:32:48Sometimes it will be convenient to consider also
00:32:52functions of the zero constant functions,
00:32:56which do not have any argument,
00:32:59but it will be
00:33:02very sheldon to use only functions of with at least one argument.
00:33:08And. So even if
00:33:18computer scientist this might be a bit
00:33:20offensive still make a couple of examples.
00:33:28The first one is showing that addition is compatible.
00:33:37Function of art.
00:33:42And the value of the function is the some of the two arguments.
00:33:49We have a way of this function.
00:33:52If you are stable exhibition
00:33:55the program program which starting from an initial configuration,
00:34:00which will contain in register register to.
00:34:07The two arguments.
00:34:12And zero other register this is our.
00:34:18Quel continuo and always terminate because
00:34:23addition is a total function
00:34:25over terminate and produce as an output.
00:34:30The same sex and. In register.
00:34:47And I care about the rest so I do not
00:34:50need to clean the rest of the memory.
00:34:56And how can I do this this is very elementary programming exercise,
00:35:02but anyway we do it and could be to.
00:35:09Keep it counter in register three.
00:35:15Which start from zero and keep the sei invarianti
00:35:20register one contain x plus k k way to
00:35:25register one contains exploit incremento incremento x
00:35:33times This is what we want to do.
00:35:40And even our languages or primitive that you have
00:35:44only absolute address for the instructions with
00:35:46us labels just to save a bit of energy and the beginning.
00:35:53What we do we check whether k
00:35:56whether register true to the same and so we are done,
00:36:03it is very useful to have tables because
00:36:06we should jump past the end of the program,
00:36:09but we have the program yet so we know where it
00:36:12is to be just right stop that will be an instructions,
00:36:15which is not their just at the end of the program.
00:36:20So here we are asking yourself is what.
00:36:26If the answer yes,
00:36:29we want to return around.
00:36:33Otherwise we continue.
00:36:41And we continue how incrementi a counter? And incrementi.
00:36:50Also because we want
00:36:55invariante and we have to jump back to the loop.
00:36:59This is an conditional.
00:37:05And we can per register one and register one they will be always
00:37:11the same and we have to place the top label here.
00:37:20Wow, addition is computer and.
00:37:27Others.
00:37:33Example. The predecessore
00:37:38we will be using predecessore
00:37:40even if this is also very simple function again.
00:37:45This is the total function.
00:37:50Which is essential ex minus one,
00:37:55but since we are over the world where to the side otto due.
00:38:00Zero and we do it to return zero.
00:38:09And this is super simple,
00:38:13but still writing a program is a bit ready,
00:38:19not a super immediate task.
00:38:24They might be the following.
00:38:28Questa from some memory at the beginning which contains our input.
00:38:36EXE Sia. E resti zero.
00:38:52And What we can do is what if if zero nothing to do.
00:39:03So we can per register one and register
00:39:07to end if they are the same.
00:39:13Ex zero, which is the result and we jump to the end of the program.
00:39:22Otherwise if is better than zero.
00:39:29Zero now if if if then zero can be we keep you.
00:39:39Do you and stop what if.
00:39:46Because I'm not consistent with can you stop.
00:39:54IT is a label yes, but it is more convenient to use.
00:39:59Stop cases ok and.
00:40:05So it is better than zero than we
00:40:08can keep it register to some counter,
00:40:12which is one in
00:40:15the original counter che started from
00:40:18zero is to ex than the result is che.
00:40:25So we will have to be registrato continuo.
00:40:32Incremento and then we start our loop.
00:40:39Which is check escape one x x x how.
00:40:48I am down But still I need to put the result.
00:40:56Which is country here che I need to post it is what.
00:41:03We are here to the end of the program.
00:41:07I need to transfer the content of register three to register one.
00:41:15Of instead.
00:41:19Che il still not to continue it rating incrementa.
00:41:30The counter. And also che to keep it
00:41:36variant one register KEE and the other key plus so to.
00:41:46Be continue we jump back. And finally.
00:41:56This is the labels stop jump when we are.
00:42:04Good also the predecessore is computer.
00:42:10That the program is already
00:42:14one two three four five six seven lines,
00:42:17long and we start understanding two things one that the model is
00:42:23reasonable because if the addition were not
00:42:26compatible that probably there would be something wrong.
00:42:30In our model and other what we start understanding is that yes,
00:42:36we have a way of the functions compatible,
00:42:40but writing the program.
00:42:44Doesn't look like the great ideas for
00:42:49the number of functions are computabile because of KEE for
00:42:53you can what you can IT
00:42:57is more difficult we could try moltiplicazione,
00:43:01but it would be even more difficult to nested loops and what we
00:43:07want to your mind is to the existence of the universal functions.
00:43:12What is the computabilità universal functions
00:43:15we want a universal machines,
00:43:17which is taking input and other machine and simulate execution
00:43:21of the machine into over the input data
00:43:27and this explicit by writing program looks like
00:43:31very difficult programming task really need to be a pro
00:43:37for that and even if you manage still
00:43:41life confidence still have to convince the person
00:43:46you're Talking to this is this program does the right things
00:43:50how to see that this is the way of the functions compatible,
00:43:55but it is not very convenient.
00:43:56We need something more upstart, but for the moment.
00:44:00This is what we are and so.
00:44:04We may be the last exercise.
00:44:09This to functions we are total.
00:44:15But you can eat
00:44:18non you can have
00:44:20non total functions partial functions with computer,
00:44:24sometimes often that is the conception that if
00:44:29function is undefined this means that it is not computer.
00:44:35This is false the link between
00:44:39non termination and non compatibility is much more
00:44:43than you can have Computer functions with partial.
00:44:48Probably simple example. You can imagine.
00:44:56Can you imagine super simple function,
00:44:58which is clear computer.
00:45:00We have in the program for it.
00:45:06Program.
00:45:11Number total this total
00:45:17doing nothing this total of.
00:45:22This is very simple, but this is total want to partial function.
00:45:26Which does not have the value sometimes but maybe always.
00:45:36Power.
00:45:40Powers Power Now this is total number of the.
00:45:47Division might be partial.
00:45:50Yes, we could partial division,
00:45:52but this time this is
00:45:55super simple super simple the function which is never defined.
00:46:04Always on the find functions.
00:46:17What sometimes we do not by the symbol like this is because
00:46:23this is this is
00:46:26this is the function from
00:46:27the natural number to the natural numbers.
00:46:32And it is always on demand.
00:46:36IT is value for now input.
00:46:41This is a function. IT is
00:46:45partial clear Vedi partial and his computer can you see,
00:46:50which is one program, which is computer.
00:46:54É per questo che.
00:46:59Io oggi continuo jumping since we don't do
00:47:03anything else we can just jump.
00:47:09To the program it to the instruction itself.
00:47:17So this is a perfect legal function and it is
00:47:22computer sometimes for reason
00:47:25people think this is it
00:47:28non computer or not functions can be computer.
00:47:32This is very very extreme.
00:47:35May be one of a more.
00:47:40Sensible function, which is the following.
00:47:48The function device number two it
00:47:52is nothing at nothing does not provided
00:47:57any result ex divided by to heaven. And undefined.
00:48:15This is computer. Yes. We can
00:48:21you do you understand better number is even or not.
00:48:28If you want to know starting from ex in register,
00:48:32whether it is even or not to just enumerate and even numbers.
00:48:38And if even it will coincide with one of
00:48:42these essential here at the beginning you have.
00:48:50But you will try to keep calm.
00:48:54And if you will become equal to to KEE for
00:48:59some che but we want to the divided to keep also.
00:49:05Ok. Qui c'è the beginning
00:49:15is also zero and this is it
00:49:18program may be is not what interesting not even the way.
00:49:24To you get whether is it to
00:49:29the if you will just need to take it one.
00:49:37Go to instruction moves the result to the right place.
00:49:43And there is in the.
00:49:50Other we incremento the counter.
00:49:58Che becomes cape and so we have to incrementa to buy to.
00:50:17This because this must of register free.
00:50:26IT will be one time because this is one.
00:50:38Understand your comments So what I want
00:50:42is that this is some counter che incrementa
00:50:46at the nation and this is the double of
00:50:49this and so what is this is to this way to.
00:50:55The only the number one is not.
00:50:59C'è sempre da tener presente che.
00:51:03Non ode to KEE the even numbers are the two KEE.
00:51:07Numbers.
00:51:09No, no not interesting in providing.
00:51:14Maybe you have in mind the different program,
00:51:17which gives you divided by the book in the case,
00:51:22which is even and also when it is not the end of this is that we.
00:51:30Are just over and Forever This is
00:51:35partial function it is on the road.
00:51:47To KEE point can be also fun to program such language,
00:51:57but that's not the point to point is to understand to the one.
00:52:02We have national computer function
00:52:04to we can really to very much with this.
00:52:07IT is it is sensible notion it is very simple.
00:52:12IT is precise, but image you want to show that integral.
00:52:22Integer part of the logaritmo in base is
00:52:27computer to take something like on line Orleans
00:52:31probably we can't really work this we need for the time being
00:52:37This is what we have and we play with this notion.
00:52:45Another point. But we can mention is
00:52:52the following do you think what if give this determined a function,
00:52:59which is computer by the program so is nothing
00:53:03like the function computer by program.
00:53:19Given program, p. Can I define
00:53:27the function call it FP Computer P. This is determined.
00:53:50Almost because might be program and if you
00:53:57give me an input computing and that we are not and if it.
00:54:04Terminate i know what the output is this is
00:54:07true what we are missing since we're focusing on functions of it.
00:54:13IT is the right because
00:54:16our language element functions
00:54:18doesn't program doesn't have a signature
00:54:20so we need to find the number of arguments that
00:54:24is this function so you have to fix also.
00:54:28the art of the function that we want to characters.
00:54:33And then this.
00:54:47Is over one each as value which is hey if the program
00:54:58starting from the initial configuration one each and
00:55:03produce as an output and it is
00:55:06undefined at the voice of the program,
00:55:09p. Over one each.
00:55:17And we are important because.
00:55:25Consider. The function the program.
00:55:43This program. And the function
00:55:53of the argument can you see this.
00:56:04Time is that they have to start with some input
00:56:09register one and all the other register are zero.
00:56:15And then my program,
00:56:18which transfer the constant register to register
00:56:21one and see the output will be zero.
00:56:31So this is the constant zero while in the function
00:56:37of the arguments based on the same program is different.
00:56:42IT is the projection of the second.
00:56:46Because start from the inputs.
00:56:58And input output gap.
00:57:04Questo è il link KEE per KEE.
00:57:11Point to point is that it is that.
00:57:19You will be convenient because to save the function computer.
00:57:23Now you can exist program.
00:57:27You can how to find?
00:57:31F from end to end his computer.
00:57:40Instead of saying if the program bla bla bla bla bla if. È program.
00:57:57That the function is this function completed
00:58:02by P with key arguments so it is just notation.
00:58:06There is nothing about that is just notation,
00:58:08which makes argument about computer of the function shorter,
00:58:13but it is not to say that is
00:58:16their something that No no it's the name that we have
00:58:21to this Function determined
00:58:24starting from the program way that it is easy to it.
00:58:31Ok, maybe the last question,
00:58:36we can ask our self is.
00:58:41As we are that we have a function and now the question might be.
00:58:50Sorry just write for the.
00:58:53Use will be reading this same definition as before.
00:59:03You just a reframing.
00:59:06Ok. The last question is.
00:59:12A give you know a function if.
00:59:21Black Passion. Programs are their computing.
00:59:41Exactly that you can eat some.
00:59:46Totally useless instructions or you can write
00:59:50programming likely different way by doing a bit of.
00:59:55A small modification doesn't
01:00:00change the concept or you could have program,
01:00:03which is based on a different,
01:00:04but still starting from one program just useless instructions.
01:00:10Maybe some code you can eat
01:00:11as much other programs
01:00:13as computing exactly the same function as you.
01:00:18Want you need one because of the function is not
01:00:23computer program so the answer is zero or infinite many.
01:00:34And this is to be the mind of the problem
01:00:40solving computing Computer function is one of the reasons why you
01:00:45should never copy and
01:00:48programming because this is
01:00:51likely that if you have exactly the same program is your league.
01:00:55This is considered a bit strange,
01:00:57but from that having infinity many programs
01:01:01for the same computer function will play
01:01:04a role in several locations to keep it in
01:01:06mind and want to get it from time to time.
01:01:11And ok before terminate
01:01:16At like to discuss if there are no questions.
01:01:23At like to discuss an exercise and leave you of other exercise.
01:01:34You can fit solutions for all about it really you can
01:01:40ask your LLM to solvit and you get it solution.
01:01:47What you can also adapt to the specific way.
01:01:49We are discuss in things.
01:01:52But I really suggest you to write
01:01:55exercise is it is really important.
01:01:59Maybe mention this is it is
01:02:01quite in effective quite in effective to
01:02:04do to read a lot of solutions exercise as it is super effective.
01:02:10If you do it just in time before the exam,
01:02:13but it is in effective anyway
01:02:15because understanding solutions something
01:02:18completely different from providing
01:02:21solutions solutions yourself from the point of view of what you get
01:02:25from the exercise so much much better to one exercise
01:02:31on the road solution of
01:02:35one hundred as is totally different from the point of view,
01:02:39what you learn and so you should be what
01:02:42about the voting five hours to solving size in
01:02:47place because this one of your understanding you and
01:02:53then you need to do one more and that it is what if you see.
01:03:01This is this is this and probably after the forgotten.
01:03:08Way this is a very simple exercise,
01:03:10but a want to do it what you Consider evaluation of
01:03:15the machine that it minus machine.
01:03:22Where you will remove.
01:03:27The transfer instruction.
01:03:40And so this is a sort of different model of computational.
01:03:45It's not so different, but it is different.
01:03:48And it induced a classes of computer functions.
01:03:58And the question is better this class out of this class
01:04:03compared to the place of you are compatible functions.
01:04:13Old. Different inclusion.
01:04:26Functions that you can can by.
01:04:31Without using the transfer
01:04:34you can can also if you have transfer available because
01:04:39you are not to use it to every program in
01:04:43this you are the machine is a program in the machine.
01:04:51But what you about the other inclusion?
01:05:01The transfer by.
01:05:07And you think we can or not.
01:05:12All confident probably also we can
01:05:18you can you see the transfer
01:05:22without using the transfer you want to simulate.
01:05:29Transfer register in register and what you
01:05:35can do you can put zero in and Incrementate.
01:05:41IT incrementa until you reach the same value as something like
01:05:48this you see you and then you start you can per.
01:06:06The current value of. If they are the same.
01:06:17Otherwise you? And you jump back.
01:06:31To you and you need time.
01:06:42So answer is the machines are equivalent,
01:06:48but since I want to the idea that we want to be super rigorose.
01:06:56If where you?
01:07:02Have to have. That.
01:07:09Program. Director of.
01:07:17The possibility of doing.
01:07:22No problem.
01:07:25Sì would be qui there would have to finish and some of.
01:07:31The year because you can't address register,
01:07:35which is not explicit mentioned in the program.
01:07:38You you don't have indirect dressing you what is that determined.
01:07:48With so this would be fine
01:07:52everybody would agree that they are equivalent.
01:07:55There is there are no thoughts
01:07:56on this is the first exercise at like to be
01:07:59pedanti super pedanti about this and
01:08:04I want to provide
01:08:05a completely precise and formal proof
01:08:09even of the first part of the fact that.
01:08:15Is included in this is what you should they are you will.
01:08:24I could do the following you take a function
01:08:27to this inclusion you take a function here you want to this year.
01:08:34Of the.
01:08:40Week. End I want to get it is it mean to be it means that.
01:08:54There is it you are minus program,
01:09:00p. Such
01:09:07that the function computer is.
01:09:18Now I want a program which is
01:09:21a program which computer dysfunction but every.
01:09:29You are minus program is
01:09:33especially you are program to you need to surf.
01:09:41What is also you are the program?
01:09:50And Conclude. Belong to see. You have to do this.
01:10:01This is. Really too
01:10:06much for something which is
01:10:08totally but still this is the complete argument.
01:10:14And for the other inclusion.
01:10:21Which is likely less
01:10:24is we do the same with the function on the left inside the show,
01:10:30but it is on the right inside set take.
01:10:35Off the.
01:10:40Inside. And then we citizens by definition.
01:10:52There is e you are the.
01:10:59Program p computer the function such that f and fp.
01:11:10Are the same function. And we want to
01:11:15show that then there is a program,
01:11:19which is not using the transfer instructions and which confused
01:11:23the same function and is that we
01:11:27want to the place the use of
01:11:28the transfer function with the subroutine.
01:11:30Here. We want to
01:11:37this is the very diligente way to say yes,
01:11:42we can be down that we are not training,
01:11:45but it is not but I want to you and more.
01:11:49And so. What we do?
01:11:57Da idea is to show?
01:12:03By induction.
01:12:08Since we want to replace a number of
01:12:11instruction with the one by one way.
01:12:14You replace something one by on your doing some sort of
01:12:17induction by induction on a number of this is the number.
01:12:26Of transfer instructions in.
01:12:33That they exist.
01:12:38Per prime which is a program without
01:12:41transfer instructions you are minus program.
01:12:50Such that the function computer,
01:12:53p. RT KEE and function computer
01:12:57by prime of rtk or the same and this.
01:13:04So what? If the number of transfer instructions zero.
01:13:17P instructions.
01:13:32For is ready you are the program.
01:13:46And so there is nothing to do. We can take.
01:13:53Primo.
01:14:02Step. So we
01:14:05are we can transform the program
01:14:08which as it transfer instructions into one,
01:14:12which is now actions and we want to the same by for each plus.
01:14:20So let p b you are an program.
01:14:28With plus one transfer.
01:14:44Senza it. IT has at least one.
01:14:49So we focus our attention one of this instructions,
01:14:54but will be some position that we can in
01:14:58TV suppose to have some transform.
01:15:03To this is our program P and we were
01:15:08some instructions and what we want to do is to
01:15:12transform it first by moving this specific transfer,
01:15:16then we will have the program transfer instructions
01:15:19and then applied induction hypothesis.
01:15:25So would be the following
01:15:28we keep everything and changed and then one possibility
01:15:33might be to replace
01:15:34the specific instructions with the subroutine before
01:15:38what if we do this then we have to update the absolute jump.
01:15:44We should update the target of the jump according
01:15:48to the displacement of instructions has been Sventato.
01:15:52By the way of the subroutine
01:15:55you think of insert in position the instead jump.
01:16:01To the subroutine. And subroutine jump back.
01:16:15And where to get. Out subroutine.
01:16:24There is not a concept like a subroutine in our primitive.
01:16:34Primitive language so we might think about it just at the end.
01:16:47Becomes. And instead of jumping to down,
01:16:55we have to jump to the instruction
01:16:56following the transfer.
01:17:06Yes.
01:17:09After instructions just.
01:17:13Instructions.
01:17:15So that the point,
01:17:17this is not correct.
01:17:19This is my next next question,
01:17:22but this is not correct.
01:17:24This is not correct because program is
01:17:27this instruction point possible and then there is nothing to do
01:17:34move forward should and and instead IT is that is not
01:17:39good to find the way out of this is not difficult.
01:17:47Just but here some jump
01:17:52and conditional jump to
01:17:53the end of the program, which is somewhere here.
01:17:59And then you can put the right numbers,
01:18:01but this is the end.
01:18:07And this is much better think.
01:18:14So we can this program the second here we yes.
01:18:22Di program by jumping.
01:18:28Yes, you are the good so yes this I want it to live at the end,
01:18:35but you are you see when you writing
01:18:37think thank you start correct thinking to
01:18:41the possible if you want to employment say
01:18:44a compiler we are some power compilation write from here.
01:18:49To you are minus machine and then some aspect which are totally
01:18:55conceptual total relevant you do something explicit and details.
01:19:00Start becoming relevant so this
01:19:02is this is not working PROpel because.
01:19:07This is not forbidden that here jump wait in order to finish jump
01:19:14somewhere out of the program
01:19:18and it might be very fortunate with jump inside the road.
01:19:24So what we can do.
01:19:27Is to assume that it doesn't happen.
01:19:33And we will always to this this is my space here and assume that.
01:19:47What is it will?
01:19:58By this is that it is.
01:20:12IT is in the instruction left.
01:20:24Behind the object yes,
01:20:26but not in this is general, but.
01:20:31Any program can be transform into a program,
01:20:36which is this very easily.
01:20:39So this is without loss of the reality.
01:20:49May be about this for the time being,
01:20:53but you can probably imaging.
01:20:55How you can show is now,
01:20:59If you think this is the problem describe
01:21:01your league does not appear any longer so this is working fine.
01:21:06And. By construction.
01:21:20FP the function computer by program is the
01:21:26same as the function computer by program the second and.
01:21:34Pista as only each transfers.
01:21:46Which means that we can apply active hypothesis to second.
01:22:02And so we can transform into.
01:22:07The program which is completely without transfer instructions.
01:22:22Such that FP is the same as fp second.
01:22:32Andavo in up together the equality and is the desert program.
01:22:42Sono salmi, happy together,
01:22:45the two equality you have the function computer by program,
01:22:48p. RT KEE is the same function computer by
01:22:52second of which is the same as the function computer by p.
01:23:14N p p prime sorry is the program.
01:23:21Designer that we can assume.
01:23:30That you can easily see that this is the case.
01:23:34Maybe you can do this.
01:23:39No il tuo taglio.
01:23:42To do it as an size that's it an observation.
01:23:47Given you are an program.
01:23:59There is always. È well.
01:24:13Program. Such that the function computer
01:24:23by p. RT KEE whatever
01:24:26it is the same as the function computer by prime without KEE.
01:24:35And his Super simple you just take
01:24:38p. And whatever jump instructions you find their.
01:24:57Witches jumping out of the program.
01:25:12So what as you replace it?
01:25:22The jump one.
01:25:37Okay. If the name is to finish that you finish by jumping to.
01:25:48And yes to exercise is.
01:25:54The one with you really to go
01:25:59to the first one is another variant of the machine.
01:26:10Where you replace the transfer instructions with the swap.
01:26:36Qui exchanges the content of register.
01:26:51Of the class of you are MS computer functions.
01:26:57And again you ask yourself is it the same
01:27:02as the class of you are compatible functions.
01:27:08As you know the answer, which is this.
01:27:14Is very similar to what we need for the previous exercise
01:27:18only similar there is
01:27:20a small detail what you should be careful about.
01:27:24And you? And the second exercise.
01:27:32Because one then convince that you change you get
01:27:37always a model which is during powerful.
01:27:42You consider? The machine you can can you are minus minus.
01:27:56Where you remove the jump?
01:28:07The king of the jump is really lost because you can't jump,
01:28:13but also the jump is
01:28:15the only conditional instructions you can't even check.
01:28:18Equality equality register so you are losing very
01:28:21much do you think that.
01:28:29Clear the class of.
01:28:34Your computer function is the subset that it is a strict subset.
01:28:49Yes. We can do your own reflections about that
01:28:56there is a clear immediately clear reason
01:28:58why you can't hold function without champs.
01:29:06Le cose program without jump
01:29:08is very boring start from the first instructions,
01:29:11the second hand and the for the last and determinata
01:29:14so it always terminate so
01:29:16there is no way of computing partial functions.
01:29:19What if the only lost where the losing partial function that
01:29:24would be a great loss for sequential setting program,
01:29:28which is not on some input is typically wrong.
01:29:34So understanding that inclusion is this easy,
01:29:38but in this is the question is more specific.
01:29:41I want you to give
01:29:43a full character of functions, which are compatible.
01:30:01If the shape of this function how they are what we do
01:30:07you can only do
01:30:08the double input you can do only the triple of the input,
01:30:12you can only at the constant the input
01:30:14that e full character of the class.
01:30:22Ok, and for me this is it is your questions to answer.