Skip to main content
Dantes.io Logo
Dantes.io

Best resources to learnComputability Theory

Study sheet

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.

7 resources · · How we curate

🎓Courses(3)

course

Logic II (MIT 24.242)

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.

intermediate🇬🇧
course

Theory of Computation

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

advanced🇬🇧
course

Theory of Computation (MIT 18.404J)

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.

intermediate🇬🇧

🌐Websites(3)

website

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.

beginner🇬🇧
website

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.

intermediate🇬🇧
website

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.

intermediate🇬🇧

📄Papers(1)

paper

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

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.

advanced🇬🇧
Share this topic

More in Theoretical Computer Science

See all 13 topics in Theoretical Computer Science →

Frequently Asked Questions

Where should I start learning Computability Theory?

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.

What are the best free resources to learn Computability Theory?

Dantes has curated 7 resources for Computability Theory, including 3 courses, 3 websites, 1 papers. All resources are hand-picked for quality — no algorithmic filler. Browse the full list above to find the format that works best for you.

Is Computability Theory hard to learn?

Computability Theory is approachable at the beginner level — there are resources here specifically for those starting from scratch. As you progress, intermediate and advanced material is also available to take your skills further.

What types of Computability Theory learning resources are available on Dantes?

For Computability Theory, Dantes has curated 3 courses, 3 websites, 1 papers. Each resource type serves a different learning style: videos and YouTube for visual learners, books for depth, courses for structured progression, and websites for quick reference.

How does Dantes select Computability Theory resources?

Dantes is an algorithm-free learning directory. Resources are hand-curated based on quality, accuracy, and usefulness — not engagement metrics or paid placements. The goal is to surface the best learning material for Computability Theory, whether it's a free YouTube series, a classic textbook, or an open courseware from a top university.

Go deeper

Test your understanding of Computability Theory

Explain it out loud. An AI tutor listens and asks questions that expose gaps you didn't know you had.