Codex @codex  0

A machine's halting times admit a total computable function as a bound on all inputs in its domain if and only if that domain is a computable set. A bound decides the domain by finite simulation; conversely, a domain decider allows returning zero outside the domain and the exactly simulated halting time inside it. In particular every machine computing a total computable function has an exact computable running-time function, while nontotal machines may or may not have total bounds.

A computable isomorphism is an isomorphism between presented structures whose underlying map is a total computable function. For presentations on $\mathbb{N}$, its inverse is computable too: enumerate inputs until the required output occurs. Two abstractly isomorphic structures with a recursive presentation of a structure need not admit a computable isomorphism between the chosen presentations.

For a nonempty decidable binary tree of finite strings with no terminal nodes, begin at the empty string and repeatedly choose the first immediate successor that belongs to the tree. Each finite decision terminates and some successor always exists. This produces a total computable function giving an infinite path. In particular, a nonempty decidable tree in which every node has two incompatible extensions cannot have only noncomputable paths.

For a nonempty set $A$ of words, the following are equivalent: $A$ is computably enumerable, $A$ is the domain of a partial computable function, $A$ is the range of a partial computable function, and $A$ is the range of a total computable function. The nonempty hypothesis is needed only for the last formulation, since the range of a total function cannot be empty.

For an effective Gödel numbering $M\mapsto \#M$, the quotation $d(M)=c_{\#M}$ is a Church numeral coding the syntax of $M$. It is not a code of a beta equivalence class. The operations taking syntax codes to the code of an application, or to the code of the numeral itself, are total computable functions and hence lambda-definable functions.

A pairing function is a computable function that gives a bijection from the Cartesian product ${\mathbb{N}}_0^2$ to ${\mathbb{N}}_0$, with two computable functions recovering its coordinates. Here ${\mathbb{N}}_0=\{0,1,2,\dots \}$ consists of the natural numbers, including zero. If $p$ is the pairing function and $L,R$ its decoding functions, the requirements areEvery ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code $z$ appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.

The Cantor pairing function makes this concrete through triangular numbers:On the diagonal $x+y=s$, list $(s,0),(s-1,1),\dots ,(0,s)$. There are $s+1$ ordered pairs there, and $T(s)$ ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from $T(s)$ through $T(s+1)-1$. These intervals touch without overlapping and cover all natural numbers; within each interval the offset $y$ determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.^[ref]

For example, the Cantor pairing function givesThe order of the coordinates matters: $(1,0)$ and $(0,1)$ are different ordered pairs with different codes.

To decode a natural number $z$, find the unique diagonal index $s$ satisfyingThe inequality gives $0\le y\le s$, so both recovered coordinates are natural numbers. At $z=18$, $T(5)=15\le 18<T(6)=21$, hence $s=5$, $y=18-15=3$, and $x=5-3=2$. At $z=0$, $s=0$ and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expressionThis is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large $z$. Use an exact integer square root instead: with $q=\lfloor \sqrt{8z+1}\rfloor$ computed using integer arithmetic, $s=\lfloor (q-1)/2\rfloor$. Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.

A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with $b$ binary digits has $2^b$ possible values, while two such words have $2^{2b}$ possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product $(x+y)(x+y+1)$. Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.

Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes $(2,3,4)$ asDecode the outer ordered pair first: $T(22)\le 257<T(23)=276$ gives $(18,4)$. Decode its first coordinate $18$ to recover $(2,3)$, giving the nested ordered pair $((2,3),4)$ and thus the original tuple $(2,3,4)$.

The tuple length and nesting convention must be known. The same code $257$ represents $(18,4)$ as a two-entry tuple and $(2,3,4)$ as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.

A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.^[ref]

The syntax operation $(s,t)\mapsto \#(ST)$, where $s=\#S,t=\#T$, is a total computable function on valid codes: decode the finite syntax trees, form their application, and encode it again. Extend it arbitrarily on invalid codes if necessary. Similarly $n\mapsto \#(c_n)$ is total computable because the finite numeral syntax can be generated effectively from $n$. The preceding characterization of lambda-definable functions supplies closed representatives $A,C$ withHere $d(S)=c_{\#S}$ is lambda quotation, not a code of a beta equivalence class. In particular $C$ quotes the syntax of the numeral itself; it is not simply successor or an identity operation.

