Computability theory

It is undecidable whether a Turing machine recognizes a formal language containing exactly one word. Reduce the halting problem by a Turing machine that rejects every nonempty input and, on the empty word, simulates a fixed computation and accepts if that computation halts. Its recognized formal language is a singleton exactly when the fixed computation halts.

Give a nonhalting Turing machine computation halting time infinity. The formal language of pairs satisfying the displayed inequality is a co-recursively enumerable language but is not a recursively enumerable language. A violation has a finite witness: $N_1$ has halted on some input after $t$ moves while $N_2$ has not halted by that time. For the other direction, reduce non-halting by making $N_1$ simulate a fixed computation on every input and making $N_2$ run forever. The pair satisfies domination exactly when the fixed computation never halts. The convention $\infty \ge \infty$ is essential to this many-one reduction.

Let $K_s$ be increasing finite stage approximations to a noncomputable computably enumerable set $K$. For $x<y<z$, colour the triple zero exactly when $K_y\cap [0,x]=K_z\cap [0,x]$. An infinite homogeneous set has colour zero, since each bounded approximation eventually stabilizes. Its first two elements above any requested bound recover the final approximation at that bound, so the homogeneous set computes $K$. Thus no infinite homogeneous set is computable. This illustrates the difference between a Ramsey's theorem existence result and an effective construction.

Let $K_s$ be a computable increasing finite-stage enumeration of the halting problem set $K$. Color $x<y<z$ by whether the approximations below $x$ differ at stages $y,z$. This is a recursive two-color partition of triples. An infinite homogeneous set cannot have color one: for fixed $x$, the finite approximation below $x$ eventually stabilizes. If its color is zero, choose $x$ from that set above an input $n$, then another member $y>x$; agreement with arbitrarily large later stages gives $K(n)=K_y(n)$. Thus every infinite homogeneous set computes $K$, and none is a recursive set. This makes the failure of an effective version of Ramsey's theorem explicit.

A function in intension is a finite program or formal construction description. Its associated function in extension is the partial or total input-output map it denotes. A Gödel number records the description rather than identifying all descriptions with the same extension.

A function in extension is a function specified by its domain and the value at each input in that domain. Distinct functions in intension can have this same extension. Properties of the extension of an arbitrary program are semantic properties, to which Rice theorem applies when the property is nontrivial.

A total binary-valued function is diagonally noncomputable if it differs from each defined diagonal value in an effective enumeration of partial computable functions. Nonbinary diagonal outputs are automatically different. No such function is computable: its own program index would contradict the defining condition. Choosing the opposite bit at every defined binary diagonal value proves existence without supplying a computable procedure.

A bounded simulation records whether a specified deterministic program has halted, with a specified output, within a given finite number of steps. This is a primitive recursive predicate of the program code, input and time bound. Peano arithmetic can verify genuine finite computation certificates and prove that two different outputs cannot both be the first halting output.

A set $P$ is productive when a partial computable function returns an element of $P$ outside any computably enumerable subset supplied by its index. The function must halt for every index of a subset of $P$, including finite subsets. Productive sets are not computably enumerable.

Uniformly diagonalize against the formula expressing membership in $W_e$ to obtain a sentence saying that its own code is not in $W_e$. If every enumerated sentence is true, this new sentence cannot be enumerated, and hence is true. Its code is a computable new element of arithmetic truth outside $W_e$.

Kolmogorov complexity measures the length of a shortest effective description of an object. Fixing an optimal description machine gives an invariant quantity up to an additive machine-dependent constant. Plain Kolmogorov complexity is especially convenient for counting descriptions shorter than a binary string.

For a fixed optimal description machine $U$, the plain Kolmogorov complexity of a binary string is the minimum length of a finite program producing it. The admissible programs need not satisfy a prefix restriction. There are at most $2^n-1$ descriptions shorter than $n$, which is the counting fact behind the existence of incompressible strings.

A binary string is incompressible relative to a fixed optimal description machine when its plain Kolmogorov complexity is at least its length. A counting argument gives at least one such string at each length, and their set is immune.

