---
title: Computability Theory
description: Computability theory explores which mathematical problems can be solved using an algorithm and which cannot. Learners will understand the halting problem, Turing degrees, and the fundamental limits of what computers can mathematically calculate.
category: programming-tech
subcategory: theoretical-computer-science
difficulty: beginner, intermediate, advanced
url: /subject/computability-theory
---

# Computability Theory

Computability theory explores which mathematical problems can be solved using an algorithm and which cannot. Learners will understand the halting problem, Turing degrees, and the fundamental limits of what computers can mathematically calculate.

## Where to start

Start with Theory of Computation (MIT 18.404J), Michael Sipser's free MIT OpenCourseWare course, whose lecture videos and problem sets build from automata to decidability and reducibility. It is also the most complete single resource here. For the next step, Vann McGee's Logic II (MIT 24.242) moves on to Gödel's incompleteness theorems and Church's undecidability theorem.

## Available Resources

3 Courses • 3 Websites • 1 Papers

## Courses

### 1. Logic II (MIT 24.242)

**Author:** Vann McGee

Computability theory followed by a detailed study of Gödel's incompleteness theorems and their applications, including Church's undecidability theorem and Tarski's theorem on the undefinability of truth. Lecture notes and problem sets with solutions let learners work through these proofs themselves.

**Difficulty:** Intermediate | **Price:** Free

**Link:** https://ocw.mit.edu/courses/24-242-logic-ii-spring-2004/

**Tags:** incompleteness-theorems, computability, undecidability, tarski-undefinability, recursion-theory

### 2. Theory of Computation

Learn computability theory with Kamala Krithivasan's Theory of Computation course. Explore fundamental concepts and problem-solving!

**Difficulty:** Advanced | **Price:** Free

**Link:** https://nptel.ac.in/courses/106105163

**Tags:** theory-of-computation, automata, turing-machines, formal-languages, decidability

### 3. Theory of Computation (MIT 18.404J)

**Author:** Michael Sipser

Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study.

**Difficulty:** Intermediate | **Price:** Free

**Link:** https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/

**Tags:** automata-theory, computability, decidability, complexity-theory, np-completeness

## Websites

### 1. nLab Computability

nLab wiki entry on computability, relating Turing machines, partial recursive functions, and realizability to type theory and category theory. Useful for readers who already know basic computability and want to see how it connects to constructive mathematics and topos theory.

**Difficulty:** Beginner | **Price:** Free

**Link:** https://ncatlab.org/nlab/show/computability

**Tags:** computability, category-theory, type-theory, realizability

### 2. theoryofcomputing.org

Theoryofcomputing.org is a practical resource hub for theory of computation, featuring lecture notes, tutorials, and problem sets on automata, formal languages, computability, and complexity to help learners build intuition and tackle exercises.

**Difficulty:** Intermediate | **Language:** English | **Price:** Free

**Link:** https://theoryofcomputing.org

**Tags:** websites, technology-computer-science, computer-sciences

### 3. brilliant.org

Brilliant.org is an online, interactive learning platform offering problem-based courses in math and computer science, including topics in automata theory, computation, and discrete mathematics, with guided lessons and practice problems.

**Difficulty:** Intermediate | **Language:** English | **Price:** Free

**Link:** https://brilliant.org

**Tags:** websites, technology-computer-science, theoretical-computer-science

## Papers

### 1. On Computable Numbers, with an Application to the Entscheidungsproblem (1936)

**Author:** Alan M. Turing

The founding paper. Turing defines his machines, builds a universal machine, proves by diagonalisation that no machine decides halting, and settles Hilbert's Entscheidungsproblem negatively. Reading it shows where every later definition of computability came from.

**Difficulty:** Advanced | **Language:** English | **Price:** Free

**Link:** https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

**Tags:** turing-machines, halting-problem, entscheidungsproblem, universal-machine, history-of-computing

---

*This content is part of Dantes.io - Your Treasure Map to Knowledge*

*Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).*

View this page online: https://dantes.io/subject/computability-theory