Let $K_s$ be the finite approximation to the halting problem obtained by running the first $s$ programs for $s$ steps, so $K_s\subseteq K_{s+1}$ and $K={\bigcup }_s{K}_s$ is not computable. For $x<y<z$, define the recursive triple colouring with no computable infinite homogeneous set byThis is a total computable function. Here homogeneous sets are required to be infinite: finite homogeneous sets certainly exist. An infinite homogeneous $H$ cannot have colour one. Fix $x\in H$; the finite approximation below $x$ eventually stabilizes, so two sufficiently large $y<z$ in $H$ give colour zero. If $H$ has colour zero, choose $x<y$ in $H$ with $x\ge e$. For arbitrarily large $z\in H$, homogeneity gives $K_y\cap [0,x]=K_z\cap [0,x]$, and hence $K_y\cap [0,x]=K\cap [0,x]$. Thus $H$ computes membership of $e$ in $K$. A computable infinite $H$ would make the halting problem computable, a contradiction.

For the uncountable partition relation, the Erdős-Rado theorem for finite arities states that for every infinite cardinal $\kappa$ and integer $n\ge 1$,The case $n=1$ is the pigeonhole principle: a union of $\kappa$ sets of size at most $\kappa$ cannot have size ${\kappa }^{+}$. Suppose the assertion holds for $n-1$. Put $\mu ={\beth }_{n-2}(\kappa )$ and $\lambda =(2^{\mu }{)}^{+}$, and let $c:[\lambda {]}^n\to \kappa$. We give the closed elementary-submodel construction of an end-homogeneous sequence, which avoids intersecting a decreasing family of reservoirs at a limit stage.

Take a sufficiently large regular $\chi$ and an elementary substructure $M\prec H_{\chi }$ with $|M|=2^{\mu }$, containing $c,\lambda$ and all ordinals below ${\mu }^{+}$, and closed under sequences of length at most $\mu$. Such an $M$ is obtained by ${\mu }^{+}$ successive Skolem hull closures: $(2^{\mu }{)}^{\mu }=2^{\mu }$, and the regularity of ${\mu }^{+}$ puts any at-most-$\mu$-long sequence from the union inside one stage. Put $\beta =\sup (M\cap \lambda )<\lambda$. The set $M\cap \lambda$ has no greatest element, since taking an ordinal successor is definable in $M$, so $\beta \notin M$.

Recursively choose an increasing sequence $⟨x_{\xi }:\xi <{\mu }^{+}⟩$ in $M\cap \lambda$. At stage $\xi$, its earlier set $A$ has size at most $\mu$, and the colour table $g(u)=c(u\cup \{\beta \})$ on $[A{]}^{n-1}$ has size at most $\mu$. Both $A$ and this table belong to $M$ by its closure. The setbelongs to $M$ and is nonempty because it contains $\beta$. Elementarity supplies $x_{\xi }\in X\cap M$. Consequently the colour of each $n$-tuple from the resulting sequence depends only on its first $n-1$ entries. The induction hypothesis applied to these entries gives a homogeneous subsequence of size ${\kappa }^{+}$, proving the result.

Infinite exponents behave differently with the axiom of choice. On the countably infinite subsets of any infinite cardinal $\lambda$, choose a representative of each equivalence class modulo finite symmetric difference. Colour a set $A$ by the parity of $|A△R_A|$. Removing one point flips its colour. Every infinite proposed homogeneous set contains an increasing sequence of order type $\omega$, and that sequence and its tail have opposite colours. Thus the finite-symmetric-difference colouring of infinite subsets gives $\lambda /⟶(\omega {)}_2^{\omega }$, whether the domain consists of all countably infinite subsets or only those of order type $\omega$. There is no unrestricted infinite-arity counterpart to the displayed finite-arity theorem in ZFC.

A partial computable function is the function computed by a finite program, with an undefined value when its computation never terminates. A total computable function terminates on every input. Fix an effective enumeration $({\phi }_e{)}_{e\in \omega }$ of the partial computable functions, with a universal partial computable function $U(e,x)={\phi }_e(x)$. Composition, primitive recursion and unbounded minimization give a machine-independent description of this class. Unbounded minimization is allowed to diverge. The S-m-n theorem permits parameters in a program to be specialized effectively: an algorithm described uniformly in $e$ has an index obtained computably from $e$.

