Confronting The Unprovable - Gödel And All That
Written by Mike James   
Thursday, 20 December 2018
Article Index
Confronting The Unprovable - Gödel And All That
Failure of Logic
The Influence of the Infinite

Banner

 

If you have taken Gödel’s theorem to heart you should know that this doesn’t have to be the case. The integers go on forever and you can’t actually decide the truth of the theorem by looking at the integers.

How far do you have to go without seeing a pair of primes to be sure that you aren’t ever going to see another pair?

How many pairs do you have to see to know that you are going to keep seeing them?

There is no answer to either question. In the same way why do you assume that there is a finite number of steps in a proof that will determine the answer.

Why should the infinite be reducible to the finite?

Only because we have grown accustomed to mathematics performing this miracle.

In the case of the twin prime conjecture recent progress has proved that that are infinitely many primes separated by N and N has to be less than 70 million. This doesn't mean that N is 2 however. Collaborative work by a lot of mathematicians has reduced the upper limit (at the end of 2013) to less than 576 which seems like progress. Can the bound be pushed down as far as 2 or is there really no proof? 

Fermat’s last theorem stated that the only integer solution to a particular equation was when n equals 2. To prove this the hard way requires examining the equation for n equal to 1, 2, 3…  and for all a,b and c and this means we have to test an infinite number of possibilities.

Yet we have a finite proof.

We have a logical derivation of the truth of the theorem, which doesn’t involve testing an infinite number of cases.

This is what Gödel’s theorem really is all about.

There are statements that are undecidable. If you add additional axioms to the system the statements that were undecidable might well become decidable but there will still be valid statements that are undecidable. Indeed every time you expand the axioms you increase the number of theorems that are decidable and undecidable. 

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 recognise 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.

 

prooficon

 

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 it you eliminate the infinite Godel's theorem doesn't hold.

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

 

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

raspberry pi books

 

Comments




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

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.

 

<ASIN:0195147227>

<ASIN:1568812566>

<ASIN:0393051692>

<ASIN:1568812388>

 



Last Updated ( Thursday, 20 December 2018 )