论文部分内容阅读
本文讨论了各种时、空资源有界的可计算函数类,诸如PF(确定的多项式时间有界可计算函数类)、NPF(非确定的多项式时间有界可计算函数类)和PSPACEF(多项式空间有界可计算函数类)等。研究了它们和时、空资源有界语言类之间的关系。同时,进一步讨论了相对化的时、空资源有界的语言类和可计算函数类,得到了它们之间,以及它们和非相对情形之间的若干关系。
In this paper, we discuss a variety of computable classes of functions, such as PF (definite polynomial time bounded computable functions), NPF (undefined polynomial time bounded computable functions) and PSPACEF (polynomial Space bounded computable function class) and so on. The relationship between them and the bounded language classes of time and space resources is studied. At the same time, we further discuss relative language classes and computable functions with space-bound and empty resources, and get some relations between them and between them and non-relative cases.