End of the Dream

It’s as if mathematics at the turn of the 20th century was seeking the ultimate theory of everything and Gödel proved that this just wasn’t possible. So far so good, or bad depending on your point of view. You may even recognize some of this theory as very similar to the theory of Turing machines and non-computability, in which case it might not be too much of a shock to you. However, at the time they were thought up both Gödel’s and Turing’s ideas were revolutionary and they were both regarded with suspicion and dismay.

It was thought to be the end of the dream: mathematics was limited. Mathematics wasn’t perfect and in fact every area of mathematics contained its limitations. Today you will find it argued that Gödel’s theorem proves that God exists. You will find it argued that Gödel’s theorem proves that human thought goes beyond logic. The human mind is capable of seeing truth that mathematics cannot prove. It is also argued that it limits artificial intelligence, because there are things that any machine cannot know and hence also proves that human intelligence is special because it can know what the machine cannot.

If you think about it, Gödel’s theorem proves none of this. It doesn’t even suggest that any of this is the case. Gödel’s theorem doesn’t deal with probabilities and what we believe, only in the limitations of finite systems in proving assertions about the infinite. Sometimes the infinite is regular enough to allow something to be proved. Sometimes, in fact most of the time, it isn’t. But important though this is, we live in a finite personal universe and we don’t demand perfect proof. We go with the flow, guess and accept good probabilities as near certainties.

And if you eliminate the infinite, Gödel's theorem doesn't hold.

Summary

• Mathematical proof can be considered to be a game with symbols, axioms, that lead to proof. It was thought that this implied that math can be mechanized and reduced to an algorithm.

• Many mathematical questions can be answered by an infinite search procedure. Not finding a counter example doesn’t prove anything and the power of math is in providing finite proofs for infinite searches.

• Gödel proved that in any system of logic that was powerful enough to include arithmetic there were theorems that were true but for which a proof using the axioms of the system did not exist.

• The incompleteness theorem was revolutionary and put a limit on what could be done with axiomatic systems. It has also been used, incorrectly, to prove many things such the existence of God and the inability of AI to equal real intelligence.

• What the incompleteness theorem is saying is that there are some truths that cannot be established by a finite procedure, i.e. a proof.

• If you expand the axioms to create a larger logical system then it is possible that what was unprovable becomes provable. The only problem is that new unprovable theorems are introduced.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

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:1568812566>

<ASIN:0393051692>

<ASIN:1568812388>