Hubbry Logo
search
logo
Computable function avatar
Computable function
Computable function
current hub
C

Computable function

logo
Community Hub0 Subscribers
Read side by side
Computable function
View on Wikipedia
from Wikipedia

Computable functions are the basic objects of study in computability theory. Informally, a function is computable if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precise definition of the concept of algorithm, every formal definition of computability must refer to a specific model of computation.

Many such models of computation have been proposed, the major ones being Turing machines, register machines, lambda calculus and general recursive functions. Although these four are of a very different nature, they provide exactly the same class of computable functions, and, for every model of computation that has ever been proposed, the computable functions for such a model are computable for the above four models of computation.

The Church–Turing thesis is the unprovable assertion that every notion of computability that can be imagined can compute only functions that are computable in the above sense.

Before the precise definition of computable functions, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently.

The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of computing the value of a function is known as a function problem, by contrast to decision problems whose results are either "yes" or "no".

Definition

[edit]
See also: Total Turing machine

Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an effective procedure. With more rigor, a function is computable if and only if there is an effective procedure that, given any k-tuple of natural numbers, will produce the value .[1] In agreement with this definition, the remainder of this article presumes that computable functions take finitely many natural numbers as arguments and produce a value which is a single natural number.

As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent models of computation, including

Although these models use different representations for the functions, their inputs, and their outputs, translations exist between any two models, and so every model describes essentially the same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow.[2] These functions are sometimes referred to as "recursive", to contrast with the informal term "computable",[3] a distinction stemming from a 1934 discussion between Kleene and Gödel.[4]p.6

For example, one can formalize computable functions as μ-recursive functions, which are partial functions that take finite tuples of natural numbers and return a single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is closed under composition, primitive recursion, and the μ operator.

Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function can be calculated if and only if there exists a computer program with the following properties:

  1. If is defined, then the program will terminate on the input with the value stored in the computer memory.
  2. If is undefined, then the program never terminates on the input .

Characteristics of computable functions

[edit]
Main article: Algorithm

The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a compiler is able to read instructions in one computer language and emit instructions in another language.

Enderton [1977] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.

  • "There must be exact instructions (i.e. a program), finite in length, for the procedure." Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required.
  • "If the procedure is given a k-tuple x in the domain of f, then after a finite number of discrete steps the procedure must terminate and produce f(x)." Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned.
  • "If the procedure is given a k-tuple x which is not in the domain of f, then the procedure might go on forever, never halting. Or it might get stuck at some point (i.e., one of its instructions cannot be executed), but it must not pretend to produce a value for f at x." Thus if a value for f(x) is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is defined as correct if and only if it produces an outcome.

Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:

  1. The procedure must theoretically work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.
  2. The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.
  3. Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.

To summarise, based on this view a function is computable if:

  1. given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions;
  2. it returns such output (halts) in a finite number of steps; and
  3. if given an input which is not in its domain it either never halts or it gets stuck.

The field of computational complexity studies functions with prescribed bounds on the time and/or space allowed in a successful computation.

Computable sets and relations

[edit]

A set A of natural numbers is called computable (synonyms: recursive, decidable) if there is a computable, total function f such that for any natural number n, f(n) = 1 if n is in A and f(n) = 0 if n is not in A.

A set of natural numbers is called computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that for each number n, f(n) is defined if and only if n is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word enumerable is used because the following are equivalent for a nonempty subset B of the natural numbers:

  • B is the domain of a computable function.
  • B is the range of a total computable function. If B is infinite then the function can be assumed to be injective.

If a set B is the range of a function f then the function can be viewed as an enumeration of B, because the list f(0), f(1), ... will include every element of B.

Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of computable relation and computably enumerable relation can be defined from their analogues for sets.

Formal languages

[edit]
Main article: Formal language

In computability theory in computer science, it is common to consider formal languages. An alphabet is an arbitrary set. A word on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet {0, 1}. A language is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet.

A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called computable (synonyms: recursive, decidable) if there is a computable function f such that for each word w over the alphabet, f(w) = 1 if the word is in the language and f(w) = 0 if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.

A language is computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that f(w) is defined if and only if the word w is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers.

Examples

[edit]

The following functions are computable:

If f and g are computable, then so are: f + g, f * g, if f is unary, max(f,g), min(f,g), arg max{y ≤ f(x)} and many more combinations.

The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

  • The function f such that f(n) = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable. (The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.)
  • Each finite segment of an uncomputable sequence of natural numbers (such as the Busy Beaver function Σ) is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ(n) for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n).

Church–Turing thesis

[edit]
Main article: Church–Turing thesis

The Church–Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church–Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis:

  • Many equivalent models of computation are known, and they all give the same definition of computable function (or a weaker version, in some instances).
  • No stronger model of computation which is generally considered to be effectively calculable has been proposed.

The Church–Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.

Provability

[edit]

Given a function (or, similarly, a set), one may be interested not only if it is computable, but also whether this can be proven in a particular proof system (usually first order Peano arithmetic). A function that can be proven to be computable is called provably total.

The set of provably total functions is recursively enumerable: one can enumerate all the provably total functions by enumerating all their corresponding proofs, that prove their computability. This can be done by enumerating all the proofs of the proof system and ignoring irrelevant ones.

Relation to recursively defined functions

[edit]

In a function defined by a recursive definition, each value is defined by a fixed first-order formula of other, previously defined values of the same function or other functions, which might be simply constants. A subset of these is the primitive recursive functions. Another example is the Ackermann function, which is recursively defined but not primitive recursive.[5]

For definitions of this type to avoid circularity or infinite regress, it is necessary that recursive calls to the same function within a definition be to arguments that are smaller in some well-partial-order on the function's domain. For instance, for the Ackermann function , whenever the definition of refers to , then w.r.t. the lexicographic order on pairs of natural numbers. In this case, and in the case of the primitive recursive functions, well-ordering is obvious, but some "refers-to" relations are nontrivial to prove as being well-orderings. Any function defined recursively in a well-ordered way is computable: each value can be computed by expanding a tree of recursive calls to the function, and this expansion must terminate after a finite number of calls, because otherwise Kőnig's lemma would lead to an infinite descending sequence of calls, violating the assumption of well-ordering.

