能行可计算性函数渐进优超等价类的可达性质

ON ACCESSIBLE PROPERTIES OF EQUIVALENCE CLASSES OF EFFECTIVE COMPUTABLE FUNCTIONS

利用理想计算机 URM关于能行可计算性函数的定义以及渐进分析的方法对能行可计算性函数进行分类后 ,建立了能行可计算性函数渐进优超等价类子结构 ,并通过引进可达性概念研究能行可计算性函数渐进优超等价类之间的关系 ,证明了任何一致无界能行可计算性函数渐进优超等价类都具有强不可达性质 .此成果对算法复杂性函数渐进优超等价类数学结构的进一步研究有一定参考价值 .

This paper studies the mathematical structure of asymptotically dominating equivalence classes, and establishes the structure of equivalence classes of effective computable functions by using the ideal computer URM and the methods of asymptotic analysis. It is proved in this structure that every uniformly unbounded equivalence class of effective computable functions has strongly inaccessible property.