Transcript
00:03:44Anyway, Good morning again, it again me,
00:03:49but the new year is professor,
00:03:51of course on computer Ability.
00:03:54To you today we start
00:03:58illustrated a bit what
00:04:01you will find in the ability course this will
00:04:04be essential a sequence of
00:04:06historical marks trying to give you an idea of what we will be
00:04:11talking about also of the approach that we will be
00:04:15taking also altri to motivate
00:04:19the presence of a computer course in a curriculum of
00:04:22computer science and this will be based essential on.
00:04:30The story which is my personal view of the story of
00:04:35computer science and that's that's interesting.
00:04:39This is a bit unusual lessons so don't be worry if something.
00:04:46Something or not completely understand about this is what you want.
00:04:52And so i start with kind of
00:04:56gioco suppose we are here to thousand and fifty,
00:05:01which is that which is in the future
00:05:05so that we can imaging between radical different from now,
00:05:09but still there is a mathematical department.
00:05:14Which is running a computer science degree and in the department.
00:05:19There is professor math matematico
00:05:22and is having hard time in keeping
00:05:25track of the number of its friends is that it is because.
00:05:36There has been quite impressive technological advancement of
00:05:43space exploration and become much more efficient in the day by day,
00:05:49which is that fan companies a lot of users
00:05:53on numbers getting longer and longer and so
00:05:56day require a lot of space to be stored clear memory is
00:06:01not the problem that time is not for the side of a number,
00:06:06but still is motion and I want to store things
00:06:10efficient and so it and think about,
00:06:17but it that is living in the same department
00:06:21as computer scientists computer scientist
00:06:25are very much concerned with efficiency.
00:06:27I talk with the friends of professor is
00:06:30a computer scientist and ask for some health and things about and
00:06:35says well is an idea for you instead of Turing directly
00:06:41the number in could store.
00:06:47È simbolica Representation by this mean a program,
00:06:52which can generate the number
00:06:56needed just to give idea is the number one,
00:07:01which is a bit peculiare.
00:07:03IT is just a sequence of the digit from zero the New York Times,
00:07:08then rather than the number you should but the program,
00:07:12which is this which once execute produced the number.
00:07:18Of KEE we have to the size of
00:07:21the number of the program is what if you
00:07:25take it view of just measuring the number of the program is.
00:07:33This kind of entusiastico this is a great idea,
00:07:39then start asking himself,
00:07:43but is this really always convenient so Is what I can always find
00:07:48a number given a number of
00:07:51mind e simbolica representation a program,
00:07:55which is able to generate
00:07:57the number and which is more than the number.
00:08:01And the answer is now.
00:08:08You have numbers for there are for your numbers for which
00:08:13it is impossible to find the program smaller than the number,
00:08:17which is in the number and actually
00:08:19this is not something that we are invention for this,
00:08:23but this are object,
00:08:26which are started in the literature.
00:08:28This random numbers they are
00:08:30related something that we want the touch in the course,
00:08:33which is algoritmiche information theory of the but the year.
00:08:39This is not important for us behind is but Intuition
00:08:44of what a random number is what you can easily find the program,
00:08:50which is in the number and which is that the number.
00:08:54I think is it easy to because
00:08:57if you get back to our previous example where is it?
00:09:02The reason why it is easy to find the program.
00:09:06This number which is better than
00:09:09the number is that the number is extremely regular.
00:09:13IT is the same pattern over and over which is
00:09:17what you can capture in
00:09:19the programmatic way the content of the number,
00:09:21but if you have the sequence of digit,
00:09:25which are completely random
00:09:28without any regular that you can imagine.
00:09:31This is not proof, but you can imagine probably
00:09:35the best the only way of printing out number would be just to
00:09:38print it single digit one by one in
00:09:41sequence And this program would be larger than
00:09:44the number so there are numbers for
00:09:49you can't have a compresse e compresse representation,
00:09:54but still one think that they are just exception,
00:10:00but not chance and so it think about it is that now,
00:10:06this is not something extremely
00:10:08rare you have infinite many random numbers.
00:10:16Maybe you can also even intuition of
00:10:21this happens because we have experience with something,
00:10:25which is kind of similar because this program can be
00:10:28seen a compression of the number version of
00:10:31the number and if you experienced compression programs
00:10:35like it to your kind of compression program.
00:10:39What you like you probably notes that from time to
00:10:43time the file is actually larger than the original file.
00:10:50This this is very frequently starting file small,
00:10:57but if you think about this,
00:11:00but it is not actually it is completely impossible.
00:11:05If you think about to have a compression program,
00:11:08which reduce the size the file the size of every file.
00:11:14Why because if.
00:11:18Then it would establish a function which goes from
00:11:22large large files to get the small files and function can exist.
00:11:31This is not programmatic,
00:11:32but this function is not the function it must be
00:11:37infected Because you don't want to different files are
00:11:40map to the same version because you want to be able to rollback.
00:11:44The compression you want to be able to keep and then if you
00:11:48want an injection function from large to this doesn't exist.
00:11:54And so this is the same for the same argument.
00:11:58If you want to you that they are
00:11:59infinite many random numbers numbers for which
00:12:03al program which are writing
00:12:05the numbers are larger than the number you
00:12:06can you more less with the same way in the same way,
00:12:10but anyway there are infinite many random numbers,
00:12:14but ok math is still
00:12:16a positive person say there are a lot of random numbers,
00:12:21but still if number is random.
00:12:24I can just do it as it is if number is not random.
00:12:27I can use the version by program.
00:12:31Ask to this friend with a computer scientist,
00:12:36Please write for me a program which
00:12:38check whether a given number is random or not.
00:12:44And things about this account to this I'm sorry account to
00:12:51this and and the reason is not
00:12:54that is your is not time is too much is to be,
00:12:58but the reason is that there is not
00:13:03such a program or to put it in
00:13:05computer terms the problem of establish,
00:13:10whether a number is random is the side is not
00:13:15compatible and so this
00:13:20is maybe the time for the first exercise in the course.
00:13:24What I do not you to be able to solve right now and
00:13:31access to prove that they are
00:13:33infinite many random numbers and that there is no program,
00:13:38which is able to determine.
00:13:39Whether number is random or not full fully general solution to
00:13:44the exercise requires all
00:13:48that we will see in the course, but instead.
00:13:51If you are happy with the specific solution based on
00:13:55some specific representation of numbers or
00:13:58instance the usual positions representation, which is the size,
00:14:01which is logaritmico in the value of
00:14:03the number and if you take that the size of a program just you
00:14:08takes specific language and the size of
00:14:10the charts that you can do
00:14:15this exercise in a easy way for the first point.
00:14:19The argument similar to before the existence of
00:14:24universal compression programs and
00:14:29for the second point in a similar way.
00:14:33of the existence of a program you can easily
00:14:38generate tradition faithful general result,
00:14:44this independent of
00:14:45the language independent representation required theory of
00:14:49the course did it all you want
00:14:53to inform you want something that you probably already know,
00:14:57which is the fact not everything is
00:15:00solvibile with the night with the computer.
00:15:04There are limits to the power to
00:15:07the computing power of our computing devices.
00:15:10This is not something new for you may be
00:15:14the specific problem is a bit peculiare not the common one because
00:15:20normally one to the thing problem and
00:15:25there are some like at
00:15:27the same not non problem there are something with compiute,
00:15:33but one night think that are problems,
00:15:36which are relevant like it cannot decide whether there are
00:15:41infinite many seven digit in the digital expansion of
00:15:47your stuff like or not decide
00:15:50better number is random or not who cares,
00:15:52but actually this is not the case,
00:15:54when we will be discussion Typekit of the course the problem.
00:15:59The problem which are not possible are
00:16:01typically extremely interesting problems
00:16:04already the problem it in an abstract sense you say
00:16:09ok cannot decide given a program
00:16:11and possible input for this program.
00:16:13Whether the execution terminate one could sei Ok. Who
00:16:17cares but instead if you experience the spirit of your mind.
00:16:23If you are the spinning will experience using
00:16:28your favorite program your favorite applications,
00:16:31then you can easily understand that actually that spinning fuck
00:16:38the system becomes non response is almost
00:16:41always determined by the fact that there is some program,
00:16:45which is not on
00:16:47some expected inputs being able
00:16:50to the problem would be interesting and this is
00:16:54not convincente to you and order
00:16:57super interesting problem would be established in mathematical with
00:17:03the white with the computer
00:17:05with the correctness of program so the problem it is
00:17:11a program and I give you a specification for this program
00:17:15like I give some text program and you this must go on the.
00:17:21The factory, please check whether this is true.
00:17:26Also this problem is not able is not
00:17:30the side not even when the specification is super simple.
00:17:33You cannot decide better program is computing,
00:17:36the constant one, this is impossible.
00:17:38There is no algoritmi way of solving.
00:17:40This is this would be extremely interesting,
00:17:44especially in this time is because now.
00:17:46We have the large language model revolution.
00:17:52You can generate program,
00:17:54but very commonly they can contain to.
00:18:02Be able to check automatic weather the program
00:18:05is correct or not to be super interesting.
00:18:09IT would be also bet for us because if you could
00:18:11really solve in algoritmi way this problem
00:18:15than I would be able to
00:18:16generate software to specification you would be
00:18:20able to check automatic software
00:18:22would be no longer bugs is computer.
00:18:25Scientists We would be an employer,
00:18:28but this is not a case.
00:18:30This is not a case and so we have a lot of
00:18:33work writing programs finding bugs stuff that.
00:18:40So. This is our starting point.
00:18:47There are problems which are not soluble by computer and you
00:18:53know already is not so it is not probably very surprise,
00:19:00but what is still find extremely surprise
00:19:04and at least this is my feeling is that this is
00:19:09what we cannot computer everything just because we
00:19:13are stupid and we did it managed to computer,
00:19:18which is a powerful,
00:19:19but this is not the case something try to say During the course is
00:19:24that this imitation completely intrinseco and
00:19:27total independent from the specific model of computational,
00:19:31but we are using.
00:19:34The results can be a way,
00:19:37which is totally independent or
00:19:39almost total independent from the model of computational,
00:19:42which means that they are written in the Stones.
00:19:46How they will be their until the end of the universe.
00:19:49IT is impossible that at some point somebody will come and
00:19:52we have the new model of computational,
00:19:56which is over coming or the problem
00:19:59all digital computers and everything is will never happen.
00:20:03This imitation will be there until the end of
00:20:06the universe is really something extremely deep
00:20:10and foundation total immutabile
00:20:14in everything is changing instead very mostly so what we know that.
00:20:23They are things which cannot be computer.
00:20:27We can easily state the name of the course,
00:20:30which is investigate the power limitazioni
00:20:35of algoritmiche computational of computers.
00:20:40What we can say to
00:20:44some of the name of the course is that we want to answer.
00:20:47This question which problems can be sold,
00:20:51which other problems cannot be sold by an effective procedures by
00:20:55computer and that you before this kind of study is not.
00:21:02Constraint related to the specific digital model of
00:21:07computational using this is some
00:21:10of this are completely general completely.
00:21:14Independent almost completely independent of the specific model of
00:21:20computational using they will be their with quantum computer.
00:21:25They will be their with biocomputer when it will
00:21:28be any kind of computer along as they are.
00:21:35Alien as completely different physics could change.
00:21:44So in order to program investigate the power and the imitation
00:21:51of computational we will seed by
00:21:54steps in order to identifying problems,
00:22:00which can can be sold by an algorithm.
00:22:03We need to define with
00:22:05an algorithm and effective procedure is an object that you know
00:22:09this which is kind of true because your
00:22:13dealing with the long time, But.
00:22:20We need to your results.
00:22:23Medical results so we need a formal definition of.
00:22:29This will be given just by following
00:22:31the classical world of Touring as something,
00:22:36which can be execution over some kind of
00:22:40idealiste abstract machines and once we have to find the computer
00:22:44is what is an effective as we
00:22:48can defined clear what it means for a problem to
00:22:52be soul effective procedures and finally we can classified problems
00:22:57according to the capability
00:22:59of an effective procedure to them or not.
00:23:04And we will see.
00:23:06Maybe not very deeply that actually.
00:23:08This is not a dicotomia is not split into
00:23:11what is what is not but among the problem,
00:23:14which are not so You can establish a years of difficult and
00:23:20this impact on the possibility of
00:23:23the mining proximity solutions not seem very much about this,
00:23:28but talk about this.
00:23:33Is a salvare il salvabile.
00:23:36Without resources it's not
00:23:40because resources are not important in general,
00:23:42but they want be very important in this course so here problem,
00:23:47which can be sold effective.
00:23:50By using a amount of resources will be considered simple problem.
00:23:56Independent of how much time and
00:23:58how much memory requires as it is not
00:24:02because resources are not important only they are
00:24:05not the target of computer theory.
00:24:09If you are interested in
00:24:10resources you have to know how to complexity theory,
00:24:13where is Attention to to problems
00:24:18with the world problems left side problems,
00:24:24which can be sold by an algorithm which always
00:24:26terminate and in that you classified
00:24:30problems in a difficult week end on the most of
00:24:34resources that they use and you
00:24:36have this is not important for this course,
00:24:38but the already heard about this
00:24:42that the problem is typically considered.
00:24:47Stable E
00:24:50with the polinomio amount of resources and non track table.
00:24:54If in order to be sold it requires at least an amount of
00:25:00resources on the split between the two is very nit,
00:25:05but this is not a case or at least we don't
00:25:08know that the use of problems,
00:25:12We are very important problems called NP complete problems for
00:25:16which we don't know their own one side table or on the other side
00:25:22or not track table and this is
00:25:24probably the most important open problem
00:25:27of political computer science by science of years.
00:25:33IT is open so if you want to become famous try
00:25:38to attack is the problem and you will also one million dollar,
00:25:42that's a minor point actually
00:25:44so solving these problems would become
00:25:48the year of computer science of
00:25:52science for you will be remember forever,
00:25:56but we want to this we concentrate
00:26:00we about resources and we talk about computer.
00:26:04We distinguished about between problems,
00:26:07which are solvibile and that we
00:26:09are not solvibile Independent Resources.
00:26:13And. Computer. If you
00:26:19love it from outside might appear as something,
00:26:23which is a bit exoterico and
00:26:27so what when it happen that computer science started working
00:26:32about this imitation this computer issues when the story goes like
00:26:38that people started building automatic machines computer machines,
00:26:44they became more and more sofisticate
00:26:48finally at some point at general purpose programmabile computer was
00:26:53built and people started thinking while
00:26:57this machine can be really do
00:26:59everything that are their imitation to this machine.
00:27:03This might be the story.
00:27:04This is typical for
00:27:06science first object that you
00:27:08start wondering about the power of these objects,
00:27:11but this is not the case also this may be or
00:27:13not actually it when the other way round
00:27:18first people started thinking to
00:27:21the machine were never released and the time machine,
00:27:28which nobody ever built at nations,
00:27:31but it was imitation,
00:27:34but it is an interesting machine so we can try it.
00:27:41So computer science is strange science,
00:27:44which discover its imitation
00:27:48before its birth and its actually from.
00:27:54The discovery of this is that
00:27:57people started thinking that it was interesting
00:28:00so there is been a dream plan a long term project,
00:28:06which last but not for fifty years one years for example
00:28:11of millennial and finally people
00:28:14that this project is not realizzabile,
00:28:17but for the epic fail of this project.
00:28:20The lady of the computer came
00:28:23out so for a great failure science like computer science,
00:28:29which is now revolution in the world start.
00:28:32This is an interesting story and to
00:28:38give you some ideas about this story in the next few minutes.
00:28:44I think it is the story,
00:28:47but before start talking about the history of computer science,
00:28:51which will be anticipate it is
00:28:54a personal history of the only one things in this way,
00:28:58but it has some personal aspects
00:29:01have to classified computer science is.
00:29:05È un computer science that
00:29:08is it comes from the name it is the science of computers,
00:29:14which is study in computers,
00:29:16but not case at least I don't believe that the case
00:29:20and not alone so I can't bring with me more autoritative,
00:29:24which is the voice of you probably about
00:29:28it is one of the founding fathers of modern computer science got
00:29:32the world of Nobel prize for computer science
00:29:36in for fundamental contributions in different areas of
00:29:41computer science algorithm for instance in algoritmi
00:29:46theory can currency theory was last of semafori and monitors.
00:29:53Language theory theory of programming languages
00:29:57famous paper B is a case
00:30:00e case against the go to statement Invece was
00:30:03at the use of God does not
00:30:07structured programming because it mite looks strange to you,
00:30:12but there has been a time in which people were
00:30:14debate about whether it was possible to
00:30:20have the way of programming without using
00:30:24low level statements like go to many people were
00:30:28supporting this would have been
00:30:29impossible while star wars supporting the use of
00:30:32structured programming and kind of light so what.
00:30:39About computer science This
00:30:42is what which is not completely attribute,
00:30:45but there are some ideas,
00:30:47but this time out from
00:30:49voice computer science is
00:30:53no more about computers than Astronomy is about telescope.
00:30:57What is this man.
00:30:59IT means that computers are
00:31:01tools which are you need for studium computer science,
00:31:05but they are not the object of the study.
00:31:09This is the full protection computer science is no more about
00:31:13computers than Astronomy is about telescope Biology
00:31:16is about microscopi or chemistry is about
00:31:19bikers and test tubes science is not about tools.
00:31:24IT is about use them and we find when we do so this
00:31:29is what computer science is not but what is it?
00:31:36Was continuing story computer science is the study of algorithm,
00:31:41including the mathematical properties.
00:31:45Also the science of computers are important,
00:31:49but they are not the focus
00:31:50their linguistic organizations programming
00:31:52languages and their applications,
00:31:54which are also very important,
00:31:55but at the core you have algorithm.
00:31:59AM. What is an algorithm where to
00:32:05defined in general terms
00:32:09some several times it is a sequence of elementari steps,
00:32:14which instructor how to great time,
00:32:20which could be construct tool or using a tool to get some results.
00:32:26Stability of using tools according to some procedure
00:32:32is considered e distinct features of human beings on
00:32:37computer science started already
00:32:41with homo habilis distintive features
00:32:44exactly the capability of using tools according to
00:32:47a great Britain modified method.
00:32:53Book this is a bit to extreme probably Not many people who is to
00:33:00the computer science started with the modern human beings.
00:33:07But instead essential everybody agree about
00:33:12the facts that computer science
00:33:14is a sort of death of an other discipline,
00:33:17which is logic and it is actually for the from as you before from
00:33:22the failure of a long standing dream of
00:33:24logic of mathematical logic, but computer science.
00:33:28And as you like to you today,
00:33:34which we are not really talking about
00:33:36our technical things and like to
00:33:38the beat about the story with it is
00:33:41nothing and now instructor and you don't need for
00:33:46the course many mathematical nations you need to know
00:33:51how very much about logic as you need to be Willing to get into
00:33:58a conceptual way to think deeply to
00:34:02things nations very limited and specific for this lesson.
00:34:06You need almost nothing.
00:34:09In particular you can just view logic as a discipline which is
00:34:13trying to identifying the reasoning mechanism,
00:34:17which are PROpel of human beings and.
00:34:22The main observation is that is the that you can
00:34:28identifying some rules some sort of
00:34:33mechanical rules in the way in which reason
00:34:37which allowed to the consequences starting from a set of
00:34:41promises without intelligence without using any kind of
00:34:46clever just by playing the role in the mechanical way and that
00:34:51is possible the existence of this independent
00:34:55from the specific meaning of the objects that we
00:35:00were manipulation is something that is has been understand
00:35:05a long time ago in particular you might be
00:35:09familiar with the Aristotele sillogismo every man is mortal,
00:35:13this is therefore Socrates is mortal and.
00:35:21You don't need to be clever to use this This is just pattern
00:35:26matching the schematico systematic
00:35:30and you just replace some holes with your might say every man
00:35:38is a carrot Socrates is
00:35:40a man and for Socrates is this is a good reduction.
00:35:46There is the only because we started from silly promises, but the.
00:35:52The mechanism has been applied in the way
00:35:56and that it was possible to drive consequences
00:36:01by using mechanical rules without
00:36:04any intelligence suggest since a long time ago of
00:36:08the possibility of it possible to device e general combinatori.
00:36:15Procedure complete di mechanical procedures to find trucks,
00:36:20starting from set of basic principles.
00:36:24And the history of the idea of the way in which it
00:36:31has been persuade long the years along
00:36:34the millennials actually and the way it fields.
00:36:38IT is linked to the history of computer science and that like
00:36:42to say something about this not starting from the homo habilis,
00:36:48not even from the.
00:36:52Aristotile, but some time recently.
00:36:58So it is the middle age you have about this guy
00:37:04before Raymond is it to palma de Mallorca.
00:37:09You have experience the seaside
00:37:11their night life is in the main cathedral.
00:37:15There is the great of Raimondo Lullo is considered
00:37:18the ground ground father of computer science.
00:37:22IT was a professor in
00:37:24the University is in the world Paris, Montpellier,
00:37:27which together with Padua in Bologna,
00:37:29where the University is in
00:37:30the world and the place where it was living.
00:37:33Palma di Maiorca as a kind of crows
00:37:37the moment for the main different cultures of the times.
00:37:41The Christian culture was support by the king and
00:37:45the Queen of the Islamic culture
00:37:49of their because of the soul of Spain.
00:37:52There are several eyes and Jewish culture,
00:37:56which was instead very
00:37:58much centered in Spain because of the presence of
00:38:00the sefardite as they were living together,
00:38:07which sounds strange by this is until finally.
00:38:12Isabel Isabel, the first with the queen the way of
00:38:16Ferdinand decided to the Jewish Congress for a.
00:38:22Lot of things including
00:38:25discovery America funding Columbus
00:38:28to discover American lot of things.
00:38:31This is not important for as.
00:38:35We just remember we are talking about Raimondo Lullo,
00:38:41after the crisis of face
00:38:43from the Rather than being a scientist it became
00:38:48a Franziska flyer and I decided that I want to unified
00:38:52different cultures of two different cultures to unity.
00:38:56I was so that the real through was the Christian one way.
00:39:01This is not important for us and its inverted a lot of effort in
00:39:05this project and support in the middle of a new crusade,
00:39:10but different from the previous crusade,
00:39:12which where with military army is
00:39:16that this crusade should have been with the intellect with
00:39:21reasoning was that I want to bring
00:39:27the main tankers of the time to a single room into
00:39:30the single place them discuss and finally reach a consensus.
00:39:36But the problem because
00:39:40this different person persons different language different cultures
00:39:46and so is main idea there is and
00:39:48we were talking about it is that is
00:39:50intended decided to construct and artificial language,
00:39:55which extremely simple and artificial philosophical language,
00:40:00which would have been used by this philosophy to
00:40:03communicate independent of their own language.
00:40:06This language was super simple very simple times,
00:40:10it was supported by what is called dell'Unione
00:40:12will e tool which con system of
00:40:15several concentrate wheels like this
00:40:18independent will split into sector it sector is
00:40:24marked by design and the science.
00:40:30And so on responses to
00:40:33concepts politics a sessions and the way you think
00:40:40different on the radius
00:40:43the different symbols construct sequence of symbols that degli
00:40:48interpreti sex and the philosophy of things about this sentence
00:40:53try to reflect and consensus whether it is through
00:40:56or not so this is just this is.
00:41:00This time is what you have to find that it was
00:41:04the middle age and the first time in which somebody
00:41:07for about construction and
00:41:09artificial combinatoria generated language,
00:41:14but without any capabilities
00:41:17reasoning reasoning still left to the human beings.
00:41:21While in step with a little bit father and
00:41:25other gigantesche figure which is Leibnitz one
00:41:27of the main philosophy of old times,
00:41:31which was pushing forward the idea
00:41:35of artificial philosophical language to present knowledge,
00:41:41but I want to be put in the picture
00:41:45also automatic mechanism for reasoning so what is
00:41:51remember Leibniz Dream is this is
00:41:55the dream to language and
00:41:57artificial language philosophical language capable of
00:42:00perfect the relations between our language
00:42:05for knowledge and relation between different areas of knowledge,
00:42:10but it is not only on about
00:42:13knowledge it also some way of reasoning about
00:42:17this knowledge to the language mind
00:42:21compose of two parts the language
00:42:24in science of the characteristic universalis universal language
00:42:28to express emotions and concepts,
00:42:31which is built by starting from
00:42:35some basic fundamental rules symbols
00:42:38and basic innovations which are combined by
00:42:41night diagram and was
00:42:43a proper language pronunciate rules IT
00:42:47really for this would have been used to talk about things,
00:42:52but the language came with
00:42:54a calculus with the mechanism for reasoning,
00:42:57which contact through formal manipulation of
00:43:01symbols with mechanical rules today and is
00:43:05it was that this would have been used to talk about
00:43:08everything God Theology mathematics.
00:43:12International dispute is back with the tool
00:43:16you need words and longer because if the two countries,
00:43:21which are say some island and you put into
00:43:25the machine and you understand who
00:43:27is the owner of the law and that's it.
00:43:30You don't need to fight for that is the famous calculator sentence,
00:43:36which is that we will
00:43:38arise between philosophy or between countries,
00:43:41not discussion will be needed in the same way as
00:43:43accounts do not discuss infected it will be to
00:43:47take pen and paper because their warrant computers at
00:43:51the time and say Let's calcolate was a psicopatiche,
00:43:57but it was not very much concrete
00:44:01for the idea of mapping is language into
00:44:07mathematics in order to be able to compute over the language
00:44:12by using the standard mathematical computational and we
00:44:17want to map the primitive nations into
00:44:21prime numbers and then use the unique of the composition of
00:44:25elements of numbers in the factors to understand things
00:44:32were presented for instance Imagine
00:44:35What you want to read the concept of a man to prime elements,
00:44:39which being an animal and being
00:44:41rational the animal and rational would
00:44:45have would have been presented by prime numbers
00:44:48to respect in the way that the complex concept,
00:44:53which is combined men,
00:44:55which is combined animal and rational.
00:44:58We have been presented by the product of the components,
00:45:03which is sex and to express the facts that the proposition.
00:45:09Subject has some quality some like
00:45:15the subject as is the property present this proposition
00:45:20as traction where the numeratore numeratore
00:45:25is the subject denominatore is the property and
00:45:30proposition is through if the portion
00:45:34is an integer or instance if you want to say
00:45:37all animals write in the number of the number forensics,
00:45:43denominato the number of animal,
00:45:46which is to this proposition is true because this is visible by to.
00:45:53IT was also very much pragmatica,
00:45:55because we are a bit playing with the small example,
00:46:00but if you really want to
00:46:02imaging what you can really reduce any kind of
00:46:04reasoning to this kind of computational you have to
00:46:07do a lot of circulation and you
00:46:09can do everything by and so in
00:46:12the time also inverted the first time machine.
00:46:16The machine it was able to
00:46:19all the four aritmetica
00:46:21operation so not only some attraction like the Pascal,
00:46:26but also product and
00:46:31Clear it managed to get much for this program did it is program,
00:46:37but it was really an incredible think you think that we are in
00:46:42the seven century to be
00:46:46continued too much time continue with our history,
00:46:52we meet and other person now you are familiar with
00:46:57George so we move from Leibniz
00:47:01was noble himself working at the court of empires and
00:47:06kings to a person living in industrial area industrial revolution.
00:47:12IT was person of the show maker,
00:47:15but it was familiar with the world of it was very
00:47:19much is work in particular
00:47:22for the fact that Leibniz wanted to use
00:47:26reasoning to simbolico manipulation and I decided to.
00:47:30even this idea and its point familiar with to transform
00:47:39reasoning over logic into
00:47:44algebra with operation taken from standard aritmetiche.
00:47:49If statements like every plant is living is more than plant living
00:47:57being human as classes and
00:48:02then over this classes use the standard and medical operations,
00:48:07but with a different meaning and what you get is
00:48:10what we can the boolean algebra or instance.
00:48:15If you have the class of animal,
00:48:16which are ships and the white and you can take their products.
00:48:22Which is combined elements,
00:48:25which is the properties of sex and the properties of the class of
00:48:30this by now we can it con
00:48:32junction logical junction or inter section.
00:48:37IT was discovery that in this kind of
00:48:41expressions over classes using medical operations
00:48:45defined working class and
00:48:50the observer that they were new loves equality,
00:48:54which didn't hold in standard aritmetiche,
00:48:57but also instead in boolean algebra like x times x x
00:49:01x. I was extremely excited by
00:49:05the observations that actually is this is not
00:49:07true in standard and this is not.
00:49:11What the kind of KEE observations that the quality that you
00:49:18want in logic are true also in your restricted values,
00:49:25Which also interprete as classes
00:49:29in the empty class where the is
00:49:31nothing and the universal class where you have
00:49:34everything or fools and we are familiar with interpretation also to
00:49:41other aritmetica operations for instance plus became
00:49:44essential dysfunction and on
00:49:47the mathematical community was extremely excited by the facts,
00:49:51but starting from equality this by
00:49:53just simbolica aritmetica manipulation
00:49:56algebriche manipulation on the.
00:50:01Principles, which is the world of ancient philosophy for you from
00:50:08this time ex which
00:50:12is an logic you bring everything on the other side.
00:50:16So you have x x x x
00:50:20zero you have the Common factor you make the common factor.
00:50:26Ex ex times on
00:50:30sex and saying that there is nothing you cannot have element,
00:50:36which is the quality properties of arts and doesn't have
00:50:40the quality of which is the principle of non-contraddizione.
00:50:44From Aristotele.
00:50:46Metafisica sui boulevards really super excited that you can
00:50:51this just by doing
00:50:53addition actions and collecting factors and like again.
00:50:57This is it have to us,
00:51:00but it looks have because we are very much used to build
00:51:02and logic at the time.
00:51:05There was not clear and logic because. This
00:51:16we are close to the end of the story and we need Gottlob Frege?
00:51:24Or not is the most important mathematics,
00:51:30mathematical logic Times and came across the word of
00:51:38light very much this idea of mathematics
00:51:42algebra making and algebra of logic,
00:51:47but it was also so I want to push this ideas,
00:51:52but it was also worry about this fact in with logic becomes
00:51:59an algebra algebra is part of mathematics and then
00:52:04use logic to reason about mathematics of this kind of circular,
00:52:09which is always habit warning and so it
00:52:13to get rid of this circular how by the logic at
00:52:18the basis and then building
00:52:20all mathematics over the logic and for this need is
00:52:24the language like like Leibnitz like an event language,
00:52:32mathematical language philosophical language called biography,
00:52:38which is very known to you even if you
00:52:40can it different because this is now
00:52:43first order logic predicate logic
00:52:46where you have you know what if you have
00:52:49variables to refer to
00:52:51entities and notification to state properties,
00:52:54which is for all entities or for some entities like horses
00:52:59are you need for all x x x x
00:53:04x x x x x x x x x
00:53:09x x black and so is
00:53:12started developing all mathematics using this language.
00:53:16Books. office box came to the best of
00:53:21Russell was like very much to work,
00:53:26but it some point head out and my friend.
00:53:32I your book I very interesting,
00:53:35but they have a problem say that
00:53:39given a property you can construct the set of all elements,
00:53:43which is this property.
00:53:44This is called compilation action.
00:53:48So take the property the set does
00:53:53not belong to ex since you can put a set as
00:53:57an element of set you can wonder whether
00:54:00a set ex belong to itself or not to take
00:54:04this property this property and that you take the old set which
00:54:09this properties set of element
00:54:13such that is not in this is set according to.
00:54:16each and you ask yourself is an element of are you know
00:54:25how the story goes probably you to possible answer yes or know
00:54:30what if the answer is us air belong to the defined property,
00:54:35which is not belong itself so not
00:54:38belong to each and this
00:54:40is a problem because we have contraddizione.
00:54:43Maybe solution is the others are does not belong to,
00:54:47but it is not the defined property,
00:54:50which means that are you have again.
00:54:53Contraddizione so what is extremely nice interesting powerful,
00:54:59but it was contraddittori,
00:55:01it has tradition and you
00:55:04know what probably for logic from logic that if
00:55:07a theory as an in consistency
00:55:11that it is useless because you can everything.
00:55:16Take it is very.
00:55:20Very much the rest and in a very bad way
00:55:25by it became the support of the regime
00:55:28and should pessimistiche because this
00:55:33remember this is the great location, but it.
00:55:39To go to this is it,
00:55:43which is in honor of this is the paradox slide in this we want you
00:55:50slides looks like paradox because this
00:55:53like this is to as you the beginning apart from today,
00:55:59which is strange lesson,
00:56:01which is the show picture to a lot of stranger things,
00:56:07then in general I will be principal right on the black board,
00:56:12but it would be difficult to record lessons will
00:56:15Wright on the tablet and because
00:56:19of things to see how and definition
00:56:23and develop IT is good to to have a step by step construction,
00:56:28but today we just show pictures and we count the last pitch
00:56:33almost last pictures must meet the world of
00:56:36Mathematics was extremely by the discovery of Russell paradox.
00:56:40They maybe we have been doing meaning
00:56:43less things for a long time without knowing so they
00:56:47were extremely married about that and so
00:56:52Dave Hilbert time support is what kind of genius
00:56:57again probably the most important mathematics of the night century.
00:57:03I was enfant prodige solving a lot of problem
00:57:06up to the age of twenty so much
00:57:10In clever board di want
00:57:13some difficult problem and you
00:57:15decided to take in consistency problem.
00:57:18Highlights by Russell. Kind of KEE.
00:57:25Wanted really to put a path to this to save mathematics
00:57:30from traditions and is essential to riformulate Leibniz program,
00:57:36but in modern the modern way so
00:57:40by getting read of
00:57:42the metafisica ambition didn't want a language to talk
00:57:45about God or about international dispute only it
00:57:48was talking about mathematics and was to reduce
00:57:53mathematics to a basic set of actions so basic small set of
00:58:00table principles and then to add a limited set of rules,
00:58:08Which should be used to the use
00:58:11everything has in mathematics starting from
00:58:13the basic principles and
00:58:16to avoid to fall in the inconsistenze problem.
00:58:19Highlights by Russell.
00:58:21I wanted that this mechanical system was strong to be able to its
00:58:26on consistency so that nobody would
00:58:29have ever later on this is Inconsistenti.
00:58:33Once you have built this we
00:58:35have to actions and rule to the things them.
00:58:42Very good situation and what you want further
00:58:46was the program a computer program actually there where
00:58:52is not computer at the time so you want the technique
00:58:56e method e procedure could be
00:59:01decision procedures that given possible theorem
00:59:06a Sentence in the language of mathematics was
00:59:11able to understand whether this sentence was
00:59:15the right table from the basic principles using the rules it was
00:59:20theorem in the theory or not this is
00:59:24the problem decision problem and it
00:59:30better there is such as is not find
00:59:34this is this is possible then matematici would have
00:59:39been an employee because you can generate
00:59:43automatic check automatic teams and the work.
00:59:49Last but.
00:59:52Somebody else later on only few years later,
00:59:58which is this guy together with item and results which that this
01:00:06is not possible is
01:00:08the famous incomplete terms of this is the technical,
01:00:13but the general is rather simple with
01:00:17some limited precision so what Hilbert want.
01:00:25To reduce mathematics to use of basic principles
01:00:29and the rules in the way that everything,
01:00:32which is true in can be the use by using
01:00:34the rules and good with the first incomplete showed that
01:00:39this is impossible also if you limit yourself
01:00:42not the full mathematics very limited branch
01:00:45of which is
01:00:47elementari aritmetiche essential natural
01:00:50number addition product and little.
01:00:54What if if you have
01:00:57the basic principles and
01:01:00these are consistent so they are not traditions,
01:01:03When there is always a sentence.
01:01:07That you cannot prove and you cannot proof of the sentence,
01:01:12but the sentence or the true it means that
01:01:16whatever it basic principles you take there is always something,
01:01:21which is true and that you can not proof.
01:01:25So was impossible and then one
01:01:32of what I can you may be the number is random or not to something,
01:01:39which could not less,
01:01:41but actually what if the second there was that
01:01:44the hypothesis is consistent
01:01:47with then among the sentence is that cannot be proof,
01:01:51which are true you have the consistency of the theory.
01:01:56So this is a terrible two Hilbert program
01:02:00of Re funding logistic basis,
01:02:06but still one could ok we cannot drive
01:02:10through we cannot be the system is
01:02:13consistent by using the system itself, but steel.
01:02:16I would like to know given whether
01:02:19something can be derived from the story or not would
01:02:23like to the problem and Turing and Hilbert didn't say check.
01:02:30Whether this is possible find the procedure find
01:02:33the algorithm did it algorithm and Turing
01:02:39came and it was optical
01:02:41about the existence of this is and I want to there was
01:02:45no algoritmo to this is needed to say with an algorithm
01:02:49is because we know what you have in ancient Babylon.
01:02:57Egypt Grace with the persian matematici
01:03:04was the extension of the fundamental books about four for numbers,
01:03:11but nobody gave a precise definition of what
01:03:15is rigorose to be able to this is about that I
01:03:20want to do not for that it is what we will be doing in the course
01:03:24and its something that you can execute
01:03:26over the machine is the machine,
01:03:29which is in the following way you have the memory where you can
01:03:33write read and the agent,
01:03:37which is a program and
01:03:40the execution of the agent can from input and continue forever
01:03:44or the output that the machine gave
01:03:51solid notion of computer what is not
01:03:55essential everything which looks computer intuitivi, intuitivi.
01:04:00Can be computer by machine.
01:04:02This is what we know how as Church Turing
01:04:05This is final observation was that yes,
01:04:11you can can be everything,
01:04:12which is intuitive compatible,
01:04:14but there are always functions,
01:04:17which are not compatible in particular for
01:04:20the problem problem that we mission before this
01:04:24related to Hilbert when touring was able to
01:04:28establish a corrispondenze between logical actions
01:04:31using the action system and computer functions in
01:04:36a way that existence of the city of the problem
01:04:41allowed to the answer to the problem so the dream which listed
01:04:48from from nullus or maybe even from
01:04:52Aristotele until Hilbert was completely destroy.
01:04:56People would have been very much,
01:04:59but actually during immediately really
01:05:03that something that developed to give this negative answer to
01:05:08the problem was extremely interesting because in order to
01:05:12give a proof to the negative proof
01:05:16of the problem solver e needed
01:05:21to the existence of
01:05:23universal machine and machine which takes in input.
01:05:27And description of machine,
01:05:30which is simulate the input machine over the input that is this was
01:05:36extremely powerful and really
01:05:39wanted to transfer this from mind to reality.
01:05:42So is started designing some ideas for building this machine,
01:05:48but the second world war came probably
01:05:52seen the imitation game the movie I was recruitment to work in
01:05:56Bletchley Park where the UK government collected a number of
01:06:02scientists genius people in order to work
01:06:08on the one machine or general on techniques for the cipher codes.
01:06:14In particular one out of this board of the Colossus machine,
01:06:19which special purpose machine used
01:06:23for the cipher codes and Turing bit a
01:06:28bit on this project in the movie movies very precise
01:06:31because this Colossus is the Turing machine,
01:06:36which is not the case it was
01:06:37a special machine with the code embedded.
01:06:42But working on this Turing
01:06:47understand the potential of electronic to
01:06:51computing machines and then it designs
01:06:55I project of the universal machine
01:06:58uses using this electronic stuff,
01:07:01but this project is not funded in
01:07:04particular it is not its considered too much
01:07:08beyond the technological limits because it requires
01:07:11six kilobyte of memory considered too much
01:07:15and then this kind of this appeared and
01:07:18the contribution of Turing in this kind
01:07:21of work and the work Bletchley Park was
01:07:24for long time neglect on the one hand because.
01:07:29This is covered by the militari service by
01:07:32the military secret and on the other hand
01:07:36because you know that Turing has been prosecutor
01:07:40because of sexual sexual and committed suicide,
01:07:45but UK was a beat about at the
01:07:50dead you probably the most
01:07:51prominente science of all time after Newton,
01:07:55but started there are
01:07:59people around Turin has been interacting with touring in
01:08:02particular John von Neumann probably about it was
01:08:08escape from hangar again during
01:08:10the nazi domination together with the bank of other Hungary,
01:08:15genius and I was the war of the ideas of
01:08:18Touring and the potential of the Touring machine.
01:08:21IT was working immediately after the war on
01:08:26project attack project design report describe
01:08:32the concrete architecture of digital computer based on the ideas.
01:08:39This steel theoretical, but after of
01:08:42years it has been transfer into practice
01:08:44with the project and this was the first computer and after
01:08:52a few years in the first commercial computer and you
01:08:55know how to develop up to the present days.
01:09:02Large language models and like.
01:09:06This is it to you the story which is a bit too much time
01:09:11probably well I think thank you this because this is my view.
01:09:17IT is interesting to understand that computer ability stands at
01:09:20the end of the convergence of
01:09:24very long intellectual adventure
01:09:29and it is at the convergence of a number of this
01:09:34is it is not just interesting just for computer science and its
01:09:39also interesting say to understand that
01:09:42sometimes also for you can happen in your life,
01:09:46sometimes on extreme extremely terrible failure something which
01:09:51destroy all your ideas something good
01:09:54can come out for the fall of Leibniz,
01:09:57dream and the dream of
01:09:59the universal machine that the art of modern computer science.
01:10:07From time to time it is really Typekit strange,
01:10:13but from time to time I feel like this person in the audience,
01:10:18but I want to do much more practical things I
01:10:22can't understand but I really think and you that the way of
01:10:28reasoning game boy compatibility theory
01:10:31is fundamental in any other kind of activity
01:10:35might face your activity of
01:10:40computer scientist because you have to think really
01:10:42deep way in a really conceptual structure.
01:10:48There are no complex nations
01:10:52the course is sometimes considered difficult
01:10:57and it is in Essence because this
01:11:02reason you need to reason why not found.
01:11:07We are not difficult nations there is
01:11:10no background only my suggestion is to to follow lessons by
01:11:15lessons because what we will be doing will be
01:11:19building a theory in layers and each layer is
01:11:23using the previous layer and so some point to say Ok this
01:11:29time skip to this for each and then following lessons again.
01:11:37This is not going to work because if you some part time start
01:11:42understanding this is really
01:11:44rating so I know that you have a lot of things to do,
01:11:47but it is to
01:11:50follow by lesson and the course can become really easy.
01:11:57AM from the organizational point of view lessons are.
01:12:03You know how?
01:12:06Are typically do not make a break between
01:12:10the lessons with the two hours will finish actually it
01:12:15around then typically this
01:12:18is convenient for students you have to make
01:12:19the other buildings and like we have a book will follow in close,
01:12:24but also some lecture notes in the moodle.
01:12:30Web page where you find static information and
01:12:35the Moodle put. Notes which.
01:12:40Take produced during the lessons they recordings
01:12:44of the lessons and other material.
01:12:50Please look and roll into the moodle
01:12:54and it up and take look at the resources,
01:13:00which there is the times with students Ok,
01:13:05but the book is difficult and their any other resources.
01:13:08This was at the end of the course.
01:13:10There are not really lots exercise and you can things their.
01:13:20Office, which is Wednesday.
01:13:23Eleven, but the best is an email and then we
01:13:29can meet and we can
01:13:31talk before the lesson after lesson during the lesson,
01:13:35when you want you ready met tutor and will be.
01:13:40telling activity taking place.
01:13:45IT is not mandatory,
01:13:46but last year that students very happy about that you may and see.
01:13:52The same is a writing test with for exercise
01:13:57as you can find example of exercise is a
01:14:01long long long taken from examples
01:14:05in the moodle page and there is an optional or a discussion,
01:14:10which is optional in the science that
01:14:12you can choose to give example.
01:14:14If you are happy about your result of your breath test and
01:14:19then this becomes part of your exam can improve air force.
01:14:24IT is essential to get dysfunction so if you get any kind
01:14:31of marked written test even over
01:14:34thirty this becomes unless you do e nord.
01:14:37Alexa and also might be optional because there is what I
01:14:43don't understand your written exam and I want to talk
01:14:46about that optional on your side,
01:14:49but also on my side.
01:14:51This is. This is it.
01:14:58If you have any kind of questions from about the lesson.
01:15:04Ok, very stranger things.
01:15:08Maybe that's not really the point,
01:15:10but it questions about the organization of any other questions,
01:15:14please ask other wise with each other.
01:15:17Next next week. No, okay,
01:15:26so see you next week.