If an infinite computably enumerable family contained only incompressible strings, select its first enumerated string of length at least $n$. This is a total computable selection rule, and its selected string has a description of length $O(\log n)$ encoding the threshold. For large $n$ that is shorter than the selected string. This contradiction proves immunity.

A description machine is a partial computable map from finite binary programs to finite binary outputs. It is optimal if, for every other description machine $V$, there is a constant $c_V$ such that $C_U(\sigma )\le C_V(\sigma )+c_V$. Encoding an interpreter index in a fixed prefix gives the constant-overhead descriptions used in incompressibility arguments.

A decision problem for which no algorithm terminates with the correct yes-or-no answer on every input. For example, if the diagonal halting set had a decision algorithm, a program could halt on its own code exactly when that algorithm says it does not halt, producing a contradiction. An undecidable decision problem may still admit a partial procedure that terminates on every yes-instance.

A finite-injury priority construction orders countably many requirements so that each has finitely many predecessors. A strategy may discard lower-priority strategies' current witnesses and restraints when it acts. If each requirement acts finitely often after its last such initialization, induction on priority shows that every requirement is injured only finitely often and eventually has a stable strategy. The Friedberg–Muchnik theorem is a central example.

A priority restraint protects finitely many oracle answers by requiring lower-priority enumerations to avoid positions below a numerical bound. Higher-priority action can cancel the priority restraint by initializing its owner. After the last such injury, the protected computation is permanent.

An oracle computation queries only finitely many positions. If the oracle remains unchanged below its use, the same computation has the same output. In a finite-injury priority construction, a successful requirement imposes this bound on lower priorities; the induction that higher priorities stop acting then makes the disagreement permanent.

To prevent a Turing functional ${\Phi }_e^B$ from computing the indicator function of an enumerated set $A$, reserve a permanently unique fresh witness $x$. On observing a convergent computation with oracle use $u$, enumerate $x$ into $A$ if the answer is zero; otherwise keep it out. Restrain subsequent lower-priority enumerations into $B$ below $u$. Higher-priority actions may initialize this strategy and retire its witness, but witnesses are never reused. In a finite-injury priority construction, mathematical induction on priority shows that the final computation, if observed, remains correct as a computation from the final oracle and disagrees with $A$ at $x$. If no computation is ever observed after the final initialization, the final oracle computation diverges, since any convergent computation uses only finitely many eventually stable oracle bits.

There are computably enumerable sets $A,B$ with $A/{\le }_{T}B$ and $B/{\le }_{T}A$. A finite-injury priority construction alternates requirements preventing oracle programs for $B$ from computing $A$ and programs for $A$ from computing $B$. Each requirement uses a private witness, enumerates it when the opposing computation gives zero, and restrains the oracle segment preserving that disagreement. Verification inducts on priority. Both degrees are noncomputable and strictly below the halting degree, resolving Post problem.

The incomparable-degree formulation is stated in Steffen Lempp's notes, section 1.1.

An injury discards a strategy's current witness or restraint when a higher-priority action changes its assumptions. Finite injury means that each strategy experiences only finitely many such resets. The final uninjured strategy must still be checked to satisfy its requirement; finite injury alone is not the conclusion.

A set $A$ is Turing-reducible to $B$ when an oracle machine with membership oracle $B$ computes the characteristic function of $A$. Unlike a many-one reduction, it may make adaptive queries and reverse or combine oracle answers.

Build an infinite oracle as an increasing union of finite binary strings. With the diagonal halting set as an oracle, decide whether some finite extension makes a specified Turing functional halt with a binary output at a fresh input. In a yes case, preserve that finite computation and commit the opposing set's bit to the opposite value. In a no case, no subsequent infinite extension can yield a characteristic-function value there. Length growth makes the resulting sets computable in the halting oracle.

A Turing functional is a partial computation performed by an oracle machine, viewed as a function of both the oracle $B$ and input $x$. Oracle programs admit an effective enumeration. Every convergent computation inspects only a finite part of its oracle, recorded by its oracle use.

The use of a convergent oracle computation is one more than its largest queried position, or zero if there are no queries. Preserving the oracle below this number preserves the computation. This finite dependence supplies the restraints in a finite-injury priority construction.

