Incompleteness
Consider the following statement:
This statement cannot be proved true in this language
If we have a supercomputer that can theoretically answer the question, there are really only 2 outputs:
Paradox
Answer 1 is:
The statement is true
This means the computer could not find a way to prove it in the language.
This however meant the original statement was false, because it was proved true.
This is the one paradox, where it is a self-reference loop.
The answer negates the premise, and the negative premise is then double negated, in an endless loop.
Unprovable
Answer 2 is:
This statement cannot be proved
The statement is true, but it still can’t be proved.
This means the system is either inconsistent or incomplete.
This example is simple enough to create, because natural language is very inconsistent.
You can order words in any way you’d like to make all sorts of illogical jumps.
Gödel
What about mathematics?
It is designed to be perfectly self consistent.
Kurt Gödel was a mathematician who lived in the early 20th century, and is widely regarded as one of the greatest logicians to ever exist.
Gödel’s Incompleteness Theorems
1. In any consistent system that is capable of describing basic arithmetic, there exist statements that are true but cannot be proven within the system.
2. A system cannot prove its own consistency. This implies that certain statements about consistency or the existence of proofs are unprovable within the system itself.
Because some concepts in mathematics are unprovable,
this must mean that mathematics is incomplete.
And since algorithms exist on top of mathematics, they too must be incomplete.
In summary, Gödel’s 2nd theorem states that no system can be self consistent, that is to say you always need an observer from outside of the system to be able to prove it’s consistency.
This means that even a system built purely from self-consistency will still run into incompleteness, unless viewed from outside of itself.