Admissible numbering¶

An effective enumeration of the partial computable functions that is computably translatable to and from a standard enumeration.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3217
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computability Theory → Computer Science & Software Engineering
Aliases: Acceptable numbering, Acceptable programming system

Core Idea¶

Numberings enumerate functions rather than program strings alone, equivalence requires total computable translators and acceptable or Gödel numbering terminology varies with the exact universality and parameterization axioms. Program indices are interpreted by a universal partial computable function, and compiler-like total computable maps translate indices in both directions while preserving the denoted partial function. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Tags for Computer Jobs

Imagine every computer job gets a number tag, and one job can have many tags. A numbering is 'admissible' if every job has a tag, and a translating machine can always turn your tags into the standard tags and back without changing which job you mean.

Job Names a Computer Can Translate

Computer scientists like to give every computer program a number so they can study programs mathematically. What really matters is what each program does, and many different programs can do the same thing. A numbering counts as admissible if every computable job gets at least one number, and a computer can translate between your numbers and a standard numbering in both directions, always landing on a number for the same job. That way, all admissible numberings are basically equally good.

Standard-Equivalent Function Numbering

In computability theory, a numbering assigns natural numbers (indices) to partial computable functions, the things programs compute, not just the program text. A universal function interprets each index by running the function it names. A numbering is admissible (also called acceptable or Gödel numbering, with details varying by author) if every partial computable function gets an index, and there are total computable translators, like compilers, going both ways between it and a standard reference numbering that preserve which function is meant. Some definitions instead use universality and parameterization (s-m-n) conditions. A key consequence is that any two admissible numberings are equivalent in a precise sense, so results don't depend on which one you pick.

An admissible numbering is a surjective map from an index domain (typically ℕ) onto the set of partial computable functions, interpreted by a universal partial computable function, that is equivalent to a reference standard numbering. Equivalence means there are total computable translation functions in both directions that preserve denotation: the translated index names the same partial function. These translators are compiler-like maps, and totality is required. Some presentations instead state the requirement through universality and s-m-n (parameterization) conditions, and the terminology (admissible, acceptable, Gödel numbering) varies with exactly which conditions are imposed. The important point is that numberings enumerate functions, not merely program strings. A central consequence is Rogers equivalence: any two admissible numberings are intertranslatable in this denotation-preserving way, so index-based results transfer between them. Verifying admissibility requires making the index domain, universal function, surjectivity, reference numbering and translation maps explicit.

Scope of Application¶

Admissible numbering belongs to computability theory and is useful where the analyst can specify the typed computability theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence are explicit. The scope is broad within that domain but bounded by the need for the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Admissible numbering. Admissible numbering compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed computability theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of computability theory because they reuse the typed computability theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, Program indices are interpreted by a universal partial computable function, and compiler-like total computable maps translate indices in both directions while preserving the denoted partial function., and type the carrier, state every parameter and convention in the definition, test that the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Admissible numbering Domain-specific

Parents (1) — outgoing typed relations

Admissible numbering is a kind of Encoding And Decoding Prime

It remains its own entry because its identity is fixed by the set of partial computable functions and index domain, numbering map or universal function, surjectivity, reference standard numbering, total computable translations in both directions, preservation of denotation, s-m-n or universality conditions and Rogers-equivalence consequence.

Hierarchy path (1) — routes to 1 parentless root

Admissible numbering → is a kind of Encoding And Decoding → includes Transformation → is a kind of, typical Function (Mapping)

Neighborhood in Abstraction Space¶

Admissible numbering sits in a crowded region of the domain-specific corpus (3^rd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Computability & Recursion Theory (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25