Tuesday, October 21, 2008

In Our Time - Gödel's Incompleteness Theorems

The first two programmes of the 2008 season were a bit dull, but Melvyn has picked up the pace nicely with a piece on Godel’s incompleteness theorem …

BBC - Radio 4 In Our Time - Gödel's Incompleteness Theorems
…Marcus du Sautoy, Professor of Mathematics at Wadham College, University of Oxford
John Barrow, Professor of Mathematical Sciences at the University of Cambridge and Gresham Professor of Geometry
Philip Welch, Professor of Mathematical Logic at the University of Bristol..

Terrific guests and Melvyn was in good form. He seemed genuinely interested, whereas in the prior two I thought he was pushing the topic along. He does very well with math and physics, perhaps because they aren’t his primary study.

I was a bit disappointed they never mentioned Hofstadter’s Godel, Escher, Bach, but it has been about 30 years (!) since that was a best-seller. Yes, I not only read the entire thing thoroughly, I also took copious notes (since lost). I was one of four people who actually read it.

Towards the end of the show one of the guests mentions that geometry was not complex enough to trigger the incompleteness clause that one can state true things that cannot be proven true. Number systems of course are incomplete in the Godelian sense, and he thought that was somehow (lost me here) related to the role of prime numbers arising from arithmetic systems. In the same context he mentioned that Turing’s proof of the Halting Problem was equivalent to the incompleteness theorem.[1]

Naturally I immediately leapt to wondering if someday someone will prove that the relationship between the primes and Godel’s theorem means the unpredictability of prime numbers is a likewise provable. That would be reassuring to users of encryption systems!

[1] Everyone’s heard of Wikipedia, so why doesn’t h2g2 get more credit? Their discussion of the Halting Problem is much more sophisticated than the Wikipedia article.

No comments: