It was in 1931 that Kurt Godel, then aged just 25, published his first incompleteness theorem. On one level it seems so long ago and yet at another so recent. We have only just begun to think about the nature and limits of computation and logic, but Godel was one of the first.

You can argue about who did what or who had most influence but the fact of the matter is that for computer scientists it is Alan Turing that we remember for the breakthroughs in thinking about computation at a very fundamental level. Part of the reason is that Turing thought about computation in a very physical way that models how real computers do it. The logicians and mathematicians, such as Godel and Church, thought in a very different way. For them computation was mathematics and in particular logic. The two frameworks lead to the same conclusions, but Turing's makes ask more direct questions about computation, such as what can be computed in a physically achievable time.

Kurt Friedrich Gödel, 1906 - 1978

Godel's great achievement was to prove two incompleteness theorems. The first states that all consistent formulations of anything equivalent to the theory of numbers based on the Peano axioms include undecidable propositions, i.e. they can neither be proved or disproved. The Peano axioms are very simple and reasonable and so this is something of a shock. The second theorem extends this to state that any consistent system that includes Peano arithmetic cannot prove itself consistent.

As Peano's formulation of arithmetic is so natural and reasonable, what all this comes down to, ignoring technicalities, is that for any system of logic that includes the natural numbers there is a formula which is true, but not provable, within the system. Of course, you can always go outside of the system by adding additional axioms, but then you get new statements which are not provable. There is always something outside of the system that you cannot reason about.

The incompleteness theorems are often used to "prove" weird and wonderful things about natural systems such as the human brain, but they depend on the system having an unbounded nature - an infinity if you like. The human brain is finite and doesn't fit in with the theorem. This is the distinction in computer science between finite state machines, for which there is no halting problem, and Turing machines for which there is. This is because Turing machines, like Peano's arithmetic, are unbounded.

If Godel's theorem's tell us something practical it is about the mathematics of unbounded processes. If you make a conjecture about, say, the integers then you might be able to prove it true or you might be able to prove it false. On the other hand, there may be no proof within the set of axioms you are using to pose the conjecture that it is true or false.

Consider the following problem: there seem to be lots of paired primes, i.e. primes that differ by two (3,5), (5,7), (11,13) and so on. It is believed that there are an infinite number of such pairs - the so called "twin prime conjecture" but so far no proof and no counterexample.

A proof is a finite sequence of steps, but a conjecture is potentially about something that goes on forever and there may be no simple finite proof that sums up the complexity of the infinite process.

While Godel's amazing results are not directly relevant to the practical world, they put limits on how we can reason about infinity, and are a  deep and important achievement.

If you want to know more about the incompleteless theory, see Confronting The Unprovable - Gödel And All That.

•  Mike James is the  author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science, including computability, the halting problem and Turing machines, in an informal and yet informative way.

More Information

Confronting The Unprovable - Gödel And All That

Related Articles

Non-computable numbers

Computability

What is a Turing Machine?

Axiom Of Choice - The Programmer's Guide 

The Programmer's Guide To The Transfinite       

Kolmogorov Complexity

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

<ASIN:0195147227>

<ASIN:1871962439>

<ASIN:0393051692>

<ASIN:1568812388>