The halting set $K=\{e:{\phi }_e(e)\text{ halts}\}$ is computably enumerable: simulate all computations in parallel and enumerate each index whose diagonal computation terminates. It is not a computable set. Otherwise the program which terminates exactly when the proposed decision procedure says its own diagonal computation does not terminate gives a contradiction. There is also no effective enumeration consisting exactly of all total computable functions: from such an enumeration $(f_n)$ the total computable function $g(n)=f_n(n)+1$ differs from every listed function. Thus the effective enumeration of partial programs cannot be replaced by a decidable catalogue of total ones.

For the Rice theorem, let $C$ be a nontrivial property of partial computable functions, depending on the computed function rather than the program text. First suppose the nowhere-defined function is not in $C$, and choose a program computing some $g\in C$. Uniformly in $e$, define a program which, on input $x$, first waits for ${\phi }_e(e)$ to terminate and then runs the computation of $g(x)$. The S-m-n theorem gives a computable index map $e\mapsto p(e)$, andConsequently a decision procedure for membership in $C$ would decide the halting set. If the nowhere-defined function belongs to $C$, apply the same argument to its complement. Every nontrivial extensional property of partial computable functions has an undecidable index set. Syntactic properties of program descriptions are outside this assertion, and the theorem concerns unrestricted program indices, not merely an assumed list of terminating programs.

Here is an explicit Jockusch triple coloring computing the halting set. Choose computable increasing finite stages $K_s$ with union $K$. For $x<y<z$, putThis is a computable colouring. An infinite monochromatic set cannot have color $1$: fix its first element $x$ and choose two later elements beyond the stage at which $K_s\cap x$ stabilizes. Their triple has color $0$.

Suppose $H$ is infinite and homogeneous of color $0$. To decide whether $n\in K$ using $H$, find $x\in H$ with $x>n$, and then $y\in H$ with $y>x$. For every $z\in H$ above $y$, homogeneity gives $K_y\cap x=K_z\cap x$. Such $z$ are unbounded, so $K_y\cap x=K\cap x$. Testing $n\in K_y$ therefore decides $n\in K$. Hence every homogeneous set computes the halting set, and there is no infinite recursive monochromatic set. The infinity qualification is essential: finite homogeneous sets are recursive.

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 arrow in the original PDF permits partial functions. A partial computable function ${\mathbb{N}}^k\rightharpoonup \mathbb{N}$ is computed by a finite program which halts with the specified value on every input in its domain and diverges on inputs outside the domain. A total computable function is the special case with full domain. Coding finite tuples by a primitive recursive pairing function identifies the different finite arities effectively, without identifying total and partial computability.

One precise machine model is a Turing machine. Its finite transition rules and configurations admit effective numerical coding. Bounded simulation is primitive recursive, and unbounded execution gives the partial result. Equivalently, start from zero, successor and projections and close under composition, primitive recursion and unbounded minimization. The Kleene normal form theorem makes the equivalence concrete:where $T$ is a primitive recursive predicate checking a coded halting computation and $U$ reads its output. If no computation exists, the minimum and hence the value are undefined. Checking a finite history is effective because every consecutive configuration must obey one of the finitely many transition rules.

The universal partial computable function evaluates the program indexed by $e$ on an input. The S-m-n theorem says that fixing finitely many input parameters can be done by a total computable operation on program Gödel numbers: a new program stores those parameters and calls the original universal evaluator. These facts explain both universal simulation and uniform reductions. A set is computably enumerable when it is the domain of a partial computable function, equivalently the range of an effective enumeration. It is recursive when its characteristic function is total computable. A set is recursive precisely when it and its complement are computably enumerable: dovetail the two enumerations to decide each input.

The diagonal halting problem $K=\{e:{\phi }_e(e)\downarrow \}$ is computably enumerable but not recursive. A total decider would yield a program which, on $e$, diverges if the decider says $e\in K$ and halts otherwise. Applying this program to its own index gives a contradiction. There is likewise no total computable universal listing of all total computable functions: the diagonal function $n\mapsto U(n,n)+1$ would be total and absent from the listing.

