Undecidability Tangent (History of Undecidability Part 1) - Computerphile

[@00Sparkie00]

Another really interesting video. One small point, in fact Hilbert said "Wir werden wissen, wir müssen wissen," which translates to "we will know, we must know." It was so important to him, they even wrote it on his gravestone.

[@slpk]

I could watch him tell me stories for hours; without even blinking

[@igNights77]

5:07 "Gauss had this name for them, he called them: the KZbin Commenters."

[@michaelbuckers]

These days we call them "cranks".

[@oafkad]

"In my younger days." Dare you tell me that such a dashing man is not still young? I cannot believe you.

[@eltyo340]

This was great! Professor Brailsford videos are my favourite

[@jesuizanmich]

These videos are wonderful. He goes through so much history, and links everything together so nicely. Even hyperbolic geometry made more sense in the context of his story than it normally does when most people try to explain it! I was waiting for completeness and paradoxes, and that's just what came in the next video. His story just flows directly into it, brilliant. :D

[@frostyusername5011]

I could listen to professor Brailsford talk about anything for ages.

[@adamd0ggg2]

"Get into a flame war with Kant" lol Kant the OG troll

[@Kabitu1]

One of the things that helped me understand undecidability was reading about hypercomputers. A hypercomputer is a theoretical machine that can solve undecidable problems. There is a list on wikipedia of supposed ways to make a hypercomputer, and it makes the whole thing very intuitive; in order to solve them, we have to do something we´d all agree is impossible.

[@HasnainHossain_h]

Has anyone realized how the wonderful Professor, from around 11:10 - 11:25, sounds exactly like Feynman? That got me so excited!

[@pur3jock2h]

Gauss is by far the most badass Mathematician!

[@ChristopherKing288]

what about Gödel?

[@DoctorDARKSIDE]

I think this is pure culture and the very basic of our modern computer science - I vote for more!

[@unvergebeneid]

Even though I know the answer, the ending still feels like a cliffhanger. Moar!

[@taylorrkenneth]

This is honestly one of my favorite video series on all of KZbin.

[@iseslc]

I think undecidability is one of the most awesome topics in mathematics/computer science! i would love to see more of this!!

[@miskee11]

professor b right on da money as always. he never ceases to amaze me with his delightful prosody and incredible accuracy, details and depth of knowledge and understanding. this dude is a true fountain of information and I'll always enjoy hearing him recite info on these interesting matters, be it however obscure. intrstng vidya )

[@veggiet2009]

I like Professor Brailsford's tangents

[@migfed]

Brilliant job professor. I do understand why you wanted to do this kind order of video long time ago. Just because it's simply beautiful.

[@Volrath1988]

Professor Brailsford is amazing at explaining concepts!

[@Mizziri]

I love this guy. Taking shots at Kant AND Newton.

[@Mizziri]

He wasn't really proving anything though, he was just saying newton's a bit of a derp for not writing anything down. A lot of people believe he stole calculus from Leibniz.

[@Mizziri]

Yep, I totally agree.

[@pfever]

Professor Brailsford is my favorite professor, I could listen to him all day! :D

[@KurakiN64]

And then Gödel came in and ruined Hilbert’s life.

[@JahMusicTube]

Spoiler alert :D

[@sadade32]

Damn man, stop spoiling history.

[@jasonneu81]

sadade32 Exactly some people still wanted to finish history :'D By the way, [spoiler alert] Oedipus was a motherf*cker :P

[@FistroMan]

Not for so long... just need to add the Wason effect to mathematics and you can obtain incredible conclusiion that nobody really wanted to see, even if they can provide computable formulas.

[@Neura1net]

This is the best video I have seen in a long time. Thank you!

[@t1ktaalik]

Can we please have more of this historical content, I really enjoy the professor's tangents on computer science and logic. Also, a part two would be amazing, you left us hanging just before getting into Gödel's work. Speaking of unusual habits, in Gödel's later years, he would only eat food prepared by his wife for fear of poisoning, and starved to death when his wife went to the hospital for an extended period. Mathematicians are strange.

[@ButzPunk]

Aww man, I wish it didn't have to end.

[@auntiecarol]

