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.     

双层耦合介质中四边形图灵斑图的数值研究

采用双层线性耦合Lengyel-Epstein模型,在二维空间对简单正四边和超点阵四边形进行了数值分析.结果表明:当两子系统波数比N1时,随耦合强度的增大,基模的波矢空间共振形式发生改变,系统由简单六边形自发演化为结构复杂的新型斑图,除已报道的超六边形外,还获得了简单正四边和多种超点阵四边形,包括大小点、点线、白眼和环状超四边等斑图.当耦合系数α和β在一定范围内同步增大时,两子系统形成相同波长的Ⅰ型简单正四边;当α和β不同步增大时,由于两图灵模在短波子系统形成共振,系统斑图经相变发生Ⅰ型正四边→Ⅱ型正四边→超点阵四边形的转变;当系统失去耦合作用时,短波子系统波长为λ的Ⅰ型正四边斑图迅速失稳并形成波长为λ/N的Ⅰ型正四边,随模拟时间的延长,两子系统中不同波长的正四边均会经相变发生Ⅰ型正四边→Ⅱ型正四边→六边形的转变.     

Chemical waves

In our paper we try to describe the basic concepts of chemical waves and spatial pattern formation in a simple way. We pay particular attention to self-organisation phenomena in extended excitable systems. These result in the appearance of travelling waves, spiral waves, target patterns, Turing structures or more complicated structures called scroll waves, which are three-dimensional systems. We describe the most famous oscillating reaction, the Belousov-Zhabotinsky (BZ) reaction, in greater detail. This is because it is of great interest in both physical chemistry and in studies on the evolution and sustenance of self-organising biological systems.     

Effect of a Local Source or Sink of Inhibitor on Turing Patterns

We investigate a reaction-diffusion model in which a Turing pattern develops and reproduces the formation of periodic segments behind a propagating chemical wave front. The chemical scheme involves two species known as activator and inhibitor. The model can be used to mimic the formation of prevertebrae during the early development of vertebrate embryo. Deterministic and stochastic analyses of the reaction-diffusion processes are performed for two typical sets of parameter values, far from and close to the Turing bifurcation. The effects of a local source or sink of inhibitor on the growing structure are studied and successfully compared with experiments performed on chick embryos. We show that fluctuations may lead to the formation of additional prevertebra.     

Numerical approximation of Turing patterns in electrodeposition by ADI methods

In this paper we study the numerical approximation of Turing patterns corresponding to steady state solutions of a PDE system of reaction–diffusion equations modeling an electrodeposition process. We apply the Method of Lines (MOL) and describe the semi-discretization by high order finite differences in space given by the Extended Central Difference Formulas (ECDFs) that approximate Neumann boundary conditions (BCs) with the same accuracy. We introduce a test equation to describe the interplay between the diffusion and the reaction time scales. We present a stability analysis of a selection of time-integrators (IMEX 2-SBDF method, Crank–Nicolson (CN), Alternating Direction Implicit (ADI) method) for the test equation as well as for the Schnakenberg model, prototype of nonlinear reaction–diffusion systems with Turing patterns. Eventually, we apply the ADI-ECDF schemes to solve the electrodeposition model until the stationary patterns (spots & worms and only spots) are reached. We validate the model by comparison with experiments on Cu film growth by electrodeposition.     

On nonlinear coupled diffusions in competition systems

A class of reaction-diffusion systems modeling plant growth with spatial competition in saturated media is presented. We show, in this context, that standard diffusion can not lead to pattern formation (Diffusion Driven Instability of Turing). Degenerated nonlinear coupled diffusions inducing free boundaries and exclusive spatial diffusions are proposed. Local and global existence results are proved for smooth approximations of the degenerated nonlinear diffusions systems which give rise to long-time pattern formations. Numerical simulations of a competition model with degenerate/non degenerate nonlinear coupled diffusions are performed and we carry out the effect of the these diffusions on pattern formation and on the change of basins of attraction.     

Spatial Dynamics of a Diffusive Prey-predator Model with Stage Structure and Fear Effect

To understand the influence of fear effect on population dynamics, especially for the populations with obvious stage structure characteristics, we propose and investigate a diffusive prey-predator model with stage structure in predators. First, we discuss the existence and stability of equilibrium of the model in the absence of diffusion. Then, we obtain the critical conditions for Hopf and Turing bifurcations. Some numerical simulations are also carried out to verify our theoretical results, which indicate that the fear can induce the prey population to show five pattern structures: cold-spot pattern, mixed pattern with cold spots and stripes, stripes pattern, hot-spot pattern, mixed pattern with hot spots and stripes. These findings imply that the fear effect induced by the mature predators plays an important role in the spatial distribution of species.     

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.     

The minimum degree of recursively representable choice functions

We show that the minimum degree of Turing complexity of a recursively representable choice function is Õ″, the degree of a complete ∑₂ set in the Kleene-Mostowski hierarchy. A consequence of this result is that the complexity of such choice functions in this sense is bounded strictly above the degrees of R.E. subsets on $\text{N}$.     

Polynomial differential equations compute all real computable functions on computable compact intervals

In the last decade, there have been several attempts to understand the relations between the many models of analog computation. Unfortunately, most models are not equivalent. Euler's Gamma function, which is computable according to computable analysis, but that cannot be generated by Shannon's General Purpose Analog Computer (GPAC), has often been used to argue that the GPAC is less powerful than digital computation. However, when computability with GPACs is not restricted to real-time generation of functions, it has been shown recently that Gamma becomes computable by a GPAC. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.