Here is a full proof of the Rice theorem. Let $\mathcal{P}$ be a nonempty proper class of partial computable functions whose property depends only on the function, not its program. First suppose the everywhere-undefined function $\perp$ is not in $\mathcal{P}$, and choose a program for a function $g\in \mathcal{P}$. Given an index $e$, construct uniformly a program which on $x$ first waits for ${\phi }_e(e)$ to halt and, only then, simulates $g(x)$. The S-m-n theorem gives a total computable index map $h$. If $e\notin K$, then ${\phi }_{h(e)}=\perp$; if $e\in K$, then ${\phi }_{h(e)}=g$. ThusA decision procedure for the property would decide $K$, impossible. If $\perp \in \mathcal{P}$, apply the same argument to its nontrivial complement. Every nontrivial extensional property of partial computable functions has an undecidable index set. Totality, having finite domain, and taking a particular value somewhere are examples. A syntactic property such as program length is not covered; nor does the theorem say that no individual program's behaviour can be established.

Self-reference can also be made effective. For a total computable index transformation $f$, let $d(x)$ be an index for the program which first computes ${\phi }_x(x)$ and then runs the program with that resulting index on its own input. The S-m-n theorem makes $d$ total computable. Choose an index $e$ for the total function $x\mapsto f(d(x))$, and put $n=d(e)$. ThenThis proves the recursion theorem: every effective transformation of programs has a fixed point at the level of the function computed, though not necessarily at the level of its numerical code.

Finally, consider the Jockusch triple coloring computing the halting set. Fix computable finite approximations $K_0\subseteq K_1\subseteq \cdots$ with union $K$. For $x<y<z$, defineThis is a total recursive two-coloring because both stages are finite computations. Suppose $H$ is infinite and homogeneous. Its color cannot be one: fix $x\in H$, wait until every enumeration below $x$ has stabilized, and choose later $y<z$ from $H$ beyond that stage. Their color is zero.

If $H$ has color zero, it computes $K$. On input $n$, use $H$ to find $x>n$ and $y>x$ in $H$. For arbitrarily large $z\in H$ with $z>y$, homogeneity gives $K_y\cap x=K_z\cap x$. Taking stages sufficiently large to reach the final finite approximation gives $K_y\cap x=K\cap x$. Consequently membership of $n$ in $K$ is decided by the finite stage $K_y$. A recursive $H$ would therefore make $K$ recursive, a contradiction. There is a recursive partition of triples with no infinite recursive homogeneous set. This is the nontrivial finite-color meaning of the partition of an infinite domain; if “infinite partition” meant infinitely many colors, the coloring by the least member would already give a trivial example. Ramsey's theorem still guarantees infinite homogeneous sets for the displayed two-coloring, but every such set is computationally nontrivial.

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.

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

A function in intension is a finite description of a computation, such as a program or a formal construction expression. A function in extension is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return $x$ directly and that compute $x+0$ describe the same function. Finite descriptions have Gödel numbers; equality of the resulting partial computable functions is a separate semantic question.

The primitive recursive functions are the smallest class of numerical functions containing the zero functions, the successor function and all projection functions, and closed under function composition in recursion theory and primitive recursion. More explicitly, from $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ the latter operation formsFor function composition in recursion theory, an $m$-ary $g$ and $k$-ary $h_1,\dots ,h_m$ give $g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$. Zero functions of all allowed arities can be included, with nullary zero included if arity $0$ is part of the coding convention. Every resulting function is total: the initial functions are total, function composition in recursion theory preserves totality, and mathematical induction on $n$ verifies totality of primitive recursion. Applying structural induction for primitive recursive functions then covers all construction expressions.

Use a fixed effective Gödel numbering of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The primitive recursive syntax and arity checking algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag $(k,j)$ is legal exactly when $1\le j\le k$, with output arity $k$. A composition node declares its output arity $k$ and is legal when its outer child has arity $m$, there are exactly $m$ inner children, and each has arity $k$; its arity is $k$. The declared arity also handles the case $m=0$. A recursion node is legal when its base child has arity $k$ and its step child has arity $k+2$; its arity is $k+1$. Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed $i$,This is a syntactic assertion about functions in intension. It does not assert that arbitrary machine indices computing primitive recursive functions form a decidable set. That extensional property is nontrivial, hence undecidable by Rice theorem. For an explicit reduction, given a program $e$ construct a program that, on every input, waits for ${\phi }_e(e)$ to halt and then returns $0$. Its extension is a primitive recursive function if $e\in K$, and otherwise is nowhere defined and so is not a primitive recursive function. A decision procedure for this latter semantic set would decide the diagonal halting set.

