Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].     

Kolmogorov Complexity and Noncomputability

We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability (e. g. by embedding in the halting problem). Also, many sets which are (at least) awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap‐theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal (shortest) proof length.     

Turing degrees of nonabelian groups

For a countable structure , the (Turing) degree spectrum of is the set of all Turing degrees of its isomorphic copies. If the degree spectrum of has the least degree , then we say that is the (Turing) degree of the isomorphism type of . So far, degrees of the isomorphism types have been studied for abelian and metabelian groups. Here, we focus on highly nonabelian groups. We show that there are various centerless groups whose isomorphism types have arbitrary Turing degrees. We also show that there are various centerless groups whose isomorphism types do not have Turing degrees.

     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

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

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

连续统与Turing度

令Ｄ为所有Ｔｕｒｉｎｇ度的集合，≤为Ｄ上的图林化归关系．一函数ｆ：Ｄ→Ｄ称为前进函数如果对任何ａ∈Ｄ，ａ≤ｆ（ａ）。对于一个前进函数ｆ，我们说Ｄ中的两个度ａ，ｂ是ｆ－不可比较的，如果ａ≮ｆ（ｂ）且ｂ ≮ｆ（ａ），否则是ｆ－可比较的．本文的一个主要结果是：在ＺＦＣ中连续统假设成立当且仅当存在一个前进函数ｆ：Ｄ→Ｄ使得Ｄ中任何两个度都是ｆ－可比较的.     

Turing incomparability in Scott sets

For every Scott set and every nonrecursive set in , there is a such that and are Turing incomparable.

     

A minimal pair joining to a plus cupping Turing degree

A computably enumerable (c.e.) degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC , and show that there exists a minimal pair which join to a plus cupping degree, so that PC ? NB . This gives a first known difference between NB and PC . (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On a Conjecture of Kleene and Post

A proof is given that 0 ′ (the argest Turing degree containing a computably enumerable set) is definable in the structure of the degrees of unsolvability. This answers a long‐standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.     

A hierarchy of Turing degrees of divergence bounded computable real numbers

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2^-n. f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ>1 such that, for any constant c, f(nγ)+n+cg(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8–15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005, Springer, Berlin, pp. 418–428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China     

Recursively compressible sets

Classes of recursively compressible and incompressible sets as well as some other classes emerging in connection with a simple recursive-theory model of data array packing are studied. Some new completeness criteria for sets are obtained.Translated fromMatematicheskie Zametki, Vol. 64, No. 1, pp. 9–16, July, 1998.     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

图灵机计算实数函数的稳定性

定义在全体实数上的可计算函数是一个很重要的概念．在这以前定义可计算的实数函数有两个途径．第一个途径是首先要定义可计算实数的指标．想要确定实数函数y=f（x）是不是可以计算就要看是否存在一个自然数的（部分）递归函数将可计算实数x的指标对应到可计算实数y的指标．这样一来对实数函数的研究依赖于对自然数函数的研究．第二个定义可计算的实数函数的途径是以逼近为基础的．一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的．用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数．例如“〈”和“=”的命题函数就是不可以计算的因为它们是不连续的命题函数．本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义．我们的定义不需要用到自然数的（部分）递归函数．根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的．用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多．     

Embedding of Countable Orders in Turing Degrees

In their classical papers, Lerman, Lachlan, and Lebeuf developed the embedding method, which provides constructions of initial segments of Turing degrees isomorphic to various partially ordered structures. We analyze this method and prove that there is a nonzero degree below each decreasing chain of degrees uniform in O'. This imposes restrictions on the application of the embedding method.     

C0复杂度的数学基础

对于许多同时具有强烈非线性和非平稳性的连续生物医学信号来说，计算其复杂度往往要求：1）在数据长度比较短的情况下也可以得出比较鲁棒的估计值；2）无需对原始信号作像二值化这样的过分的粗粒化，我们以前所提出的C0复杂度就是这样的一种度量，但是这种度量缺乏严格的数学基础，因而影响到它的应用，提出了一种改进形式，并严格证明了它的重要性质。从而表明这个量在一定条件下可以作为时间序列随机程度的指标，因而在随机性复杂度的意义下也可作为复杂性的一个定量指标，由于这个量有计算速度快的优点，因此特别适合于一些需要大量计算复杂度的场合，例如计算长时间过程中滑动窗口中复杂度的动态变化。     

Turing Machines Connected to the Undecidability of the Halting Problem

The problem of finding a Turing machine with undecidable halting problem whose program contains the smallest number of instructions is well known. Obviously, such a machine must satisfy the following condition: by deleting even a single instruction from its program, we get a machine with decidable halting problem. In this paper, Turing machines with undecidable halting problem satisfying this condition are called connected. We obtain a number of general properties of such machines and deduce their simplest corollaries concerning the minimal machine with undecidable halting problem.