Computability theory asks which tasks can be performed by an algorithm, and which cannot, using precise models such as Turing machines and recursive functions. It distinguishes a total computable function, which returns an answer on every input, from a partial one, which may never halt on some inputs.
The halting problem is the central limitation: no algorithm decides for every encoded program and input whether that computation eventually stops. Nevertheless, halting instances can be enumerated by simulating computations for successively longer times. This illustrates the distinction between a computable set and a computably enumerable set. The subject concerns the existence of computation; computational complexity theory further asks how much time or space a computation needs.
A program index is a natural number encoding a program in a fixed effective enumeration of programs, often written for the corresponding partial computable functions. The meaning of an index depends on the chosen programming model and enumeration; may be undefined because program does not halt on input .
The universal partial computable function simulates the indexed program: whenever that computation halts. Two different indices can compute the same partial function, because different program texts can implement identical behavior. Equality of indices is therefore a syntactic test, whereas equality of computed functions is a semantic property.
The halting problem becomes the question whether is defined. Encoding programs as numbers also permits diagonal arguments, such as constructing a computation that uses its own index as input. These arguments concern a specified effective enumeration, rather than assuming every sequence of functions can be uniformly simulated.
A computable predicate is a yes-or-no relation for which an algorithm halts on every input and returns the correct truth value. Equivalently, its indicator function takes values in and is a total computable function. For predicates of several natural numbers, a fixed effective tuple encoding reduces the inputs to one number if needed.
For example, defined by is computable: with a stated convention for , integer division or finite arithmetic decides it. The predicate that program halts on input within at most steps is also computable, by bounded simulation.
In contrast, the existence of some halting time, , is not a computable predicate in general: it is the halting problem. It is computably enumerable because a successful simulation eventually witnesses it. Thus an unbounded existential quantifier can turn a decidable relation into one whose false instances cannot be recognized by a terminating procedure.
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: has halted on some input after moves while has not halted by that time. For the other direction, reduce non-halting by making simulate a fixed computation on every input and making run forever. The pair satisfies domination exactly when the fixed computation never halts. The convention is essential to this many-one reduction.
Let be increasing finite stage approximations to a noncomputable computably enumerable set . For , colour the triple zero exactly when . 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 . Thus no infinite homogeneous set is computable. This illustrates the difference between a Ramsey's theorem existence result and an effective construction.
Let be a computable increasing finite-stage enumeration of the halting problem set . Color by whether the approximations below differ at stages . This is a recursive two-color partition of triples. An infinite homogeneous set cannot have color one: for fixed , the finite approximation below eventually stabilizes. If its color is zero, choose from that set above an input , then another member ; agreement with arbitrarily large later stages gives . Thus every infinite homogeneous set computes , 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 is productive when a partial computable function returns an element of outside any computably enumerable subset supplied by its index. The function must halt for every index of a subset of , including finite subsets. Productive sets are not computably enumerable.
Uniformly diagonalize against the formula expressing membership in to obtain a sentence saying that its own code is not in . 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 .
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 , 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 descriptions shorter than , 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 . This is a total computable selection rule, and its selected string has a description of length encoding the threshold. For large 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 , there is a constant such that . 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 from computing the indicator function of an enumerated set , reserve a permanently unique fresh witness . On observing a convergent computation with oracle use , enumerate into if the answer is zero; otherwise keep it out. Restrain subsequent lower-priority enumerations into below . 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 at . 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 with and . A finite-injury priority construction alternates requirements preventing oracle programs for from computing and programs for from computing . 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 is Turing-reducible to when an oracle machine with membership oracle computes the characteristic function of . 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 and input . 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 ; incomparability makes them nonzero and strictly below . 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 to , with two computable functions recovering its coordinates. Here consists of the natural numbers, including zero. If is the pairing function and 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 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 , list . There are ordered pairs there, and ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from through . These intervals touch without overlapping and cover all natural numbers; within each interval the offset 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]
https://www.cs.cmu.edu/~cdm/resources/02-coding.pdf. Klaus Sutner, Primitive Recursion, Carnegie Mellon University, spring 2021, slides 9–13: pairing systems and the Cantor polynomial
For example, the Cantor pairing function givesThe order of the coordinates matters: and are different ordered pairs with different codes.
The Cantor pairing function on a finite window: labels are codes, and the first 21 ordered pairs fill diagonals zero through five
. Details. To decode a natural number , find the unique diagonal index satisfyingThe inequality gives , so both recovered coordinates are natural numbers. At , , hence , , and . At , 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 . Use an exact integer square root instead: with computed using integer arithmetic, . 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 binary digits has possible values, while two such words have 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 . 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 asDecode the outer ordered pair first: gives . Decode its first coordinate to recover , giving the nested ordered pair and thus the original tuple .
The tuple length and nesting convention must be known. The same code represents as a two-entry tuple and 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]
https://doi.org/10.1515/crelle-1878-18788413. Georg Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, 1878: publisher bibliographic record
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]
https://www.cs.cmu.edu/~cdm/resources/02-coding.pdf. Klaus Sutner, Primitive Recursion, slide 9: primitive recursive encoding and unpairing functions
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 and 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 : , so the candidate always succeeds. The search includes zero; when , it immediately returns . If , the preceding candidate failed, which gives ; when , that lower inequality follows from . 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 is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation : apply the predecessor function times to by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply . Consequently and are primitive recursive functions, and . 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 here.[ref]
https://tore.tuhh.de/bitstream/11420/1312/1/book.pdf. Karl-Heinz Zimmermann, Computability Theory, §2.3, Proposition 2.26 and Propositions 2.32–2.34, printed pages 18 and 21–22
For a worked bounded minimization, take . Candidates give , none exceeding . Candidate gives , so , , and . The search bound was ; 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 , define a tuple encoder byEach and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to . For the three-entry tuple encoded as , applying returns , applying returns , and then , . 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 and update byThe codes start , decoding to . 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 . Every positive integer has exactly one decomposition into a power of times such an integer, so this formula is a bijection from to . Subtracting one in the codomain includes zero without requiring a trailing-zero convention for its decimal representation. For the inverse, write with , then .
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, appends to register ; branches according to whether its final letter is ; tests emptiness; and branches to when empty, or deletes the final letter and branches to otherwise.
A machine computes the characteristic function of a language when it halts on every input with the one-letter output for inputs in and for inputs outside .
Two string registers can recognize by storing one marker per and removing one per . A machine with only its input register cannot: two different terminal -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 , test the final input letter, choose one of two erasing loops, and append after the accepting loop or 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 or , 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- 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 , and interpret each extension . The function is a total computable function, since each finite construction terminates. If it were primitive recursive, some would equal , giving . 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 on input halts within 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 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 and . 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 successor function on the natural numbers is the function . With as the initial natural number, its repeated application produces .
In recursion theory, the successor function is an initial function of recursion theory. Together with the other initial functions and the permitted operations, it helps generate primitive recursive functions. For example, addition can be specified recursively by and . This description builds addition from a base case and a successor step, matching the structure used in mathematical induction.
The functions generated from the initial functions using composition alone are exactlyfor a constant . 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 has a formulain the language of ordered rings, where every quantifier inside 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 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 , , and for every . Uniqueness of remainders proves ; 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 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 . For each , once a witness appears in , enumerate one such witness into and never act for again. Every infinite supplies a witness. Only requirements can put numbers into , so at least numbers in that interval stay outside . Thus 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 is the range of a primitive recursive function . Choose , decode using a primitive recursive pairing function, and output if the recognizing machine halts within steps, or otherwise. The bounded halting predicate makes this function primitive recursive, and every member of 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 of words, the following are equivalent: is computably enumerable, is the domain of a partial computable function, is the range of a partial computable function, and 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.
Fix an effective numbering of the partial computable functions with a universal partial computable function and the parameter compilation supplied by the S-m-n theorem. For every total computable function , there is a program index such thatHere means equality as partial functions, including the inputs on which computation diverges. The conclusion concerns a program's behavior, not equality of program indices: has no numerical fixed point, but still has this semantic fixed point.[ref]
Introduction to the Theory of Computation by Jean Gallier (2017). Section10.5, Theorem10.22, printed pp.276–277
For a proof, the S-m-n theorem gives a total computable function compiling into a program that, on input , first computes and then runs the program with that resulting index on . Thuswhere both sides diverge if the inner computation does. Choose an index for the total computable function . Setting givesThe theorem makes rigorous a program's ability to use a description of itself. For example, let compile a program that ignores its input and prints . Its semantic fixed point is a program that prints its own index. This does not require a program to read its source file.
Two sets have the same many-one degree when each many-one reduces to the other.
A many-one reduction can compile a source instance into a program whose domain of a function changes according to the successive finite stages of a simulation. The compiler must be a total computable function; the compiled program may diverge.
For example, let be the diagonal halting set. Compile into a program that, on input , uses a bounded simulation of a computation to test whether halts within steps. If no halt is seen, return zero; if a halt is seen, loop forever. The S-m-n theorem gives a total computable function producing the index of . ConsequentlyThe second set is a finite initial segment. Therefore if and only if belongs to the infinite-domain index set. This proves , and hence is not computably enumerable: preimages of computably enumerable sets under total computable functions are computably enumerable, whereas is not. The construction detects halting by finite evidence and never attempts to decide nonhalting.
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 a nonempty set 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 satisfies it. The Rice theorem therefore makes its index set undecidable.
The cofinite index set contains codes whose enumerable language has finite complement.
For a standard effective numbering of partial computable functions, there is a total computable function , injective in the pair , such that . Thus infinitely many different program indices can describe exactly the same computation. The uniformity matters: the extra index can be chosen algorithmically, rather than merely known to exist.
For a concrete Turing machine coding, insert an unreachable block carrying the original description and the integer , with a recognizable delimiter. Execution never enters that block, so the partial computable function remains unchanged; the recognizable description makes the padded indices distinct. The general version for acceptable numberings transfers this construction through a computable isomorphism of numberings. Padding distinguishes properties of program indices from properties of the partial computable functions they compute.
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 , there is a total computable 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 on input , 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 would be a missing diagonal row.
For every partial computable function , there are total primitive recursive functions such thatHere is zero exactly on codes of valid halting computation histories for the chosen program and input, and 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 , unbounded minimization definesas the least at which is zero, provided the preceding required computations are defined. If no such is found, is undefined. Closing the primitive recursive functions under this operation gives the partial recursive functions.
For a theory of arithmetic and a program index , the function is provably total in when proves its canonical totality sentenceIf is recursively axiomatized, the indices of its provably total functions form a computably enumerable set.
For a program code , input , and time bound , the truncated computation simulates program on for at most steps and reports either its output or that no halt occurred within the bound. This is a total computable function of .
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 for positive integers . It gives through , from through , and from through . 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 measures how many alternating blocks of unbounded quantifiers over natural numbers are needed to define a set of natural numbers. In its lightface version, when membership has the formwith a computable predicate and alternating blocks; a block can code a finite tuple. The class starts with a universal block, and . At level zero the matrix is computable; these definitions allow natural-number parameters, rather than arbitrary sets as oracle parameters.
The halting set is : membership says that some finite computation halts. Its complement is . The index set of total computable functions is , since totality says that the computation on input halts within steps. Alternation therefore records a concrete difference between witnessing one successful finite search and certifying that every input eventually succeeds.
A bounded quantifier has the form or , where the term does not contain . 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 and , 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.
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 , . Applying this to a provability assertion, which is itself Sigma-1, gives the third of the Hilbert-Bernays-Löb derivability conditions.
Articles were limited to the first 100 out of 182 total.
Articles by others on the same topic
Computability theory, also known as recursive function theory, is a branch of mathematical logic and computer science that deals with the question of what it means for a function to be computable. It explores the limits of what can be algorithmically solved and examines the characteristics of functions, problems, or decision-making processes that can be effectively computed by mechanical means, such as algorithms or theoretical models like Turing machines.

