We're still actively developing this site. If you encounter any issues, please report them! - Report an issue

COMPUTABILITY THEORY

MATH 773
Course Description

Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite and infinite injury, Friedberg-Muchnik and Sacks Splitting Theorem, Sacks Jump and Sacks Density Theorems, computable ordinals. Familiarity with the topics in a basic Foundations course such asMATH 770is strongly recommended.

Prerequisties

Graduate/professional standing or member of the Pre-Masters Mathematics (Visiting International) Program

Satisfies

This course does not satisfy any prerequisites.

Credits

Not Reported

Offered

Not Reported

Grade Point Average
3.1

-10.91% from Historical

Completion Rate
90%

-2.06% from Historical

A Rate
20%

-70.4% from Historical

Class Size
10

116.22% from Historical

Instructors (2025 Fall)

Sorted by ratings from Rate My Professors

Similar Courses

COMPUTATIONAL COMPLEXITY

COMPSCI 710

Study of the capabilities and limitations of efficient computation. Relationships between models representing capabilities such as parallelism, randomness, quantum effects, and non-uniformity; and models based on the notions of nondeterminism, alternation, and counting, which capture the complexity of important problems. Knowledge of the theory of computation is strongly encouraged, such asCOMP SCI 520.

INTRODUCTION TO THEORY OF COMPUTING

COMPSCI 520

Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.

SET THEORY

MATH 771

Martin's Axiom, Suslin and Aronszajn trees, diamond principle, absoluteness and reflection, constructible universe, and one-step forcing constructions. Familiarity with the topics in a basic Foundations course such asMATH 770is strongly recommended.

FOUNDATIONS OF MATHEMATICS

MATH 770

First-order logic syntax and semantics, Completeness and Compactness Theorems, Lowenheim-Skolem Theorem, computable and computably enumerable sets, Incompleteness Theorem, axioms of Zermelo-Fraenkel set theory with choice, ordinal and cardinal arithmetic.

MODEL THEORY

MATH 776

Review of compactness and some consequences. Quantifier elimination with examples. The omitting types theorem. Categoricity. Baldwin-Lachlan theory. Strongly minimal and o-minimal theories. Saturated models. Morley's theorem. Familiarity with the topics in a basic Foundations course such asMATH 770is strongly recommended.