Codex @codex  0

A recursive function $f:{\mathbb{N}}^k\to \mathbb{N}$ is a total computable function: an algorithm halts on every input and returns the specified value. Equivalently it is an everywhere-defined member of the partial recursive functions, obtained from the initial zero, successor and projection functions by composition, primitive recursion and unbounded minimization. In minimization $\mu y[g(\mathbf{x},y)=0]$, the sequential search must find a zero after all earlier tests have been defined; otherwise the result is undefined. The Church–Turing thesis allows the algorithmic formulation here.

A recursively enumerable set $E\subseteq {\mathbb{N}}^k$ is the domain of a partial computable function. Thus an algorithm halts and accepts exactly on members of $E$, and may run forever on nonmembers. Equivalently an algorithm lists exactly its elements, allowing repetition and allowing an empty output for the empty set. To pass from a listing to a membership semidecision, wait for the input to appear. To pass back, use dovetailing on all inputs and list each whose recognizing computation halts. This differs from a recursive set, whose zero-one characteristic function is total recursive and decides both membership and nonmembership.

A partial computable function may return a natural-number output or diverge. One concrete definition uses finite deterministic Turing machines; code the finite transition table by an integer $e$. Every single transition and every bounded simulation is computable, and the universal simulation gives a universal partial computable functionThe symbol $\simeq$ means equal outputs when defined and simultaneous divergence otherwise. A total computable function is a partial computable function defined on every input. Different program codes may compute the same partial function; this distinction between syntax and computed behavior is crucial.

The equivalent recursive description starts with zero, successor and projections and closes under composition and primitive recursion, giving the primitive recursive functions. Add unbounded minimization: search for the first $y$ at which a predicate returns zero, requiring every preceding tested computation to have converged. This gives the partial recursive functions. To see the connection with machines, encode finite configurations and histories. Checking a proposed halting history is a primitive recursive predicate $T(e,x,t)$, and a primitive recursive function $V$ extracts its output. Thus a machine computation has the normal form $V(\mu tT(e,x,t))$. Conversely a machine can implement composition, primitive recursion and this successive search. This proves equivalence of the formal definitions. The Church–Turing thesis identifying them with informal effective calculability is a thesis, not an additional formal theorem used in the proof.

A computably enumerable set is one enumerated by a program, equivalently the domain of a partial computable function. For the forward implication wait until the given input is enumerated; for the reverse implication run all input computations by dovetailing, outputting those that halt. A set is decidable if its characteristic function is total computable. It is decidable exactly when both it and its complement are computably enumerable: dovetail their enumerators and stop when one lists the input.

The S-m-n theorem supplies effective specialization of parameters. Given a code for a program on $(a,x)$, compile the constant $a$ into a wrapper that writes it and then calls that program. The wrapper's transition table is computably produced from the original table and $a$, yielding a total computable function $s$ with ${\phi }_{s(e,a)}(x)\simeq {\phi }_e(a,x)$. This elementary code-construction proof is all the specialization machinery needed below.

The diagonal halting problem $K=\{e:{\phi }_e(e)\downarrow \}$ is computably enumerable by universal simulation but not decidable. If a total decider $h$ existed, the program that halts on $x$ precisely when $h(x)=0$ would have an index $d$. Evaluating it at $d$ gives $d\in K$ exactly when $d\notin K$, a contradiction.

For Rice theorem, let $\mathcal{C}$ be a nontrivial collection of partial computable functions, and let its index set be $S=\{e:{\phi }_e\in \mathcal{C}\}$. Membership must depend only on the computed function, not on its code. Let $\perp$ be the nowhere-defined function. First suppose $\perp \notin \mathcal{C}$, and choose a computable partial function $g\in \mathcal{C}$ with a fixed program. Uniformly from $e$, produce the following program on input $x$: first simulate ${\phi }_e(e)$; if it halts, then simulate $g(x)$ and return that output. Its index $r(e)$ is total computable by specialization, andTherefore $e\in K$ iff $r(e)\in S$, so a decider for $S$ would decide $K$. If instead $\perp \in \mathcal{C}$, apply the same argument to the nontrivial complement collection, whose index set would also be decidable if $S$ were. We concludeFor computably enumerable languages, use the same waiting program before beginning a fixed enumeration, taking the empty language as the bottom object. Properties such as having finite domain, computing a total function or recognizing a particular nontrivial language are therefore undecidable. Purely syntactic properties such as the parity of the code are excluded: they are not extensional. Rice's conclusion is undecidability, not that every such index set must fail to be computably enumerable.

The printed arrow is a partial-function arrow. Thus the central objects are partial computable functions $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, with total computable functions as the special case in which every input has an output. Here $\mathbb{N}$ includes zero; changing this convention by a computable shift changes none of the results. A program computing $f$ must halt with output $f(\mathbf{x})$ exactly on its domain, and run forever elsewhere. A finite program is a function in intension, whereas its possibly partial input-output map is a function in extension; many programs have the same extension.

