Computability theory wiki

Welcome to the Computability theory wiki, a comprehensive resource dedicated to the study of computability and recursion theory. This wiki aims to provide clear and rigorous definitions of core terminology, as well as structured mini-courses to facilitate learning at different levels. See the computability portal for a list of members, books, articles and videos on the subject.

• Definitions – Precise explanations of key concepts in computability theory, such as Turing machines, recursive functions, and degrees of unsolvability.
• Mini-courses – Structured lessons ranging from introductory topics to advanced subjects in computability and logic.
• Theorems and Proofs – Formal statements of fundamental results, including classical and modern developments.
• Applications – Discussions on how computability theory connects to other areas, such as complexity theory, logic, and philosophy.
• Open Questions – A list of unresolved problems in the field for those interested in research directions.

Use the navigation menu or search bar to explore different topics. You can start with:

• Computability theory in a nutshell

• Rice's theorem
• SMN theorem
• Undecidability of the halting set

• Turing degree

• Sets, sequences and real numbers
• Incompleteness theorems as paradoxes
• Reducibilities on sets
• Reducibilities on problems

• Introduction to models of computation
• Introduction to classical computability theory
• Introduction to reverse mathematics
• Introduction to algorithmic randomness

This wiki is a collaborative effort! If you have expertise in computability theory and would like to contribute, feel free to edit pages or suggest new content.

For any questions or suggestions, visit the Contact Page.

Happy learning!