Theoretical Computer Science: Computability, Decidability and Logic

This chapter deals with a question in the very core of IA: what can be computed by a machine? An agreement has been reached on the answer brought by Alan Turing in 1936. Indeed, all other proposed approaches have led to exactly the same answer. Thus, there is a mathematical model of what can be done by a machine. And this has allowed to prove surprising results which feed the reflection on intelligence and machines.