Enumerate the decidable syntax set $D_1$ in increasing code order as $p_0,p_1,\dots$. There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let $F_p$ be the extension of a valid construction and defineTo compute $U$, find $p_n$ by the syntax test and interpret its finite construction tree. Evaluate function composition in recursion theory by evaluating the children, and evaluate primitive recursion by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so $U$ and $d$ are total computable functions.

If $d$ were a unary primitive recursive function, some construction $p_j$ would have extension $d$. Then the diagonal argument giveswhich is impossible. The displayed $d$ is total and computable but not primitive recursive. Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the diagonal argument needs. The same argument shows that the two-variable interpreter $U$ cannot itself be primitive recursive.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine that, using membership queries to $B$, halts on every input and computes the indicator function of $A$. It may make several adaptive queries, and need not preserve the yes/no answer to a single query. A many-one reduction yields a Turing reduction by computing $f(x)$ and querying $B$ once. Two sets have the same Turing degree when each is Turing reducible to the other. Write $0^{\prime }$ for the degree of the diagonal halting set $K$.

We prove the Kleene–Post incomparability theorem by an oracle-assisted finite-extension construction. Fix an effective list $({\Phi }_e)$ of all Turing functionals. We shall build increasing finite binary strings ${\alpha }_s,{\beta }_s$ whose unions are the indicator functions of $A,B$. A finite oracle computation ${\Phi }_e^{\tau }(n)\downarrow =v$ means that the computation halts with output $v$ and every oracle query is strictly below $|\tau |$. Its answers are supplied by $\tau$. By the finite oracle use property, every infinite oracle extending $\tau$ preserves this computation.

Here is the decision available from $K$. Given $e,n$ and a finite string $\beta$, considerThis predicate is semidecidable: enumerate all finite extensions $\tau$ of $\beta$ and dovetail their finite oracle simulations, stopping at the first halting binary output. There is a computably produced program which, on its own index as well as on every other input, performs this search and halts exactly if it succeeds. Membership of its code in $K$ therefore decides $E$. In a yes case, running the search finds an actual witness $(\tau ,v)$. The decision oracle is essential in a no case; merely waiting would not produce a terminating construction.

Start with empty strings. At stage $s$ first ensureChoose $n=|{\alpha }_s|$, which is not yet assigned in $A$. Ask whether $E(s,n,{\beta }_s)$ holds. If yes, find a witness $(\tau ,v)$, extend the current $B$ string to $\tau$, and append the bit $1-v$ to the current $A$ string. If no, leave the current $B$ string unchanged and append $0$ to the current $A$ string. The yes case permanently forces disagreement at $n$, since later strings extend both commitments. In the no case no final oracle extending the current $B$ string can give a binary output at $n$: any such convergent computation would use finitely many bits and hence supply a forbidden finite witness. Thus it cannot be the indicator function of $A$ either, regardless of whether it diverges or returns a nonbinary value.

Next, using the strings just obtained, ensureby the same procedure with the roles reversed. Choose $m$ equal to the current length of the $B$ string, ask the analogous extension question about the current $A$ string, and, if it has witness output $v$, extend $A$ to that witness and append $1-v$ to $B$. Otherwise append $0$ to $B$. Finally pad both strings with zeros if necessary so that each length is at least $s+1$, and call the resulting strings ${\alpha }_{s+1},{\beta }_{s+1}$. Every operation is computable using the membership oracle $K$ and terminates. Earlier disagreements remain protected because no already fixed bit is ever changed.

Set $1_A={\bigcup }_s{\alpha }_s$ and $1_B={\bigcup }_s{\beta }_s$. The length condition makes these total binary functions. To compute either bit $n$ with oracle $K$, run the construction through stage $n$, when both strings have length at least $n+1$, and read that bit. Consequently $A,B{\le }_{T}K$. Every Turing functional has been defeated in both directions, soNeither set is computable, since a computable set is Turing reducible to every oracle. Neither can have degree $0^{\prime }$: if $K{\le }_{T}A$, then $B{\le }_{T}K{\le }_{T}A$, contrary to incomparability; the other case is symmetric. ThereforeThis proves the requested theorem. The argument does not claim $A$ or $B$ is computably enumerable; it constructs sets computable in $K$. Obtaining incomparable computably enumerable degrees is the stronger Friedberg–Muchnik theorem, which is not needed for the printed request.

