Definition
The class of computable functions can be defined in many equivalent models of computation, including
- Turing machines
- μ-recursive functions
- Lambda calculus
- Post machines (Post–Turing machines and tag machines).
- Register machines
Although those models use different representations for the functions, their inputs and their outputs, translations exist between any two models. In the remainder of this article, functions from natural numbers to natural numbers are used (as is the case for, e.g., the μ-recursive functions).
Each computable function f takes a fixed, finite number of natural numbers as arguments. Because the functions are partial in general, they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). These functions are also called partial recursive functions. In computability theory, the domain of a function is taken to be the set of all inputs for which the function is defined.
A function which is defined for all possible arguments is called total. If a computable function is total, it is called a total computable function or total recursive function.
The notation f(x1, ..., xk)↓ indicates that the partial function f is defined on arguments x1, ..., xk, and the notation f(x1, ..., xk) = y indicates that f is defined on the arguments x1, ..., xk and the value returned is y. The case that a function f is undefined for arguments x1, ..., xk is denoted by f(x1, ..., xk)↑ .
Read more about this topic: Computable Function
Famous quotes containing the word definition:
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)