On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata

Cellular automata are models for massively parallel computation. A cellular automaton consists of cells which are arranged in some kind of regular lattice and a local update rule which updates the state of each cell according to the states of the cell's neighbors on each step of the computation. This work focuses on reversible one-dimensional cellular automata in which the cells are arranged in a two-way in_nite line and the computation is reversible, that is, the previous states of the cells can be derived from the current ones. In this work it is shown that several properties of reversible one-dimensional cellular automata are algorithmically undecidable, that is, there exists no algorithm that would tell whether a given cellular automaton has the property or not. It is shown that the tiling problem of Wang tiles remains undecidable even in some very restricted special cases. It follows that it is undecidable whether some given states will always appear in computations by the given cellular automaton. It also follows that a weaker form of expansivity, which is a concept of dynamical systems, is an undecidable property for reversible one-dimensional cellular automata. It is shown that several properties of dynamical systems are undecidable for reversible one-dimensional cellular automata. It shown that sensitivity to initial conditions and topological mixing are undecidable properties. Furthermore, non-sensitive and mixing cellular automata are recursively inseparable. It follows that also chaotic behavior is an undecidable property for reversible one-dimensional cellular automata.

RF Field Immunity of a Network Terminating Unit at Over One Gigaherz Frequencies

Työssä tutkitaan telepäätelaitteen yli gigahertsin taajuisen säteilevän RF kentän sietoisuutta. Mittauksissa testattava laite on Tellabs Oy:n valmistaman CTU modeemin tuotekehitysversio. Teoriaosassa käydään läpi sähkömagneettisten aaltojen teoriaa, sekä säteilevän RF kentän aiheuttamien sähkömagneettiset häiriöiden syntymekanismeja. Myös säteilevien häiriöiden EMC mittauksiin tarvittavien mittalaitteiden tärkeimmät ominaisuudet esitellään, sekä pohditaan yli gigahertsin taajuuksille sopivien EMC mittalaitteiden vaatimuksia. EMC standardit eivät tällä hetkellä aseta vaatimuksia telelaitteiden RF kentän sietoisuudelle yli gigahertsin taajuudella. Tämän vuoksi työssä käsitellään myös todennäköisimpiä häiriölähteitä tällä taajuusalueella. Mittauksissa tutkittiin CTU:n RF kentän sietoisuutta taajuusalueella l - 4.2 GHz. Mittaukset suoritettiin sekä radiokaiuttomassa kammiossa että GTEM solussa. Myös metallisten lisäsuojien vaikutusta CTU:n kentänsietoisuuteen tutkittiin GTEM solussa.

The duality of tactical thought : a study of how Swedish land forces' commanders view tactics in irregular warfare

This is a sociological study of the views of officers in the Swedish Army and its Amphibious Forces on tactics in Irregular Warfare (IW), in particular, Counterinsurgency (COIN). IW comprises struggles, where the military weaker part uses an indirect approach with smaller units and integrates the civilian and military dimensions in a violence spectrum including subversion, terrorism, Guerrilla Warfare and infantry actions. IW is the main armed warfare style in insurgencies. COIN is the combined political, military, economic, social and legal actions in counter insurgencies. Data has been collected by means of interviews with almost all (n =43) officers, who were either commanding battalions or rifle and manoeuvre companies while undergoing training for general warfare and international operations. The main theoretical and methodological inspiration is the traditional one for research on social fields, inaugurated by the French sociologist Pierre Bourdieu. The statistical technique used is Multiple Correspondence Analysis. As a background and context base, an inquiry inspired by the Begriffsgechichte (Conceptual History) tradition explores the genesis and development of understandings of the term Irregular Warfare. The research question is outlined as; “how can contemporary Swedish military thought on tactics in Irregular Warfare be characterized using descriptive patterns, mapped in relation to background factors and normative standards? The most significant findings are that there are two main opposing notions separating the officers’ views on tactics in Irregular Warfare: (1) a focus on larger, combat oriented and collectively operating military units versus smaller and larger, more intelligence oriented and dispersed operating units, and (2) a focus on military tasks and kinetic effects versus military and civilian tasks as well as “soft” effects. The distribution of these views can be presented as a two-dimensional space structured by the two axes. This space represents four categories of tactics, partly diverging from normative military standards for Counterinsurgency. This social space of standpoints shows different structural tendencies for background factors of social and cultural character, particularly dominant concerning military backgrounds, international mission experiences and civilian education. Compared to military standards for Counterinsurgency, the two tactical types characterized by a Regular Warfare mind-set stands out as counter-normative. Signs of creative thought on military practice and theory, as well as a still persistent Regular Warfare doxa are apparent. Power struggles might thus develop, effecting the transformation to a broadened warfare culture with an enhanced focus also on Irregular Warfare. The result does not support research results arguing for a convergence of military thought in the European transformation of Armed Forces. The main argument goes beyond tactics and suggests sociological analysis on reciprocal effects regarding strategy, operational art, tactics as well as leadership, concerning the mind-set and preferences for Regular, Irregular and Hybrid Warfare.

