Undecidability Tangent (History of Undecidability Part 1) – 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 Gauss

3/ 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:
Fermat’s Last Theorem – Numberphile:
Turing & The Halting Problem:

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham:

Computerphile is a sister project to Brady Haran’s Numberphile. See the full list of Brady’s video projects at:

Products You May Like

Articles You May Like

29 Early Sports Rules – mental_floss List Show (Ep.223)
MrBeast’s $1,000,000 Dilemma
Does hitting the snooze button help? – Big Questions – (Ep. 34)
Learning About Lightning from Superbolts
You Are Not Where You Think You Are

Leave a Reply

Your email address will not be published.