This course has two themes: computability and logic. In the first part of the course (chapters 1-8 of our text), we characterize what it means (classically) for a function to be computable. We develop three different definitions of computability, using Turing machines, abacus machines and recursive functions. This part of the course concludes by demonstrating that all three definitions are equivalent: any function that counts as computable on one of the definitions also counts as computable on the other two as well. This equivalence result provides some support for Church’s Thesis (which states that all effectively computable functions are recursive functions).
The second part of the course (chapters 9-14) develops some of the main ideas of intermediate logic. For this part, we assume that you have a solid grasp of predicate logic. That is, you should understand truth-functional connectives and quantifiers; you should be able to symbolize English sentences in a formal language; and you should know how to construct proofs in first-order predicate logic. Rather than doing proofs within a system of predicate logic, our principal aim in this course is to prove important facts about our system of predicate logic itself.