CS 70 Discrete Mathematics and Probability Theory

Spring 2015 Vazirani Note 11

Self-Reference and Computability

In this lecture we will explore the deep connection between proofs and computation. At the heart of this

connection is the notion of self-reference, and it has far-reaching consequences to the limit of computations

(the Halting Problem) and the foundation of logic in mathematics (Gdels incompleteness theorem).

The Liars Paradox

Recall that propositions are statements that are either true or false. We saw before that some statements are

not well dened or too imprecise to be called propositions. But here is a statement that is problematic for

more subtle reasons:

  ...