Category:Computability theory

C

• ► Combinatory logic‎ (1 C, 9 P)
• ► Computable analysis‎ (8 P)

E

• ► Effective descriptive set theory‎ (6 P)

H

• ► Hypercomputation‎ (6 P)

L

• ► Lambda calculus‎ (1 C, 52 P)

R

• ► Recursion‎ (3 C, 39 P)

T

• ► Turing machine‎ (32 P)

• 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)
• Computably inseparable (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)