Total functions that are not provably total

[edit]

In a sound proof system, every provably total function is indeed total, but the converse is not true: in every first-order proof system that is strong enough and sound (including Peano arithmetic), one can prove (in another proof system) the existence of total functions that cannot be proven total in the proof system.

If the total computable functions are enumerated via the Turing machines that produces them, then the above statement can be shown, if the proof system is sound, by a similar diagonalization argument to that used above, using the enumeration of provably total functions given earlier. One uses a Turing machine that enumerates the relevant proofs, and for every input n calls fn(n) (where fn is n-th function by this enumeration) by invoking the Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound.

Uncomputable functions and unsolvable problems

[edit]
Main article: List of undecidable problems

Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only countably many computable functions. For example, functions may be encoded using a string of bits (the alphabet Σ = {0, 1}).

The real numbers are uncountable so most real numbers are not computable. See computable number. The set of finitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are Busy beaver, Kolmogorov complexity, or any function that outputs the digits of a noncomputable number, such as Chaitin's constant.

Similarly, most subsets of the natural numbers are not computable. The halting problem was the first such set to be constructed. The Entscheidungsproblem, proposed by David Hilbert, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations.

Extensions of computability

[edit]

Relative computability

[edit]

The notion of computability of a function can be relativized to an arbitrary set of natural numbers A. A function f is defined to be computable in A (equivalently A-computable or computable relative to A) when it satisfies the definition of a computable function with modifications allowing access to A as an oracle. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of A. We can also talk about f being computable in g by identifying g with its graph.

Higher recursion theory

[edit]

Hyperarithmetical theory studies those sets that can be computed from a computable ordinal number of iterates of the Turing jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of Hypercomputation. Even more general recursion theories have been studied, such as E-recursion theory in which any set can be used as an argument to an E-recursive function.

Hyper-computation

[edit]

Although the Church–Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies models of computation that go beyond normal Turing computation.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Computable function

View on Grokipedia
from Grokipedia
In computability theory, a computable function is a mathematical function from natural numbers to natural numbers (or more generally, from strings to strings) whose output can be produced by an algorithm that halts after finitely many steps on every valid input, typically formalized using models like Turing machines.[1] This notion captures the intuitive idea of effective calculability, where the algorithm follows a fixed, finite set of instructions without unbounded search or non-deterministic choices.[2] The foundational definitions emerged in the mid-1930s amid efforts to resolve David Hilbert's Entscheidungsproblem, which asked whether there exists an algorithm to determine the truth of mathematical statements in first-order logic. Alan Turing introduced computable numbers and functions via his abstract "computing machine" in 1936, showing that certain problems, like the halting problem, are inherently non-computable.[2] Independently, Alonzo Church proposed lambda-definability in 1933–1936, while Kurt Gödel and Stephen Kleene developed the theory of recursive functions starting from Gödel's 1933 lectures and formalized in Kleene's 1936 work on general recursive functions.[1] These approaches—lambda calculus, recursive functions, and Turing machines—were proven equivalent in their computational power, meaning any function computable in one model is computable in the others.[3] The Church-Turing thesis, formulated around 1936, asserts that these formal models precisely delineate the class of all effectively computable functions, bridging the gap between informal human computation and rigorous mathematics; though unprovable, it is widely accepted as a cornerstone of theoretical computer science.[1] Partial computable functions allow for non-halting behavior on some inputs, enabling the study of computably enumerable sets, while total computable functions are defined everywhere in their domain.[3] The theory underpins key results, such as Gödel's incompleteness theorems (1931), which demonstrate limits on formal systems, and has profound implications for algorithm design, software verification, and the boundaries of artificial intelligence.[1]

Foundations

Definition

A computable function is one that can be calculated by a mechanical procedure or algorithm, which, when provided with any input from its domain, produces the corresponding output after a finite number of steps and always terminates.[2] This intuitive notion captures the idea of effective computability, where the procedure follows precise, step-by-step rules without reliance on intuition or infinite processes.[2] Formally, in terms of Turing machines, a function f:N→Nf: \mathbb{N} \to \mathbb{N} is computable if there exists a Turing machine that, starting from input nn encoded as a string, halts in a finite number of steps and outputs the representation of f(n)f(n).[2] This definition extends Turing's original characterization of computable real numbers to functions on natural numbers, where the machine's tape serves as both input and output medium, and halting ensures termination.[2] Computable functions are distinguished as total or partial depending on their domain. A total computable function is defined and computable for every input in N\mathbb{N}, always halting with an output. In contrast, a partial computable function may be undefined for some inputs, meaning the corresponding algorithm does not halt or produce an output for those cases; for example, the partial function that attempts to compute the output of a given Turing machine on empty input if it halts, but remains undefined (loops indefinitely) otherwise, is partial computable but not total.[4] The concept of computable functions emerged in the 1930s through parallel formalizations. Alonzo Church introduced λ\lambda-definability in 1936 as a precise notion of effective calculability, where functions are expressed via abstractions in the λ\lambda-calculus.[5] Independently, Stephen Kleene developed the theory of recursive functions in 1936, defining them through composition, primitive recursion, and the μ\mu-operator for minimization.[4] The μ\mu-operator, denoted μy[P(n,y)]\mu y [P(n,y)], yields the smallest natural number yy such that the predicate P(n,y)P(n,y) holds, assuming such a yy exists; this allows construction of partial functions when no such yy is found.[4]

Models of Computation