The Turing degree of a set is its equivalence class under mutual Turing reducibility. Degrees inherit the partial order induced by Turing reducibility. The Friedberg–Muchnik theorem gives incomparable degrees represented by computably enumerable sets.

There are incomparable Turing degrees strictly between the computable degree and the degree of the diagonal halting set. An oracle-assisted finite-extension construction alternately defeats each Turing functional in the two directions. Since the sets are computable in the halting oracle, their degrees are at most $0^{\prime }$; incomparability makes them nonzero and strictly below $0^{\prime }$. This theorem does not require the constructed sets to be computably enumerable. The Friedberg–Muchnik theorem supplies that stronger conclusion.

Post problem asks whether a computably enumerable set can have a Turing degree strictly between the computable degree and the degree of the halting problem. The Friedberg–Muchnik theorem answers yes by constructing two incomparable computably enumerable degrees.

The Church–Turing thesis asserts that every effectively calculable function is computable by a formal model equivalent to a Turing machine. It identifies an informal notion of effective procedure with a mathematical class rather than stating a theorem within one formal system.

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]

A primitive recursive pairing function is a pairing function whose encoding function and both coordinate functions of its inverse function are primitive recursive functions. Thus the bijection can be used in either direction inside a construction by primitive recursion and function composition in recursion theory. A decoder that is merely a computable function would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding functions; his more general systems need only be injective, whereas a pairing function here is a bijection.^[ref]

The Cantor pairing function is a primitive recursive pairing function. For its encoding, construct the triangular numbers directly by primitive recursion:Since addition is primitive recursive, so are $T$ and $\pi$ by primitive recursion and function composition in recursion theory. This establishes the claim without treating division by two as an unexplained primitive operation.

For decoding, use bounded minimization to defineThe bound is valid for every natural number $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\le z$; when $s(z)=0$, that lower inequality follows from $T(0)=0$. Thus this search finds exactly the diagonal in the Cantor pairing function inverse, withThe comparison is primitive recursive, and bounded minimization of a primitive recursive predicate is primitive recursive. Therefore $s$ is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation $a\dot{-}b=\max (a-b,0)$: apply the predecessor function $b$ times to $a$ by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply $0\le R(z)\le s(z)$. Consequently $L$ and $R$ are primitive recursive functions, and $\pi (L(z),R(z))=z$. Zimmermann proves the relevant closure under bounded minimization and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.^[ref]

For a worked bounded minimization, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the primitive recursive functions; it is not a claim that scanning all candidates is the fastest implementation.

For each fixed $k\ge 1$, define a tuple encoder byEach $E_k$ and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to $\pi ,L,R$. For the three-entry tuple encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The tuple length remains part of the agreed convention, as explained for a general pairing function.

This makes primitive recursive pairing functions useful for encoding several evolving values as one state in primitive recursion. For example, store consecutive Fibonacci numbers as $c(0)=\pi (0,1)$ and update byThe codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses primitive recursive encoding, decoding and addition; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable Gödel numbering should permit sufficiently simple decoding: representation should preserve the class of functions being studied.

The bracket enumerates the positive integers not divisible by $10$. Every positive integer has exactly one decomposition into a power of $10$ times such an integer, so this formula is a bijection from ${\mathbb{N}}^2$ to $\mathbb{N}$. Subtracting one in the codomain includes zero without requiring a trailing-zero convention for its decimal representation. For the inverse, write $N+1=10^{i}q$ with $10\nmid q$, then $j=q-1-\lfloor q/10\rfloor$.

A register machine has finitely many states and finitely many addressed registers, together with instructions that inspect and modify register contents and change state. A computed partial function is defined by the contents at the halt state.

In a string register machine, ${+}_a(k,q)$ appends $a$ to register $k$; ${?}_a(k,p,q)$ branches according to whether its final letter is $a$; ${?}_{\epsilon }(k,p,q)$ tests emptiness; and $-(k,p,q)$ branches to $p$ when empty, or deletes the final letter and branches to $q$ otherwise.

