Wang’s B machines are efficiently universal,as is Hasenjaeger’s small universal electromechanical toy

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger’s machine simulates Hao Wang’s B machines, which were proved universal by Wang. Unfortunately, Wang’s original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger’s machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang’s B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger’s machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger’s machine is both small and fast. In another application of our result, we show that Hooper’s small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.     

Stability and Hopf bifurcation of a diffusive predator–prey model with predator saturation and competition

This article discusses a predator–prey system with predator saturation and competition functional response. The local stability, existence of a Hopf bifurcation at the coexistence equilibrium and stability of bifurcating periodic solutions are obtained in the absence of diffusion. Further, we discuss the diffusion-driven instability, Hopf bifurcation for corresponding diffusion system with zero flux boundary condition and Turing instability region regarding the parameters are established. Finally, numerical simulations supporting the theoretical analysis are also included.     

用图灵机计算热传导方程

研究了带初值的热传导方程广义解的可计算性。首先，给出TTE的一些基本概念，然后，通过广义函数的理论得出热传导方程的基本解，最后，运用广义函数卷积的可计算性质得到最后证明。     

Uniform reducibility of representability problems for algebraic structures

Given a countable algebraic structure \(\mathfrak{B}\) with no degree we find sufficient conditions for the existence of a countable structure \(\mathfrak{A}\) with the following properties: (1) for every isomorphic copy of \(\mathfrak{A}\) there is an isomorphic copy of \(\mathfrak{A}\) Turing reducible to the former; (2) there is no uniform effective procedure for generating a copy of \(\mathfrak{A}\) given a copy of \(\mathfrak{B}\) even having been enriched with an arbitrary finite tuple of constants.     

Multiscale analysis for diffusion-driven neutrally stable states

The Turing instabilities for reaction–diffusion systems are studied from the Fourier normal modes which appear by searching the solution obtained from linearization of the reaction–diffusion system at the spatially homogeneous steady state. The linear stability analysis is only appropriate when the temporal eigenvalues associated to every given spatial eigenvalue have non-zero real part. If the real part of the temporal eigenvalue in a normal mode is equal to zero there is no enough information coming from the linearized system. Given an arbitrary spatial eigenvalue, by equating to zero the real part of the corresponding temporal eigenvalue will lead to a neutral stability manifold in the parameter space. If for a given spatial eigenvalue the other parameters in the reaction–diffusion process drive the system to the neutral manifold, then neither stability nor instability can be warranted by the usual linear analysis. In order to give a sketch of the nonlinear analysis we use a multiple scales method. As an application, we analyze the behavior of solutions to the Schnakenberg trimolecular reaction kinetics in the presence of diffusion.     

Modeling ternary mixtures by mean-field theory of polyelectrolytes: Coupled Ginzburg-Landau and Swift-Hohenberg equations

The purpose of this work is to model ternary mixtures using the theory of pattern formation and of polyelectrolytes, with mean-field approximations. The model has two local, non-conserved order parameters. In the free energy short-range and long-range nonlocal interactions between elements of the mixture are considered. The spatiotemporal dynamics of the system is described by coupling the time-dependent Ginzburg-Landau equation and the Swift-Hohenberg equation. These non-linear partial differential equations are solved with numerical methods to study the emergent spatially stable configurations. The model shows a large diversity of patterns, which permit an interpretation of the behavior of some biological systems and presents different growth lengths within its spatial structures.     

Some New Lattice Constructions in High R. E. Degrees

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets (Lerman, Lachlan). In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that (i) A has no dense simple superset, (ii) the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with (i), and (iii) A ?_T B if B is high, and A ≥_T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.     

A New Reducibility between Turing- and wtt-Reducibility

A new reducibility between Turing and weak truth-table reducibility is defined, which gives an affirmative answer to the open question about the existence of such an intermediate reducibility proposed formally by M. Stob. Mathematics Subject Classification: 03D25.     

关于递归控制Turing可化归性

证明了“递归控制Ｔｕｒｉｎｇ可化归性”（简称ｒｃｔ－可化归性）崩溃成平凡情形，即证明了任何两个有穷集合或任何两个无穷的递归可枚举集合都分别是ｒｃｔ－等价的，而它们两者之间则又不是ｒｃｔ－等价的．也即有且只有两个递归可枚举的ｒｃｔ－度．从而ｒｃｔ－可化归性不是通常递归论意义下的合适的可化归性．