Upper Semicomputable
   HOME

TheInfoList



OR:

In
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, a semicomputable function is a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
f : \mathbb \rightarrow \mathbb that can be approximated either from above or from below by a
computable function 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 precis ...
. More precisely a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
f : \mathbb \rightarrow \mathbb is upper semicomputable, meaning it can be approximated from above, if there exists a
computable function 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 precis ...
\phi(x,k) : \mathbb \times \mathbb \rightarrow \mathbb, where x is the desired parameter for f(x) and k is the level of approximation, such that: * \lim_ \phi(x,k) = f(x) * \forall k \in \mathbb : \phi(x,k+1) \leq \phi(x,k) Completely analogous a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
f : \mathbb \rightarrow \mathbb is lower semicomputable if and only if -f(x) is upper semicomputable or equivalently if there exists a
computable function 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 precis ...
\phi(x,k) such that: * \lim_ \phi(x,k) = f(x) * \forall k \in \mathbb : \phi(x,k+1) \geq \phi(x,k) If a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
is both upper and lower semicomputable it is called computable.


See also

*
Computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...


References

* Ming Li and Paul Vitányi, ''An Introduction to Kolmogorov Complexity and Its Applications'', pp 37–38, Springer, 1997. Mathematical logic {{mathlogic-stub