Functions computable by programs; recursive functions and Turing machines; simulation and diagonalization; universality and unsolvable problems; recursively enumerable sets and the recursion theorem; Gregorczyk's hierarchy and Ackermann's function; abstract complexity theorem; formal languages and classes of automata.
Arithmetic Undecidability G22.2355,2356 Identical to G63.2270, 2280. 3 points.
A rapid introduction to 20th-century mathematic logic assuming no previous knowledge of the subject. The emphasis is on Godel's incompleteness theorem and on undecidability results for Diophantine equations. The completeness of first order logic and the Skolem-Lowenheim theorem will also be covered.
Theory of Computation (Honors) G22.3350 Prerequisites: one semester of undergraduate theory of computation or formal languages and permission of the instructor. 4 points.
Formal languages: regular languages, regular expressions, finite-state machines, context-free languages, grammars, and pushdown machines. Computability: primitive recursive functions, partial recursive functions, recursive languages, recursively enumerable languages, and Turing machines. Computational complexity: space and time complexity, complexity classes (such as P, NP, PSPACE, L, and NL), and complete problems.
GSAS /
NYU
-- last modified 24 September 1996