“Semicomputable function”的意思、由来-开放百科全书

词条

Semicomputable function

释义

See also
References

In computability theory, a semicomputable function is a partial function that can be approximated either from above or from below by a computable function.

More precisely a partial function is upper semicomputable, meaning it can be approximated from above, if there exists a computable function , where is the desired parameter for and is the level of approximation, such that:

Completely analogous a partial function is lower semicomputable iff is upper semicomputable or equivalently if there exists a computable function such that

If a partial function is both upper and lower semicomputable it is called computable.

References

Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, pp 37–38, Springer, 1997.

1 : Mathematical logic

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

See also

References