Main article: computability theory

Subcategories

There are 2 subcategories to this category.

C

• Cellular automata
• Computational complexity theory

Articles in category "Computability"

There are 43 articles in this category.

Ackermann function Arithmetical hierarchy B Busy beaver C Chaitin's constant Church-Turing thesis Combinatory logic Computability theory Computable function Computable number Computation problem Counting problem D Decision problem Digital physics E Entscheidungsproblem

F Fixed point combinator G Gödel number H Halting problem Hypercomputation K Kleene's recursion theorem L List of undecidable problems M Markov algorithm Mu operator P Post correspondence problem Post's theorem Primitive recursive function Promise problem R Range problem Real computation Recursive function

R cont. Recursive language Recursive set Recursively enumerable language Recursively enumerable set Rice's theorem S Search problem String rewriting system T Termination Turing completeness Turing degree Turing equivalence U User:LunaticFringe/Busy beaver W Wang tile Word problem (computability)