1 Definitions and Basic Notions

1.1 Partial functions and domains

In computability theory, a partial function from inputs in a set \(X\) to outputs in a set \(Y\) is allowed to be undefined on some inputs. Formally, it corresponds to a subset of \(X\) called the domain of definition together with a function from that subset into \(Y\). Intuitively, the function “gives an answer” only when the input lies in its domain; otherwise, no value is assigned.

1.2 Partial computable functions (Turing-machine view)

A function is partially computable if there exists an effective procedure—classically, a Turing machine—that may not terminate on every input, but does terminate and produce the correct value whenever the function is defined. The machine can behave arbitrarily on inputs where the function is undefined, including looping forever.

1.3 Domains of definition vs. computable outputs

Two related but distinct questions arise: (i) whether the computation eventually produces an output value, and (ii) whether the function’s output is defined mathematically. In partial computability, the emphasis is on matching these two notions: for inputs where a value is defined, there is an effective computation that halts with that value; for inputs outside the domain, the procedure may fail to halt (or halt incorrectly is not allowed by correctness requirements).

2 “Halts exactly when defined” Property

2.1 Formal statement of halting equivalence

A common refinement for partial computability is a tight correspondence between termination and definedness. A partial function \(f\) satisfies the halting equivalence property with respect to a given machine \(M\) if for every input \(x\):

  • \(M(x)\) halts with output \(y\) iff \(x\) belongs to \(\mathrm{dom}(f)\),
  • and when it halts, the produced output equals \(f(x)\).

This yields a machine whose halting set is exactly the domain of the function.

2.2 Divergence corresponds to undefinedness

Under the halting equivalence property, divergence (non-termination) is not merely an accident of an implementation; it is the computational reflection of undefinedness. If \(x\notin \mathrm{dom}(f)\), the corresponding computation does not terminate, so the algorithm never produces an output that would contradict the mathematical specification.

2.3 Domain reconstruction from machine behavior

When a machine is constructed to satisfy the halting equivalence property, the domain can be reconstructed from runtime behavior alone: the set of inputs on which the machine halts is precisely the domain. This makes the notion of definability operational rather than purely abstract.

2.4 Relationship to partiality semantics

In semantics-oriented presentations, one distinguishes between:

  • inputs where the semantics assigns a value, and
  • inputs where the semantics assigns no value.

Halting equivalence aligns the operational semantics (halts versus diverges) with the semantic notion of value versus undefinedness. This alignment is central to many proof strategies in the theory.

3 Machines and Representations

3.1 Single-tape vs. multi-tape computation models

The precise model of computation varies, but the theory is designed so that standard models are equivalent up to computable translation. For instance, single-tape and multi-tape Turing machines differ in efficiency but not in the class of partial computable functions they can compute. Thus the halting equivalence property can be established across models without changing the underlying conceptual content.

3.2 Output conventions for partial computation

To interpret partial computation, a machine must have a clear rule for what counts as an output. Commonly, halting implies that the machine enters a designated halt state and has written the value on a work tape (or in a distinguished output region). For partial functions, this output is required to match the specification whenever it exists.

3.3 Encoding inputs and outputs

Because machines operate on finite strings (or symbols), mathematical inputs and outputs are typically encoded via standard Gödel numbering or other effective encodings. An encoding scheme must be computable so that a machine can decode inputs and encode outputs without changing computability properties.

3.4 Equivalence across standard models

Equivalence across models relies on effective simulation: given one machine model, another can emulate it step-by-step using a computable procedure. As a result, the class of partial computable functions is invariant under reasonable changes of representation, including variations in tapes, heads, or minor conventions.

4 Computably Enumerable (c.e.) Domains

4.1 c.e. sets as halting domains

A set \(D\subseteq \mathbb{N}\) is computably enumerable (c.e.) if there is an effective procedure that eventually lists all elements of \(D\) (possibly with repetition) and never outputs elements not in \(D\). The fundamental link is that c.e. sets correspond to halting domains of partial computable functions: an input belongs to a c.e. set exactly when some computation eventually halts on it under a suitable machine.