Conservation Laws in Cellular Automata

Conservation laws in physics are numerical invariants of the dynamics of a system. In cellular automata (CA), a similar concept has already been defined and studied. To each local pattern of cell states a real value is associated, interpreted as the “energy” (or “mass”, or . . . ) of that pattern.The overall “energy” of a configuration is simply the sum of the energy of the local patterns appearing on different positions in the configuration. We have a conservation law for that energy, if the total energy of each configuration remains constant during the evolution of the CA. For a given conservation law, it is desirable to find microscopic explanations for the dynamics of the conserved energy in terms of flows of energy from one region toward another. Often, it happens that the energy values are from non-negative integers, and are interpreted as the number of “particles” distributed on a configuration. In such cases, it is conjectured that one can always provide a microscopic explanation for the conservation laws by prescribing rules for the local movement of the particles. The onedimensional case has already been solved by Fuk´s and Pivato. We extend this to two-dimensional cellular automata with radius-0,5 neighborhood on the square lattice. We then consider conservation laws in which the energy values are chosen from a commutative group or semigroup. In this case, the class of all conservation laws for a CA form a partially ordered hierarchy. We study the structure of this hierarchy and prove some basic facts about it. Although the local properties of this hierarchy (at least in the group-valued case) are tractable, its global properties turn out to be algorithmically inaccessible. In particular, we prove that it is undecidable whether this hierarchy is trivial (i.e., if the CA has any non-trivial conservation law at all) or unbounded. We point out some interconnections between the structure of this hierarchy and the dynamical properties of the CA. We show that positively expansive CA do not have non-trivial conservation laws. We also investigate a curious relationship between conservation laws and invariant Gibbs measures in reversible and surjective CA. Gibbs measures are known to coincide with the equilibrium states of a lattice system defined in terms of a Hamiltonian. For reversible cellular automata, each conserved quantity may play the role of a Hamiltonian, and provides a Gibbs measure (or a set of Gibbs measures, in case of phase multiplicity) that is invariant. Conversely, every invariant Gibbs measure provides a conservation law for the CA. For surjective CA, the former statement also follows (in a slightly different form) from the variational characterization of the Gibbs measures. For one-dimensional surjective CA, we show that each invariant Gibbs measure provides a conservation law. We also prove that surjective CA almost surely preserve the average information content per cell with respect to any probability measure.

Magnetic Resonance Experiments with Atomic Hydrogen

