90 Years Since Kurt Godel Showed Us What We Cannot Know 
Written by Mike James 
Friday, 18 June 2021 
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
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.
More InformationConfronting The Unprovable  Gödel And All That Related ArticlesAxiom Of Choice  The Programmer's Guide The Programmer's Guide To The Transfinite 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
or email your comment to: comments@iprogrammer.info <ASIN:0195147227> <ASIN:1871962439>
<ASIN:0393051692> <ASIN:1568812388>

Last Updated ( Friday, 18 June 2021 ) 