Semicomputable function
Encyclopedia
In computability theory
a subfield of computer science
a semicomputable function is a partial function
that can be approximated either from above or from below by a computable function
.
More precisely a partial function
is upper semicomputable, meaning it can be approximated from above, if there exists a computable function
, where 
is the desired parameter for 
and 
is the level of approximation, such that:
Completely analogous a partial function
is lower semicomputable iff 
is upper semicomputable or equivalently if there exists a computable function
such that
If a partial function
is both upper and lower semicomputable it is called computable.
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
a subfield of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
a semicomputable function is a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
that can be approximated either from above or from below by a computable functionComputable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
.
More precisely a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
is upper semicomputable, meaning it can be approximated from above, if there exists a computable functionComputable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
, where is the desired parameter for and is the level of approximation, such that:
Completely analogous a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
is lower semicomputable iff is upper semicomputable or equivalently if there exists a computable functionComputable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
such that
If a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
is both upper and lower semicomputable it is called computable.