| 词条 | 递归可枚举集 |
| 释义 | § 递归可枚举集 § 正文 又称部分递归集。在能行性理论中，基本概念是递归函数，它可刻画为：任给x，只要它在x处有定义必可在有限步骤内求出其值。因此递归全函数（即处处有定义的）必可在有限步骤内求出它的任一值，至于递归部分函数（未必处处有定义的）则只要求有定义处可求出其值，但不要求能够在有限步骤内判定它的定义域的元素，即对任给的x判定x是否属于函数的定义域。 设有一集合 A与一函数α(x)，如果α(x)=0当且仅当x∈A，则α(x)叫做A的特征部分函数,如果还有α(x)=1,当且仅当x唘A,则α（x）叫做A的特征全函数,简称特征函数。如果一集合 A的特征部分函数（也是特征函数）是递归全函数，则A叫做递归集；如果一集A的特征部分函数是递归部分函数，则A叫做部分递归集;部分递归集又可定义为某个递归部分函数的定义域。显然,A为递归集当且仅当:任给x,x属于A与否,恒可在有限步内判定；A为部分递归集当且仅当：任给x,如果x∈A,则必可在有限步内判定，但如果x唘A，可能永远不知道这件事（除非从别的途径）。因此有下列结果： ①如果A为递归集，则A为部分递归集； ②A为递归集当且仅当A的补集亦为递归集； ③A为递归集当且仅当A与它的补集都是部分递归集。 最后一点可看出：如果x∈A,因A为部分递归集必可在有限步内看出；如果x唘A,因A的补集为部分递归集亦可在有限步内看出，从而A必为递归集。 递归可枚举集是指它是某个一般递归函数（即递归全函数）ƒ(x)的值域。因为递归全函数ƒ(x)的每一个值都可在有限步内算出，可以逐步地计算ƒ（0），ƒ（1），ƒ(2)，…，从而得出递归可枚举集的所有元素。这便是递归可枚举集名称的来源。ƒ（x）叫做该集的枚举函数，可能有两值ƒ(α)与ƒ(b)是相等的，即容许重复枚举。如果ƒ(x)是不减函数或(严格)递增函数，便叫做不减枚举或（严格）递增枚举。 显然，如果x在一个递归可枚举集A内，必可在有限步内判定（只须依次计算ƒ(0)，ƒ(1)，…，便可）；但如果x不在A内，而A又不是严格递增枚举,则很可能人们永远也不知道这事。根据上述部分递归集的特性，可知递归可枚举集都是部分递归集。反之,如果A为部分递归集，命其特征部分函数为α(x)，当A为空集时,它当然不是任何递归全函数的值域，当A非空集时,则在第一阶段对α(0)，α(1)各计算1步,第二阶段对α(0),α(1)，α(2)各计算2步，…，第n阶段对α(0),α(1),α(2),…，α(n)各计算n步,…,并把首先出现的α(x)=0的根取为ƒ(0),以后在每一阶段之末均把在该阶段时所已知的α(x)=0的根取为ƒ在新主目处的值，ƒ必为递归全函数,而且A的元素恰巧便是ƒ(0)，ƒ(1)，…的值。可见非空的部分递归集必是递归可枚举集。一般还把空集也算作递归可枚举集，这样两种集便一致起来了。 可以证明,A为递归可枚举集当且仅当它是某个原始递归函数的值域，又当且仅当它是某个初等函数的值域。另一方面,A为递归可枚举当且仅当它是某个递归部分函数的值域，只须仿照上法,在第n阶段计算ƒ(0),ƒ(1),…，ƒ(n)各n步,便可把递归部分函数的值全部都枚举出来了。 已有办法把全体递归部分函数全部枚举起来，因此也可以把它们的定义域或值域全部枚举起来。设把第 x个递归部分函数的定义域（值域）记为Wx，则Wx便是全体部分递归集（递归可枚举集）的枚举（注意其中是有重复的）。如命K={x:x∈Wx}（即如果x恰巧在第x个部分递归集之内,便把x作为K 的元素）,则K是一个递归可枚举集但不是递归集，从而K 的补集既不是递归集又不是递归可枚举集。这是人们作出的第一个不是递归可枚举集的例子，它也是一个很重要的集，对它已有充分的研究。 此外，如果ƒ 为递归部分函数，A为递归可枚举,则ƒ-1(A)也是递归可枚举集。 著名的希尔伯特第10问题是：有没有一个能行方法，可决定任给的一个不定方程是否有整数解?这里P、Q是两个具有整系数的多项式。这个问题到1970年已经被否定地解决了,即如果把“能行方法”理解为“用计算递归全函数的方法”，那末可以证明：这个能行方法是没有的。因为任何一个部分递归集（递归可枚举集）A,都有两个带整系数的多项式P、Q，使得 特别是当A即集合K时,也可找出相应的两个多项式P、Q。既然K不是递归的，x属于K与否是不能递归地判定的,那末对于“什么样的x能够使有解”的问题，也就不能递归地判定了。 上面关于集合的讨论可以推广到n元关系去。就n元关系R(x1,x2,…,xn)而言,如果R(x1,x2,…，xn)成立当且仅当，则ƒ(x1,x2,…,xn)叫做R(x1,x2,…,xn) 的特征部分函数，如果还要求：R(x1,x2，…,xn)不成立当且仅当,则ƒ 叫做R的特征全函数,简称特征函数。如果关系R(x1,x2,…,xn)的特征部分函数(也是特征函数)是一个递归全函数，则R叫做递归关系；如果R(x1,x2,…,xn)的特征部分函数是递归部分函数,则R叫做部分递归关系。有了这些定义以后，以上的讨论完全可以推广到递归关系与部分递归关系方面来。当然,由于函数的值是一个数而不是n元向量，所以“递归可枚举关系”不能定义为某个递归全函数的值域而只能定义为部分递归关系。 但是对递归关系而论，有下列的结果，这是讨论递归时所没有的。 ① R(x1，x2，…,xn)为部分递归关系当且仅当有一个n+1元递归关系或部分递归关系 W 使得。 ② R(x1,x2,…,xn)为部分递归关系当且仅当有一个n+m 元递归或部分递归关系W 使得。 ③ A为部分递归集当且仅当有一个二元递归或部分递归关系W 使得。 § “递归可枚举集”与“递归集”的比较 可数集合: 可以与正整数集建立一一对应的无穷集合. 递归可枚举集合: 可数集合S被称为递归可枚举的, 如果存在生成S的元素的算法. 等价定义:可数集合S被称为递归可枚举的, 如果有一个图灵机, 在给定S的一个元素作为输入的时候总是停机, 并在给定的输入不属于S的时候永不停机. 递归集合: 可数集合S被称为递归的, 如果存在能够在有限步骤内判定任意给定元素是否属于S的算法. 从定义中可以推导出几个有用的性质. 所有递归集合都是递归可枚举的, 但不是所有递归可枚举集合都是递归的. 如果一个集合本身及其补集都是递归可枚举的, 那么这个集合是递归的. 显然, 递归集的补集也是递归集. 总结 通常的形式系统中, 所有公理构成的集合可以是有限集合, 也可以是无穷集合, 但公理集都是递归集. 在一阶逻辑中, 所有定理构成的集合P是递归可枚举集合: 存在一个可以枚举出所有定理的算法. 对于只有有限条公理的情况, 这个算法的大致思路是: 从公理出发,将形式系统中的所有推理规则依次作用于每一条公理得到第一批定理, 再将所有推理规则依次作用于第一批定理得到第二批定理, 照此不断进行下去. 于是我们看到, 每一个形式系统中的P都是递归可枚举集合. 皇帝新脑中指出P不是递归的, 也就是说一般地说不存在一个能够依次生成P的补集中的元素的算法. 我的理解是, 可以构造一个简单的形式系统(比如集异璧中的“pq系统”)使其中所有定理构成的集合P是递归的, 不过也存在一些形式系统, 其集合P是非递归的. 事实上这一结论并不是显然的, 因为它与哥德尔定理具有相同的深度. 通常的想法是, 形式系统中所有命题要么能被证明要么能被证伪. 注意任一可证伪的命题恰好是P中某一个命题的逆命题, 所以所有可证伪的命题构成的集合是递归可枚举的. 如果P不是递归的, 也就是说, P的补集不是递归可枚举的, 那么P的补集中除了可证伪的命题之外一定还包括既不可证明又不可证伪的命题. 因为在满足哥德尔定理条件的“足够强”的形式系统中存在着既不可证明又不可证伪的命题, 所以对于形式系统, P是非递归的递归可枚举集. |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。