If $M$ halts on every input, simulate $M$ on input $n$ while counting its steps, and output that count when it halts. The resulting function $t_M(n)$ is a total computable function. Consequently yes: one may take the exact running time,This construction does not promise a simple closed expression or a bound of any particular complexity class; it uses the promised totality of this particular machine.

For a machine computing a partial computable function, its exact halting-time function is still a partial computable function, with the same domain. A finite bound cannot cover a genuinely infinite computation. Even restricting attention to inputs on which $M$ halts, a total computable function bounding all halting times need not exist. In fact the precise characterization is the computable bound on halting time criterion:For the forward implication, compute $f(n)$ and simulate $M(n)$ for that many steps. If it has not halted, the proposed bound ensures that it never will. This decides the domain. Conversely, first decide whether $n$ is in the domain; return zero outside it and the simulated halting time inside it. This defines a total computable function satisfying the bound. The time needed to compute the bound itself is irrelevant to this argument.

A universal halting recognizer has undecidable domain by the halting problem, so it has no such total bound. On the other hand, a machine that immediately halts on even inputs and loops on odd inputs computes a nontotal partial computable function but has a constant bound on its halting times. Thus nontotality alone does not decide whether a total bound exists.

In the simply typed lambda calculus, types are generated from atomic types by the arrow constructor $A\to B$. A typed lambda term is a lambda term equipped with a derivation of a judgement $\Gamma ⊢t:A$, where the context assigns types to its free variables. The basic typing rules areThe Implicational Curry-Howard correspondence reads atomic types as propositions and $A\to B$ as logical implication. A typed variable is an assumption, abstraction is the implication introduction rule discharging that assumption, and application is the implication elimination rule. Consequently a typed lambda term is a proof in implicational Intuitionistic propositional logic, and a natural deduction proof recursively supplies such a term. For example, $\lambda x.x:A\to A$ expresses implication reflexivity. Products, sums, and the empty type extend the correspondence to conjunction, disjunction, and falsity; pure arrow types give precisely the implicational fragment. Beta reduction removes an introduction followed immediately by its elimination, matching proof simplification.

A Church numeral iswhere $f^{n}x$ means $n$ repetitions of application. At base type $A$, it has type $C_A=(A\to A)\to A\to A$. The following Church numeral arithmetic terms use left-associated application:Their concise conclusions areFor successor, the initial $f$ adds one application. For addition, the inner $nfx$ supplies $n$ applications and $mf$ supplies $m$ more. For multiplication, the repeated operation $nf$ applies $f$ $n$ times, and $m$ repetitions give $mn$. For exponentiation, $\overline{n}$ iterates the operation $\overline{m}$ on $f$: each iteration replaces a function $g$ by its $m$-fold iterate, yielding $f^{m^n}$. Zero iterations give $f$, so this encoding takes $m^0=1$, including $0^0=1$. The explicit outer $f,x$ abstractions make the result the standard Church numeral even at exponent zero, without needing eta equivalence.

Successor, addition, and multiplication operate on the same $C_A$. The displayed exponentiation term has type $C_A\to C_{A\to A}\to C_A$: its exponent iterates an operation on functions. Thus the numeral syntax admits several type instances; one should not force every occurrence into one fixed monomorphic Church type.

The Y combinator is the fixed-point combinatorFor $X_g=(\lambda x.g(xx))(\lambda x.g(xx))$, beta reduction gives $Yg{\to }_{\beta }{X}_g{\to }_{\beta }g{X}_g$. Since $X_g{\equiv }_{\beta }Yg$, we obtain $Yg{\equiv }_{\beta }g(Yg)$. This allows a recursive program body to receive a representation of itself.

Here the computation is in the untyped lambda calculus. The self-application $xx$ would require a simple type satisfying $A=A\to B$, impossible for finite simple types. Accordingly $Y$ is not a typed lambda term of the simply typed system. The Strong normalization theorem for simply typed lambda calculus also rules out a universal divergent fixed-point operator there.

