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.

Version: v2 · 2026-09-19 · History
Domain-specific #: 5009
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computability Theory → Computer Science & Software Engineering

Core Idea¶

Extensional invariance makes nontrivial index sets subject to Rice-style undecidability, while arithmetical-hierarchy complexity depends on the semantic property and the fixed acceptable numbering. A Gödel numbering maps natural numbers to partial computable functions; a semantic class pulls back along that map, and equality of denoted functions forces equivalent membership for all alternative indices. 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…

The Same-Cake Club

Imagine every recipe in a giant cookbook has a page number. Now circle every page whose recipe makes chocolate cake. Two different recipes that make the very same cake must both be circled. Here is the tricky part: no helper robot can always look at a page and tell you for sure whether it belongs in the circle.

Programs Sorted by Behavior

In computer science, every program can be given a number, called its index. Pick a property of what programs do, not how they are written, such as "this program outputs 7 for every input." The index set is the set of numbers of all programs with that property. Two programs that behave exactly the same must both be in or both be out. A famous result says that unless the property is true of every program or of none, no program can always correctly decide whether a number is in the set.

Behavior-Closed Program Numbers

In computability theory, every program, and so every partial computable function, is given a code number through a fixed numbering. An index set is the set of all code numbers whose functions have some property of their behavior, not of their code. The key rule is extensional invariance: if two codes compute the same function, both are in the set or both are out. Rice's theorem says every nontrivial index set (neither empty nor everything) is undecidable. How hard such a set is beyond that depends on the property and on the numbering chosen. Do not confuse it with a property of program text, like 'has fewer than 100 lines,' which is not an index set.

Fix an acceptable (Gödel) numbering that maps natural numbers to partial computable functions, or similarly to c.e. sets, under a fixed machine model. A semantic class of functions pulls back along this map to a set of indices. That pullback is the index set. Its defining feature is extensional invariance: if indices e and e' denote the same function, then e is in the set exactly when e' is. Trivial cases are the empty set and all of N. By Rice's theorem, every nontrivial index set is undecidable. The finer classification, its level in the arithmetical or analytical hierarchy, depends on the specific semantic property and on the fixed numbering. A careful analysis therefore states the numbering, machine model, carrier, and property explicitly. It also separates what must hold (the invariance), what proves it, and what it licenses, such as applying Rice's theorem.

Scope of Application¶

Index set (computability) belongs to computability theory and is useful where the analyst can specify the typed computability theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the acceptable numbering and machine model, partial computable functions or c.e. sets, semantic class, pullback set of indices, extensional-invariance condition, trivial and nontrivial cases, Rice theorem application, arithmetical or analytical complexity and dependence on numbering are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the acceptable numbering and machine model, partial computable functions or c.e. sets, semantic class, pullback set of indices, extensional-invariance condition, trivial and nontrivial cases, Rice theorem application, arithmetical or analytical complexity and dependence on numbering 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 Index set (computability). Index set (computability) 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, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the acceptable numbering and machine model, partial computable functions or c.e. sets, semantic class, pullback set of indices, extensional-invariance condition, trivial and nontrivial cases, Rice theorem application, arithmetical or analytical complexity and dependence on numbering 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, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, A Gödel numbering maps natural numbers to partial computable functions; a semantic class pulls back along that map, and equality of denoted functions forces equivalent membership for all alternative indices., and type the carrier, state every parameter and convention in the definition, test that the acceptable numbering and machine model, partial computable functions or c.e. sets, semantic class, pullback set of indices, extensional-invariance condition, trivial and nontrivial cases, Rice theorem application, arithmetical or analytical complexity and dependence on numbering are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Index set (computability) Domain-specific

Parents (1) — outgoing typed relations

Index set (computability) is a kind of Index Prime

What makes it its own entry: the domain-specific identity determined by the acceptable numbering and machine model, partial computable functions or c.e.

Neighborhood in Abstraction Space¶

Index set (computability) 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

Admissible numbering — 0.96
General recursive function — 0.94
Forcing (computability) — 0.94
Maximal set (computability theory) — 0.94
Semicomputable function — 0.93

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