4.2 Characterizing definable inputs via enumeration

Given a partial computable function with halting equivalence, one can enumerate its domain by running the machine on candidate inputs in a dovetailing schedule and outputting those that halt. The key observation is that undefined inputs never trigger output, so the enumeration stays correct.

4.3 From halting sets to partial functions

Conversely, if \(D\) is c.e., one can build a partial computable function whose domain is exactly \(D\). One approach uses a machine that enumerates \(D\), then for each input \(x\) waits until the enumeration produces \(x\); upon seeing \(x\), it returns a fixed output value (or a computed value derived from the stage of discovery). This constructs a function that halts precisely for inputs in \(D\).

4.4 From partial functions to c.e. domains

If a function is partially computable, its domain can be recognized by a search procedure: run the machine on each input and record those for which it eventually halts. Hence the domain of any partial computable function is c.e. This provides a bidirectional correspondence between partial computability and c.e. domains.

5 Effective Operations on Partially Computable Functions

5.1 Composition of partial computable functions

Partial computability is stable under composition. If \(f\) and \(g\) are partial computable, then the composed function \(h(x)=g(f(x))\) is partial computable with the usual caveat: \(h(x)\) is defined only when both \(f(x)\) is defined and \(g(f(x))\) is defined. Operationally, a constructed machine runs the computation for \(f\); if it does not halt, neither does the whole computation, and if it halts with a value, it then attempts the computation for \(g\).

5.2 Partial evaluation and chaining computations

Partial evaluation refers to using the output of one effective computation as input to another in a staged manner. For partial functions, chaining must respect that the intermediate value may never appear. Therefore, the composed procedure’s divergence behavior mirrors the combined undefinedness of intermediate steps.

5.3 Closures under computable transformations

If a computable transformation is applied to inputs or outputs—such as an effective encoding/decoding, or a computable post-processing of a produced value—then partial computability is preserved. The reason is that computable pre- and post-processing can be hardwired into a universal construction around the original machine.

5.4 Constructing new machines from old ones

Many operations on partial computable functions are implemented by machine-level assembly: take machines \(M_f\) and \(M_g\), connect their tapes appropriately, and define a new control structure that orchestrates their execution. The design ensures correctness on inputs where defined values exist, and it allows divergence to propagate where values are absent.

6 Universal Constructions and Self-Reference (Foundational, Not Controversial)

6.1 Universal partial computable functions

A universal partial computable function is one that, given an index representing a machine/function and an input, simulates the corresponding computation. In effect, it can emulate any partial computable function provided as a parameter. The universality is partial in the same way: if the simulated computation diverges, so does the universal one.

6.2 Indexing partial computable functions

Indexing provides a way to name partial computable functions via natural numbers (indices) so that a single meta-level machine can interpret them. This relies on an effective correspondence between indices and machine descriptions, typically via a Gödel numbering scheme.

6.3 Simulations and effective translations

Simulations are effective translations: a universal machine reads an index, reconstructs the corresponding machine description, and performs the same computation on the given input. When machines are translated between models or conventions, the translation must remain computable to preserve the class of partial computable functions.

6.4 Using “halts iff defined” in universal settings

In universal constructions, halting equivalence helps identify where simulations terminate. If the chosen universal simulation halts exactly when the simulated partial function is defined on that input, then the universal machine’s termination behavior encodes the same domain information. This viewpoint is useful for relating domain properties to machine behavior in proofs.

7 Common Theorems and Proof Patterns

7.1 Halting domain characterization theorem sketches

A standard characterization states that c.e. sets are precisely the domains of partial computable functions. Proof sketches usually proceed in two directions:

  1. Given a partial computable function, show its domain is c.e. by enumerating inputs on which the machine halts.
  2. Given a c.e. set, build a partial computable function that halts exactly for those inputs by using a machine that enumerates the set.