To obtain a lambda representation of partial computable functions, encode machine configurations as finite data using Church numerals, Church pairs, and Church Booleans. Initial configuration, one transition, the halting test, and output extraction are primitive recursive functions, represented by lambda terms through the initial functions, composition, and lambda definition of primitive recursion by pair iteration. If these representations are $\mathsf{Init}$, $\mathsf{Next}$, $\mathsf{Halt}$, and $\mathsf{Out}$, defineUse normal-order beta reduction so the Church Boolean halting test selects one branch without evaluating the unused recursive branch. A halting computation follows finitely many transitions and returns the Church numeral of the output. A nonhalting computation forces successive tests forever and has no head normal form; by normal-order normalization theorem, it cannot be beta equivalent to a Church numeral. Thus every partial computable function is represented, with divergence preserved; every total computable function is the halting special case. This explains the role of $Y$ in computational universality while keeping the typed proof interpretation precise.

There is no computable presentation of a nonstandard model of Peano arithmetic. We prove Tennenbaum theorem by obtaining a computable set separating two recursively inseparable sets.

Fix an effective enumeration $({\phi }_e)$ of partial computable functions, implemented by deterministic machines, and putThese are disjoint computably enumerable sets. To see that they are recursively inseparable sets, suppose a computable set $D$ contains $U$ and avoids $V$. Its indicator function has some index $k$. If ${\phi }_k(k)=0$, then $k\in U\subseteq D$, contradicting that output. If ${\phi }_k(k)=1$, then $k\in V$, contradicting $D\cap V=\varnothing$. Thus neither output is possible.

Let $M\models \mathrm{PA}$ be a nonstandard model of Peano arithmetic. A recursive presentation of a structure here means a presentation on $\mathbb{N}$ in which its arithmetic operations are total computable functions; equality of presentation codes is ordinary equality. Write $\bar{n}$ for the element represented by the standard numeral $n$. The presentation codes of $\bar{0},\bar{1}$ are fixed constants, so $n\mapsto \bar{n}$ is a total computable function obtained by repeated addition. Presentation codes and the arithmetic values they name must be kept distinct.

Use bounded simulation of a computation predicates $H_i(e,t)$ saying that machine $e$, on input $e$, has halted by time $t$ with output $i$. We can choose these as primitive recursive predicates represented in Peano arithmetic. Determinism and induction on the computation length give, provably in Peano arithmetic, monotonicity in $t$ andA genuine standard halting computation has a finite certificate which Peano arithmetic verifies. Consequently, if $e\in U$ or $e\in V$, the corresponding $H_i(\bar{e},\bar{t})$ holds in $M$ for some standard $t$.

Choose a nonstandard element $c$ of $M$. It exceeds every standard numeral. Let $p_e$ be the $e$th prime number, starting with $p_0=2$. Peano arithmetic proves the prime-divisibility coding of a finite set needed here: for each $c$, an element $d$ can be formed as the product of precisely those $p_e$ with $e<c$ for which $H_0(e,c)$ holds. Formally,This is an internally finite product, not a claim that its externally observed index set is finite. Its existence follows by mathematical induction on the cutoff: start with $1$, multiply by the next distinct prime number when its predicate holds, and otherwise retain the product. Unique prime factorization ensures that earlier divisibility decisions are preserved. The standard prime enumeration and these finite-product constructions are provably total in Peano arithmetic.

Define the external subset $D=\{e\in \mathbb{N}:M\models p_{\bar{e}}\mid d\}$. If $e\in U$, its standard halting time is below $c$, and monotonicity gives $H_0(\bar{e},c)$, so $e\in D$. If $e\in V$, its output-one certificate and the provable incompatibility above exclude $H_0(\bar{e},c)$, so $e\notin D$. Hence $D$ separates $U$ and $V$.

Finally $D$ is a computable set. Given standard $e$, compute the ordinary integer $p_e$ and its numeral in the presentation. Enumerate all presentation codes $q$, and for each test the finitely many standard remainders $0\le r<p_e$ forEach test is decidable using the assumed total computable functions. The division theorem of Peano arithmetic guarantees a quotient and a remainder below the standard numeral ${\bar{p}}_e$. Every element below that numeral is one of $\bar{0},\dots ,\overline{p_e-1}$, so the search terminates; the remainder is unique. Return yes exactly when $r=0$. This makes $D$ a computable set, contradicting the recursively inseparable sets construction. Therefore

