Computability Theory

← Back to Domain-Specific Abstractions by Domain

16 domain-specific abstractions whose origin domain is Computability Theory.

• 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.
• Description number — A natural-number encoding of a Turing machine's finite transition description under a fixed universal-machine alphabet and coding scheme.
• 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.
• Post Canonical System — A finite string-production formalism that derives words from finite axioms by matching whole-word antecedent patterns and reassembling their matched variables in consequents.
• 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.
• Truth-table reduction — Reduce membership in one decision problem to a finite, nonadaptive batch of oracle queries whose answer bits are combined by an input-computable Boolean truth table.
• Turing degree — An equivalence class of sets or decision problems under mutual Turing reducibility, representing one level of relative computability.