One of the foundational models for computable functions is the Turing machine, introduced by Alan Turing in 1936. A Turing machine consists of an infinite tape divided into cells, each capable of holding a symbol from a finite tape alphabet Γ, a read/write head that moves left or right along the tape, and a finite set of states Q. The machine's behavior is governed by a partial transition function δ: Q × Γ → Q × Γ × {L, R}, where L and R denote left and right head movements, respectively; the machine starts in an initial state q₀ with the input encoded on the tape (surrounded by blanks from a special blank symbol), and computation proceeds by repeatedly applying δ until reaching a halting state, at which point the tape contents represent the output. This model computes partial functions from natural numbers to natural numbers by encoding inputs and outputs as unary or binary strings on the tape, with the computation halting if the function is defined for the input.[2] Another key model is that of recursive functions, formalized by Stephen Kleene in 1936 building on Alonzo Church's earlier work. Primitive recursive functions form a subclass generated from basic functions—the zero function Z(n) = 0, the successor function S(n) = n + 1, and projection functions P_i^k (n_1, ..., n_k) = n_i—using two schemas: composition, where a new function h is formed as h(n) = g(f_1(n), ..., f_m(n)) for previously defined g and f_j, and primitive recursion, defining h(0, \vec{y}) = f(\vec{y}) and h(S(n), \vec{y}) = g(n, h(n, \vec{y}), \vec{y}) for base f and recursion step g. The full class of recursive (or general recursive) functions extends this by adding the μ-operator, which yields the least n such that a primitive recursive predicate P(n, \vec{y}) holds, allowing computation of partial functions via minimization; this captures all computable functions through effective enumeration and diagonalization arguments.[6] Alonzo Church's lambda calculus, developed between 1932 and 1936, provides a different formalism using untyped lambda terms for function definition and application. Terms are built from variables x, abstractions λx.M (functions taking input x to output M), and applications (M N); computation proceeds via β-reduction, substituting arguments into functions as (λx.M) N → M[x := N], with normal forms representing results after reductions. Natural numbers and operations are encoded via Church numerals, such as 0 = λf.λx.x, 1 = λf.λx.f x, successor S = λn.λf.λx.f (n f x), enabling arithmetic and recursion through fixed-point combinators like Y = λf.(λx.f (x x)) (λx.f (x x)) for general computability.[7] Additional models include register machines, as described by Marvin Minsky in 1967, which use a finite number of registers holding non-negative integers and a program of instructions including increment (R_i += 1), decrement (if R_i > 0 then R_i -= 1 else jump), zero-test (if R_i = 0 then jump), unconditional jump, and halt; Minsky showed that two registers suffice for universal computation equivalent to Turing machines. Post systems, introduced by Emil Post in 1936, operate on strings over an alphabet via a finite set of production rules that replace a designated substring P with another Q, starting from an initial string and generating outputs through repeated applications until no further rules apply, capturing computability through tag or canonical forms.[8] The equivalence of these models—Turing machines, recursive functions, lambda calculus, register machines, and Post systems—establishes that they all characterize the same class of partial computable functions, as demonstrated through mutual simulations in the 1930s and 1960s; this robustness underpins the Church-Turing thesis, conjectured by Church in his 1936 paper on lambda calculus and independently by Turing in his 1936 analysis of computable numbers, positing that these models capture all effectively computable functions. While classical models assume sequential computation, modern variants like linear bounded automata, introduced in the 1960s and still studied today, restrict tape length to the input size for context-specific computability relevant to context-sensitive languages.[7][2]

Properties

Characteristics

Computable functions, also known as partial recursive functions, form a robust class characterized by strong closure properties under basic operations, which distinguish them from broader classes of mathematical functions. Specifically, the class is closed under composition: if $ g_1, \dots, g_m $ and $ h $ are partial computable functions, then so is $ f(\vec{x}) = h(g_1(\vec{x}), \dots, g_m(\vec{x})) $. It is also closed under primitive recursion: given computable functions $ \psi $ and $ \gamma $, the function defined by $ \phi(\vec{x}, 0) = \psi(\vec{x}) $ and $ \phi(\vec{x}, y+1) = \gamma(\vec{x}, y, \phi(\vec{x}, y)) $ is computable. Finally, closure under minimization holds: if $ \psi $ is computable, then $ \phi(\vec{x}) = \mu y [(\forall z \leq y) \psi(\vec{x}, z) \downarrow \land \psi(\vec{x}, y) = 0] $ (the least $ y $ satisfying the condition, if it exists) is computable. These closures can be established via simulation in equivalent models of computation, such as Turing machines. For composition, a Turing machine computing $ h $ can be modified to first simulate machines for each $ g_i $ on input $ \vec{x} $, then feed the outputs into the simulation of $ h $; primitive recursion follows by encoding iterative steps in the machine's tape management; and minimization by dovetailing searches over increasing $ y $ values until the condition halts. Such simulations preserve computability since Turing machines can effectively enumerate and combine descriptions of other machines. The domain of a partial computable function—the set of inputs on which it halts and produces an output—is always recursively enumerable, as it corresponds to the range of a total computable function enumerating valid inputs via the normal form theorem. The range (set of outputs) is also recursively enumerable, generated by applying the function to its enumerated domain. If the function is total (defined everywhere), its range remains recursively enumerable, though not necessarily recursive. Within this class, computable functions exhibit non-monotonic complexity behavior, as captured by Blum's speed-up theorem: for any total computable function $ r(x, y) $ serving as a time bound, there exists a total computable $ f(x) $ such that for infinitely many $ x $, $ f(x) $ is computed in time much faster than any $ r $-bounded program for $ f $. This implies no optimal algorithms exist universally across the class, highlighting inherent inefficiencies. Despite these closures, non-trivial semantic properties of computable functions—such as whether a function computes the zero function or has an infinite domain—are undecidable, per Rice's theorem: any such property is either trivial (holding for all or no computable functions) or its decision problem is undecidable. The integration of computability with resource-bounded complexity theory in the 1980s revealed that while the unrestricted class enjoys full closure, bounded analogs like polynomial-time computable functions exhibit uniform closure under operations such as polynomial-time reductions and composition, but lack closure under unrestricted minimization without additional nondeterminism.[9]

Computable Sets and Relations

