10.3 Church Turing
The purpose of computability theory is to make precise the idea of an effective procedure. Informally, an effective procedure is a method that can be followed step by step, without guesswork, and which produces an answer after finitely many steps whenever it is meant to halt. The central question is whether this informal idea can be captured by a formal mathematical definition. Recursive functions give one such definition. Turing machines...