Restrictions on the degree spectra of algebraic structures

We construct the degree b ≤ 0″ admitting no algebraic structure with degree spectrum {x: x ? b}. Moreover, we solve Miller’s problem of distinguishing incomparable degrees by the spectra of linear orderings.     

Increasing η ‐representable degrees

In this paper we prove that any Δ₃⁰ degree has an increasing η ‐representation. Therefore, there is an increasing η ‐representable set without a strong η ‐representation (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strong jump-traceability I: The computably enumerable case

Recent investigations in algorithmic randomness have lead to the discovery and analysis of the fundamental class K of reals called the K-trivial reals, defined as those whose initial segment complexity is identical with that of the sequence of all 1's. There remain many important open questions concerning this class, such as whether there is a combinatorial characterization of the class and whether it coincides with possibly smaller subclasses, such as the class of reals which are not sufficiently powerful as oracles to cup a Turing incomplete Martin-Löf random real to the halting problem. Hidden here is the question of whether there exist proper natural subclasses of K. We show that the combinatorial class of computably enumerable, strongly jump-traceable reals, defined via the jump operator by Figueira, Nies and Stephan [Santiago Figueira, André Nies, Frank Stephan, Lowness properties and approximations of the jump, Electr. Notes Theor. Comput. Sci. 143 (2006) 45-57], is such a class, and show that like K, it is an ideal in the computably enumerable degrees. This is the first example of a class of reals defined by a “cost function” construction which forms a proper subclass of K. Further, we show that every c.e., strongly jump-traceable set is not Martin-Löf cuppable, thus giving a combinatorial property which implies non-ML cuppability.     

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.     

双层耦合非对称反应扩散系统中的超点阵斑图

通过线性耦合Brusselator模型和Lengyel-Epstein模型,数值研究了双层耦合非对称反应扩散系统中图灵模之间的相互作用以及斑图的形成机理.模拟结果表明,合适的波数比以及相同的对称性是两个图灵模之间达到空间共振的必要条件,而耦合强度则直接影响了图灵斑图的振幅大小.为了保证对称性相同,两个图灵模的本征值高度要位于一定的范围内.只有失稳模为长波模时,才能对另一个图灵模产生调制作用,并形成多尺度时空斑图.随着波数比的增加,短波模子系统依次经历黑眼斑图、白眼斑图以及时序振荡六边形斑图的转变.研究表明失稳图灵模与处于短波不稳定区域的高阶谐波模之间的共振是产生时序振荡六边形的主要原因.     

六边形格子态斑图的数值模拟

采用双层耦合的Lengel-Epstein模型, 通过改变两子系统图灵模的强度比, 获得了四种的六边形格子态和多种非格子态结构. 模拟结果表明: 反应扩散系统的格子态结构由三套子结构叠加而成, 是两图灵模的波数比和强度比共同作用的结果, 两模的强度比决定了三波共振的具体模式; 另外, 系统选择格子态斑图所需的两图灵模的强度比大于非格子态斑图的强度比; 逐步增加两图灵模强度比, 出现的斑图趋于从复杂到简单变化. 深入研究发现: 不同互质数对(a, b)对应的格子态斑图的稳定性不同, 其中(3, 2)对应的格子态结构最为稳定.     

Note on a universal quantum Turing machine

In this Letter, we construct a novel model of universal quantum Turing machine (QTM) by means of a property of Riemann zeta function, which is free from the specific time for an input data and efficiently simulates each step of a given QTM.