Semicomputable function

In <a href="/facts/Recursion_theory/cqDfXwdf">computability theory</a>, a semicomputable function is a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> 
 
 
 
 f
 :
 
 Q
 
 →
 
 R
 
 
 
 {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }
 
 that can be approximated either from above or from below by a <a href="/facts/Computable_function/dzwBlLGn">computable function</a>.
More precisely a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> 
 
 
 
 f
 :
 
 Q
 
 →
 
 R
 
 
 
 {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }
 
 is upper semicomputable, meaning it can be approximated from above, if there exists a <a href="/facts/Computable_function/dzwBlLGn">computable function</a> 
 
 
 
 ϕ
 (
 x
 ,
 k
 )
 :
 
 Q
 
 ×
 
 N
 
 →
 
 Q
 
 
 
 {\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} }
 
, where 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is the desired parameter for 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 and 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is the level of approximation, such that:

<ul><li>
 
 
 
 
 lim
 
 k
 →
 ∞
 
 
 ϕ
 (
 x
 ,
 k
 )
 =
 f
 (
 x
 )
 
 
 {\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}
 
</li>
<li>
 
 
 
 ∀
 k
 ∈
 
 N
 
 :
 ϕ
 (
 x
 ,
 k
 +
 1
 )
 ≤
 ϕ
 (
 x
 ,
 k
 )
 
 
 {\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\leq \phi (x,k)}
 
</li></ul>
Completely analogous a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> 
 
 
 
 f
 :
 
 Q
 
 →
 
 R
 
 
 
 {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }
 
 is lower semicomputable if and only if 
 
 
 
 −
 f
 (
 x
 )
 
 
 {\displaystyle -f(x)}
 
 is upper semicomputable or equivalently if there exists a <a href="/facts/Computable_function/dzwBlLGn">computable function</a> 
 
 
 
 ϕ
 (
 x
 ,
 k
 )
 
 
 {\displaystyle \phi (x,k)}
 
 such that:

<ul><li>
 
 
 
 
 lim
 
 k
 →
 ∞
 
 
 ϕ
 (
 x
 ,
 k
 )
 =
 f
 (
 x
 )
 
 
 {\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}
 
</li>
<li>
 
 
 
 ∀
 k
 ∈
 
 N
 
 :
 ϕ
 (
 x
 ,
 k
 +
 1
 )
 ≥
 ϕ
 (
 x
 ,
 k
 )
 
 
 {\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\geq \phi (x,k)}
 
</li></ul>
If a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> is both upper and lower semicomputable it is called computable.

Semicomputable function open-in-new

Semicomputable function