Transcript
00:00:00Good morning everybody.
00:00:03In the first lesson I have a general introduction to the course and
00:00:08some historical marks where you to
00:00:11understand relevance of the nation of an effective procedures,
00:00:15where it comes from where from this idea of
00:00:18having general mechanism of all the possible through.
00:00:24Starting from the state of basic principles,
00:00:28but the kind of an history,
00:00:31but today we start getting more to the point,
00:00:34but we will still stay at the general level and the name
00:00:40of today is to get a bit more into
00:00:42the details of what is an effective procedures,
00:00:45so what is an algorithm and essential.
00:00:49We will reduced this to
00:00:50the idea that something is an effective procedure.
00:00:53If it can be execute on some computational model.
00:00:57If there is a computational model which is able to execute
00:01:00it and this computational model must be some how
00:01:05reasonable and must have some finish features so it
00:01:10should be able to modify
00:01:12all in infinite memory in a single step for instance.
00:01:18So of today is more of what effective procedure is.
00:01:37To define a little bit better what is.
00:01:49This will to it first steal a
00:01:54bit general not very completely formal notion
00:01:59of a computer functions something,
00:02:01which can be computer by an effective procedures.
00:02:10And on the basis of this whatever
00:02:15the computational model is we will be able to the existence of
00:02:21home computer functions See that this is
00:02:24something really intrinseca can't get out of it
00:02:28something that just is not really dependent on
00:02:32the specific kind of computers that we are using by now,
00:02:37but it is something really intrinsechi in
00:02:40our capability of computing
00:02:42so existence of non computabile functions.
00:02:51This is the program for the essential.
00:03:02Start we start with the sort of definition
00:03:07of a sort of because
00:03:10it won't be formal definition for the formal definition.
00:03:12We need something more what we start giving the
00:03:15features of what effective procedure and algoritmi Yes.
00:03:21We start with the general.
00:03:27Formal definition of an effective procedure as
00:03:32a sequence of elementary steps possible with
00:03:37control construct which to repeat something
00:03:41given number of time or until given condition
00:03:44becomes true on the execute piece of the block of
00:03:48these instructions only if some condition
00:03:51is through but essential it is a sequence of elementary steps.
00:04:00Which is named at solving e problem which in our view is
00:04:06a computational problem which
00:04:09means essential transforming some input data.
00:04:15Into corrispondenti output data
00:04:19with some relation with the input data.
00:04:21So if you want to the factory input output is an factory.
00:04:30And you see that there is an notion some of the year
00:04:35of an elementary step
00:04:38is this will be a basic cooperation in the computational model.
00:04:41So it is the computational model
00:04:44and we will be able to make it precise
00:04:46only by fixing computational model and we will
00:04:48do this starting from the next lesson,
00:04:51but today we just used That this must be something,
00:04:58which is execute able without any clever without in
00:05:01an automatic way and also with the finite amount of resources.
00:05:07This is the general idea for now.
00:05:10This is for all the world said today
00:05:13that the is something like a black box.
00:05:24With receive some input does
00:05:28some computational sequence of elementary steps.
00:05:32This is not terminate,
00:05:36but it does terminate to have some output.
00:05:42And even if this is very very informal and that.
00:05:50Being you can really probably that if you if you this effect of
00:05:58this hybrid assume this deterministica deterministica
00:06:03mean that it any moment given the current state of computational.
00:06:08There is only a possible next step
00:06:12no choice so this is
00:06:16an option that we will be always
00:06:18making of everything is deterministiche.
00:06:23It's not but non deterministico options are
00:06:26not in interesting only they
00:06:28don't very much only complexity so from the point of view computer.
00:06:34They don't have the picture we will always
00:06:37use of computational models, which are deterministiche.
00:06:42You see that is for every input you have nothing or
00:06:47possible output and the science in duces e functions.
00:06:57E function which goes from the possible input.
00:07:06To the possible output.
00:07:12And dysfunction we will essential always take this implicite
00:07:19it is partial general
00:07:22you have the case that for some input you don't have any output.
00:07:32Good and given this even if again,
00:07:38this is very generic.
00:07:41We can try to give a sort of
00:07:44the definition of what computer function is it is pleonastico.
00:07:50IT is that the function is compatible.
00:08:07If their exist such that
00:08:11the function in the algorithm in the just mention is.
00:08:24An algorithm or an effective procedures.
00:08:27We will use the two things as is.
00:08:37This is very generic.
00:08:41A lot of things, which need to be fixed and we will do.
00:08:47Ehm.
00:08:48The end of transformation of
00:08:52this genetic definition to rigorose
00:08:54definition fixing computational model,
00:08:58but by now I just want to observer that there is something,
00:09:02which is relevant here,
00:09:03which is in order for a function to be compatible.
00:09:07What you need is the existence of
00:09:12and you don't need to know what if you don't need to know,
00:09:17which is it is computing as you just need to
00:09:21know that there is what the difference look to you.
00:09:26Want to know what you will see in the moment that
00:09:30actually this is relevant and it might
00:09:34gives false impression in several situations
00:09:37and and also something
00:09:40that we will get may be out of this discussion,
00:09:42which is the general in informal
00:09:45is that we are dealing with conceptual things,
00:09:47which are a bit deep so to be any complex mathematics year,
00:09:54but only some complex reasoning.
00:09:57This you will have.
00:10:00With very genetic definition of computational computer function
00:10:05We can steal try to discuss about the computer ability.
00:10:10Gli stili informali of
00:10:12some function that comes naturally to our mind
00:10:14in the city of basic of the greatest common divisore.
00:10:21Of the numbers. Is this compatible.
00:10:31What we can easily think of it
00:10:36for you want to take that the number take everything remains out.
00:10:43Of the largest divided by the smaller once you get zero.
00:10:50You have been clear effective.
00:10:55IT is really execute on the machine.
00:10:58IT is execution machine clear because we have machine,
00:11:03which are execution this kind of its.
00:11:19Developed computer theory, which the greatest comun
00:11:23divisore of the numbers is not
00:11:25compatible probably our theory is not.
00:11:30We move to something different a function,
00:11:33which tells you primalità function the function with which is
00:11:37the number is not this is computer.
00:11:45E decision function IT is one it is.
00:11:51IT. Is this computer.
00:12:01There is there is an algorithm I remember if the name white while.
00:12:07O that's ok, that's a good point to point because of your thinking,
00:12:12but in this course.
00:12:15We don't care about the efficiency,
00:12:16we just need to be able to see you
00:12:19have at least one algorithm it might be as
00:12:22much as you want and for
00:12:24the mining number is prime that's it principle very easy,
00:12:28then if you apply this with you
00:12:31in a second you it will take forever,
00:12:34but it principal you can do the following start from to the three,
00:12:39Thank you for up to end
00:12:41minus one e to divide your number by of this.
00:12:45If you are not your number esprime
00:12:49unless it is to it is very stupid,
00:12:53but it is not so this is compatible.
00:12:57We will never worry about resources time for as a function,
00:13:04which can be computers in some way
00:13:06may be taking a long long time is compatible.
00:13:12Something may be less is the following.
00:13:22The function which given gives you the end of.
00:13:27IT in the digit.
00:13:31In the decimal representation of pay.
00:13:36As just write digit in pipe.
00:13:42Is this computer? Can you think of an algorithm.
00:13:52Numerica algorithm have a serious which is to
00:13:56pay you can over estimate the error that you
00:14:01make by cheating the serious certain point and so if you
00:14:06go for you have which is up to digit and
00:14:11you take that the output it might take again a long time in this is
00:14:17it doesn't really take it is not in efficient there is for that,
00:14:23but it is computer.
00:14:26Ok. Something likely more complex I call it again
00:14:35f. And this is again and the season function and
00:14:41gives you one if we still concentrate on the number,
00:14:48if the number in the decimal representation of
00:14:52p. You can find exactly.
00:15:07And consecutive digit which are five.
00:15:22And other wise by this just
00:15:28to classici what I mean by dysfunction you write your your.
00:15:33Your number which is three one for more than there is five.
00:15:42Four and its point to point seven five five five five for.
00:15:52This is what I mean by a sequence of
00:15:56exactly four five digit in
00:15:59a row you have four five year exactly four.
00:16:04It's not the most four at least four it is exactly
00:16:09four because before after you have something which is
00:16:11different from the five.
00:16:20Four five.
00:16:29Okay am
00:16:32by the presence of this is that Over four is one.
00:16:40Is it clear what I mean.
00:16:43This is always on there are any.
00:16:49In the all the wall.
00:16:53Ehm, ehm this this is
00:16:58just a welcome to that welcome to that is the function clear.
00:17:06Of the function will output one all or will not because this is.
00:17:16Ok. Now coming to the computer your league.
00:17:21This function is not really or at least it is clear.
00:17:27Whether it is computer one of your have instead different opinion,
00:17:33but this is the Costant.
00:17:35Put in principle if I try to do it try say ok I give
00:17:42you for this able to get the top five of spirit so my idea.
00:17:50Ma might be the following.
00:17:55In order to compiute my function i compiute al digit of pipe.
00:18:12And then in the next step I check
00:18:16whether there are and digit to five in a row.
00:18:26Is this an algorithm.
00:18:33La first compute al digital by you can compute all of them,
00:18:42but well as you will never finish,
00:18:45you will go and go and go go go
00:18:47and see you can't say and then check whether they
00:18:51are exactly and digit five in the representation because
00:18:56this is after infinite Lehman steps
00:18:59and even if you managed to the infinite sequence,
00:19:02then you should search and infinite sequence,
00:19:04which doesn't look something,
00:19:06which is easy to.
00:19:08Pay.
00:19:13That point this cannot be considered.
00:19:17We will agree, but it cannot be
00:19:20considered in elementary step so what I am trying to
00:19:23intuition we are trying to know what is that we have
00:19:27a clear intuition of what should be considered and.
00:19:31what should don't be and we have the idea
00:19:34that at least you should be imagine
00:19:37that this should be
00:19:40implementabile some way in some real machine mechanical,
00:19:43otherwise what is it mean computer
00:19:46is an infinite computational when we should stop and to this.
00:19:51Ok. So this is not a good we agree.
00:20:15To un.
00:20:18Computer. And. Eccoli of
00:20:28this is always Actually nobody knows at least I don't
00:20:36and nobody else because it is through what you have which are.
00:20:45The number is not very it is an relational number,
00:20:50but this doesn't mean in principle that you
00:20:56have all the possible sequence is
00:20:58it this is something, which is not non.
00:21:03About that, but it is not know how to know what is what we
00:21:10know how the right answer to the question whether
00:21:13this functions compatible as we don't know how.
00:21:18We don't know. We don't
00:21:23know because if your league is right and Grande concerto
00:21:28is normal which means that you have all
00:21:32possible all possible sequence
00:21:36of digit it than the functions constant,
00:21:40but this is something nobody knows.
00:21:45To the best of my. Way to different is this is this fine.
00:21:58Currently the question is
00:22:01this function computabile is good news open.
00:22:06The function which looks similar that is
00:22:11only similar the function we can gi.
00:22:18And this is one.
00:22:23Way this is one if.
00:22:29P. In P. We can find?
00:22:36Again e sequence of five but the land must be at
00:22:42least and. Ma possibili more.
00:22:58Entities. This function looks similar,
00:23:08but only looks similar because it is much much
00:23:11much more simply because this
00:23:14is now in the same situation as before so if you have see.
00:23:22If you what you have This pattern
00:23:26the digital and decimal representation of pay.
00:23:32From this is that is not only that g of four is one.
00:23:44But also over three is
00:23:46one because you want at least tre digit four is five,
00:23:53but also g of the one and.
00:23:59One of zero.
00:24:08Ok, it is clear.
00:24:17Which means that are generally.
00:24:27When your function is one on some input.
00:24:32IT is one on all the smaller input.
00:24:43Which makes it a function way simple then the one
00:24:48before much much simple.
00:24:55And how I can you that this is computer.
00:25:00And in the following way.
00:25:03You can consider the set.
00:25:08Of index of numbers and that.
00:25:15There are an digit.
00:25:20Five in arrow and the passion of fire.
00:25:28Possible infinite we can take the supreme.
00:25:35To the maximum if it is finite or it will be infinite and.
00:25:50You have to possibility.
00:25:59Cake meaning.
00:26:16And you see of the function G is.
00:26:23Over sequence of life of KEE.
00:26:28Larger than this. No, no,
00:26:36it is total no function is total is always by definition.
00:26:40This function is one.
00:26:44In this case and zero other wise.
00:26:47IT is never. Undefined. What if is it?
00:27:04Clear sequence of life and for every and smaller qualche because we
00:27:13have KEE and so the function is one At KEE and other wise.
00:27:23IT is a steps function.
00:27:32So it is very simple function.
00:27:57Possibility that is infinite.
00:28:10In a case. What is g?
00:28:18Si pensi a it is always because we have sequence
00:28:23of at least and for every because upper limits infinite.
00:28:31The function is even simple is one for.
00:28:40The simple function.
00:28:56Whatever we might be in one situation or in the other actually.
00:29:02The first case is a set of cases because KEE can be any number.
00:29:07Whatever case. We are the function is
00:29:10extremely simple and it is compatible.
00:29:14If you are in the case,
00:29:15we have a clear it program,
00:29:17which is computing dysfunction these program,
00:29:19which check the input it is.
00:29:23IT outputs on the output write it in
00:29:29Python If you want it is the following function.
00:29:35G of it and more KEE return on.
00:29:49As return zero.
00:29:59This is the program computing in this is.
00:30:11In the other case that is even simple.
00:30:15IT function G. And completely regard to the argument and return.
00:30:31To the function g is computabile.
00:30:34You might object, but you don't know what you
00:30:38are so you don't know which is the program,
00:30:42which is computing write write.
00:30:45But this is not relevant.
00:30:51You have a program you don't know what it
00:30:53is one program for computing is there.
00:30:57Is strange you find strange that we can
00:31:01save the function table and we don't know,
00:31:04which is the program, which is computing the function.
00:31:08This is that may be bit counter intuitive
00:31:12what if you think a little bit more
00:31:14about it would be even stranger.
00:31:16If you have that dysfunction is
00:31:18not compatible because you don't know
00:31:20what the program is because maybe tomorrow.
00:31:24A very great motivation come out and see you
00:31:27clear start seven and then said
00:31:32the function becomes compatible function cannot be compatible or
00:31:35not the end of the function
00:31:38must be computabile demanding, but it is.
00:31:41IT cannot be what we have function today's computer and
00:31:46tomorrow somebody comes to say I have the great results
00:31:50and becomes not compatible the functions compatible or
00:31:55not the end of the function is not on how clever we are che.
00:32:04Assume that we are a bit confused this is
00:32:07fine I just want to point out that.
00:32:12With simple things in Essence because
00:32:16everything is very basic that we have to reason in a quei.
00:32:24Anni question out.
00:32:30And if you have the impression that this is a bit.
00:32:35And that you could play the same trick for you remember if.
00:32:43You make the object can can do the same for each.
00:32:50And so the same similar might be can do the same here e b.
00:32:58And. That that there are exactly and the five narrow in pie.
00:33:12And then I make mi program demanding
00:33:17dependent on this way and the program computing.
00:33:25By function is the following.
00:33:31Function of an and I check it is in one.
00:33:43Else.
00:33:46Zero.
00:34:05Is this program
00:34:07is this is it the same as before.
00:34:12What is what is?
00:34:24Not.
00:34:28Es. But it might be and infinite set.
00:34:34If it is infinite that
00:34:36this is not a program because how do you are presenta
00:34:39infinite set without any regolarità if the conceptual normal.
00:34:47Is write that it is the state of natural numbers,
00:34:53which is infinite, but it is easy to it is everything.
00:34:57This becomes true, but otherwise it.
00:35:02IT is an extremely complex infinite set.
00:35:04How can you need this is not
00:35:06a program in general We don't know how.
00:35:12E I might be. And we don't like infinite programs.
00:35:25Because in the previous we didn't considered the set.
00:35:30Which which is number.
00:35:36This we are not able we don't know what it is what we can find it.
00:35:42IT is it is a number.
00:35:45And that's make a great difference.
00:35:54Confused don't be worry, I just want to.
00:36:00This is not computer.
00:36:03No, no, no, no, No,
00:36:04no, No we don't know.
00:36:08What that is normal.
00:36:13Becomes constant on this computer,
00:36:16but it is not it becomes computer really want to stress.
00:36:19This the function is this function
00:36:22we know what it is exactly tomorrow.
00:36:27We might understand what is the constant one,
00:36:29but it is not with the function has become compatible.
00:36:32The function is over the same
00:36:33only we know know what it is computers.
00:36:36I know this is but I really want to stress this.
00:36:47Is this is not further questions would move on.
00:36:58And what I want to the second part,
00:37:02of course of the lesson we will.
00:37:05Occupy the rest of the lesson,
00:37:07which is essential trying to be more precise about what
00:37:12is the right from this set of
00:37:16features of an effective that you always have.
00:37:21Non compatible functions.
00:37:24IT is able to have functions,
00:37:26which you can't computer to
00:37:29the title might be existence of home computer functions.
00:37:36So what you have
00:37:38home computer functions doesn't need to have entire course,
00:37:43you just need for the minutes,
00:37:46Then the course is to understand functions or compatible,
00:37:51which are not and how the end of their properties.
00:37:56But the existence of home computer function is
00:38:00almost clear after you know what you know it
00:38:05because otherwise you think thank you so famous
00:38:12for the real deep things
00:38:15are before you don't understand after understand to say yes.
00:38:21Ok, so we have to know
00:38:26how about what is
00:38:28a good algorithm so the characteristic of a good night.
00:38:31We are the essential being execute able on a computational model.
00:38:39Good is your life when I say implicite a good.
00:38:49Night look and that it is not is the one,
00:38:54which before expand all the digital files of pie and.
00:39:00That's But I want to say want to read that I want to say
00:39:06that's not really a good one it that we should and.
00:39:22So good could be because it is implicite and. In being.
00:39:35And is that it. IT must be execute able and the machine,
00:39:40which is not necessarie a real machine,
00:39:42but it is something that it is it computational model it was
00:39:49some properties in sense
00:39:52that it never does something which requires infinite resources.
00:40:00ENSO in principle it could be employment.
00:40:07And this allows us to the number of basic features for instance.
00:40:13We say that it is a sequence of instructions.
00:40:18IT was the first requirement is that it is the final sequence.
00:40:24IT must be finite.
00:40:34KEE. WISE and the previous case of the case of computing.
00:40:44The power function related to the function could say in line.
00:40:50With the first let the first digit the second in the second digit
00:40:55in line with you have many lines available,
00:40:58you can computer digit,
00:41:00but clear this is meaning.
00:41:01This is nothing not really sampling,
00:41:04you want to do and you can see
00:41:07If you have if you are you for infinite programs at the theory
00:41:12of compatibility becomes both because you can compute
00:41:16everything because every function can be
00:41:20computer by and infinite if else
00:41:23if else if else if else if if else if if
00:41:27the argument is one to this it is to do this
00:41:30is this everything becomes trivial and useless.
00:41:36And you need is it to do before a computing agent.
00:41:44Computational model.
00:41:50Which execute the algorithm instructions in the.
00:42:05And this as a number of features. IT has a memory.
00:42:13For string input intermediate results
00:42:19and the output and this memory is bound.
00:42:24You think that this contract effect.
00:42:27I want to be able to you will have embodied memory,
00:42:32but the point is that I will never use
00:42:34infinite mani register or in infinite memory will always use it,
00:42:41but I want to be able to end it has much
00:42:44as a monte and again this is
00:42:47needed because otherwise not even the moltiplicazioni
00:42:50would be computer if limit in the size of the memory.
00:42:54Of the number of their large it is larger than
00:42:58the input numbers and so would be able to you
00:43:02don't want compatibility theory
00:43:03where moltiplicazione not compatible
00:43:06because this result large so you will never used infinite memory,
00:43:11but you want to be able to get much as you want.
00:43:16The mutation process by the script steps.
00:43:24To the state is the secret.
00:43:29IT is digital in science.
00:43:32You do you are not elaborate
00:43:34continuous functions continuous entities.
00:43:38If you are some knowledge of physics or
00:43:42electronic are you can have
00:43:44amplificare take away and produce in output larger wave.
00:43:49This is not something what you want to do here.
00:43:51We are not dealing with continuous entities only with
00:43:55entities as a to do before is deterministiche.
00:44:01The machine is deterministiche sorry which means
00:44:04that it any moment given the current state and
00:44:08the program you know what of the program to
00:44:10execute and in particular it is not probabilistiche.
00:44:19This is not because probabilistiche computational is not
00:44:23interesting only it is something different more advanced.
00:44:30Your machine or computational model is an instruction set,
00:44:36but we want to have a limit to
00:44:40the number of the instructions and also to their power.
00:45:01By night limit the power of the instructions I mean for
00:45:05instance in infinite memory in
00:45:07principle I don't want an instructions,
00:45:10which is one to all the register of
00:45:13the register the memory this would be effective.
00:45:19And finally the competition.
00:45:25Which execute your program.
00:45:28Step up after steps.
00:45:34È to possibility this it can terminate after a number of steps.
00:46:02And in this case you have in output only in this case.
00:46:09Ad Auschwitz it mi.
00:46:16So never terminate.
00:46:22And in this case you have no output.
00:46:28We don't want a competition which is
00:46:32a stream in output by continue continue in
00:46:35forever this is not what we
00:46:37discuss Ok I think it all of this characteristic are quite
00:46:43reasonable and we will see that by only lying on
00:46:48this we can show that
00:46:51clear there are always non compatible functions.
00:46:58If the competition continuous forever.
00:47:03Loop if you're thinking programming language you have
00:47:07no output nothing that you can consider as an output.
00:47:27We can discuss. This kind
00:47:35of actions we take this using only this.
00:47:40We want to show that you have
00:47:44non compatible functions and the reason is kind of simple.
00:47:48IT is a combinatoria reason essential what you are who is
00:47:52that you are to many functions and to
00:47:55you and for this you need a bit.
00:47:59I need to you about the math that we will use in
00:48:03the course. Which is very little.
00:48:12IT will take the minutes to explain all the use in the course.
00:48:24We will use natural numbers.
00:48:29And for natural numbers.
00:48:32Start from zero.
00:48:36And we will only with computational acting on
00:48:41this type not numbers will understand that this is not.
00:48:47Se sequence of input sequence output sequence
00:48:53of instructions we need paper stripes
00:48:56and so on so we need to define they
00:48:58are this is just notation, if you and.
00:49:06You can construct the set which is their product setup per.
00:49:19This is just to fix the notation,
00:49:22but ok to feel offender if you're ready
00:49:26very well as you and instead ask if you don't.
00:49:31And then we consider also sequence so
00:49:36the product of an bit a bit and times.
00:49:46So elements here.
00:49:48Air one way to an.
00:49:56Ok. Sequence that we will use relations.
00:50:11You know what relations are? You so.
00:50:17In algebra so relation
00:50:21is a subset form subset of the cartesiane product.
00:50:26After product because element
00:50:32is in corrispondenze with some element in b and the.
00:50:38Example is for the device relations Advisor.
00:50:47Of all you can think of this is something logical that you can
00:50:53also think of this extension is a relation to devices.
00:50:59You can think that it is the state of
00:51:02peace and and all the numbers,
00:51:06which are divided by and we are the multiple.
00:51:18So this is that it is a subset of times
00:51:22and it is a relation e binary relation of the natural numbers.
00:51:33At the good.
00:51:37Please stop if you don't know this is not for give me.
00:51:42If you is the functions.
00:51:48A special relations very special
00:51:52because this special relations and the science that
00:51:57any element in the source is in corrispondenze with
00:52:01most one element in the target at most because
00:52:04our functions will be almost invariabili partial.
00:52:09So it function from e to be is a relation from e to be.
00:52:26Such that it is in corrispondenze
00:52:30with an element that you can write
00:52:33like for all and for all be be prime in b,
00:52:40if is in wide and is in prime time B is the same as b prime.
00:52:53Will be often driving drawing pictures.
00:52:59Because this is the best way of understanding things
00:53:03drawing pictures so if this is this
00:53:06is what you are saying is that you don't want
00:53:10that a single element here responses to to things.
00:53:18This is. Good. Can't corrisponde to do things,
00:53:29but you can can it to one or to zero
00:53:32and so we have a notation for those elements,
00:53:35which corrisponde to one other element on the other side,
00:53:39we have the a image. This is the domain.
00:53:55Key and also.
00:54:01We is the standard notation for functions so instead of.
00:54:11Abi belong to write the usual thing f b.
00:54:26And we have notation also for saying that
00:54:29something is to find or not defined.
00:54:33IT is in the domain,
00:54:37we say that is
00:54:40defined if we don't want to
00:54:42specifiche the output we just say the files.
00:54:47And how is instead for elements,
00:54:51which are not in the domain.
00:54:58Okay. Now notation and we continue bit sorry a five minutes more.
00:55:12Because we need also to talk about
00:55:15the cardinal city of sets because you that the reason.
00:55:18Why they are non computer functions
00:55:20is that they are to many functions and to you
00:55:22so we need to talk about
00:55:24cardinali set which should be also familiar to you,
00:55:29but still I tell you what if you to remember.
00:55:35Cardinali. For this is something very simple.
00:55:43IT is a set than the quality of is the number of elements,
00:55:50but we want to compare also set,
00:55:53which are infinite and for this.
00:55:55IT is less is how to seed and we want to define infinite sets.
00:56:04At the same cardinalità.
00:56:12For finance it is they have the same number of elements,
00:56:16but infinite sets you can say the same is that for
00:56:20any element in hey you can have
00:56:25e one and only one element so you have by the way to be.
00:56:45N.B. have the same number of elements and b are
00:56:49not necessario fine you want a function which
00:56:53makes which established a
00:56:56corrispondenze one to one between elements and elements of b.
00:57:11IT is the usual notion same number of elements.
00:57:18But. The city of
00:57:27a smaller than the city of B.
00:57:30When you have an injection.
00:57:47Invece means that you have.
00:57:56And you can injection in to be you can view
00:58:01it by f. As a subset of b.
00:58:18This happens equivalent if you have
00:58:21the subject functions in the other direction.
00:58:24This equivalent is mathematical habit problematiche
00:58:28because you need some actions,
00:58:30which are not in the basic theory Sets
00:58:33of choice and like but here we are take the simple.
00:58:37We do not get it to those details and we say equivalent.
00:58:51You know what if and functions are.
00:59:02You can platter dell'hardware set into the smaller on this is B.
00:59:10This is this time,
00:59:13you need to cover entire.
00:59:16Hey will be.
00:59:19This is equivalent injection ones suggestions and other sense.
00:59:26Sorry just to nations more than.
00:59:33E set is count able times will also use
00:59:38the number and you should know this you know what it is.
00:59:48Sometimes they say it.
00:59:51IT is the same cardinals of the natural numbers,
00:59:54but notation which is
00:59:56the notation of the book the cardinalità smaller.
01:00:02Smaller. Which according to
01:00:09what is said before means that you have a suggestion.
01:00:22From the natural numbers to which
01:00:26some how explain also the name the numerabile IT me.
01:00:30IT means that if you like the function apply to zero to
01:00:36one to two and
01:00:40so what you get is
01:00:43a list of all elements of a so this is the new black,
01:00:46if you can list the elements of the asset one
01:00:49after the other you think that you can do this for every,
01:00:53but if you remember something from analysis.
01:00:57This is not through you can do it for the real.
01:01:10Times I will be informal about
01:01:13the ability and the city is the numerabile because of
01:01:17the elements so will take the possibility of listing
01:01:20the elements as a witness of the effect that it is the.
01:01:31That's not Forbidden. Okay. Enough to
01:01:42properties of the numerabili of count ability.
01:01:45If you have to accountable sets.
01:01:52Then also their product is.
01:02:05Okay, and the reason for this.
01:02:10Ok. We don't see in explicit proof,
01:02:12but you can just to get Typekit
01:02:14familiar with you can think of the intuition,
01:02:17which is very simple.
01:02:19If the which is which is so you can list
01:02:24the elements e zero e one e two b
01:02:30which you can list elements b zero b
01:02:34one two and then
01:02:38you can place the elements of the products in a sort of matrix.
01:02:47So here you least the element of the.
01:02:52Year you list elements.
01:02:58And the elements of the product can be but here.
01:03:02E00100E0
01:03:13b one e
01:03:14one b one way
01:03:17to be one.
01:03:28And there are dots in directions.
01:03:34And you can list enumerate elements of the products,
01:03:39which are in this large matrix starting here and the going
01:03:45here and then going here so
01:03:48along the diagonal the non maior diagonal.
01:03:54Ok, you can eat this formule by
01:03:57writing the function and using the index,
01:04:01but you can imagine what you can go through
01:04:03the matrix by going for the diagonal.
01:04:08Ok. Now just remember if the accountable products.
01:04:18And last property for Union of tables.
01:04:25Esino è one.
01:04:30If you have accountable sequence of accountable sets.
01:04:42Tender union.
01:04:50Which is asilo in unione tutto that is again count.
01:05:03Properties seen as where.
01:05:10Is now this kind of.
01:05:19God This is all you need to
01:05:24know all you need to know for this is this you need to know.
01:05:33And then in they remain in
01:05:37twenty minutes by only on this element and the algorithm.
01:05:44We can proof that you will always
01:05:48have non compatible functions now where to the last.
01:05:57Time which is existence.
01:06:04Of non computer functions.
01:06:17Just rolling on the In forma General definition of what we have
01:06:24before and we don't
01:06:28consider functions on several types this application,
01:06:33we restricted functions from
01:06:35the natural numbers to the natural numbers.
01:06:39And today we are functions argument.
01:06:50And this function for us less is different partial about
01:06:56every time functions can be
01:06:59undefined when partial function
01:07:03that it can be partial not necessarie it is KEE.
01:07:08So we want to focus on the set of.
01:07:15Functions. From the numbers to the numbers.
01:07:26This is the set of functions partial functions.
01:07:35This is one object of interest for us.
01:07:40And now we move to compatible functions so for this.
01:07:45We have to fix some model of computational.
01:07:50E computing agent.
01:08:00This will have corrispondenze set of algorithm.
01:08:10Per. Fix a model of
01:08:17computational the machine algorithm is the set of Python program.
01:08:24If you fix Java if the Java program here we
01:08:29are focus for functions from natural function of type.
01:08:36And then given and in their.
01:08:49Use Tiscali graphics for the use of
01:08:53us and then the capital standard as a single algorithm.
01:09:01I think difference is visible,
01:09:03but it is not one time to time.
01:09:08The cost context should not
01:09:11so for each as we said the beginning we have the
01:09:14corrispondente function the function computer
01:09:16by the given input it is
01:09:18possible and output or the function is undefined.
01:09:29So one week fix module mutation.
01:09:35We have a class of compatible functions.
01:09:40The functions compatible in the model.
01:09:55Are. Not by as
01:10:03is the set of functions.
01:10:10Of functions that There exist and the function.
01:10:29The function computer is exactly.
01:10:34What you can Wright in a simple way as.
01:10:39IT is the class of functions computer by the times.
01:10:47Ok. No clear the functions computer
01:10:54are a subset of all the functions.
01:11:08By definition. And our doubt is whether this.
01:11:16Is actually inequality or if the inclusion is street.
01:11:23If they are some functions,
01:11:25which are in here and not here some functions,
01:11:30which are not compatible and the answers will be yes there are.
01:11:36And the reason will be extremely
01:11:40simple some how it is because they are to
01:11:43many functions and to you about
01:11:47this we say more precise what is in our computational model.
01:11:54IT will be a sequence of instructions.
01:12:02From an instruction set which is the action set language.
01:12:20We. Will said that we
01:12:24want the final instruction set and also the sequence is.
01:12:39The state of which consiste of the art
01:12:44of lamp one so single instruction.
01:12:50Union of two two instructions one after the other three.
01:12:59Triple first second fourth and so for any possible lamp
01:13:06so for the great I want you take program of last.
01:13:20But now actually would work also if I were
01:13:25accountable infinite you have accountable union of counting sets.
01:13:32So this is accountable the algorithm accountable.
01:13:59So we have that.
01:14:05You are not larger than
01:14:08the state
01:14:08of
01:14:17Falso good,
01:14:19but not your heart that the function which
01:14:23map every algorithm to the corrispondente computer function.
01:14:29Is soggettive.
01:14:32You take the function from the algorithm to the state of functions,
01:14:39which are computer based in the computational model, which maps.
01:14:48To the function. This is subjects by definition.
01:15:00Because something to be computer must be
01:15:03computer by algorithm so if I take the function,
01:15:07which map it is it to
01:15:08the computer function subject functions
01:15:12into the computer functions,
01:15:16but you remember that since this is.
01:15:26The city of the function computer it.
01:15:31Computational model is smaller cardinalità of this is this.
01:15:46And also you remember this.
01:15:50Is the cardinalità of.
01:15:54So you that.
01:16:00The computer functions are accountable.
01:16:10Okay. Up to know.
01:16:22How you just need that all the functions are
01:16:26more than accountable their accountable
01:16:29their larger and this will
01:16:32immediately play that you have functions, which are not compatible.
01:16:44So the next observation is that the set of all functions.
01:16:57Is not compatible. And this
01:17:05is something also probably know or ready from analysis,
01:17:09but anyway we will it.
01:17:19Will be tradition.
01:17:22As it is accountable.
01:17:36Taking the informal view.
01:17:40This means that we can least one after the other of the functions.
01:18:01So you can stand by saying this is the first function.
01:18:05This is the second function.
01:18:07This is the first and you will get all the possible functions.
01:18:13This looks something without any consequences,
01:18:17but it is not because if here we put possible argument zero one
01:18:23two that you can see any function as the sequence of its values.
01:18:31If zero zero zero this could be undefined zero due.
01:18:39Uno zero.
01:18:42One of one of two.
01:18:46To.
01:18:59Know a No problems,
01:19:02but you can take the diagonal here.
01:19:09And you can see the diagonal as a function,
01:19:13which is this value on this value on this value on to this is still
01:19:23a bit how innocui but what you can do now is to
01:19:28change systematic every point dysfunction the diagonal function.
01:19:41Function by changing systematic Diagonal.
01:19:54By design. Defined D over by seeing look.
01:20:04For instance any zero zero zero
01:20:08defined then I make the undefined is it.
01:20:12Undefined then I make the art of it to this kind of time to take.
01:20:21Over and check is it.
01:20:24Undefined If so I make my function defined so
01:20:28different as it defined.
01:20:34Bene, I make my function
01:20:37undefined so it is systematic different from the day you.
01:20:44Know you see that this is a problem because
01:20:48this defined function which is by
01:20:51construction different from the functions which listed,
01:20:54but it is a function so d should appear In this least.
01:21:02Since this is a function it must be in the list.
01:21:13So must find.
01:21:21Some index that d is
01:21:26f. This is the list of functions so must be their this.
01:21:38But it is different from all of them that it must be one of
01:21:42one of them so we have tradition, but let's explicit.
01:21:47We have the possibility about. The end of.
01:21:56Either haven is defined.
01:22:03Or it is undefined.
01:22:09But in the first case since when it is defined. By definition.
01:22:21Must be undefined.
01:22:32IT is different from.
01:22:38This is because this must be equal to have.
01:22:50The other case is kind of because now
01:22:54is Undefined So we are in this case so d must be.
01:23:06So it is again different from FM over.
01:23:13But we choose an to be the index of the so this is again.
01:23:19Contraddizioni. This is contraddizioni
01:23:23in the state of Russell. If you want.
01:23:30This camp from the option that the elements
01:23:35of functions were accountable.
01:23:46So it must be that it is not accountable.
01:23:57Penso. Ai cardinali This
01:24:02is larger than the cardinale of natural number is not smaller.
01:24:10But the end because.
01:24:17Summer.
01:24:28Of computer functions
01:24:31is clear a subset of the functions.
01:24:38But the set of computer functions is constable.
01:24:46This is that we need before here it is.
01:24:54Wild functions is not.
01:25:02So the computer functions are the subset
01:25:07of smaller cardinalità so they can't be the same set.
01:25:16And that is the subject of which is
01:25:25what we want to
01:25:29be just that we take reasonable computational model.
01:25:33We immediately that is that there are functions,
01:25:37which are not compatible.
01:25:41Time. Does not on the facts or not so clever.
01:25:48IT is not on the facts that our computer based on
01:25:52this is what with quantum
01:25:55computational with
01:25:57biological computational bonding artificial intelligence
01:26:01always be functions,
01:26:03which are not computer
01:26:06and they are very many because the last question.
01:26:10Yes, we are, but not how are the non computer functions.
01:26:26So what is the city of the set of the functions,
01:26:31which are not compatible.
01:26:34All the functions, but the computer ones. Che io stesso.
01:26:46Sono.
01:26:51Harvey Accountable.
01:26:54No, no dei can't
01:26:56they can't be able because if they were accountable.
01:26:59The union of the computer e non computer.
01:27:02Which is the functions will be computer so this must
01:27:06be larger than and so not only the non computer functions,
01:27:11but they are some of the majority for what means in
01:27:14an infinite set if you take by random functions.
01:27:18IT will be the probability probability almost one non computer.
01:27:24So this is the point.
01:27:30Kind of bad news,
01:27:32but this is where are journey starts that we want to study.
01:27:37Computer non computer functions
01:27:39knowing that they will be there for ever.
01:27:41This is not something of
01:27:43these days of the night century on the time.
01:27:46This is this will be there for ever.