Skip to content
Undecidability Tangent (History of Undecidability Part 1) - Computerphile episode artwork

Oct 13, 2026 18 min

Undecidability Tangent (History of Undecidability Part 1) - Computerphile

from Computerphile Hosted by Computerphile

What was the first undecidable problem? Professor Brailsford takes us on a computerphile tangent & gives us his angle on a pre-computer example of undecidability.Note from Professor Brailsford: a couple of corrections for this film:1/ "... early 18th Century" for Gauss should be " ... early 19th century" 2/ "... 100 years ago" for Newton should be "... 100 years before Gauss3/ The Greek word I was struggling with was "Boeotians". I have now taken expert advice which tells me that the "oe" is pronounced "ee" as in "Oedipus". Hence a reasonable approximation to the correct pronunciation is "Bee-oh-shuns"4/ In my excitement to get the message across I sometimes refer, in the video, to Euclid's 5th axiom being a "proposition". However it is more accurately a "postulate" i.e. something which should be provable from the other axioms/postulates of the Euclidean system. The fact that it can't be thus proved means that the other axioms are insufficiently powerful to prove it -- hence it is "undecidable" within that axiom system."Riemann Hypothesis – Numberphile: http://youtu.be/d6c6uIyieoo Fermat's Last Theorem – Numberphile: http://youtu.be/qiNcEguuFSA Turing & The Halting Problem: http://youtu.be/macM_MtS_w4 http://www.facebook.com/computerphilehttps://twitter.com/computer_phileThis video was filmed and edited by Sean Riley.Computer Science at the University of Nottingham: http://bit.ly/nottscomputerComputerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: http://bit.ly/bradychannels

Episode details come from the podcast's RSS feed.

Embed this episode

Ready to play

Undecidability Tangent (History of Undecidability Part 1) - Computerphile

0:00 18:59

No transcript yet.

Requests help us decide what to transcribe next.

Frequently asked questions

How long is this episode of Computerphile?

This episode is 18 minutes long.

When was this Computerphile episode published?

This episode was published on October 13, 2026.

Can I download this Computerphile episode?

Yes. Use the download control on the episode player to save the publisher-provided media file.