The “halts exactly when defined” alignment underpins both directions because it ensures that runtime termination events correspond directly to membership.

7.2 Standard proof techniques for partial computability

Typical proof techniques include:

  • Dovetailing: systematically interleave computations to ensure progress across many branches.
  • Simulation: reuse existing machines as subroutines via an effective coding mechanism.
  • Diagonalization-style arguments (in a general sense): constructing machines with carefully controlled behavior relative to a given family, especially to demonstrate non-decider properties or show limitations of computability.

These methods frequently track divergence as the analogue of undefinedness.

7.3 Reductions involving domains of definition

Reductions can target domains rather than values. A common pattern is to map an input \(x\) to another input \(x'\) such that \(x\) is in the domain of one function exactly when \(x'\) is in the domain of another. This kind of domain-focused reduction transfers difficulty results and helps classify the complexity of definability.

7.4 Typical counterexamples and pitfalls

A frequent pitfall is assuming that c.e. implies decidable; c.e. domains may be non-decidable. Another common mistake is conflating “machine halts” with “function is total”: a halting computation on some inputs does not guarantee a function has values on all inputs. In proofs, care is required to ensure that correctness holds wherever the function is defined, while divergence is permitted elsewhere.

8 Examples

8.1 A function with a domain defined by halting behavior

Consider a partial function \(f\) defined using a machine \(M\) such that \(f(x)\) is defined exactly when \(M(x)\) halts. If \(M(x)\) halts, \(f(x)\) can output a fixed value, such as \(0\). If \(M(x)\) diverges, then \(f(x)\) is undefined. This example illustrates how domains can be engineered to match halting sets.

8.2 Functions defined “on purpose” by staged computation

A staged construction can define \(f(x)\) only when a witness appears. For instance, suppose an effective process searches for a certificate verifying a computable condition about \(x\). When a certificate is found, the machine halts and outputs a corresponding value; until then it continues searching. Inputs for which such certificates exist become exactly the domain, making the definability dependent on search success.

8.3 Comparing total vs. partial computability on test inputs

To contrast total and partial computation, take a partial procedure that halts only for some inputs (e.g., those satisfying a property that can be confirmed but not always resolved). On test inputs where the procedure halts, one observes correct output; on others, execution may continue indefinitely. The distinction is not about correctness on observed cases, but about whether termination is guaranteed universally.

8.4 Reading halting traces as domain evidence

In practice, one often treats halting traces as evidence for membership in a domain: if the machine halts on \(x\), then \(x\) is confirmed to lie in \(\mathrm{dom}(f)\). Conversely, the absence of halting within an observed time window is not evidence of non-membership in general; it may simply reflect that the computation would eventually halt. This asymmetry is characteristic of c.e. domains.

9 Notation and Terminology

9.1 Undef/↑ vs. defined outputs conventions

Common notation distinguishes between an actual output and undefinedness. A value might be written as \(f(x)\downarrow\) to mean “\(f(x)\) is defined,” and \(f(x)\uparrow\) to mean “\(f(x)\) is undefined,” or alternatively “the computation does not halt.” These conventions compactly express divergence as part of the function’s behavior.

9.2 “Partial computable” vs. “computably enumerable domain”

The phrases refer to different aspects:

  • partial computable describes the existence of an effective machine that outputs values when defined,
  • computably enumerable domain describes the effective enumerability of the set of inputs where values exist.

For partial computable functions, these two notions are tightly linked via the halting behavior.

An effective procedure is an algorithmic method implementable by a machine model. Partial correctness means that whenever the procedure terminates, the output is correct; it does not require termination on all inputs. This is closely aligned with partial computability, where non-termination is allowed outside the domain.

9.4 Practical shorthand for “halts exactly when defined”

Because the halting equivalence property is central, it is often summarized informally as: the machine “halts iff the function is defined.” In formal writing, this shorthand is clarified by specifying both the halting condition and the correctness of outputs upon termination.