Computability, Enumeration & Reducibility

← Back to Domain-Specific Families

Abstractions about computable functions, effective numberings, reducibility, Turing degrees, recursive hierarchies, index sets, and decision problems.

15 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Ackermann function — A total computable two-argument function defined by nested recursion that grows faster than every primitive-recursive function, demonstrating that total computability strictly exceeds primitive recursion.
• Admissible numbering — An effective enumeration of the partial computable functions that is computably translatable to and from a standard enumeration.
• Dovetailing (computer science) — A fair scheduling technique that interleaves steps of multiple potentially nonterminating computations so none can block all others forever.
• Effective Polish space — A complete separable metric space supplied with a computable dense presentation that makes basic distance comparisons effectively decidable or enumerable.
• Enumeration reducibility — A computability reduction in which every enumeration of one set can be transformed effectively into an enumeration of another.
• Forcing (computability) — A forcing-style construction of generic computability-theoretic objects by meeting effective dense requirements.
• General recursive function — A partial natural-number function generated from initial functions by composition, primitive recursion and unbounded minimization.
• Grzegorczyk hierarchy — A stratification of primitive-recursive functions into successively stronger classes generated from rapidly growing basis functions and closure operations, calibrating rates of growth and definitional complexity.
• Index set (computability) — A set of program indices whose membership depends only on the partial computable function or computably enumerable set denoted by the index, not on the particular code chosen.
• Matrix mortality problem — The decision problem asking whether the zero matrix belongs to the multiplicative semigroup generated by a finite set of integer matrices.
• Maximal set (computability theory) — A coinfinite computably enumerable set that cannot be enlarged by another computably enumerable set without changing it only finitely or making the enlargement cofinite.
• Mortality (computability theory) — The reachability property asking whether some finite composition from a given set of transformations sends the system to a designated zero, empty or dead state.
• Nondeterministic Turing machine — A Turing-machine model whose transition relation may offer multiple successor configurations and which accepts when at least one computation branch accepts.
• Semicomputable function — A real-valued function on a computable domain that admits a uniform computable sequence of rational approximations converging monotonically from below or from above.
• Turing degree — An equivalence class of sets or decision problems under mutual Turing reducibility, representing one level of relative computability.