PR (复杂度)

PR 是包含所有原始递归函数 – 或者换句话说,所有能被这类函数定义的形式语言,这包含了加法,乘法,指数,以及迭代幂次等等。

阿克曼函数则是一个并非 原始递归函数的范例,告诉我们R包含但不等同(strictly contain,或者说严格包含)PR

PR 函数可以被独立的列举,而并非所有R里面的函数皆可。这告诉我们'PR'有一个语意的定义,但是R则没有。

另一方面,我们可以用下列的概念去使用原始递归函数"列举"任何的递归可枚举集合 (参见另一个复杂度类RE):给定输入 (M, k),M是一个图灵机而k是一个正整数,如果M会在k步以内停止则输出M;否则就什么都不输出。然后,这里输出的联集,也就是(M, k)这些组合所有可能的输出,恰好是会停止的M的集合。

PR 包含但不等于ELEMENTARY

参考资料