CSC438H1: Computability and Logic

Hours: 
24L/12T

Computable functions, Church's thesis, unsolvable problems, recursively enumerable sets. Predicate calculus, including the completeness, compactness, and Lowenheim-Skolem theorems. Formal theories and the Gödel Incompleteness Theorem. Ordinarily offered in years alternating with CSC448H1.

Prerequisite: 
Exclusion: 

MAT309H1; PHL348H1. NOTE: Students not enrolled in the Computer Science Major or Specialist program at the UTSG, UTM, or UTSC are limited to a maximum of three 300-/400-level CSC/ECE half-courses.

Distribution Requirements: 
Science
Breadth Requirements: 
The Physical and Mathematical Universes (5)