 |
Math 114AB: Logic & Computability |
||||||||||||||||||||||||||||||||||||||||||||||||
Catalog Description
114A-114B. Logic and Computability. Lecture, three hours; discussion, one hour. Prerequisite: course 115A. Propositional and predicate logic; syntax and semantics; formal deductions; completeness and compactness; Herbrand expansions. Effectively computable, Turing computable, and recursive functions; Church's thesis. Universal functions; unsolvability results. Recursive and recursively enumerable sets; recursive enumerability of valid sentences. Formal number theory; definability of recursive functions; incompleteness and undecidability; theorems of Goedel, Tarski, Church. P/NP or letter grading.
|
||||||||||||||||||||||||||||||||||||||||||||||||
General Information
The course 114AB stands at the crossroads of mathematical logic and computer science. It explores such concepts as computation, proofs, and truth. Some typical questions:
If a sentence is "true", is there necessarily a "proof" of it? What is the connection between "computations" and "proofs"? Some of the major goals are these results: The completeness theorem for first-order logic, which shows that the concept of provability (from axioms) can be completely nailed down. The unsolvability of the halting problem, which shows that it is impossible to do everything. The Goedel incompleteness theorem, which shows that there is an inherent gap between what is true (about the natural numbers, for example) and what can be proved in a formal system. |
||||||||||||||||||||||||||||||||||||||||||||||||
Recent Enrollment Statistics |
||||||||||||||||||||||||||||||||||||||||||||||||
Course 114A is offered in alternate years. |
||||||||||||||||||||||||||||||||||||||||||||||||