More than eighty five years ago Kurt Gödel proved, roughly speaking, that no fixed set of a formal facts (like 23+14=37) and rules (like x+y = y+x) can establish the truth or falsity of every theorem about arithmetic over the counting numbers.

This result, known as Gödel’s Theorem, has a lot of formal and informal consequences. It means there is no computer program that can infallibly decide whether or not a statement about arithmetic is true or false. It means we will never know everything about arithmetic, though we may know more and more as time goes on. It means, however, that this knowledge will not come about purely as a result of manipulating formal facts and rules. We will have to rely on other sources, including experiment.

Even more interesting is the fact that this situation – the limits of facts and rules – reappears in other domains, including games, natural language, and even psychology.

Continue reading →