关于创造对,产生对

Smullyan在[1,第五章c]中把post引进的并经过Myhill等人系统研究过的创造集、产生集等概念推广为创造对、产生对。可是其中许多结果是错误的。Smullyan在[5]中作了修改,但结果仍不能使人满意。我们这里试图把[1]中结果作如下改正。下面以表示空集。分别表示α与β之交,α与β之和,α减β之差,α之补集。仿一般文献,以g.r.f:表示一般递归函数;r.e.s.表示递归可枚举集;表示见表示一组取定的     

结构多项式复杂性研究中使用的一些方法

本文介绍了结构多项式复杂性研究中用的一些方法，包括能行对角线方法，能行有穷延伸法，填料法，间隙法，延迟对角线法，加速法。     

关于原始递归性

<正> 我们假定读者了解[1,2,3]中的内容,因而在使用其中符号吋不再详细说明.本文所用的字母表(?)指有穷字母表{0_1,…,0_k}.自从1928年 Ackermann 指出以后,大家都知道递归全函数范围是超出原始递归函数范围的(见[4])。但原始递归函数类,确为一个很自然的,有鲜明特色的函数类。它包括古     

数理逻辑及其重要意义

<正> 1.数理逻辑对计算机发展的作用 早在公元前,中国、希腊数学家已经有了算法的概念,其后,印度、阿拉伯数学家也致力于寻找代数问题的算法.后来,欧洲数学发展起来了,人们不仅要找计算的算法,还想找推理的算法.为了给出证明一切数学定理的算法Leibzitg创造了数理逻辑,人们发现一些数学问题不易找到算法,如半群上字的问题,丢番图方程求解问题,谓词演算判定问题等,怀疑有一些数学问题是没有解决它们的算法的,为了证明对某些问题不存在算法,     

胡世华先生的学术成就

胡世华先生,1912年1月28日生于上海,祖籍浙江吴兴,1935年毕业于北京大学哲学系并获得学士学位,1936年先后赴奥地利维也纳大学,德国敏思特威廉大学学习,并获得博士学位,1949年加入中国民主同盟,1954年加入中国共产党。     

α-非有丝分离集的存在性

<正> 近年来自然数域上的递归论已向广义递归论上发展.广义递归论的一个分支是研究在序数的可允许前节α上的递归论,人们通常称之为α-递归论α目前α-递归论的大多数成果是探讨哪些自然数域上递归论的结果可以推广到α-递归论上去.已有的结果表明,有些自然数域上递归论的结果可以推广到序数的一切可允许前节上去.例如Post问     

证明论的一些新进展

自从1935年Peano算术系统的协调性被证明以来,证明论的进展不像数理逻辑的其他分支那么快,因此一般人对它不大注意。但是最近一段时间证明论有很大进展,引起人们注意。特别是H.Friedman被授与Waterman奖以后,国内数学界不少同志希望了解这方面工作。本文主要介绍两方面工作:1°数学的反推导;2°独立性问题。     

O'下纯正多项式极小度的存在性

引言Homer 在中证明了在 P=NP 条件下可以证明 O′下纯正多项式极小度的存在性,他还证明了若干种 O″下的集不具有纯正多项式极小度.如果可以证明一切 O″下的集都不具有纯正极小度,那么可以证明 P≠NP。因此 Homer 的工作给出了一个解决“P=?NP”问题的一个可能途径.本文目的是在 P=NP 条件下证明在 O′下存在纯正多项式极小度.这样只须证明一切O′下的集都不具有纯正多项式极小度,则有 P≠NP.从而可以使证明 P≠NP 的这种途径     

结构多顶式复杂性研究中使用的一些方法

本文介绍了结构多项式性研究中用的一些方法，包括能行对角线方法，能行有穷延伸法，填料法，间隙法，延迟对角线法，加速法。     

相对于 △_2~0集的α-分离定理

<正> 引言如果把序数看成自然数的推广,那么很自然地会想到要把自然数集上的递归论推广成序数上的递归论.序数上递归函数的概念首先是 Takeuti 提出来的.后来 Kripke 又在可允许序数α的前节上建立了递归函数的概念.并把和 Kleene 的 T 谓词有关的定理,如部分递归函数的通用函数定理、S_n~m 定理、递归式定理以及有关算术谓词分层的结果都成功地推广了,并建立了可允许序数α的前节上的递归论.一般人称之为α-递归论.