Ma/CS 117 abc

Computability Theory

9 units (3-0-6)  |  first, second, third terms
Prerequisites: Ma 5 or equivalent, or instructor's permission.
Various approaches to computability theory, e.g., Turing machines, recursive functions, Markov algorithms; proof of their equivalence. Church's thesis. Theory of computable functions and effectively enumerable sets. Decision problems. Undecidable problems: word problems for groups, solvability of Diophantine equations (Hilbert's 10th problem). Relations with mathematical logic and the Gödel incompleteness theorems. Decidable problems, from number theory, algebra, combinatorics, and logic. Complexity of decision procedures. Inherently complex problems of exponential and superexponential difficulty. Feasible (polynomial time) computations. Polynomial deterministic vs. nondeterministic algorithms, NP-complete problems and the P = NP question. Not offered 2021-22.

Please Note

The online version of the Caltech Catalog is provided as a convenience; however, the printed version is the only authoritative source of information about course offerings, option requirements, graduation requirements, and other important topics.