A set $ S \subseteq \mathbb{N} $ is recursive if its characteristic function $ \chi_S: \mathbb{N} \to {0,1} $, defined by $ \chi_S(n) = 1 $ if $ n \in S $ and $ \chi_S(n) = 0 $ otherwise, is total computable.[10] This means membership in $ S $ is decidable: a Turing machine can always halt and correctly output whether a given natural number belongs to $ S $ or not. Recursive sets form the core of decidable predicates in computability theory, extending the notion of total computable functions to decision problems over the naturals.[10] A set $ S \subseteq \mathbb{N} $ is recursively enumerable (r.e.), also known as computably enumerable, if there exists an index $ e $ such that the domain of the partial computable function $ \phi_e $ equals $ S $, i.e., $ \operatorname{dom}(\phi_e) = S $.[10] Equivalently, $ S $ is semi-decidable: there is a Turing machine that halts on input $ n $ if and only if $ n \in S $, but may loop indefinitely otherwise. R.e. sets can also be enumerated by a computable process, though the enumeration may include repetitions or require dovetailing over multiple machines.[10] Every recursive set is r.e., since its characteristic function allows semi-decision by halting on yes-instances and rejecting no-instances, but the converse fails: there exist r.e. sets that are not recursive.[10] For relations, an $ n $-ary relation $ R \subseteq \mathbb{N}^n $ is computable (recursive) if its characteristic function $ \chi_R: \mathbb{N}^n \to {0,1} $ is total computable, allowing uniform decision of membership for any tuple of natural numbers.[10] Similarly, $ R $ is r.e. if it is semi-decidable: a Turing machine exists that halts precisely when a given tuple is in $ R $. This generalizes the unary case to higher-arity predicates, capturing the computability of joint properties over multiple inputs.[10] The hierarchy of r.e. and recursive sets highlights fundamental limits: all recursive sets are r.e., but the inclusion is proper, as demonstrated by the halting set $ K = { e \mid \phi_e(e) \downarrow } $, which consists of indices of partial computable functions that halt on their own index.[2] The set $ K $ is r.e., since a universal Turing machine can simulate $ \phi_e(e) $ and halt if it does, but $ K $ is not recursive, as its complement encodes the undecidable halting problem.[2] This separation underlies the unsolvability of many decision problems in logic and computation.[2] Productive sets provide a stronger notion of non-recursiveness within the r.e. hierarchy: a set $ A \subseteq \mathbb{N} $ is productive if there exists a total computable function $ p: \mathbb{N} \to \mathbb{N} $ such that for every index $ e $, if $ W_e \subseteq A $ (where $ W_e = \operatorname{dom}(\phi_e) $), then $ p(e) \in A \setminus W_e $.[10] Thus, productive sets are r.e. sets equipped with a computable "witness producer" that outperforms any recursive approximation by finding elements outside any contained r.e. subset. No productive set can be recursive, and they capture maximal degrees of unsolvability among r.e. sets.[10] These concepts extend beyond discrete domains to continuous settings, such as computable analysis over the real numbers, where a real is computable if its decimal expansion (or rational approximations) is generated by a Turing machine.[2] Recent work in the 2020s has advanced verified exact real computation using proof assistants to formalize computable reals and operations, enabling rigorous analysis of continuous functions and sets.[11]

Examples and Applications

Concrete Examples

Computable functions encompass a wide range of practical operations in arithmetic, where basic operations like addition and multiplication serve as foundational examples. These functions are primitive recursive, a subclass of the total computable functions built from zero, successor, and projection functions via composition and primitive recursion.[12] The addition function add(x,y)=x+yadd(x, y) = x + y is defined primitively recursive as add(x,0)=xadd(x, 0) = x and add(x,y+1)=succ(add(x,y))add(x, y+1) = succ(add(x, y)), where succ(z)=z+1succ(z) = z + 1.[13] Similarly, multiplication mult(x,y)=x×ymult(x, y) = x \times y is primitive recursive, defined as mult(x,0)=0mult(x, 0) = 0 and mult(x,y+1)=add(mult(x,y),x)mult(x, y+1) = add(mult(x, y), x).[14] The factorial function fact(n)=n!fact(n) = n!, which multiplies all integers from 1 to nn, is also primitive recursive via bounded recursion on the multiplication operation.[15] A prominent example beyond primitive recursion is the Ackermann function, a total recursive function that grows faster than any primitive recursive function, illustrating the boundaries within the computable class. It is defined recursively for natural numbers mm and nn as follows:
A(0,n)=n+1,A(m+1,0)=A(m,1),A(m+1,n+1)=A(m,A(m+1,n)). \begin{align*} A(0, n) &= n + 1, \\ A(m + 1, 0) &= A(m, 1), \\ A(m + 1, n + 1) &= A(m, A(m + 1, n)). \end{align*}
[16] This function is total computable but not primitive recursive, as proven by showing it outpaces the growth rates in the primitive recursive hierarchy through diagonalization over levels of nested recursion.[17] In logic, the evaluation of propositional formulas provides another concrete computable operation. For a formula with kk variables, truth-table evaluation involves assigning truth values to each variable across all 2k2^k possible combinations and recursively computing the formula's value using the semantics of connectives like conjunction and disjunction. This process is computable via syntactic parsing and finite enumeration, as the number of assignments is finite and each evaluation follows a fixed recursive procedure.[18] Programming analogs further demonstrate computability through algorithmic implementations. The factorial function, as a total computable operation, can be realized via an iterative loop that accumulates the product, ensuring termination for all natural number inputs. For instance, in Python pseudocode: 
def factorial(n):
    if n == 0:
        return 1
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result
This halts for all n≥0n \geq 0.[13] In contrast, partial computable functions arise in programming when loops may not terminate, such as an infinite search without a halting condition, yielding undefined output for some inputs while remaining within the computable class. The greatest common divisor (GCD) function, computed via the Euclidean algorithm, is total computable and primitive recursive, repeatedly applying subtraction or modulo until the remainder is zero. Python pseudocode for GCD illustrates this: 
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
The algorithm terminates due to the decreasing remainder, making GCD defined for all nonnegative integers.[19] Diagonalization constructs computable functions that highlight growth and enumeration within the class. Consider the partial recursive function f(n)=ϕn(n)+1f(n) = \phi_n(n) + 1 if ϕn(n)\phi_n(n) is defined (halts), where ϕn\phi_n enumerates the partial recursive functions; otherwise, f(n)f(n) is undefined. This ff is computable as a partial function, as it relies on the universal Turing machine to simulate ϕn(n)\phi_n(n) and add 1 upon halting, demonstrating self-referential growth that differs from each ϕn\phi_n on its diagonal argument when defined.[13] A historical application underscores computability in number theory: while Yuri Matiyasevich proved in 1970 that determining solvability of general Diophantine equations is undecidable, simpler cases remain computable. Specifically, linear Diophantine equations like ax+by=cax + by = c have solutions verifiable algorithmically using the extended Euclidean algorithm to check if gcd⁡(a,b)\gcd(a, b) divides cc and compute particular solutions if so.

