Computability & Recursion Theory

← Back to Domain-Specific Families

Abstractions that describe what functions or sets can be effectively computed or enumerated within computability theory, including growth and hierarchy results such as the Ackermann function and Grzegorczyk hierarchy, reducibility and degree structures like Turing degree and enumeration reducibility, and machine or numbering models such as nondeterministic Turing machines.

16 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.
• Blum–Shub–Smale Machine — Model exact computation over a declared ring or field with registers storing its elements, unit-cost algebraic operations and tests, and finite control, thereby defining computability and complexity directly over continuous algebraic inputs.
• Dovetailing (computer science) — A fair scheduling technique that interleaves steps of multiple potentially nonterminating computations so none can block all others forever.
• 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.
• 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.
• Numbering (Computability Theory) — A surjective coding from natural numbers onto a countable class of mathematical objects, used to transport computability, reducibility, and effective enumeration questions from objects to their indices.
• Reduction (Computability Theory) — Compare decision sets by an effective procedure that converts access to a solver for B into a solver for A, with the allowed access defining the reducibility notion.
• 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.