I am not a true statement.

Not only is this sentence rather paradoxical in meaning (if it’s false, it’s true; it it’s true, it’s false), but it is also self-referential. This is rather an odd thing for a sentence to be.

Mathematics is not about numbers, not really. Math is about logic and objectivity. It is about creating a system that is useful for solving real world problems. Such systems are based on axioms, assumptions. These axioms are like the foundation of a house, they are not proven, they are just accepted. Axioms are like primary colors, if we start with ‘axioms’ red, and blue, we can mix a multitude of various shades by combining these colors. These combinations ‘purple’, are like theorems. Note that if we start with different primary colors – perhaps blue and yellow, we get an entirely different set of color-theorems. It is the same way with math; different systems develop depending on which axioms we assume up front. Systems like “Natural Numbers”, “Integers”, “Real Numbers”, all have different axioms at their origin. But they are all useful, depending on the situation.

The interesting question to ask is, are any of these systems “perfect”. Perfection in this sense would mean two things: every true statement about numbers could be proven with the system (every true statement is a theorem), and nothing could be proved with the system that is false. Up until Kurt Godel, it was generally believed that there was such a system – a perfect, mathematical theory of everything.

In 1931, Kurt Godel proved this theory incorrect. He proved that any formal system is fundamentally incomplete (hey, the title!). The way he did it was incredibly clever, and cemented his mathematical legacy at the age of 25. The method of the proof was to assume that the formal system WAS complete and then discover a logical inconsistency that derives from this assumption, thereby proving that the assumption of completeness was false.

The first step of his proof was to create a translation of a formal statement into numbers. For each symbol of the system, he created a mapping to a number. For example, we could assign “123″ to the symbol “0″ and “111″ to the equals sign. The statement “0=0″ becomes the number “123111123″. Whereas the former is a statement about numbers, the latter is a number about numbers. They both mean the same thing, that zero equals zero, but the latter is a number. 123111123 is a theorem of the formal system. And now the previous sentence is a new theorem of the formal system. This mapping has created a new property of numbers – “thoeremhood”. This property is just like any other property of numbers like, “perfect square”, “prime”. Some numbers will have it, others will not. Since our formal system is capable of expressing all properties of numbers, we can state this theorem in the formal system itself. What this means is that a theorem can assert the truth of another theorem.

Let’s go back to the sentence that I started with “I am not a true statement”. If we could express that theorem in the formal system, we would have discovered an inconsistency. We saw how to express the “am not a true statement” above – this is the property of theoremhood. We need to figure out the statement in the formal system that equates to “I”, and encode it with the number trick, and then we can assert that this number does NOT have theoremhood.

To do so, we need one more piece of cleverness. We can take the statement of the variable (in the sentence, this is the subject, the word “I”), and replace it with the entire sentence. That is “I am not a true statement” becomes “I am not a true statement is not a true statement” This allows the self referentiality we are looking for. We can call this trick “Arithmoquining” after Douglas Hofstadter. When you arithmoquine a statement, the statement makes a statement about itself. We can perform the same trick with a number-encoded theorem. We can start with the theorem “the arithmoquine of this statement is not a valid theorem-number”, and then arithmoquine it to be:

The arithmoquine of “the arithmoquine of this statement is not a valid theorem-number” is not a valid theorem-number. And voila – the formal system is defeated. This can be expressed in the formal system itself, so the formal system is fundamentally incomplete.

This has interesting implications for artificial intelligence. Computer programs are, after all, formal systems. If we want a computer to be able to make new discoveries, we must first provide it with the basics of the problem (axioms), and then rules to operate on these axioms to derive new observations (theorems). In this light, the question is, is there anything that is true, but that a machine could never discover? Further, is there anything that a machine will believe to be true, but in fact not be? Many have argued that Godel has proven the impossibility of machine intelligence, at least that of rivaling human intelligence, saying that there are always things a human can discover that a machine cannot, as a machine is bound by this fundamental incompleteness and a human is not.

I will not posit a definitive answer to this question, but I think it is important to consider that creating intelligence does not necessarily equate to creating human intelligence. There are likely many scenarios where a non-human intelligence is better suited to a specific problem, and who is to say which is superior? What would it even mean to call an intelligence “superior”?

One final thought, while it is possible that computer intelligences may in fact be susceptible to believing in things that are false, isn’t that just the human notion of an “opinion”?

For more on this, I highly recommend the book Godel Escher Bach by Douglas Hofstadter.