R/M中的与R中的≤T的关系

证明存在递归可枚举图灵度a和c使得ca,并且对每个递归可枚举图灵度b≤_Ta, b≠c, 其中a是R/M中的一个元素,R/M是递归可枚举图灵度集R模可盖图灵度集M的商.     

每个非零的 a∈ R/ M 中不存在极小元

证明了给定任何非零的递归可枚举图灵度 a存在递归可枚举图灵度 c   

R/M中的(≤)与R中的≤T的关系

证明存在递归可枚举图灵度a和c使得c(≤)a,并且对每个递归可枚举图灵度b≤Ta, b≠c, 其中a是R/M中的一个元素,R/M是递归可枚举图灵度集R模可盖图灵度集M的商.     

Rwtt/ Mwtt中的枝点元素

该文证明了在 R_wtt/ M_wtt中除了最大元和最小元外 ,每个元 c是枝点元素 ,即为某两个大于 c的元素的最大下界 ,其中 R_wtt/ M_wtt是递归可枚举弱真值表归约度集 R_wtt模可盖递归可枚举弱真值表归约度集 M_wtt的商.     

稀疏图灵归约“NP=P？”的关系

本文定义了稀疏图灵归约，证明了定量，若ＮＰ（或ＰＳＰＡＣＥ）有≤Ｋ－ｓ－Ｔ＾－困难庥，则ＮＰ＝Ｐ（或Ｐ＝ＰＳＰＡＣＥ）由此还获得了一些结果。     

图灵:计算理论的奠基人

广义的信息理论包含计算理论和通信理论两大部分。计算理论指经典的可计算性理论,代表人物是英国科学家图灵;通信理论指经典的信息论,代表人物是美国科学家香农。本文介绍图灵的杰出贡献,一是建立了图灵机模型,奠定了可计算理论的基础;二是提出了图灵测试,阐述了机器智能的概念。他当之无愧地被誉为“计算机科学之父”。但是在他生活的时代,却完全没有这些赞誉。当时认为他不过是一位古怪的数学家、超前的哲学家、神秘的密码破译专家,没有人会想到他的思维能燃起信息时代的烈焰。童年的艰辛艾兰·图灵(Alan MathisonTuring,1912-1954年)于…     

进化计算的可计算性

本文针对进化计算的进化控制特点，提出了一种进化程度的描述方式，并讨论了进化计算的可计算性。该项工作有助于进化计算形式化理论的建立和应用系统的开发。     

高斯混合分布之间K-L散度的近似计算

高斯混合分布之间的 K-L 散度没有闭式解, 通常采用其上界来近似. 对于具有相同高斯数的混合分布, 基于相对熵链规则推导其 K-L 散度上界, 提出一种更紧上界的计算方法. 为计算具有不同高斯数的混合分布之间的 K-L 散度上界, 提出基于最佳高斯分量复制的方法. 在中文声韵母声学模型上的实验结果显示, 所提出方法可更好地近似等高斯数的混合分布之间的 K-L 散度, 并能有效处理具有不同高斯数的混合分布.     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

Plus cupping degrees do not form an ideal

~~Plus cupping degrees do not form an ideal~~     

The Contiguity in R/M

An r.e. degree c is contiguous if degwtt(A)=degwtt(B)for any r.e. sets A,B∈c.In this paper,we generalize the notation of contiguity to the structure R/M, the upper semilattice of the r.e. degree set R modulo the cappable r.e. degree set M.An element[C]∈R/M is contiguous if s[degwtt(A)]=[degwtt(B)]for any r.e. sets A,B such that degT(A),degT(B)∈[c],It is proved in this paper that every nonzero element in R/M is not contiguous,i.e.,for every element [C]∈R/M,if[C]≠[O] then there exist at least two r.e. sets A,B such that degT(A),degT(B)∈[C]and [degwtt[A]≠[degwtt(B)].     

An extension of Harrington''''s noncupping theorem

(i) Call a c.e. degree b anti-cupping relative to x, if there is a c.e. a < b such that for any c.e. w, w x implies a ∪ w b ∪ x.(ii) Call a c.e. degree b everywhere anti-cupping (e.a.c.), if it is anti-cupping relative to x for each c.e. degree x.By a tree method, we prove that every high c.e. degree has e.a.c. property by extending Harrington's anti-cupping theorem.     

Turing-, Human- and Physical Computability: An Unasked Question

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis (or Thesis M), according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify (or even to be true). In this paper I articulate this question and consider several tentative answers to it.

A Jump Inversion Theorem for the Degree Spectra

In the present article, we continue the study of the propertiesof the spectra of structures as sets of degrees initiated in[11]. Here, we consider the relationships between the spectraand the jump spectra. Our first result is that every jump spectrumis also a spectrum. The main result sounds like a Jump inversiontheorem. Namely, we show that if a spectrum is contained inthe set of the jumps of the degrees in some spectrum then thereexists a spectrum such that and is equal to the set of thejumps of the degrees in .     

Spiking neural P systems: An improved normal form

Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computation (such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems without forgetting rules and delay remains to be found.     

Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

Comments on some theories of fuzzy computation

In classical computability theory, there are several (equivalent) definitions of computable function, decidable subset and semi-decidable subset. This paper is devoted to the discussion of some proposals for extending these definitions to the framework of fuzzy set theory. The paper mainly focuses on the notions of fuzzy Turing machine and fuzzy computability by limit processes. The basic idea of this paper is that the presence of real numbers in the interval [0,1] forces us to refer to endless approximation processes (as in recursive analysis) and not to processes terminating after a finite number of steps and giving the exact output (as in recursive arithmetic). In accordance with such a point of view, an extension of the famous Church thesis is proposed.