论文标题
关于在计算时间层次结构中存在隐藏机器的存在
On the existence of hidden machines in computational time hierarchies
论文作者
论文摘要
挑战可计算函数中总体的标准概念，一个人具有任何表达式形式的公理系统，但总的函数虽然可计算和“直觉上”为总体，但不能证明是总功能。在本文中，我们表明，这意味着存在时间复杂性类别的无限层次结构，其代表成员隐藏了（或未知）相应的正式公理系统。尽管这些类包含总可计算功能，但有些功能中有一些功能无法识别为属于时间复杂性类别的功能。这导致了计算复杂性形式化的不完整结果。
Challenging the standard notion of totality in computable functions, one has that, given any sufficiently expressive formal axiomatic system, there are total functions that, although computable and "intuitively" understood as being total, cannot be proved to be total. In this article we show that this implies the existence of an infinite hierarchy of time complexity classes whose representative members are hidden from (or unknown by) the respective formal axiomatic systems. Although these classes contain total computable functions, there are some of these functions for which the formal axiomatic system cannot recognize as belonging to a time complexity class. This leads to incompleteness results regarding formalizations of computational complexity.
