دالة شبه قابلة للحساب

في نظرية الحوسبة ، الدالة شبه القابلة للحوسبة هي دالة جزئية${\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)}

إذا كانت الدالة الجزئية قابلة للحساب من الأعلى والأسفل، فإنها تسمى قابلة للحساب.

• نظرية الحوسبة

• مينغ لي وبول فيتاني، مقدمة في تعقيد كولموغوروف وتطبيقاته ، الصفحات 37-38 ، سبرينغر، 1997.