Emergence of self-replicating structures in a cellular automata space

Past cellular automata models of self-replication have always been initialized with an original copy of the structure that will replicate, and have been based on a transition function that only works for a single, specific structure. This article demonstrates for the first time that it is possible to create cellular automata models in which a self-replicating structure emerges from an initial state having a random density and distribution of individual components. These emergent self-replicating structures employ a fairly general rule set that can support the replication of structures of different sizes and their growth from smaller to larger ones. This rule set also allows “random” interactions of self-replicating structures with each other and with other structures within the cellular automata space. Systematic simulations show that emergence and growth of replicants occurs often and is essentially independent of the cellular space size, initial random pattern of components, and initial density of components, over a broad range of these parameters. The number of replicants and the total number of components they incorporate generally approach quasi-stable values with time.     

Reversibility Problem of Multidimensional Finite Cellular Automata

While the reversibility of multidimensional cellular automata is undecidable and there exists a criterion for determining if a multidimensional linear cellular automaton is reversible, there are only a few results about the reversibility problem of multidimensional linear cellular automata under boundary conditions. This work proposes a criterion for testing the reversibility of a multidimensional linear cellular automaton under null boundary condition and an algorithm for the computation of its reverse, if it exists. The investigation of the dynamical behavior of a multidimensional linear cellular automaton under null boundary condition is equivalent to elucidating the properties of the block Toeplitz matrix. The proposed criterion significantly reduces the computational cost whenever the number of cells or the dimension is large; the discussion can also apply to cellular automata under periodic boundary conditions with a minor modification.     

Application of a cellular automaton for the evolution of etched nuclear tracks

In the present work, it is demonstrated the first application of cellular automata to the growing of etched nuclear tracks. The simplest case in which conical etched tracks are gradually formed is presented, as well as a general case of time varying etching rate V_t. It is demonstrated that the cellular automata elements consist in an image pattern of the latent nuclear track input cells, 16 rules for updating states, the Moore neighborhood and an algorithm of four states.     

Spatial updating, spatial transients, and regularities of a complex automaton with nonperiodic architecture

We study the dynamics of patterns exhibited by rule 52, a totalistic cellular automaton displaying intricate behaviors and wide regions of active/inactive synchronization patches. Systematic computer simulations involving 2(30) initial configurations reveal that all complexity in this automaton originates from random juxtaposition of a very small number of interfaces delimiting active/inactive patches. Such interfaces are studied with a sidewise spatial updating algorithm. This novel tool allows us to prove that the interfaces found empirically are the only interfaces possible for these periods, independently of the size of the automata. The spatial updating algorithm provides an alternative way to determine the dynamics of automata of arbitrary size, a way of taking into account the complexity of the connections in the lattice.     

A numerical scheme for the integration of the Vlasov–Poisson system of equations, in the magnetized case

We present a numerical algorithm for the solution of the Vlasov–Poisson system of equations, in the magnetized case. The numerical integration is performed using the well-known “splitting” method in the electrostatic approximation, coupled with a finite difference upwind scheme; finally the algorithm provides second order accuracy in space and time. The cylindrical geometry is used in the velocity space, in order to describe the rotation of the particles around the direction of the external uniform magnetic field.Using polar coordinates, the integration of the Vlasov equation is very simplified in the velocity space with respect to the cartesian geometry, because the rotation in the velocity cartesian space corresponds to a translation along the azimuthal angle in the cylindrical reference frame. The scheme is intrinsically symplectic and significatively simpler to implement, with respect to a cartesian one. The numerical integration is shown in detail and several conservation tests are presented, in order to control the numerical accuracy of the code and the time evolution of the entropy, strictly related to the filamentation problem for a kinetic model, is discussed.     

Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields $\pmb{ {\mathbb{Z}}}_{p}$

The reversibility problem for linear cellular automata with null boundary defined by a rule matrix in the form of a pentadiagonal matrix was studied recently over the binary field ℤ₂ (del Rey and Rodriguez Sánchez in Appl. Math. Comput., 2011, doi:). In this paper, we study one-dimensional linear cellular automata with periodic boundary conditions over any finite field ℤ _p . For any given p≥2, we show that the reversibility problem can be reduced to solving a recurrence relation depending on the number of cells and the coefficients of the local rules defining the one-dimensional linear cellular automata. More specifically, for any given values (from any fixed field ℤ _p ) of the coefficients of the local rules, we outline a computer algorithm determining the recurrence relation which can be solved by testing reversibility of the cellular automaton for some finite number of cells. As an example, we give the full criteria for the reversibility of the one-dimensional linear cellular automata over the fields ℤ₂ and ℤ₃.     