It doesn't... if you read Huxley, listen to McKenna, roll with Rogan, or take a trip yourself. BTW, it's shroom season. "There are more things in heaven and earth, ~~Horatio~~ @Ben Rowe, Than are dreamt of in your philosophy"

[@jeffirwin7862]

I would hardly call this a tangent; it was an excellent monologue. Professor Brailsford seems to be quite the expert on the history of mathematics. The incompleteness theorem and the halting problem are tightly linked. If it weren't for those like Laplace (and his demon) and Gödel, I would be uncomfortably reasonable.

[@LeiosLabs]

Man. Guass. Electricity and Magnetism wouldn't be the same without him.

[@DanieleGiorgino]

That was a very interesting video.

[@eldizo_]

muh incompleteness Very nice video, I can always listen to Prof. B.

[@dalerobertson4662]

So lucky to learn from you Mr. Brailsford

[@Chr0nalis]

Please keep these videos coming :) Very interesting to listen to prof Brailsford talk about this kind of stuff.

[@longlostwraith5106]

Wasn't Euclid talking about *straight lines* in particular? A straight line is, by definition, not curved. Therefore his proposition is proven to be true. Is this lost in translation? Euclid was talking about "ευθείες"( straight lines ), not "γραμμές"( lines ) in general.

[@akashpremrajan9285]

Straight line is different in a Euclidean vs non Euclidean space. E.g. On a sphere, two straight and parallel lines will eventually meet.

[@NeilDeshpande313]

My morning is made. Thanks for the video, Professor! 😌

[@AdeonWriter]

This is exactly what I want from this channel. (Had to counter.)

[@EcceJack]

Very well explained!

[@DC-zi6se]

Gauss actually went to Konigsberg to meet Immanuel Kant, there's a very interesting story behind it. Kant was hugely impressed by what he heard from Gauss.

[@ZardoDhieldor]

Aaaaah! Why stop at the Hilbert project! I want to know more! :D

[@nickscurvy8635]

Anyone who's listening to the drama about euclidean geometry and finding it interesting. Extra history has a short series on non euclidean geometry that is also very interesting, goes into slightly more detail, but is still introductory and very easy to follow.

[@Kram1032]

Hah this is awesome. Connecting Euclid's geometry with today's problems of undecidability. Also, this came awfully close to discussing the very foundation of both computation and maths. Things like the Zermelo-Fraenkel-Set-Theory-With-(the Axiom of)-Choice (ZFC) or the very new, geometrically inspired idea of Homotopy Type Theory (HoTT)* etc. I take it we'll hit topics roughly about those things soon-ish, and I'm excited about that prospect. :) *The later, by the way, is discussed a lot on Nottingham University's own Functional Programming division and I hope you get to talk to those people too, Sean, or Brady, or who ever might do those videos.

[@BeCurieUs]

Oh I hope the next one of the rants is about Kurt Gödel. Until then... ♫One man deserves the credit One man deserves the blame And Nicolai Ivanovich Lobachevsky is his name, hi!♪

[@NathanTAK]

The 180 degree thing isn't a postulate (or proposition, I know.) It's a theorem. The postulates are things like a line intersecting a line is a point, planes intersect at a line, that if equal quantities are added to equal quantities, then the sums are equal, that right angles are congruent, all that stuff. Triangles are proven off of that.

[@elliottmcollins]

Echoing some other contents, *please* don't just stop here! The next part of the story's great, and profoundly linked to computer science.

[@NoriMori1992]

I was just reading about geometry and Euclid's postulates on Wikipedia a few weeks ago, so this video was very pleasing to me. :)

[@ElectricEvan]

I love this!

[@VincentRubinetti]

Awesome video. This guy is great. Perhaps this belongs better on Numberphile? Is this related to Godel's incompleteness theorem? What he describes at the end - Hilbert wanting a real answer, not "it's undecidable"?

[@LittlePeng9]

This is actually very far from undecidability. This is unprovability. We can have different set of propositions (axioms, actually), which proves every proposition we can state _and_ be decidable, so geometric problems are bad example to undecidability.

[@zemariagp]

beautiful, thank you so much

[@raynorkerrigan1]

I love how Newton and Gauss is relatable, not me beeing a genious but horrible bad at the social bits :) and i strogly encourage these videos where you go in detailed history explaining stuff. The more facts the better! Lets end with a joke: Why is Pi a bad story teller, he just goes on forever