In this thesis three experiments with atomic hydrogen (H) at low temperatures T<1 K are presented. Experiments were carried out with two- (2D) and three-dimensional (3D) H gas, and with H atoms trapped in solid H2 matrix. The main focus of this work is on interatomic interactions, which have certain specific features in these three systems considered. A common feature is the very high density of atomic hydrogen, the systems are close to quantum degeneracy. Short range interactions in collisions between atoms are important in gaseous H. The system of H in H₂ differ dramatically because atoms remain fixed in the H₂ lattice and properties are governed by long-range interactions with the solid matrix and with H atoms. The main tools in our studies were the methods of magnetic resonance, with electron spin resonance (ESR) at 128 GHz being used as the principal detection method. For the first time in experiments with H in high magnetic fields and at low temperatures we combined ESR and NMR to perform electron-nuclear double resonance (ENDOR) as well as coherent two-photon spectroscopy. This allowed to distinguish between different types of interactions in the magnetic resonance spectra. Experiments with 2D H gas utilized the thermal compression method in homogeneous magnetic field, developed in our laboratory. In this work methods were developed for direct studies of 3D H at high density, and for creating high density samples of H in H₂. We measured magnetic resonance line shifts due to collisions in the 2D and 3D H gases. First we observed that the cold collision shift in 2D H gas composed of atoms in a single hyperfine state is much smaller than predicted by the mean-field theory. This motivated us to carry out similar experiments with 3D H. In 3D H the cold collision shift was found to be an order of magnitude smaller for atoms in a single hyperfine state than that for a mixture of atoms in two different hyperfine states. The collisional shifts were found to be in fair agreement with the theory, which takes into account symmetrization of the wave functions of the colliding atoms. The origin of the small shift in the 2D H composed of single hyperfine state atoms is not yet understood. The measurement of the shift in 3D H provides experimental determination for the difference of the scattering lengths of ground state atoms. The experiment with H atoms captured in H2 matrix at temperatures below 1 K originated from our work with H gas. We found out that samples of H in H2 were formed during recombination of gas phase H, enabling sample preparation at temperatures below 0.5 K. Alternatively, we created the samples by electron impact dissociation of H₂ molecules in situ in the solid. By the latter method we reached highest densities of H atoms reported so far, 3.5(5)x10¹⁹ cm^-3. The H atoms were found to be stable for weeks at temperatures below 0.5 K. The observation of dipolar interaction effects provides a verification for the density measurement. Our results point to two different sites for H atoms in H2 lattice. The steady-state nuclear polarizations of the atoms were found to be non-thermal. The possibility for further increase of the impurity H density is considered. At higher densities and lower temperatures it might be possible to observe phenomena related to quantum degeneracy in solid.

Two-dimensional drift-diffusion simulation of organic solar cells

The aim of this master's thesis is to develop a two-dimensional drift-di usion model, which describes charge transport in organic solar cells. The main bene t of a two-dimensional model compared to a one-dimensional one is the inclusion of the nanoscale morphology of the active layer of a bulk heterojunction solar cell. The developed model was used to study recombination dynamics at the donor-acceptor interface. In some cases, it was possible to determine e ective parameters, which reproduce the results of the two-dimensional model in the one-dimensional case. A summary of the theory of charge transport in semiconductors was presented and discussed in the context of organic materials. Additionally, the normalization and discretization procedures required to nd a numerical solution to the charge transport problem were outlined. The charge transport problem was solved by implementing an iterative scheme called successive over-relaxation. The obtained solution is given as position-dependent electric potential, free charge carrier concentrations and current densities in the active layer. An interfacial layer, separating the pure phases, was introduced in order to describe charge dynamics occurring at the interface between the donor and acceptor. For simplicity, an e ective generation of free charge carriers in the interfacial layer was implemented. The pure phases simply act as transport layers for the photogenerated charges. Langevin recombination was assumed in the two-dimensional model and an analysis of the apparent recombination rate in the one-dimensional case is presented. The recombination rate in a two-dimensional model is seen to e ectively look like reduced Langevin recombination at open circuit. Replicating the J-U curves obtained in the two-dimensional model is, however, not possible by introducing a constant reduction factor in the Langevin recombination rate. The impact of an acceptor domain in the pure donor phase was investigated. Two cases were considered, one where the acceptor domain is isolated and another where it is connected to the bulk of the acceptor. A comparison to the case where no isolated domains exist was done in order to quantify the observed reduction in the photocurrent. The results show that all charges generated at the isolated domain are lost to recombination, but the domain does not have a major impact on charge transport. Trap-assisted recombination at interfacial trap states was investigated, as well as the surface dipole caused by the trapped charges. A theoretical expression for the ideality factor n_id as a function of generation was derived and shown to agree with simulation data. When the theoretical expression was fitted to simulation data, no interface dipole was observed.