Formal Languages and Automata

In formal language theory, the concept of computable functions manifests through the decidability of language membership. A language $ L \subseteq \Sigma^* $ over a finite alphabet $ \Sigma $ is decidable if there exists a Turing machine that, on every input string $ w \in \Sigma^* $, halts and accepts if $ w \in L $ and rejects otherwise.[20] This ensures that membership testing is a computable function, aligning with the broader framework of recursive languages. Decidability captures the computational boundary where automata can fully resolve acceptance for all inputs without non-termination. The Chomsky hierarchy classifies formal languages by generative power, each corresponding to specific automata models with implications for computability. Type-3 regular languages are recognized by finite automata and are decidable, as membership can be computed in linear time via deterministic finite automata. Type-2 context-free languages are accepted by pushdown automata, with membership decidable using algorithms like Cocke-Younger-Kasami, though equivalence and inclusion are undecidable. Type-1 context-sensitive languages, recognized by linear bounded automata, remain decidable but with higher complexity. At the apex, type-0 unrestricted grammars generate recursively enumerable languages, recognized by Turing machines, but only the recursive subset is decidable.[21] This hierarchy delineates computable boundaries: lower levels offer efficient decidability, while higher levels approach the limits of Turing computability. Pumping lemmas provide tools to analyze language classes within the hierarchy, particularly for proving non-context-freeness and supporting computability arguments. For context-free languages, the pumping lemma states that if $ L $ is context-free, there exists a pumping length $ p $ such that any string $ z \in L $ with $ |z| \geq p $ can be divided as $ z = uvxyz $, where $ |vxy| \leq p $, $ |vy| > 0 $, and $ uv^ixy^iz \in L $ for all $ i \geq 0 $.
z=uvxyz,∣vxy∣≤p,∣vy∣>0,uvixyiz∈L ∀i≥0 z = uvxyz, \quad |vxy| \leq p, \quad |vy| > 0, \quad uv^ixy^iz \in L \ \forall i \geq 0
This property enables computational verification of membership by generating pumped strings to test boundaries, reinforcing the decidability of context-free membership despite the undecidability of broader structural properties. Rice's theorem extends undecidability results to formal languages, asserting that any non-trivial semantic property of recursively enumerable languages is undecidable. A property is non-trivial if it holds for some but not all such languages; for instance, determining whether a Turing machine recognizes a language with an even number of strings is undecidable. This applies directly to language classes, showing that questions like "Does this grammar generate a regular language?" are undecidable for non-trivial cases, highlighting the limits of computable analysis in the Chomsky hierarchy.[22] Historically, Emil Post's work in the 1940s bridged recursively enumerable sets and formal languages through the correspondence problem, an undecidable decision problem that encodes computations as string matchings. Introduced in 1946, the Post correspondence problem asks whether, given lists of strings over $ \Sigma $, there exists a sequence of indices forming a concatenation where the top and bottom strings match; its undecidability demonstrates how language recognition can simulate arbitrary Turing machine behavior, linking re sets (Turing-recognizable but not necessarily decidable) to undecidable language properties.

Theoretical Foundations

Church–Turing Thesis

The Church–Turing thesis posits that every effectively calculable function on the natural numbers is computable by a Turing machine.[23] This conjecture, formulated independently by Alonzo Church and Alan Turing in 1936, equates the informal notion of effective calculability—requiring only finite mechanical procedures without appeal to intuition or higher faculties—with the formal power of Turing machines or equivalent models.[2] Church grounded his version in the lambda calculus, defining effective methods as those expressible through lambda-definable functions, while Turing modeled computation via an idealized human calculator using simple operations on symbols.[23] The thesis emerged in the context of David Hilbert's 1928 Entscheidungsproblem, which challenged mathematicians to devise a general algorithm for determining the provability of any statement in first-order logic from given axioms. Church and Turing each provided negative solutions, proving the problem unsolvable within their respective frameworks, and argued that their models captured all possible effective procedures.[7][2] Turing further developed his ideas in 1939 through ordinal logics, aiming to formalize constructive ordinals to address limitations in capturing human mathematical intuition, though this work reinforced rather than superseded his 1936 analysis of computability. Empirical support for the thesis derives from the equivalence of diverse models of computation developed post-1936. Stephen Kleene demonstrated that general recursive functions coincide with Turing-computable functions, while later proofs extended this to lambda-definability, register machines, and Post systems.[23] Hartley Rogers Jr. synthesized these results in his 1967 monograph, establishing that the class of computable functions is invariant across all standard models, providing strong inductive evidence for the thesis's claim of universality.[23] Variants of the thesis include the physical Church–Turing thesis, which asserts that no physically realizable device can perform computations beyond those of a Turing machine, limited by the laws of physics such as finite speed and locality.[23] David Deutsch proposed a strong physical form in 1985, emphasizing that every finitely describable physical process can be efficiently simulated by a universal quantum computer, yet still within Turing-equivalent bounds. The weak form focuses solely on computational power, while the strong incorporates efficiency constraints, as in the extended Church–Turing thesis for feasible computation. Criticisms of the thesis often center on whether human cognition or exotic physical processes exceed Turing limits, though no counterexamples have materialized. Roger Penrose, in his 1989 analysis, contended that non-computable elements of quantum gravity enable human mathematical understanding to surpass algorithmic computation, but this remains speculative without empirical validation.[23] Debates in the 2010s regarding probabilistic and quantum models raised questions about extensions like the probabilistic Church–Turing thesis, yet these systems prove equivalent in expressive power to deterministic Turing machines, as affirmed in recent theoretical surveys. Michael Sipser, in his 2020 lectures, underscored the thesis's robustness through model-independence, noting its enduring acceptance despite such discussions.[24]

