====== 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 [[http://portal.computability.org|computability portal]] for a list of [[http://portal.computability.org/directory|members]], [[http://portal.computability.org/books|books]], [[http://portal.computability.org/publications|articles]] and [[http://portal.computability.org/videos|videos]] on the subject.

===== What you will find here =====
  * **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.

===== How to Navigate =====
Use the navigation menu or search bar to explore different topics. You can start with:
  * [[introduction:computability|Computability theory in a nutshell]]


===== Main theorems =====

  * [[theorem:rice|Rice's theorem]]
  * [[theorem:smn|SMN theorem]]
  * [[theorem:undecidability_halting_set|Undecidability of the halting set]]


===== Main concepts =====

  * [[turing_degree|Turing degree]]


===== Topics =====


  * [[topic:sets_sequences_reals|Sets, sequences and real numbers]]
  * [[topic:incompleteness_paradox|Incompleteness theorems as paradoxes]]
  * [[topic:set_reducibilities|Reducibilities on sets]]
  * [[topic:problem_reducibilities|Reducibilities on problems]]

===== Learning material =====

  * [[course:computational_models|Introduction to models of computation]]
  * [[course:classical_theory|Introduction to classical computability theory]]
  * [[course:reverse_mathematics|Introduction to reverse mathematics]]
  * [[course:algorithmic_randomness|Introduction to algorithmic randomness]]
===== Contributing =====
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:start|Contact Page]].

Happy learning!