Concept
Computable function
Overview
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".
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
To complete this rapid general enumeration of the different essential parts of the calculus of direct functions, I must, lastly, mention expressly one of the most fruitful and important theories of algebra proper, that relating to the transformation of functions into series by the aid of what is called the _Method of indeterminate Coefficients_. This method, so eminently analytical, and which must be regarded as one…
Auguste Comte, The philosophy of mathematics
States what Computable function is.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Computable function is.
Thus the set s does indicate an ideal simplicity of natural relations, though this simplicity is not the character of any actual event in s. We can make an approximation to such a simplicity which, as estimated numerically, is as close as we like by considering an event which is far enough down the series towards the small end. It will be noted that it is the infinite series, as it stretches away in unending…
Alfred North Whitehead, The Concept of Nature The Tarner Lectures Delivered in Trinity College, November 1919
States what Computable function is.
Philosophers who discussed Computable function
Related ideas
- Formal language
- First-order logic
- Effective method
- Tuple
- If and only if
- Computability theory
- Kurt Gödel
- Lambda calculus
- Function (mathematics)
- Mathematician
- Exponential growth
- Natural number
- Peano axioms
- Set (mathematics)
- Soundness
- Turing machine
- Computably enumerable set
- Second-order arithmetic
- Domain of a function
- Compiler
- Church–Turing thesis
- Computational complexity theory
- Algorithm
- David Hilbert
Opposing perspectives
Place in the tradition
Part of Outline of logic.