Provability in Formal Systems

Gödel's first incompleteness theorem, published in 1931, demonstrates that any consistent formal system capable of expressing basic arithmetic, such as Peano arithmetic (PA), is incomplete, meaning there exist true statements in the language of arithmetic that cannot be proved within the system. This result has profound implications for computable functions: while PA can formalize the notion of computability through recursive functions, it cannot prove the totality (i.e., definedness for all inputs) of all total computable functions. Specifically, the theorem relies on the representability of recursive sets within PA, where computably enumerable sets are weakly representable and recursive sets are strongly representable, but the undecidability of certain Σ10\Sigma_1^0 statements, like the Gödel sentence, reveals gaps in provability.[25] In contrast, primitive recursive arithmetic (PRA), a weaker subsystem of PA featuring induction only for Σ1\Sigma_1 formulas, proves the totality of all primitive recursive functions, which form a proper subclass of the total recursive functions. These functions, built from basic operations via composition, primitive recursion, and unbounded minimization restricted to total cases, are Σ1\Sigma_1-definable in PRA, ensuring their provable totality through induction on their recursive definitions. Recursively defined functions that go beyond primitive recursion, such as those involving general recursion with the μ\mu-operator, exceed PRA's provable totals but remain within the scope of computability.[26] A striking example of a total computable function whose totality is unprovable in PA is the Busy Beaver function BB(n)BB(n), which gives the maximum number of steps that an nn-state Turing machine takes to halt starting from a blank tape. Although BB(n)BB(n) is well-defined and computable in principle as a total function, proving BB(n)<kBB(n) < k for specific bounds kk would solve the halting problem for nn-state machines, which is undecidable; thus, for sufficiently large nn, statements about BB(n)BB(n) are independent of PA due to Gödel's second incompleteness theorem and the arithmetical soundness of PA. This unprovability arises because BB(n)BB(n) grows faster than any provably total recursive function in PA, linking directly to the undecidability hierarchies in recursion theory.[27] The provability of totality for computable functions often involves Π10\Pi_1^0 sentences asserting "for all nn, f(n)f(n) halts," which capture the total recursive functions but exceed PA's deductive power for certain cases. Goodstein's theorem (1944), stating that every Goodstein sequence—defined by iterated base-bb representations in hereditary notation, decrementing to base b+1b+1—eventually reaches zero, exemplifies this: the theorem is true but unprovable in PA, as shown by Kirby and Paris in 1982, because its proof requires transfinite induction up to ε0\varepsilon_0, beyond PA's ordinal strength. Their model-theoretic argument establishes independence by constructing non-standard models of PA where Goodstein sequences fail to terminate. Georg Kreisel's 1952 work on the interpretation of non-finitist proofs introduced the "unwinding" program, aiming to extract effective computational content from classical proofs in number theory and analysis. By defining computable interpretations—functions f(n,a)f(n, a) that realize existential quantifiers in proofs of Π20\Pi_2^0 sentences—Kreisel showed how non-constructive proofs in systems extending PRA could yield primitive recursive bounds, bridging provability to explicit computability without full consistency proofs. This approach influenced later proof mining techniques, emphasizing the extraction of recursive functions from formal derivations.[28] Recent developments in reverse mathematics, particularly Stephen Simpson's computability-focused subsystems of second-order arithmetic, highlight ongoing refinements in understanding provability limits for recursive functions. Simpson's 2009 framework identifies subsystems like RCA0\mathsf{RCA}_0—which proves only computable sets exist—as base theories for reverse mathematics, where theorems equivalent to Π12\Pi_1^2-comprehension capture totality proofs for higher recursive functions, extending Kreisel's unwinding to computable structure theory. These developments underscore that while PA misses certain totalities, targeted subsystems align provability more closely with effective computability.[29]

Limitations and Extensions

Uncomputable Functions

One of the most famous examples of an uncomputable function is the halting function, defined as $ h(e, n) = 1 $ if the Turing machine encoded by $ e $ halts on input $ n $, and undefined otherwise. This function is undecidable, meaning no Turing machine can compute it for all inputs, as proven by Alan Turing using a diagonalization argument analogous to Cantor's method for showing the uncountability of the reals. Specifically, assuming a halting oracle exists leads to a contradiction by constructing a machine that behaves oppositely on its own description.[2] Another prominent uncomputable function is the busy beaver function $ \Sigma(n) $, which gives the maximum number of steps taken by any halting Turing machine with $ n $ states and two symbols before halting, starting from a blank tape. Introduced by Tibor Radó, this function grows faster than any computable function, implying its uncomputability, since if it were computable, one could solve the halting problem by simulating all $ n $-state machines up to $ \Sigma(n) $ steps.[30] Uncomputability extends to many problems via reductions, which map instances of one problem to another while preserving decidability. A many-one reduction embeds one decision problem into another such that solutions correspond directly, while a Turing reduction allows oracle queries. For instance, the Post correspondence problem—given two lists of strings over an alphabet, decide if there is a sequence of indices forming a match where concatenations are equal—is undecidable, as shown by reducing the halting problem to it.[31] The Kolmogorov complexity function $ K(x) $, defined as the length of the shortest Turing machine program that outputs string $ x $, is also uncomputable. This measure quantifies the intrinsic randomness or information content of $ x $, and its undecidability follows from the halting problem, as computing $ K(x) $ would require determining if programs halt and produce $ x $. Andrey Kolmogorov formalized this approach to algorithmic information theory, linking it to notions of randomness where strings with high $ K(x) $ relative to their length appear incompressible.[32] Historically, in the late 1960s, Daniel Richardson proved that deciding whether expressions built from elementary functions (such as exponentials, logarithms, sine, and absolute value) with integer coefficients and constants like $ \pi $ and $ \ln 2 $ integrate to zero over $ [0, 1] $ is undecidable. This result, known as Richardson's theorem, demonstrates uncomputability in classical analysis by reducing the halting problem to integration queries.[33] In recent applications to artificial intelligence, verifying properties of neural agents interacting with non-deterministic environments, such as reachability in systems driven by deep feed-forward networks, has been shown to be undecidable, extending classical limits to modern computational models.[34]

