半計算可能関数

計算可能性理論において、半計算可能関数は部分関数である。${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$それは、計算可能な関数によって上からも下からも近似することができる。

より正確には部分関数${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$は上半計算可能であり、計算可能な関数が存在する場合、上から近似できることを意味します。${\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} }$、 どこ${\displaystyle x}$は、${\displaystyle f(x)}$そして${\displaystyle k}$は近似レベルであり、次のようになる。

• ${\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}$
• ${\displaystyle \forall k\in \mathbb {N}$ \phi (x,k+1)\leq \phi (x,k)}

完全に類似した部分関数${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$下半計算可能であるのは、${\displaystyle -f(x)}$上半計算可能、または同等に計算可能な関数が存在する場合 ${\displaystyle \phi (x,k)}$すなわち、

• ${\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}$
• ${\displaystyle \forall k\in \mathbb {N}$ \phi (x,k+1)\geq \phi (x,k)}

部分関数が上半計算可能かつ下半計算可能である場合、その部分関数は計算可能であると呼ばれる。

• 計算可能性理論

• Ming Li および Paul Vitányi、「コルモゴロフ複雑性とその応用入門」、pp 37 – 38、Springer、1997 年。