复合元胞自动机系统反向迭代加密技术研究

提出了元胞自动机的交叉复合在序列R下随机复合的思想,分析了复合元胞自动机系统的密码学特性,利用元胞自动机反向迭代加密技术,构造了两个基于复合元胞自动机的密码系统.新的复合元胞自动机密码系统很好地解决了单一元胞自动机密码系统中存在的误差单向扩散的问题,并且能够以较小的规则半径获得大密钥空间.计算机仿真结果表明,复合元胞自动机密码系统具有良好的扰乱和扩散性能,能够有效地抵抗蛮力攻击和差分分析. 关键词： 离散动力系统 复合元胞自动机 反向迭代 分组密码     

基于复合符号混沌的伪随机数生成器及加密技术

提出了复合符号混沌序列的概念;并以符号动力学的揉序列为基础,将已知的伪随机数与揉序列规则下的短序列复合后得到新的符号混沌序列,再转换成二进制序列,从而得到长度随迭代次数成几何级数增加的伪随机序列(PRN).理论与实证分析都表明这是一个有效的伪随机生成器.为应用到图像的加解密技术中,建立了一个新型元胞自动机.该元胞自动机能有效地避免数据膨胀,加密效率高,并能产生显著的"雪崩效应",提高了加密技术的安全性. 关键词： 复合符号混沌序列 符号动力学 伪随机序列 元胞自动机     

Flux-corrected transport. III. Minimal-error FCT algorithms

This paper presents an error analysis of numerical algorithms for solving the convective continuity equation using flux-corrected transport (FCT) techniques. The nature of numerical errors in Eulerian finite-difference solutions to the continuity equation is analyzed. The properties and intrinsic errors of an “optimal” algorithm are discussed and a flux-corrected form of such an algorithm is demonstrated for a restricted class of problems. This optimal FCT algorithm is applied to a model test problem and the error is monitored for comparison with more generally applicable algorithms. Several improved FCT algorithms are developed and judged against both standard flux-uncorrected transport algorithms and the optimal algorithm. These improved FCT algorithms are found to be four to eight times more accurate than standard non-FCT algorithms, nearly twice as accurate as the original SHASTA FCT algorithm, and approach the accuracy of the optimal algorithm.     

Three-dimensional diffuse optical imaging of hand joints: System description and phantom studies

In this paper we describe a three-dimensional (3D) continuous wave (CW) diffuse optical tomography (DOT) system and present 3D volumetric reconstruction studies using this DOT system with simple phantom models that simulate hand joints. The CCD-based DOT system consists of 64×64 source/detector fiber optic channels, which are arranged in four layers, forming a cylindrical fiber optic/tissue interface. Phantom experiments are used to evaluate system performance with respective to axial spatial resolution, optical contrast and target position for detection of osteoarthritis where cartilage is the primary target region of interest. These phantom studies suggest that we are able to quantitatively resolve a 2 mm thick “cartilage” and qualitatively resolve a 1 mm thick “cartilage” using our 3D reconstruction approach. Our results also show that optical contrast of 3:1–7:1 between the “disease cartilage” and normal cartilage can be quantitatively recovered. Finally, the target position along axial direction on image reconstruction is studied. All the images are obtained using our 3D finite-element-based reconstruction algorithm.     

Cellular automata for nanometer-scale computation

Cellular automata have recently been proposed as an architecture for dense, locally-interacting arrays of submicron devices. However, because conventional von Neumann cellular automata do not correctly reflect the long-range behavior of typical inter-device interactions, they do not provide a suitable theoretical model for the proposed device arrays. In this paper we define replica cellular automata, a class of cellular automata that can be generated from lattice-gas cellular automata. We show that for inter-device interactions that have a well-defined screening length D, replica cellular automata provide a suitable formal model. As an example of their applicability, we exhibit a computation-universal cellular automata architecture in which the cells consist of charge-transfer quantum dot devices.     

Phenomenology of nonlocal cellular automata