Relative and Higher Computability

Relative computability extends the notion of Turing computability by allowing machines access to oracles, which provide instantaneous answers to membership queries for a fixed set A⊆NA \subseteq \mathbb{N}. An oracle Turing machine is a standard Turing machine augmented with an additional read-only oracle tape containing the characteristic function of AA, enabling the machine to query whether a given natural number belongs to AA in a single step.[35] This relativization, introduced by Turing in his analysis of degrees of difficulty for decision problems, permits the study of computational power relative to arbitrary oracles rather than absolute computability.[36] A function f:Nk→Nf: \mathbb{N}^k \to \mathbb{N} is AA-computable if there exists an oracle Turing machine with oracle AA that, on input x∈Nk\mathbf{x} \in \mathbb{N}^k, halts and outputs f(x)f(\mathbf{x}). Similarly, a set B⊆NB \subseteq \mathbb{N} is AA-computable if its characteristic function is AA-computable. Turing reducibility, denoted B≤TAB \leq_T A, captures this relation: BB is Turing reducible to AA if BB is AA-computable. This forms the basis for the arithmetic hierarchy relativized to AA, where sets are classified by the complexity of their defining formulas in second-order arithmetic. The levels Σn0(A)\Sigma^0_n(A) consist of sets definable by formulas with nn alternating unbounded quantifiers starting with existential, prefixed by arithmetic quantifiers over AA, while Πn0(A)\Pi^0_n(A) starts with universal; the hierarchy is strict for each n≥1n \geq 1.[3][37] Turing degrees partition sets under Turing equivalence, where B≡TAB \equiv_T A if A≤TBA \leq_T B and B≤TAB \leq_T A; each equivalence class, called a Turing degree, measures a "degree of unsolvability." The degree 0\mathbf{0} contains all computable sets, while 0′\mathbf{0}', the degree of the halting set (the set of indices of Turing machines that halt on the empty input), is the first non-computable degree and marks the boundary of recursively enumerable sets. The structure of Turing degrees is rich and complex, with 0′\mathbf{0}' initiating the jump operation that generates higher degrees. Post's problem, posed in 1944 by Emil Post, asked whether there exist recursively enumerable sets with Turing degrees strictly between 0 and 0'. This was resolved affirmatively in 1957–1958 by Richard M. Friedberg and A. A. Muchnik independently, using the priority method to construct such sets of every degree below 0', thereby showing that the r.e. degrees are dense in that interval.[38][39] Higher recursion theory generalizes these ideas to transfinite iterations, focusing on hyperarithmetic sets, which form the sets computable relative to ordinal notations below the Church-Kleene ordinal ω1CK\omega_1^{CK}, the least non-recursive ordinal. These sets lie below the degree 0(ω)\mathbf{0}^{(\omega)}, the ω\omega-th jump of 0\mathbf{0}, and coincide with the Δ11\Delta^1_1 sets in the projective hierarchy. Kleene's OO is the canonical set of well-founded notations for recursive ordinals, serving as a mastercode for hyperarithmetic computations; a set is hyperarithmetic if and only if it is computable from finitely many sections of OO. This framework captures the effective content of second-order arithmetic up to 0(ω)\mathbf{0}^{(\omega)}.[40] Recursion on higher types extends computability to functionals operating on functions, treating type-2 objects (functions from N\mathbb{N} to N\mathbb{N}) as inputs. Kleene's schemata S1–S9, introduced in 1959, define recursive functionals of finite type by generalizing μ\mu-recursive functions to higher types: S1–S5 handle composition, primitive recursion, and minimization over previous types, while S6–S9 incorporate universal quantification and recursion on type-1 variables. These schemata generate all continuous functionals on the type structure over N\mathbb{N}. In the 1960s, Feferman developed classifications of recursive functions via hierarchies for higher types, extending arithmetic and hyperarithmetic notions to type-2 and beyond, including transfinite progressions of theories and ordinal notations for higher computability.[41][42][43] In descriptive set theory, Borel computability concerns the effective Borel hierarchy on Polish spaces, where Borel sets are generated from open sets by countable unions, intersections, and complements up to countable ordinals. A Borel set is computable relative to an oracle if its Borel code—a tree encoding the construction—is oracle-computable; the effective Borel hierarchy Σα0\boldsymbol{\Sigma}^0_\alpha for admissible ordinals α<ω1CK\alpha < \omega_1^{CK} parallels the lightface arithmetic hierarchy, with hyperarithmetic sets corresponding to Borel sets of rank below ω1CK\omega_1^{CK}. This intersection of computability and descriptive set theory reveals the hyperarithmetic sets as exactly the Borel sets with hyperarithmetic codes.[44]

Hypercomputation

