Godel’s Incompleteness Theorem – Intro to Theoretical Computer Science

Godel’s Incompleteness Theorem – Intro to Theoretical Computer Science


You may or may not have heard of Godel’s Incomplete Theorem, but since they are also mentioned in conjunction with the Halting Problem and undecidability, it worth saying a few words about them. Godel’s Incompleteness Theorem is named Austrian-born mathematician, Kurt Godel, are concerned with mathematics, but are actually closely related to undecidability and as you might know, any mathematical system starts out with a set of axioms. What are axioms? Axioms are statements which you assume to be true without having any formal proof of them, such as if A equals B and B equals C, then A must also equal C or you can always draw a line from one point to another point, no matter where they are. Those would be axioms. Now axioms often sound very trivial, like this one here or the fact that you can always draw a line between 2 points but for many of them there are actually scenarios where they are not true. So axioms are the basis of any mathematical theorem or proof. Now what Kurt Godel showed, and it was a shocker at his time and to many it is still today, is the following: So what Kurt Godel showed was that if you had a set of axioms and they don’t contradict each other and they are listable, which means you could have an algorithm that lists you all of these axioms, so either they are finite or they can even be infinite as long as you have an algorithm that can produce them all; if this is the case, then there are some statements that are true but which you cannot prove based on these axioms and this is what he meant by incompleteness how he basically showed that no matter what foundation you base a mathematical system on, as long as that is a consistent foundation, then you can not prove everything without adding additional axioms at least. He also showed, and this is the second Incompleteness Theorem, which is basically an extension of the first one that a system of axioms cannot not demonstrate its own consistency and what that means is that very informally, a mathematical system can not be used to show that it itself is consistent. These 2 statements are in a way very similar to the Halting Problem and Undecidability. The axioms; you can think of those as programming statements. So any program or algorithm is composed of a number of simple instructions that are then arranged, and of course there is an infinite number of possible computer programs that you can write, but they are made up of a fine set of building blocks and the second Incompleteness Theorem is of course very similar to undecidability in the sense that it shows that you cannot use a system to prove everything about that system, very loosely speaking, and the undecidability of the Halting Problem and all of the other undecidable problems, of course says that we cannot use algorithms to calculate everything about algorithms. I know that from a practical perspective there’s lots of criticism of this, but truth be told, I just find that super fascinating.

5 thoughts on “Godel’s Incompleteness Theorem – Intro to Theoretical Computer Science”

  1. When you say you can't use algorithms to calculate everything about algorithms, is what you're really saying that not all of mathematics is computable? I think what you meant at 2:40 is you cannot use algorithms to calculate everything that can be manually calculated. Correct?

Leave a Reply

Your email address will not be published. Required fields are marked *