[@mohakhe]

I think here we are talking about Euclid's Postulate 5 not Euclid's Proposition 5. And as you know postulates do not need proof. You should accept them and use them in your proofs. The question whether we need a specific postulate in a theory or does it make sense in the context of the theory is another matter.

[@santerisatama5409]

Exactly. Euclid's propositions are necessitated in order to be able to formally prove his final conclusion, that there 5 platonic solids, and you don't need curved planes etc. for that. Actually the 2nd proposition ("Line has no width.") is much more problematic than the contextual requirement to stay limited to flat plane. 2nd proposition and calculus - as invented by by Archimedes - are in deep intuitive conflict. Archimedes reasoned that if line segments have weight, you can start to prove calculus stuff. But it's highly counterintuitive to try to imagine line segments without width having a weight. And thus we are still stuck in trying to come up with a coherent theory of quantum gravity...

[@teekanne15]

Love it, but why isnt it a numberphile ?

[@calfischer1149]

Because it relates to undecidability

[@tshddx]

This example sounds more like incompleteness than undecidability.

[@Vulcapyro]

Spoiler, they're very much related. One use of "undecidable" is essentially incompleteness.

[@elliottmcollins]

That's likely to be a sequel video to this one. *fingers crossed*

[@kwanarchive]

Incompleteness in mathematics is not the same as not-yet-completeness. There will always be things that are true or false within a system that is not provable within that system.

[@LittlePeng9]

This isn't necessarilly right - we can have systems with very little expressive power, in which every statement is (dis)provable. Check out Tarski's axiomatization of geometry or Presburger arithmetic.

[@mage1over137]

You need incompleteness to show undecidability.

[@moepet1]

*puts on wishlist* 3 hour blu-ray of Brailsford's history of math :)

nice video.. is this a intro to uncomputable problems like the halting problem?

[@anon8109]

This is neither about undecidability nor about incompleteness a la Godel. This is simply about independence of the parallel axiom from the other axioms. This means that the parallel axiom is not provable from the other axioms. This is actually a pretty common concurrence since in most axiomatic systems we choose axioms that are independent. If an axiom is not independent then it is redundant and can just be tossed out.

[@profdaveb6384]

Yes, I agree that the unprovability of the parallel lines axiom from the rest of the Euclidean axioms is of a different nature to that of (inescapable) Godelian incompleteness. But it does serve as an example of how the "undecidability" of the parallel axiom in Euclidean geometry arises from the remainder of the axioms being insufficiently powerful to prove it -- a defect which is neatly remedied by "thinking outside the box", and developing a more general system of geometries, which can enable the Euclidean parallel axiom to be seen as a special case.

[@anon8109]

I would say that the defect was with people's philosophical understanding of what an axiomatic system is, and its relation to mathematical truth, because modern logic and set theory were not yet fully developed. The long held intuition that the parallel axiom should be provable from the other axioms was just wrong. -- The term "undecidable" is usually used to describe a sentence which is semantically true but for which no proof exists in a given formal logic. The parallel axiom is not semantically true so is not undecidable in this sense.

[@niloymondal]

If proposition 5 is an axiom, why would people want to prove it? Aren't axioms just taken as absolute truths?

[@Cybeonix]

Good stuff guys :)

[@zooblestyx]

But how do I decide which one is best for me?

[@handyMath]

That was a truly interesting video

[@sebastiansimon7557]

The word at 05:13 is probably “Boeotians”, right?

[@MindLessWiz]

Brilliant video!

[@kammi5]

I really enjoyed this!

[@Pedritox0953]

Love your histories professor

[@Oneofawesome]

You probably already know this, but in the absence of matter or energy, space time is not euclidean as Professor Brailsford says, it is a flat Minkowski space. Love the video and the channel as a whole though.

[@NathanTAK]

Whoa! He made a pop culture reference before the book was even written (42)!

[@auntiecarol]

It was a BBC Radio play before it became a book before it became a movie. PS. Don't forget to bring a towel!

[@santerisatama5409]