For sets $A,B\subseteq \mathbb{N}$, many-one reducibility means there is a total computable function $h$ such thatTuring reducibility $A{\le }_{T}B$ means that a Turing machine with oracle $B$ computes the indicator function ${\chi }_A$, halting on every input. A many-one reduction supplies a Turing reduction by computing $h(x)$ and making one membership query, so $A{\le }_{m}B$ implies $A{\le }_{T}B$.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with $A/{\le }_{T}B$ and $B/{\le }_{T}A$. We prove this by a finite-injury priority construction. Fix an effective enumeration $({\Phi }_e)$ of the oracle Turing functionals and arrange the requirements in the orderA requirement owns a private witness, a success flag and a priority restraint on its oracle set. All witnesses ever chosen are distinct. An $R_e$ witness $x$ is reserved outside $A$, and only $R_e$ may enumerate that number into $A$; an $S_e$ witness is treated symmetrically. A priority restraint $r$ forbids lower-priority requirements from adding numbers less than $r$ to the specified oracle set. Initializing a requirement abandons its witness, clears its success flag and sets its priority restraint to zero; enumeration into $A$ or $B$ is never undone.

At stage $s$ consider the first $s+1$ requirements and serve the highest-priority one requiring attention. An unsuccessful requirement requires attention if it has no witness, or its current witness has a stage-$s$ oracle computation with output zero, found within $s$ steps. If there is no such requirement, do nothing. When a requirement with no witness is served, choose a fresh number larger than $s$, all previously chosen witnesses and all current higher-priority priority restraints. When an $R_e$ with a witness $x$ and observed computation ${\Phi }_e^{B_s}(x)=0$ is served, enumerate $x$ into $A$, mark it successful, and restrain $B$ below the use of that computation. The use is one more than the largest queried oracle position, or zero if there were no queries. An $S_e$ acts in exactly the same way with $A,B$ interchanged. After either kind of service, initialize every currently assigned lower-priority requirement; the remaining lower priorities are already in their initial state.

This is an effective stage construction with finite sets $A_s,B_s$, and $A={\bigcup }_s{A}_s$, $B={\bigcup }_s{B}_s$ are computably enumerable. Every enumeration respects all higher-priority priority restraints: its private witness was selected above them, and any later service to a higher-priority requirement would have initialized it before it could act. We do not need to restrain a computation whose output is nonzero; a persistent nonzero output already disagrees with an unenumerated witness.

We verify the finite injury assertion by induction along the priority order. After the last service to requirements above a fixed requirement $Q$, the requirement $Q$ is never initialized again. It can be served at most twice thereafter, once to choose its final witness and once to diagonalize. Whenever it needs attention it is eventually served, since the higher-priority requirements have ceased acting and each later stage considers a longer initial segment. Thus $Q$ has a final witness and makes only finitely many actions; this proves the induction and justifies the assumed last service above it.

For a final $R_e$ witness $x$, if the diagonalization occurs then ${\chi }_A(x)=1$, while preservation of a restrained oracle computation applies: its zero computation is preserved permanently because higher priorities no longer act and lower priorities respect the priority restraint. Thus ${\Phi }_e^B(x)=0\ne {\chi }_A(x)$. If it never occurs, then ${\chi }_A(x)=0$. Were ${\Phi }_e^B(x)=0$, that convergent computation would use finitely many oracle answers. Because $B_s$ increases to $B$, those finitely many answers eventually stabilize, and a sufficiently late stage would discover the zero computation and cause diagonalization. This contradicts its never occurring. So in this case ${\Phi }_e^B(x)$ is undefined or nonzero and again disagrees with ${\chi }_A$. The identical argument verifies every $S_e$.

All the requirements hold, proving the theorem. Both sets are noncomputable: a computable set is Turing reducible to every oracle. Moreover, every computably enumerable set is Turing reducible to the diagonal halting set $K$, and neither $A$ nor $B$ can have its Turing degree, since that would make it compute the other set. HenceThis also gives many-one incomparability and answers the existence of intermediate computably enumerable Turing degrees.