2006 was a special year for both mathematical logic and computer science, as it celebrated Gödel's centenary. Although Gödel's work was mainly concerned with mathematics and metamathematics, the crucial role it had in the foundation of modern theoretical computer science is undeniable: for instance, one only has to remember Gödel's contributions to the birth of recursion theory as well as his part in the debate in the nineteen thirties on the subject of the Church Thesis.