A machine computes the characteristic function of a language $X$ when it halts on every input with the one-letter output $1$ for inputs in $X$ and $0$ for inputs outside $X$.

Two string registers can recognize $\{a^n{b}^n:n>0\}$ by storing one marker per $a$ and removing one per $b$. A machine with only its input register cannot: two different terminal $b$-block lengths eventually reach the same state and remaining prefix, forcing equal outputs for one member and one nonmember.

To recognize words ending in a fixed symbol $a$, test the final input letter, choose one of two erasing loops, and append $1$ after the accepting loop or $0$ after the rejecting loop. The empty word follows the rejecting branch.

Replace the original halt state by a continuation state that tests whether its one-letter output is $0$ or $1$, removes it, appends the other symbol, and enters a new halt state. This computes the complement language without changing termination behavior.

Primitive recursive functions are generated by zero, successor, and projections under composition and primitive recursion.

For a decidable coding of finite construction trees, the codes of arity-$i$ primitive recursive functions in intension are decidable. Check initial-function tags, then verify the child arities at each composition and recursion node. This is a terminating finite syntax check, distinct from asking whether an arbitrary program's extension happens to be primitive recursive.

Enumerate all valid unary primitive recursive functions in intension by their decidable codes $p_n$, and interpret each extension $F_{p_n}$. The function $d(n)=F_{p_n}(n)+1$ is a total computable function, since each finite construction terminates. If it were primitive recursive, some $F_{p_j}$ would equal $d$, giving $d(j)=d(j)+1$. Repeated extensions in the syntax enumeration do not affect this argument.

A valid finite construction expression from the initial functions of recursion theory by function composition in recursion theory and primitive recursion. Its extension is a primitive recursive function. The construction grammar supplies both a decidable syntax and a total computable interpreter, but no uniformly primitive recursive interpreter for all valid codes.

For a fixed effective machine coding, the predicate that program $e$ on input $x$ halts within $t$ steps is primitive recursive. Code finite configurations, iterate a total single-step function by primitive recursion, and test for the halt state. This supplies a bounded simulation even though the unrestricted halting problem is undecidable.

Search over the finite interval $0\le y\le b$ for the least witness to a primitive recursive predicate, with an explicitly chosen default if there is none. The result is a primitive recursive function, by scanning this finite interval using primitive recursion. This differs from unbounded minimization, which may fail to terminate.

The predecessor function on the nonnegative integers is $\mathrm{pred}(0)=0$ and $\mathrm{pred}(n+1)=n$. This is a primitive recursive function by primitive recursion from the zero and projection functions.

The initial functions are the zero function, the successor function, and all coordinate projections.

The zero function has the constant valueDummy variables give a zero function of any finite arity.

The successor function is

The $i$th $k$-ary projection returns its $i$th input:

Given a $m$-ary function $g$ and $k$-ary functions $h_1,\dots ,h_m$, composition forms

From $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$, primitive recursion defines

The functions generated from the initial functions using composition alone are exactlyfor a constant $c\in \mathbb{N}$. Structural induction proves necessity, and iterating the successor function on zero or a projection proves sufficiency.

To prove a property of every primitive recursive function, prove it for the zero, successor, and projection functions, then prove that it is preserved by composition and by primitive recursion. This is structural induction on the finite construction of the function.

The initial functions are total, composition preserves totality, and ordinary induction on the recursion argument shows that primitive recursion applied to total functions is total. Structural induction therefore proves that every primitive recursive function is total.

The graph of every primitive recursive $f:{\mathbb{N}}^k\to \mathbb{N}$ has a formulain the language of ordered rings, where every quantifier inside $\delta$ is bounded. Composition uses existentially quantified intermediate values, while primitive recursion uses a boundedly checked code for the finite sequence of intermediate values.

The Gödel beta function codes finite sequences by remainders:Choosing $c$ sufficiently large and divisible by the relevant small integers makes the moduli pairwise coprime, so the Chinese remainder theorem codes any prescribed finite sequence.

