No fim da primeira aula o Duilio me pediu indicações de leitura sobre os trabalhos de Gödel e do Turing a que me referi em aula. Aqui vão algumas.
A Wikipedia é um ponto de partida bem confiável para assuntos de Matemática e Computação; em geral os textos em inglês são mais completos e bem produzidos que os em português. Recomendo procurar nela: Godel, Incompleteness theorem, Turing, Halting problem.
Uma apresentação menos detalhada mas que aponta bem as ideias são as transparências do Prof. Walter Carnielli, da Unicamp. Valem também as referências ao final delas. O livro de Carnielli e Epstein pode ser um pouco pesado nesta altura do campeonato. Já, o livro do Hofstadter, me lembro de ter achado fantástico quando li (no ano em que foi publicado ); ele cobre muito mais que este assunto, e além de instrutivo é bem humorado. Acho que dá prá entender muito, ele foi escrito para público sem formação específica em Matemática. Só precisa não ter medo de 800 páginas. Talvez não dê para encontrar em português.
Finalmente, um texto de tamanho médio, que está mais para um apanhado histórico (em inglês) foi escrito por S. Barry Cooper. (é um pdf que demora um pouco prá carregar)