Placeholder Image

字幕列表 影片播放

  • so I wanted to talk about propositions as types because it was something which sort off came out.

  • When I talked about type theory, I thought some people asked about this and I thought, It's a good bit more to go a bit more to detail.

  • Explain things a bit.

  • Yeah.

  • So what does this mean?

  • The nature you could say the relation between proofs and propositions, A straight cop for short is the same, in some sense, as programs.

  • Basically commission, which I would like to explain.

  • So first of all, let me explain a little bit by proposition.

  • I mean, a mathematical statement.

  • Like the injury.

  • Many prime numbers are this program swords, numbers, stuff like this.

  • Yeah, and you'll even explain things.

  • I sometimes use examples from the view bird like trains.

  • Today we go to the zoo or something like this.

  • But really, it's not about the propositions I'm interested in here are not like everyday propositions, but they're so precise.

  • Statements about programs are mathematical objects or whatever.

  • What do I mean by by types?

  • Because they are the types.

  • We haven't a computer.

  • Pull them and a computer.

  • You know something?

  • Pool warrant, ages but I'm going to use maybe some more primitive types, which maybe not s as coming.

  • Well, that explains it.

  • Uh, it's a proof want survey to justify a proposition, I'd and what's the problem?

  • I should be watching computer file if you know what this is.

  • The thing about about logic and reasoning.

  • So traditionally there's another creation I would liketo I don't This is the idea that top equals booth.

  • What's Boo?

  • It's a type.

  • It's just two elements to enforce.

  • This idea is very widespread on mathematics.

  • It's related to what we call classical logic.

  • And initially, if you first learn a bit of a logical looks quite well, there's these operations we like and conjunction or disjunction implication navigation.

  • We can explain them as operations on Duel, and maybe you've seen these tooth tables which defying all this operations.

  • But that's cool.

  • But then you learn about predicated logic.

  • So Critical Lodging has some other symbols, like this one, which means for all and this one which means exist.

  • So, for example, we can work something like for all natural numbers for all ex in N.

  • And then something holds.

  • So something holds for financial numbers you know nothing.

  • F off x the F It's a function which assigns to every national number two civilians.

  • That's a predicated for every natural number.

  • We have a truce value.

  • Now, if I want to define the meaning of this statement, I have to compute a 1,000,000,000 this bullion it's okay to if this function returns to for every input.

  • But I don't know how to pull them such a function because I have to check infinitely many inputs to say that I can't return to what it has to be to everywhere, a kind of guy to pull them.

  • Which justice?

  • I mean, I can't start tying f zero f one f or two and if it's always to it if it ever falls, because it must be for you.

  • But if it stays too, I never know when to return to.

  • To me, that means that this idea of Popsicles school doesn't really work for me.

  • As a computer scientist, maybe may say OK and mathematics, that's okay, but I like to use a deal's from computer science toe, explain mathematics and here let me turn over.

  • There is the other idea, which is pop.

  • It's tight, but that's just me.

  • You have a proposition.

  • Instead of trying to explain minutes tool, which is tricky, it may explain what it's evidence for this proposition.

  • I say a proposition and then explain what sort off, except as evidence evidence to accept this proposition and the evidence of a proposition.

  • It's a type off its pools.

  • So the idea is we assigned to every proposition a type off its proofs or evidence.

  • And whenever you find can deliver an element off this type, you have very fine this proposition, so it's really, really a fundamental, different point of view to logic.

  • Instead of talking about tooth, we talk about evidence and the proposition as types.

  • Translation translates propositions as types is a heartless is work.

  • So I want to do an example.

  • I want just to tell you what a proof, a simple proposition and proposition a logic.

  • I want to prove what's called a tautology, p and Q or our implies P and Q or peace sent.

  • I find obviously useful to think off complete association so that C P means it rains today.

  • Q.

  • Is we go to the zoo and are we have chicken for dinner.

  • So I say, Okay, it rains and we go to the zoo where we have chicken.

  • Then either it drains and we go to the zoo over it rains and we have chicken for dinner.

  • This implication hasn't got anything to do this to concrete instance, she ations off P Q and R.

  • If ever replace it with something else, it would still remain to.

  • So it doesn't tell you anything about whether it rains.

  • But what zoo or chicken dinner?

  • It is what's called a tautology, which means it's, too for any peak.

  • You are being propositions.

  • Okay, so everyone to check that this is a tautology and we use the previous idea.

  • Proposition equals bull populace poor.

  • We have just took a ball to stable and shake.

  • That's two everywhere, but I won't know to use this proposition.

  • Is types principle to explain viruses a tautology?

  • What I'm going to do is I'm going to consummate this into a type and the town station.

  • It's actually quite straightforward.

  • I have to give a translation for every operation here for every logical operation for the end of the hall for authentication.

  • Okay, let's do this.

  • So what's end What is evidence for P and Q evidence for P and Q is a pair off evidence for P and evidence or Q and the D notice as the product?

  • P Times Q.

  • So this is what mathematics called cottage in Poland or product off types.

  • It corresponds to constructing records.

  • And the basic rule is if you have an element X off P and an element of eye off, you can put them together like two pools.

  • Thanks, Come.

  • All right, That's element off P times killed.

  • I mean, he knows us from coordinates.

  • Real times, Lou have a peer off numbers.

  • That's the product was quite widely used, so we translate conjunction.

  • That's the product, because evidence would pee in, few disappear off evidence would be and evidence work.

  • You know, the next thing is P or kick you out of it.

  • Complete peor que.

  • There's another operation, which is less familiar in mathematics.

  • It's wouldn't plus, it's a son, and this coast wants to either.

  • Your element of P.

  • We have an element of Cuba, but we're labeling which one of this so it's not.

  • It's different to the union operator on, Dhe said.

  • Clearly, we just put things together.

  • But here we put them together.

  • But we label what they are on an example.

  • If you have some database and maybe members off the university can be either stuff.

  • Okay, So members of the university can be as a dog's over humans.

  • Yeah.

  • So then you may have different data for dogs and for humans.

  • So you say that that type of a member of the university is Doc plus human.

  • But you're basically member who was a dog and he was human.

  • You don't mix him up to be either, or so let me write on the world.

  • If you have an element X in P.

  • So if you have a dog, then you have also element left.

  • Thanks off P plus que And if you have an element of eye off you, then you come there right by and P plus Que Okay, here's the words left and right.

  • The orbital.

  • You could use other symbols.

  • Something they will in the I don't know whatever.

  • Okay.

  • The one thing I have to explain as well is what means p implies Q.

  • There used the same symbol.

  • P employees Q.

  • It's the type of functions frumpy took, You know, if I want to convince you that if peace and Q the evidence was this, it's a function which, whenever you feed it, evidence for P spits out evidence.

  • Work you?

  • Yeah, And instead of inventing lots of notations for functions, I just drew a picture.

  • So function f off Pierrot Q is a box.

  • Whenever I feed it Elements off P on the other end elements of Q come out.

  • Okay, so this is my explanation.

  • Translation off oppositional symbols into operations on types.

  • And now let's go back So proposition.

  • And I think I have to go to a different page Snow Oh, boy.

  • Translators as p and cute.

  • Plus, uh, ho p times cules class peace times are so I'm just applying the translation which are just explain.

  • So this proposition and now to convince you that a tautology I have to write a function whenever it gets this input to reverse this output, how do we find such a function?

  • Cf off some input, X equals some output.

  • So ex CNN element was in court.

  • My question.

  • Look, it's an element of the output.

  • How can I write such a function now?

  • I kind of really given answer.

  • I first have to analyze with my input, men put its first of all a product.

  • So I know it must be appear X comma and then something.

  • And there's something is an element off you plus r.

  • There are two possibilities that as a left off lives or right off that define dysfunction have to give to your creations.

  • I have to give two definitions.

  • Two lines.

  • One for the case to hear the first element X is in peace.

  • And the 2nd 1 element of Coop Lazar was avoid being a pew.

  • And here I also have another P and this that is an element off.

  • What I've done is I've analyzed the input.

  • What could be the possible elements off the input for each element of the input?

  • I have to give an output to define dysfunction.

  • So in this case Ah, I haven't p and Q.

  • And if you look at this, I can could use an output by going left left.

  • Thanks.

  • Come over.

  • And the whole thing to x comma by is an element of P.

  • Times two and left X comma virus.

  • Another mint off this type here.

  • Same right?

  • Thanks.

  • Common is it for what I've done here is having written a simple program in the functional style which inhabits this type.

  • Anderson's evidence for this proposition.

  • Whenever I feel defeated an element off this type and the output an element of system.

  • Okay, This ah, very to proof propositions.

  • Just using programming is instead off instead off looking up to the stables or something is just about the program.

  • And, um so what's what?

  • What follows from this virus is good or how this is compare.

  • That's a previous idea of using boo.

  • I mean, I've always say that the idea just using bull for propositions doesn't really scale.

  • So there, there, other differences.

  • So the logic we get here is different from the logic from the classical logic were used to.

  • So there are statements because they're not provable using the understand station, the famous fondness to be or not to be with e p or not peace.

  • But what does this mean?

  • I haven't really explained What notice?

  • Let me do this.

  • What is not not off p means that if p holds them false to say not you see, if P then you're in trouble, okay?

  • And how do we consider it?

  • Falls it translate Force see Empty type.

  • The empty type has no elements.

  • So in this case, they cannot be evidence for P.

  • Because if there would be evidence for P, then we won't have evidence for the empty type.

  • And there's no evidence for the empty type.

  • There's no problem in the end to top.

  • OK, Is that like no.

  • Ah, I was finally is like picks can fly, huh?

  • So if if if a girl wants to see she doesn't want to marry you, she could say If I marry, use and ticks can fly, which is a bit off, a complicated way to seem normal.

  • So here, if if you translate this, this means p class pea gravel empty.

  • So now what does ask you is for every type to either return element off p or not, Pee pee implies empty.

  • And you can't do this because you can't even look at it.

  • The type, so you have to decide either or propositions to old positions affords.

  • That's not the case because there's some tools and some of forts.

  • So this statement here, which is ah, classical tautology.

  • You can even your check that this horse and toast tables because two stables just realized this idea that every proposition is either to a fault is not provable.

  • This is evidence.

  • Semantics.

  • Let me That sounds like it.

  • Disadvantage.

  • Something we would maybe want to use in your proof.

  • It doesn't work on Dhe.

  • Some people, some mathematicians actually think it's a disadvantage.

  • Uh, miss most famously, Hibbert, a famous German mathematician.

  • He didn't like this on and had a big argument with Dutch Guy called pro.

  • But I think especially from a computer science perspective, it's actually quite useful, not effort, because in computer science, I'm often interested in something that's decided well, so we may have a predicated, as called Q, which gives me, for every natural number a proposition.

  • And now I want to express that this predicated decided well so that you could be, for example, pine predicate of being time, which I can distract you.

  • Give me a number I can tell you is it's fine with me.

  • Maybe not me, but computer takes me too long.

  • But there are other problems.

  • So, for example, if you've used the natural number as some memory off a computer, you ask the question.

  • Is the program going to stop toe hold?

  • That's a famous hoarding problem that's not decided.

  • It's no program, which finds out any program which you feel it will hold or not.

  • They're decidedly undecided about predicates, and in using this evidence semantics, I could give a simple formula.

  • I say.

  • Four natural numbers either cure Fix.

  • Well, not your effects.

  • So this looks like it's an instant off those tautology, but he cannot prove it.

  • But in some cases it can prove it foots off a prime for every national number, I can tell you that that's a poem or not a crime.

  • So then that's a element of proof of this.

  • But for other predicates, Q.

  • So, for example, the predicate holes.

  • You cannot provide evidence.

  • So I think this sort of logic fits very very was computer sense because of things which are important for me.

  • I can actually express for easily, so sometimes he fall.

  • Please would dies.

  • He often would make backup copies.

  • Uh, let's try this one.

  • It sounds more helpful.

so I wanted to talk about propositions as types because it was something which sort off came out.

字幕與單字

單字即點即查 點擊單字可以查詢單字解釋

B1 中級

作為類型的命題 - Computerphile (Propositions as Types - Computerphile)

  • 2 0
    林宜悉 發佈於 2021 年 01 月 14 日
影片單字