Dynamical systems with nonlocal connections have potential applications to economic and biological systems. This paper studies the dynamics of nonlocal cellular automata. In particular, all two-state, three-input nonlocal cellular automata are classified according to the dynamical behavior starting from random initial configurations and random wirings, although it is observed that sometimes a rule can have different dynamical behaviors with different wirings. The nonlocal cellular automata rule space is studied using a mean-field parametrization which is ideal for the situation of random wiring. Nonlocal cellular automata can be considered as computers carrying out computation at the level of each component. Their computational abilities are studied from the point of view of whether they contain many basic logical gates. In particular, I ask the question of whether a three-input cellular automaton rule contains the three fundamental logical gates: two-input rules AND and OR, and one-input rule NOT. A particularly interesting edge-of-chaos nonlocal cellular automaton, the rule 184, is studied in detail. It is a system of coupled selectors or multiplexers. It is also part of the Fredkin's gate—a proposed fundamental gate for conservative computations. This rule exhibits irregular fluctuations of density, large coherent structures, and long transient times.     

Vertical magneto-tunneling through a quantum dot and the density of states of small electronic systems

One-electron tunneling through a quantum dot with a strong magnetic field in the direction of the current is studied. The linear magneto-conductance is computed for a model parabolic dot with seven electrons in the intermediate states and for different values of the magnetic field. It is shown that the dot density of states at low excitation energies can be extracted from a precise measurement of the conductance at the upper edge of the Coulomb blockade diamond. We parametrized the density of states with a single “temperature” parameter (in the so called “constant temperature approximation”), and found that this parameter depends very weakly on the magnetic field.     

Detonability limits in thin annular channels

In this paper, detonability limits in two-dimensional annular channels are investigated. Since the channel heights are small in comparison to the tube diameter, curvature effects can be neglected and the annular channels can be considered to be essentially two-dimensional. Mixtures that are highly diluted with argon are used since previous investigations seem to indicate that detonations in such mixtures are “stable” in that cellular instabilities play minor roles on the propagation of the detonation. For stable detonations where the ZND structure is valid, boundary layer effects can be modeled as a flow divergence term in the conservation of mass equation following the pioneering work of Fay [J.A. Fay, Phys. Fluids 2(3) (1959) 283–289]. Expansion due to flow divergence in the reaction zone results in a velocity deficit. There exists a maximum deficit when an eigenvalue detonation velocity can no longer be found, which can be taken as the onset of the detonability limits. Experimentally, it was found that unlike “unstable” detonations, the detonability limits for “stable” detonations are well-defined. No unstable near-limit phenomena (e.g., galloping detonations) was observed. Good agreement is found between the theoretical predictions and the experimentally obtained velocity deficits and limits in the two channel heights of 2.2 and 6.9 mm for hydrogen–oxygen and acetylene–oxygen mixtures diluted with over 50% argon. It may be concluded that at least for these special mixtures where the detonation is “stable,” the failure mechanism is due to flow divergence caused by the negative displacement thickness of the boundary layer behind the leading shock front of the detonation wave.     

Supervised nuclear track detection of CR-39 detectors by cellular automata

In this paper, cellular automata are used to detect the nuclear tracks in the track images captured from the surface of CR-39 detectors. Parameters of the automaton as the states, neighborhood, rules and quality parameters are defined optimally for the track image data set under analysis. The presented method is a supervised computational algorithm which comprises a rule definition phase as the learning procedure. Parameter optimization is also performed to adapt the algorithm to the data set used.     

Two-dimensional cellular automata

A largely phenomenological study of two-dimensional cellular automata is reported. Qualitative classes of behavior similar to those in one-dimensional cellular automata are found. Growth from simple seeds in two-dimensiona! cellular automata can produce patterns with complicated boundaries, characterized by a variety of growth dimensions. Evolution from disordered states can give domains with boundaries that execute effectively continuous motions. Some global properties of cellular automata can be described by entropies and Lyapunov exponents. Others are undecidable.This work was supported in part by the U.S. Office of Naval Research under Contract No. N00014-80-C-0657.     

Viscous drag by cellular automata

A simple method to compute the drag coefficient of two-dimensional bodies with arbitrary shapes is presented. The procedure is based on cellular automata as an extreme idealization of the molecular dynamics of a viscous fluid. We verify the algorithm by examples and obtain results in quantitative agreement with experiments even when eddies behind the obstacle are formed.