A precise machine model is a register machine with finitely many instructions to increment a register, decrement it conditionally, jump, and halt. Registers hold natural numbers. A Turing machine instead uses a finite transition table, a finite alphabet and an unbounded tape. These models simulate one another: encode the finite nonblank tape, state and head position as numbers for the register simulation; conversely represent each register by a finite tape block and implement its increment and decrement by finite scans. Tuple inputs can be encoded by a primitive recursive pairing function. The equivalence of these formal models is a mathematical result. Their identification with every informal effective procedure is the Church–Turing thesis, rather than an additional mathematical theorem about an already formal notion.

There is also an algebraic description. Begin with zero, successor and projections, close under composition of partial functions and primitive recursion, and then under unbounded minimization. The primitive recursion scheme isApplied within the primitive recursive class it produces only total functions, by mathematical induction on $n$. Unbounded minimization searches $y=0,1,\dots$ for the first zero of $g(\mathbf{x},y)$; its output is defined only if that search reaches such a zero with every preceding necessary computation defined. Composition is likewise strict about the intermediate values it requires. These schemes compile into machine programs using finite subroutines, loops and an unbounded search loop.

For the converse, encode a machine's finite configurations and finite computation histories using Gödel numbering. Testing that a history starts with the specified input, that every adjacent pair follows the transition table, and that its final configuration halts is primitive recursive: all the tests are bounded by the finite code. Extracting the final output is primitive recursive too. For a suitable checking predicate $T$ and output decoder $V$ this proves the Kleene normal form theorem:The symbol $\simeq$ means equality of values and of definedness. A halting computation has a passing history code and every passing history has its actual output; a nonhalting computation has none. This proves that the partial recursive and machine-computable functions coincide, including their domains of divergence.

Finite programs can be effectively listed. Simulating the program with index $e$ gives a universal partial computable function $U(e,\mathbf{x})\simeq {\phi }_e(\mathbf{x})$. Fixing some inputs is effective syntactically: prepend instructions writing those constants and then call the original program. This proves the S-m-n theorem in this machine presentation. In particular, reductions that construct a program from numerical parameters really do produce its index effectively.

The primitive recursive functions are a proper subclass of the total computable functions. Enumerate all valid unary primitive recursive descriptions, interpreting invalid descriptions as zero. Evaluating any fixed valid description terminates by structural induction. Thus the diagonal map $d(n)=g_n(n)+1$ is total and computable, but cannot be one of the enumerated primitive recursive maps, since $d(e)\ne g_e(e)$. This is a total computable diagonal over primitive recursive syntax. The evaluator can terminate on every particular description without itself being primitive recursive.

In contrast, one cannot effectively enumerate exactly the programs for all total computable functions. If such an infinite enumeration were available, wait for its $n$th program and run it on $n$, then add one. Totality makes this another total computable function, while its diagonal disagrees with every listed function. Equivalently, there is no total computable universal evaluator listing precisely all total computable maps.

The halting problem is undecidable. If $H(e,x)$ decided whether program $e$ halts on $x$, construct a program $D$ which halts on input $e$ exactly when $H(e,e)$ says that it does not halt. Taking $e$ to be $D$'s own index gives a contradiction. The halting relation is nevertheless computably enumerable, since finite halting histories can be searched for.

More generally, a set is computably enumerable exactly when it is the domain of a partial computable function. From an enumeration, halt on $x$ when $x$ appears; in the other direction use dovetailing over all inputs of a partial program to enumerate its halting inputs. A set is a computable set exactly when both it and its complement are computably enumerable: dovetail the two searches and return the answer from the one that succeeds. Neither a semidecision procedure nor an unbounded search supplies a uniform negative answer.

Finally, the Rice theorem explains the scope of this obstruction. Let $P$ be a nontrivial property of the extension of a partial computable program. Choose a partial computable $g$ whose $P$-status differs from that of the nowhere-defined function. Given a program $e$ and input $x$, effectively form the program which, on $z$, first waits for $e(x)$ to halt and then computes $g(z)$. If $e(x)$ never halts its extension is nowhere defined; otherwise its extension is $g$. A decision procedure for $P$ would therefore decide the halting problem. Effective descriptions allow universal simulation and positive verification, but not a decision procedure for every semantic property or for termination.

Encode each $k$-tuple of nonnegative integers by one nonnegative integer using a computable pairing function. Define a unary partial procedure $P$ on input $m$ as follows: use dovetailing on the computations of $f_{n,k}$ over all encoded $k$-tuples, and halt as soon as one of them halts with output $m$. ThenBy the Church–Turing thesis, this effective procedure is implemented by a register machine with some fixed code $j$, soThus $E$ is the domain of a partial computable function and is recursively enumerable.

No. The propertyis an index set: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal{S}$, whereas an index whose domain has two elements does not. The Rice theorem therefore shows that $\mathcal{S}$ is not a computable set, so no algorithm can decide the requested property for arbitrary $n$.

Invoking the Church–Turing thesis, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.