标题： 图灵机计算原始递归函数的特征 显示英文标题

标题： A Characterization of Turing Machines that Compute Primitive Recursive Functions

摘要： 本文提供了对以下断言的新且更直接的证明：自然数的图灵可计算函数当且仅当对应图灵机的时间复杂度由该函数参数的原始递归函数界定时，才是原始递归的。 此外，它提供了这一事实的两个后果的详细证明，尽管在某些圈子中广为人知，但似乎从未被发表过。 第一个是，正确构造为自然数函数的可满足性问题，是原始递归的。 第二个是一个推广，断言所有NP中的问题同样都是原始递归的。 此处的目的是在档案期刊中全面详细地呈现这些定理，从而赋予它们永久性和普遍可用性的地位。 显示英文摘要

摘要： This paper provides a new and more direct proof of the assertion that a Turing computable function of the natural numbers is primitive recursive if and only if the time complexity of the corresponding Turing machine is bounded by a primitive recursive function of the function's arguments. In addition, it provides detailed proofs of two consequences of this fact, which, although well-known in some circles, do not seem to have ever been published. The first is that the Satisfiability Problem, properly construed as a function of natural numbers, is primitive recursive. The second is a generalization asserting that all the problems in NP are similarly primitive recursive. The purpose here is to present these theorems, fully detailed, in an archival journal, thereby giving them a status of permanence and general availability.