The graph of the factorial function has a fixed-length first-order formula in the language of ordered rings interpreted on the natural numbers. A remainder code records $a_0=1$, $a_n=y$, and $a_{i+1}=(i+1)a_i$ for every $i<n$. Uniqueness of remainders proves $y=n!$; sufficiently large pairwise-coprime moduli and the Chinese remainder theorem supply a code for every input. Formula length is independent of the input variable's value, although substituting a numeral adds its encoding length.

In a primitive recursion, an existential representation of the step function may need a different witness tuple at every time. Code each coordinate of the finite witness array by a separate beta-function code pair. All row witnesses then have bounded remainder quantifiers under the bounded time quantifier, while the finitely many code pairs remain in the outer unrestricted existential block.

A list $f(n,k)$ of all functions in a class closed under diagonal substitution and successor misses $d(k)=f(k,k)+1$.

A set is computably enumerable when a program halts precisely on its members. Equivalently, it is the domain of a partial computable function or some algorithm lists its elements.

A computably enumerable set is simple when its complement of a set is an immune set: the complement is infinite and contains no infinite computably enumerable subset. Equivalently, it is coinfinite and meets every infinite computably enumerable set. A simple set is not decidable.

Enumerate all computably enumerable sets as $W_e$. For each $e$, once a witness $x>2e$ appears in $W_e$, enumerate one such witness into $X$ and never act for $e$ again. Every infinite $W_e$ supplies a witness. Only requirements $e<n$ can put numbers into $[0,2n]$, so at least $n+1$ numbers in that interval stay outside $X$. Thus $X$ is a simple set. The proof uses a numerical bound rather than an infinitude test.

An immune set is infinite but contains no infinite computably enumerable subset. Thus its infinitude cannot be witnessed by any effective infinite listing that stays entirely inside the set. Finite strings can be treated as natural-number codes for this definition.

Every nonempty computably enumerable set $X\subseteq \mathbb{N}$ is the range of a primitive recursive function $f:\mathbb{N}\to \mathbb{N}$. Choose $x_0\in X$, decode $n=⟨x,t⟩$ using a primitive recursive pairing function, and output $x$ if the recognizing machine halts within $t$ steps, or $x_0$ otherwise. The bounded halting predicate makes this function primitive recursive, and every member of $X$ occurs for a sufficiently large bound. The empty set is excluded because such a function is total.

A set is computable when an algorithm decides membership for every input and always halts. Equivalently, both the set and its complement are computably enumerable.

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.

Kleene recursion gives programs access to their own effective descriptions: every computable transformation of program indices has a semantic fixed point.

A many-one reduction $A{\le }_{m}B$ is a total computable $f$ satisfying $x\in A$ exactly when $f(x)\in B$.

Two sets have the same many-one degree when each many-one reduces to the other.

A staged-enumeration reduction controls an output language by enumerating more elements at each simulation stage and changing behavior when a source computation halts.

A set $A$ is complete for a class $\mathcal{C}$ under many-one reductions when $A\in \mathcal{C}$ and every $B\in \mathcal{C}$ satisfies $B{\le }_{m}A$.

An index set is a set of program codes whose membership depends only on the partial function or enumerable language computed, rather than the code's syntax.

An extensional program property gives identical answers to all codes computing the same object.

Every nontrivial extensional property of partial computable functions or computably enumerable languages is undecidable.

For an effective enumeration $f_{w,1}$ of unary partial computable functions,is an index set.

For a nonempty set $X$ of words, the propertyis a nontrivial extensional property of unary partial computable functions: the nowhere-defined function fails it, while any total constant function with value in $X$ satisfies it. The Rice theorem therefore makes its index set undecidable.

The cofinite index set contains codes whose enumerable language has finite complement.

The padding lemma produces infinitely many syntactically distinct program indices for the same computed function or language.

Dovetailing interleaves finite stages of multiple computations so that every computation that halts is eventually observed.

The S-m-n theorem says that fixed inputs can be compiled into program codes by a total computable transformation. For every $m,n\ge 1$, there is a total computable $s_n^m$ such thatwhenever either side is defined.

A partial function is computable when a program returns its value on every input in its domain and runs forever on inputs outside its domain.

