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: 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/computerphile
Tweets by computer_phile

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

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