Euclidean limitation to flat plane is deeply connected with the Euclidean definition of point: According to propositions 1 and 3, point has no part and is an end of a line segment - in other words the relation of point and line is mereological part - whole relation. Euclid was not a reductionist, he was a holist, ie. line is not a sum of points, and the meaning of point is defined by lines and flat plane. The intuitive way to *see* a point with minds eye requires to make a cut in a straight line, so that you can look from endpoint to endpoint over the cut. If the plain is curved and/or the lines are not parallel, you can't see a point, you see only lines.

[@Roxor128]

I'm guessing we're going to get a video on Goedel's Incompleteness Theorem soon.

[@devjock]

Love the monty pythoin reference. That is pretty accurate :D

[@abdlwahdsa]

I am still confused, I understand the postulate can not be proved with euclidean geometry, but then what is the proof ? Can someone refer me to it ?

[@johnvonhorn2942]

So if you told Hilbert that the answer was undecidable would he bark, "What a load of hyperbollocks"?

[@travboat]

I read the description, and I see what you did there... that's very clever :D

[@chrisofnottingham]

The illustrations show non Euclidean geometry as distortions on a 2 dimensional plane, or having a locally flat plane curve into a third dimension, but my understanding is that this is at best only a visual analogy.

For the record: in Hungarian, you pronounce "ly" as it wold be an "i" - so Bolyai is pronounced like "boiai". It's a nice video, I really want some more, too :-)

[@DudokX]

Great video!

[@robertzhowie]

Link this at the beginning of a numberphile video, it's about maths as much as anything!

[@NilsR]

Gödel next?

[@tiborpejic2341]

My thought exactly.

[@vandee28]

Loved the story, but isn't this for numberphile?

[@trevorwoods]

This video made me realize that in school we are not left with enough room to ask real questions...perhaps because teachers would not be able to explain sufficiently... -_- and also not be able to nurture and support the inquisitive mind...

[@kevind814]

Still not sure what is even meant by "undecidable". Unprovable theorems?

[@0pyrophosphate0]

Undecidable just means it can't be proven true or false. The thing people have trouble understanding is what makes a problem undecidable or how that is even possible.

[@TheRealDerohneNick]

Something where you cannot say "True" or "False", "Yes" or "No".

[@m4medzik]

In axiomatic mathematics you build your theory on a small set of axioms, statements you define as true and some set of inference rules, i.e. logic. Specifically, mathematicians mostly use first order logic (that's not really important now). Let's try a magical Lego analogy. Consider axioms of a given system as basic Lego blocks and logic rules as the possible ways of "combining" the blocks. What would be a theorem in this case? A Lego construct, for example, a cube. Given all the basic blocks you have is it possible to build a cube using "combining" rules and as much of each basic block as you need, but only a finite amount. And the proof of that theorem would be a list of instructions for building it. To complicate things, every theorem has it's negation. In our example let's call it anticube. It's an object "opposite" to cube - if you can build one of them it is certain you can't build the other - only theorem or its negation can be true, never both. What does it mean for our Lego world to be decidable? Every imaginable theorem xor its negation in the Lego world must have a list of instructions. It can be as long and as complicated as you like, but finite. If our Lego world is undecidable there are some constructions that you can imagine but simple cannot give a list of instruction for them nor their negation. Sorry if I further complicated things.

[@THEEVANTHETOON]

"Undecidable" means there is no mechanical procedure or algorithm--however we wish to define that--that can determine whether an arbitrary statement is a theorem of mathematics. "Incomplete" means that there is no set of axioms that can prove every true mathematical statement, or in other words, there are statements in mathematics such that neither them nor their negation are provable, e.g. the Continuum Hypothesis. The two ideas are very closely related, both historically and conceptually, and the proofs are more or less similar. However, the former has to do with computability, while the latter has to do with provability. And they don't necessarily imply each other either. For example, first-order logic is complete--i.e. If a statement A is true, there is a proof for it in any reasonable axiom system--but it is also undecidable. (More specifically, if A implies B, then algorithms exist that will tell you this in a finite amount of time. However, if A does not imply B, then your computing program will end up performing calculations for ever, never giving you an answer.)

[@RMarsupial]

Wait wait wait... I'm really confused. How can people think "space is euclidean"? Surely, as soon as you look at a ball or any curved surface you can see it is not? Also, how is the parallel postulate unprovable? I don't understand how it can possibly be untrue in Euclidean maths. Really,@2:30 where he starts talking about Saccheri, I get lost. I don't understand how this (or much afterwards) is related to the first part about the parallel postulate?

[@KarnKaul]

So if all current maths is based on the True/False axiom - that every proposition can be classified into either category, isn't that presumptuous?

[@bulbmaker]

Luv U granpa for your math science stories :)

