Computer science and the theory of computation has much to say about philosophy and mathematics. In particular, what is computable is closely connected to what is provable and hence what is knowable in mathematics.

The recent Yip lecture at Harvard gave Scott Aaronson, our favourite quantum computer expert the chance to widen his scope with a look at the interaction of computing, philosophy, logic and mathematics. It is clear that computer science puts limits on what is computable but what does this mean for endeavours that use computation like math?

The talk is full of really fun, interesting and, yes, mind boggling examples that make the talk unmissable. The key observation is that we are finite beings trying to deal with the infinite. The first example in the lecture makes the problem plain. The Goldbach Conjecture is that every even number greater than 2 can be expressed as the sum of two primes. This is a simple conjecture and it has been validated computationally for very large numbers. You should be able to see the problem - to prove the conjecture you would have to compute the decomposition for every number from 4 to infinity and this isn't possible. To disprove the conjecture all you have to do is find a counter example - but if one doesn't exist you have to go to infinity again. Many questions in mathematics are like this in that they in principle involve an infinite number of test cases. 

For example, suppose you didn't know that Pythagoras' Theorem was true.  You would be in exactly the same position as the Goldbach Conjecture in that you could only prove it true by testing every possible right-angled triangle. In this case the infinity involved is of a higher order - there are Aleph 1 triangles and only Aleph 0 integers - but it is the same problem. But wait. we do know that Pythagoras' theory is true - so how can this be? The simple fact is that some infinite problems have regularities which allow a finite proof that renders the infinite testing unnecessary.  Is the Goldbach conjecture regular enough for the to be a proof? Who knows.

The lecture opens with a way to compute the test of the Goldbach conjecture in finite time. Simply perform the tests in decreasing time sequence. In the first second, test for 4; in the next half a second, test for 6, in the next quarter of a second; test for 8 and so on. After two seconds you have your answer. Of course. this is based on Zeno's Paradox and there are many problems with Zeno's Paradox. At a physical level we cannot simply increase computational speed without limit - quantum mechanics puts a limit, for example, in the form of the "Planck Time".

The lecture goes on to consider the crazy Busy Beaver functions and how evaluating BB(6) is likely beyond us -  and it isn't even infinite. Next, we have the all important P!=NP Conjecture and what it does and doesn't tell us about what can be known. Finally we have some fanciful imaginings of how computability could be extended. All great fun and it should convince you that computer science is fundamental:

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way. Another of his books, The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, examines the nature of programming and reveals why it is a very special skill.

More Information

Goldbach Conjecture

Related Articles

Goldbach Conjecture - Closer to Solved?

Busy Beaver 6,2 Is Just Too Big!

BusyBeaver(5) Is 47,176,870

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info