Phone: x33205
e-mail: garson@uh.edu
One goal of this course is to prove the three most important theorems
in logic and the foundations of mathematics. These are Turing's Theorem
(There is no method to determine whether a computer program will halt),
Church's Theorem (Predicate Logic has no Decision Procedure), and Goedel's
Theorem (Arithmetic is Incomplete). The course will begin with a thorough
hands on exploration of Turing machines, and then apply lessons learned
here to predicate logic and then arithmetic. There will be numerous exercises,
many using the software Turing's World. After each theorem has been proven,
we will explore its implications for issues in the philosophy of mathematics.
Text: Boolos and Jeffrey, Computability and Logic
There will be two in class Quizes and a Final.