Semicomputable function
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computability theory, a semicomputable function is a partial function f : \mathbb{Q} \rightarrow \mathbb{R} that can be approximated either from above or from below by a computable function. More precisely a partial function f : \mathbb{Q} \rightarrow \mathbb{R} is upper semicomputable, meaning it can be approximated from above, if there exists a computable function \phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q} , where x is the desired parameter for f(x) and k is the level of approximation, such that: * \lim_{k \rightarrow \infty} \phi(x,k) = f(x) * \forall k \in \mathbb{N} : \phi(x,k+1) \leq \phi(x,k) Completely analogous a partial function f : \mathbb{Q} \rightarrow \mathbb{R} is lower semicomputable if and only if -f(x) is upper semicomputable or equivalently if there exists a computable function \phi(x,k) such that: * \lim_{k \rightarrow \infty} \phi(x,k) = f(x) * \forall k \in \mathbb{N} : \phi(x,k+1) \geq \phi(x,k) If a partial function is both upper and lower semicomputable it is called computable.
In computability theory, a semicomputable function is a partial function f : \mathbb{Q} \rightarrow \mathbb{R} that can be approximated either from above or from below by a computable function. More precisely a partial function f : \mathbb{Q} \rightarrow \mathbb{R} is upper semicomputable, meaning it can be approximated from above, if there exists a computable function \phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q} , where x is the desired parameter for f(x) and k is the level of approximation, such that: \lim_{k \rightarrow \infty} \phi(x,k) = f(x) \forall k \in \mathbb{N} : \phi(x,k+1) \leq \phi(x,k) Completely analogous a partial function f : \mathbb{Q} \rightarrow \mathbb{R} is lower semicomputable if and only if -f(x) is upper semicomputable or equivalently if there exists a computable function \phi(x,k) such that: \lim_{k \rightarrow \infty} \phi(x,k) = f(x) \forall k \in \mathbb{N} : \phi(x,k+1) \geq \phi(x,k) If a partial function is both upper and lower semicomputable it is called computable. ==See also== Computability theory
Text derived from https://en.wikipedia.org/w/index.php?oldid=1032157670 under CC BY-SA 4.0; modifications have been made.