Programmer's Guide To Theory - Gödel And All That
Written by Mike James   
Monday, 16 September 2024
Article Index
Programmer's Guide To Theory - Gödel And All That
Failure of Logic
The Influence of the Infinite

Banner

 

 

 

prooficon

 

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.

cover600

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.

Banner


Yugabyte Improves Postgres Compatibility
24/09/2024

YugabyteDB has been upgraded with what the developers describe as enhanced Postgres capability in the form of new capabilities and architectural enhancements that allow a broader range of Postgres app [ ... ]



MongoDB 8 Reduces Memory Use And Increases Speed
07/10/2024

MongoDb 8 has been released, and the developers have said this is the most secure, durable, available, and performant version of MongoDB yet, with significantly reduced memory usage and query times, a [ ... ]


More News

kotlin book

 

Comments




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

 

 

<ASIN:0195147227>

<ASIN:1568812566>

<ASIN:0393051692>

<ASIN:1568812388>

 



Last Updated ( Tuesday, 17 September 2024 )