Hypercomputation refers to theoretical models of computation that surpass the capabilities of Turing machines, enabling the solution of problems deemed uncomputable within standard recursive function theory. These models often invoke supertasks—sequences of infinitely many operations completed in finite or transfinite time—and rely on idealized physical or mathematical assumptions that extend beyond classical computability. While intriguing for exploring the boundaries of the Church–Turing thesis, hypercomputational devices remain purely hypothetical, as their realization would necessitate violations of established physical laws such as relativity or quantum mechanics.[45] One prominent model of oracle hypercomputation is the infinite-time Turing machine (ITTM), which extends the operation of a standard Turing machine into transfinite ordinal time. Introduced by Hamkins and Lewis, an ITTM performs computations over limit ordinals, where the machine's state at a limit time α\alpha is determined by the limit of its states at previous times less than α\alpha. These machines can halt after ω\omega steps or longer transfinite durations, allowing them to compute functions beyond Turing computability, such as deciding the halting problem for all Turing machines. For instance, an ITTM can write its own real number representation on the tape in ω\omega steps and use it to simulate oracle access for uncomputable sets. However, ITTMs require infinite tape and time, rendering them non-physical.[46] Analog models of hypercomputation draw from general relativity to enable supertasks via spacetime geometries. In Malament-Hogarth spacetimes, an observer can experience an infinite proper time along a timelike curve while a distant observer measures only finite coordinate time, permitting the completion of infinitely many computational steps in finite external time. Earman and Norton analyzed such spacetimes, showing how a Turing machine could perform a supertask to solve the halting problem by iterating through all possible programs in accelerating proper time. These models exploit causal structures like those near black holes, where infinite computation occurs before an event horizon. Tipler's earlier proposal of an infinitely long, rotating cylinder generates closed timelike curves, potentially allowing repeated traversals for unbounded computation; recent discussions in the 2020s link this to quantum gravity effects, though without resolving stability issues.[47][48] Quantum hypercomputation proposes leveraging quantum effects for super-Turing power, such as Zeno machines that approximate supertasks through repeated measurements approaching infinite frequency, or oracle-like quantum devices accessing non-computable information. Zeno machines, building on quantum Zeno effect, could in principle perform infinite operations in finite time by halting evolution via frequent observations. However, these are constrained by fundamental quantum principles; Deutsch demonstrated that quantum computers cannot exceed Turing limits due to the no-cloning theorem, which prevents copying unknown quantum states needed for oracle simulations. Thus, while quantum models like adiabatic computing offer efficiency gains, they do not enable true hypercomputation.[49] Malicious or accelerating Turing machines represent another approach, where the device's clock speed increases without bound, allowing a standard Turing machine architecture to complete supertasks in finite real time. Copeland and Sylvan described these as machines whose computation rate accelerates such that the nn-th step takes 1/2n1/2^n time units, summing to finite duration despite infinite steps. This enables solving uncomputable problems, like determining if a Turing machine halts, by simulating it through all steps. Yet, such unbounded acceleration implies infinite energy or non-physical hardware.[50] Criticisms of hypercomputation emphasize its reliance on non-physical assumptions, challenging the Church–Turing thesis only in idealized settings. Models like ITTMs or accelerating machines presuppose infinite resources or supertemporal processes incompatible with finite physical systems, while relativistic supertasks risk causality violations or instabilities under quantum gravity. As of 2025, no experimental evidence supports hypercomputational devices, and quantum limits reinforce Turing-equivalence for realizable computers. These proposals thus serve more as thought experiments probing computability's philosophical limits than viable extensions.[45]

References

  1. Computability and Complexity - Stanford Encyclopedia of Philosophy
  2. [PDF] ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ...
  3. [PDF] Computability theory - UC Berkeley math
  4. General recursive functions of natural numbers
  5. [PDF] A Note on the Entscheidungsproblem Alonzo Church The Journal of ...
  6. General recursive functions of natural numbers
  7. [PDF] An Unsolvable Problem of Elementary Number Theory Alonzo ...
  8. [PDF] Finite Combinatory Processes-Formulation 1 Emil L. Post The ...
  9. Scalable Parallel Processing: Architectural Models, Real-Time ...
  10. Uniform closure properties of P-computable functions
  11. Recursively enumerable sets of positive integers and their decision ...
  12. Computable Analysis for Verified Exact Real Computation - DROPS
  13. primitive recursive function - PlanetMath.org
  14. Recursive Functions - Stanford Encyclopedia of Philosophy
  15. [PDF] Primitive recursive functions
  16. [PDF] 9 Primitive recursive functions - - Logic Matters
  17. Ackermann Function -- from Wolfram MathWorld
  18. Ackermann function is not primitive recursive - PlanetMath.org
  19. Propositional Logic - Stanford Encyclopedia of Philosophy
  20. [PDF] Primitive Recursive Functions as Description of For-Loops
  21. [PDF] Decidable and Semi-Decidable Languages - Computer Science
  22. [PDF] ECS 120 Lesson 16 – Turing Machines, Pt. 2
  23. [PDF] 1 Rice's Theorem
  24. A review of Quantum Cellular Automata
  25. The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)
  26. Lecture 6: TM Variants, Church-Turing Thesis | Theory of Computation
  27. Gödel's Incompleteness Theorems
  28. [PDF] The Witness Function Method and Provably Recursive ... - UCSD Math
  29. [PDF] The Busy Beaver Frontier - Scott Aaronson
  30. [PDF] ON THE INTERPRETATION OF NON-FINITIST PROOFS-PART I
  31. Reverse Mathematics - Stanford Encyclopedia of Philosophy
  32. [PDF] On Non-Computable Functions - By T. RADO
  33. A VARIANT OF A RECURSIVELY UNSOLVABLE PROBLEM
  34. [PDF] AN Kolmogorov
  35. SOME UNDECIDABLE PROBLEMS INVOLVING ELEMENTARY ...
  36. Formal verification of neural agents in non-deterministic environments
  37. [PDF] Turing Machines, Oracle Turing Machines, and the Turing Hierarchy
  38. Turing machine - Stanford Encyclopedia of Philosophy
  39. [PDF] Computable Structure Theory: Within the arithmetic Draft Antonio ...
  40. [PDF] Degrees of unsolvability: a tutorial - Stephen G. Simpson
  41. [PDF] Post's Problem and the Priority Method in CIC
  42. [PDF] Kleene [1943], Post [1944] and Mostowski [1947] . . . . . . . . . . . 2 1A ...
  43. [PDF] Computability and Recursion
  44. Recursive Functionals and Quantifiers of Finite Types I - jstor
  45. Classifications of Recursive Functions by Means of Hierarchies - jstor
  46. [PDF] Effective Descriptive Set Theory - UC Berkeley math
  47. [PDF] Hypercomputation: computing more than the Turing machine - arXiv
  48. Infinite time Turing machines | The Journal of Symbolic Logic
  49. Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth ...
  50. Rotating cylinders and the possibility of global causality violation
  51. Zeno machines and hypercomputation - ScienceDirect.com
  52. Accelerating Turing Machines | Minds and Machines
User Avatar
No comments yet.