A universal partial computable function simulates the program with index $e$ on input $\mathbf{x}$, reproducing both its output and its divergence. Decode the finite program and repeatedly apply its transition rule. This gives a partial computable function of the code and inputs. There can be no total computable evaluator whose rows are precisely all total computable functions, because $n\mapsto U(n,n)+1$ would be a missing diagonal row.

For every partial computable function $f(\mathbf{x})$, there are total primitive recursive functions $C,U$ such thatHere $C$ is zero exactly on codes of valid halting computation histories for the chosen program and input, and $U$ extracts the final output. Coding finite configurations and finite histories makes checking every local step a bounded primitive recursive operation. If a computation halts, some history code passes and every passing code has the same output; if it does not halt, none passes. This is the usual normal-form version with the program index fixed; a universal predicate can also retain that index as an input.

For a partial function $g(\mathbf{x},y)$, unbounded minimization definesas the least $y$ at which $g$ is zero, provided the preceding required computations are defined. If no such $y$ is found, $f(\mathbf{x})$ is undefined. Closing the primitive recursive functions under this operation gives the partial recursive functions.

A total computable function is a computable function whose domain is the entire input space.

A total computable function is a computable function whose domain contains every allowed input.

For a theory of arithmetic $T$ and a program index $e$, the function ${\phi }_e$ is provably total in $T$ when $T$ proves its canonical totality sentenceIf $T$ is recursively axiomatized, the indices of its provably total functions form a computably enumerable set.

For a program code $e$, input $x$, and time bound $t$, the truncated computation simulates program $e$ on $x$ for at most $t$ steps and reports either its output or that no halt occurred within the bound. This is a total computable function of $(e,x,t)$.

One convention for the Ackermann function on nonnegative integers isIts two-argument recursion defines a computable function; fixing the convention matters when defining an inverse Ackermann function.

For the displayed Ackermann function convention, one possible inverse-growth scale is $\alpha (n)=\min \{m\ge 1:A(m,m)\ge n\}$ for positive integers $n$. It gives $\alpha (n)=1$ through $3$, $2$ from $4$ through $7$, and $3$ from $8$ through $61$. Several inverse Ackermann function conventions occur in algorithm analysis; changing convention can shift these small values without changing the very slow growth relevant to the disjoint-set data structure. This inverse-growth definition does not invert a two-variable function as an ordinary one-variable inverse function.

The arithmetical hierarchy classifies sets by alternating blocks of number quantifiers over computable predicates.

A bounded quantifier has the form $\exists x<t\phi$ or $\forall x<t\phi$, where the term $t$ does not contain $x$. It ranges over a finite initial segment in the standard natural numbers.

An arithmetic bounded formula uses only quantifiers bounded by arithmetic terms, such as $\exists u<t$ and $\forall u<t$, with the bound not containing the quantified variable. Existential bounded representation of a primitive recursive function places all unrestricted existential variables in a single outer block.

A bounded arithmetic sentence is an arithmetic bounded formula with no free variables. Every quantifier is restricted by an arithmetic first-order term. In the standard natural numbers such a first-order sentence has a definite truth value determined by finite bounded searches.

A ${\Delta }_0$ formula is an arithmetical formula in which every quantifier is bounded.

A ${\Sigma }_1$ formula is equivalent to $\exists \mathbf{y}\delta$ with $\delta$ bounded. A ${\Pi }_1$ formula is equivalent to $\forall \mathbf{y}\delta$ with $\delta$ bounded.

If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.

An arithmetic theory is Sigma-1 complete when it proves every true Sigma-1 formula that is a sentence. A genuine finite proof gives a true existential assertion that a code is a proof; Sigma-1 completeness therefore supplies the external necessitation clause for the usual arithmetical provability predicate. Its formalized version says that, for each Sigma-1 sentence $\sigma$, $T⊢\sigma \to {\mathrm{Pr}}_T(┌\sigma ┐)$. Applying this to a provability assertion, which is itself Sigma-1, gives the third of the Hilbert-Bernays-Löb derivability conditions.

A set $A$ is in ${\Sigma }_1$ exactly when it is the domain of a partial computable function. Equivalently, there is a computable predicate $R$ such that