What is a universal computing machine?

A computer is classically formalised as a universal Turing machine or a similar device. However over the years a lot of research has focused on the computational properties of dynamical systems other than Turing machines, such cellular automata, artificial neural networks, mirrors systems, etc.In this paper we propose a unifying formalism derived from a generalisation of Turing’s arguments. Then we review some of universal systems proposed in the literature and show that are particular case of this formalism. Finally, we review some of the attempts to understand the relation between dynamical and computational properties of a system.     

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.     

Spatial Dynamics of a Diffusive Predator-prey Model with Leslie-Gower Functional Response and Strong Allee Effect

In this paper, spatial dynamics of a diffusive predator-prey model with Leslie-Gower functional response and strong Allee effect is studied. Firstly, we obtain the critical condition of Hopf bifurcation and Turing bifurcation of the PDE model. Secondly, taking self-diffusion coefficient of the prey as bi- furcation parameter, the amplitude equations are derived by using multi-scale analysis methods. Finally, numerical simulations are carried out to verify our theoretical results. The simulations show that with the decrease of self- diffusion coefficient of the prey, the preys present three pattern structures: spot pattern, mixed pattern, and stripe pattern. We also observe the transi- tion from spot patterns to stripe patterns of the prey by changing the intrinsic growth rate of the predator. Our results reveal that both diffusion and the intrinsic growth rate play important roles in the spatial distribution of species.     

Effect of herd shape in a diffusive predator-prey model with time delay

In this paper, we deal with the effect of the shape of herd behavior on the interaction between predator and prey. The model analysis was studied in three parts. The first, The analysis of the system in the absence of spatial diffusion and the time delay, where the local stability of the equilibrium states, the existence of Hopf bifurcation have been investigated. For the second part, the spatiotemporal dynamics introduce by self diffusion was determined, where the existence of Hopf bifurcation, Turing driven instability, Turing-Hopf bifurcation point have been proved. Further, the order of Hopf bifurcation points and regions of the stability of the non trivial equilibrium state was given. In the last part of the paper, we studied the delay effect on the stability of the non trivial equilibrium, where we proved that the delay can lead to the instability of interior equilibrium state, and also the existence of Hopf bifurcation. A numerical simulation was carried out to insure the theoretical results.     

Interactions of Turing and Hopf bifurcations in an additional food provided diffusive predator-prey model

Complex spatiotemporal dynamics of a diffusive predator-prey system involving additional food supply to predator and intra-specific competition among predator, are investigated. We establish critical conditions of the occurrence of Turing instability, which are necessary and sufficient. Furthermore, we also establish conditions of the occurrence of codimension-2 Turing-Hopf bifurcation and Turing-Turing bifurcation, by exploring interactions of Turing bifurcations and Hopf bifurcation. For Turing-Hopf bifurcation, by analyzing normal form truncated to order 3 which are derived by applying normal form method, it is shown that under proper conditions, diffusive predator-prey system generates interesting spatial, temporal and spatiotemporal patterns, including a pair of spatially inhomogeneous steady states, a spatially homogeneous periodic solution and a pair of spatially inhomogeneous periodic solutions. And numerical simulations are also shown to support theory analysis. Moreover, it is found that proper intra-specific competition among predator helps generate complex spatiotemporal dynamics. And, proper additional food supply to predator helps control the population fluctuations of predator and prey, while large quantity and high quality of additional food supply will lead to the extinction of prey and make predator change the source of food, which finally destroy the ecosystem. These investigations might help understand complex spatiotemporal dynamics of predator-prey system involving additional food supply to predator and intra-specific competition among predator, and help conserve species in an ecosystem via supplying suitable additional food.     

Turing pattern formation in a three species model with generalist predator and cross-diffusion

In a natural ecosystem, specialist predators feed almost exclusively on one species of prey. But generalist predators feed on many types of species. Consequently, their dynamics is not coupled to the dynamics of a specific prey population. However, the defense of prey formed by congregating made the predator tend to move in the direction of lower concentration of prey species. This is described by cross-diffusion in a generalist predator–prey model. First, the positive equilibrium solution is globally asymptotically stable for the ODE system and for the reaction–diffusion system without cross-diffusion, respectively, hence it does not belong to the classical Turing instability scheme. But it becomes linearly unstable only when cross-diffusion also plays a role. This implies that cross–diffusion can lead to the occurrence and disappearance of the instability. Our results exhibit some interesting combining effects of cross-diffusion, predations and intra-species interactions. Furthermore, we consider the existence and non-existence results concerning non-constant positive steady states (patterns) of the system. We demonstrate that cross-diffusion can create non-constant positive steady-state solutions.     

耦合诱导Turing斑图的形成

通过数值模拟的方法研究了耦合的CDIMA反应模型。结果显示:处于不能形成图林斑图区域的系统与另一个处于图林斑图区域的系统进行耦合,两系统都能形成图林斑图。     

Polynomial recognition of equal unions in hypergraphs with few vertices of large degree

A family of nonempty sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions. If every point belongs to the unions, then we say the family has the full equal union property. Recognition of both properties is NP-complete even when restricted to families for which the degree of every point is at most three. In this paper we show that both recognition problems can be solved in polynomial time for families in which there is a bound on the number of points whose degree exceeds two.