[@Seegalgalguntijak]

So are there things that are undecidable, or not?

[@m93sek]

what is the name of these"slow uptake" people gauss talks about. I dont really understand it when the prof says it. Does anybody know?

[@robmoss858]

fascinating stuff.

[@kingjamie2]

what's the big deal about a proposition being unprovable? Doesn't that just make it an axiom? There are plenty of 'propositions' in for instance linear algebra that are unprovable as well.

[@SpackoEntertainment]

When i see the face of Gauss i automatticly think about the 10 DM Bill.

[@TheRandomInternetGuy]

I love this guy. He reminds me of the Ice King from Adventure Time :D

[@KelemenLajos]

Professor Brailsford, you pronounced the name János excellent, This is how the family name is pronounced: translate.google.com/?hl=hu#hu/en/Bolyai Also, Wolfgang Bolyai was born as Farkas Bolyai.

[@honkatatonka]

Oh wonderful! Science history! More of it! Thank you :)

[@VtotheItotheI]

Could someone please explain to me why the third case, where the parallels went apart, can't be proven by running the same lines as seen on the globe on the inside of a torus?

[@user-wg1nr1lg2p]

This should be on Numberphile, even if it's meant to illustrate a Computerphile idea.

[@b.thorne5652]

I don't understand why the parallel lines problem is so hard to prove, please hear me out a bit. Suppose the sum of those two angles is 180. If the lines aren't parallel, they will eventually cross each other to form a triangle. Since the sum of the interior angles in a triangle is 180 degrees and the third angle is evidently greater than zero, it means that the lines can never cross each other to form a triangle (in Euclidian space) which means they're parallel.

[@Cardgames4children]

+B. Thorne If I remember correctly, the statement "the sum of the interior angles in a triangle is 180 degrees" is actually equivalent to the parallel postulate, and this would be circular reasoning.

[@cottonycloud-]

+B. Thorne You're actually assuming the parallel postulate in your proof, in the part that they will eventually cross to form a triangle, which you are trying to prove.

[@MateusKahler]

Please, could you add subtitles captions in the videos? No really need to translation. Non speakers like me can have a hard time understanding some words =(( specially some technical terms. Thanks!

[@NathanTAK]

Was retirement day literal or was it a euphemism for death?

[@joealias2594]

If the parallel line proposition cannot be proved in Euclidean geometry, doesn't that make it part of the definition of Euclidean geometry? If it does not hold in other geometries, then either it is part of the definition, or it follows from another part of the definition. If you cannot show it from what you think is the definition, perhaps it really is part of the definition. When I learned some basic Euclidean geometry, I learned there we five starting propositions you just had to accept because they were what set up the rules for how to work in Euclidean space, the fifth being the parallel line one, but that people had always felt like possibly the fifth could be shown to follow from the first four, but could never show it. If one has the unshakable view that geometry must occur on a flat plane, then the fifth proposition is necessarily true, but I think the first four do not imply that you are working on a flat plane. It is the fifth proposition that tells you space is flat (Euclidean.)

Wow... very intersting

[@Resurr3ction]

I think Kurt Gödel follow up video would be wonderful. :-)

[@MrBeiragua]

"even if the answer is 42" lol

[@TiagoSima0]

This!

[@HalcyonSerenade]

We may never know if he chose that number on purpose, but I like to believe he did!

[@lucasferrarisoto4866]

@@HalcyonSerenade Wir müssen wissen!

[@Cypher10110]

Interesting stuff, where can I find more on this topic?

[@A3roboy]

The father-son Bolyai pair are Hungarian, and their names were quite a bit mispronounced here. I don't mind, really, I'm just posting so that people can know: Anyway, in Hungarian "ly" together form a single sound identical to "j" in language, both pronounced like the English "y". Boyai, if you prefer, emphasis on the "o", which is slightly elongated. The vowels are also a bit off but that's less relevant. The "i" at the end is short, like in the word "bit".