Category:Computability theory
![]() | Computing portal |
Here is a list of articles in the Computability theory category of the Computing portal that unifies foundations of mathematics and computations using computers.
This category is for articles about recursion theory, also called computability theory, which is a branch of mathematical logic and computer science concerned with generalizations of the notion of computable function, and with related concepts such as Turing degrees.
Subcategories
This category has the following 7 subcategories, out of 7 total.
C
E
H
L
R
T
Pages in category "Computability theory"
The following 107 pages are in this category, out of 107 total.
- Computability theory (computing)
*
- Computability (computing)
- List of undecidable problems (computing)
A
- Ackermann function (computing)
- Admissible numbering (computing)
- Algorithm characterizations (computing)
- Alpha recursion theory (computing)
- Analytical hierarchy (computing)
- Arithmetical hierarchy (computing)
- Arithmetical set (computing)
- Automatic group (computing)
- Automatic semigroup (computing)
B
- Basis theorem (computability) (computing)
- Bounded quantifier (computing)
- Busy beaver (computing)
- Busy Beaver game (computing)
C
- Chain rule for Kolmogorov complexity (computing)
- Church–Turing thesis (computing)
- Church–Turing–Deutsch principle (computing)
- Circuit satisfiability problem (computing)
- Complete numbering (computing)
- Computability logic (computing)
- Computable analysis (computing)
- Computable function (computing)
- Computable isomorphism (computing)
- Computable number (computing)
- Computation (computing)
- Computation in the limit (computing)
- Computational theology (computing)
- Course-of-values recursion (computing)
- Craig's theorem (computing)
- Creative and productive sets (computing)
D
- Decision problem (computing)
- Description number (computing)
- Double recursion (computing)
E
- Effective method (computing)
- Effective Polish space (computing)
- ELEMENTARY (computing)
- Entscheidungsproblem (computing)
- Enumerator (computer science) (computing)
F
- Fast-growing hierarchy (computing)
- Forcing (recursion theory) (computing)
- Friedberg numbering (computing)
G
- Gödel numbering for sequences (computing)
- Grzegorczyk hierarchy (computing)
H
- Halting problem (computing)
- Hardy hierarchy (computing)
- High (computability) (computing)
- History of the Church–Turing thesis (computing)
- Hyperarithmetical theory (computing)
I
- Incompressibility method (computing)
- Index set (recursion theory) (computing)
K
- K-trivial set (computing)
- Kleene's recursion theorem (computing)
- Kleene's T predicate (computing)
- König's lemma (computing)
- Kőnig's lemma (computing)
- Kolmogorov complexity (computing)
- Krivine machine (computing)
L
- Lambda calculus (computing)
- Lempel-Ziv complexity (computing)
- LOOP (programming language) (computing)
- Low (computability) (computing)
- Low basis theorem (computing)
M
- Many-one reduction (computing)
- Martin measure (computing)
- Maximal set (computing)
- McCarthy Formalism (computing)
- Model of computation (computing)
- Μ operator (computing)
- General recursive function (computing)
- Μ-recursive function (computing)
- Myhill isomorphism theorem (computing)
N
- Normal form (abstract rewriting) (computing)
- Numbering (computability theory) (computing)
O
- Oracle machine (computing)
P
- PA degree (computing)
- Π01 class (computing)
- Post correspondence problem (computing)
- Post's theorem (computing)
- Primitive recursive function (computing)
- Primitive recursive functional (computing)
- Primitive recursive set function (computing)
R
- Recursion (computer science) (computing)
- Recursive language (computing)
- Recursive ordinal (computing)
- Recursive set (computing)
- Recursively enumerable set (computing)
- Recursively inseparable sets (computing)
- Reduction (recursion theory) (computing)
- Reverse mathematics (computing)
- Reverse Mathematics: Proofs from the Inside Out
- Richardson's theorem (computing)
S
- Simple set (computing)
- Slicing the Truth (computing)
- Slow-growing hierarchy (computing)
- Smn theorem (computing)
T
- Tarski–Kuratowski algorithm (computing)
- Trakhtenbrot's theorem (computing)
- Truth-table reduction (computing)
- Turing computability (computing)
- Turing degree (computing)
- Turing jump (computing)
- Turing machine (computing)
- Turing reduction (computing)
U
- Undecidable problem (computing)
- UTM theorem (computing)