Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2015 | Buch

The Unconventionality of Nature: Biology, from Noise to Functional Randomness Kapitel lesen Erstes Kapitel lesen

Unconventional Computation and Natural Computation

14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 -- September 3, 2015, Proceedings

herausgegeben von: Cristian S. Calude, Michael J. Dinneen

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book constitutes the refereed proceedings of the 14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015, held in Auckland, New Zealand, in August/September 2015. The 16 revised full papers were carefully reviewed and selected from 38 submissions. The papers cover a wide range of topics including among others molecular (DNA) computing; quantum computing; optical computing; chaos computing; physarum computing; computation in hyperbolic spaces; collision-based computing; cellular automata; neural computation; evolutionary computation; swarm intelligence; nature-inspired algorithms; artificial immune systems; artificial life; membrane computing; amorphous computing; computational systems biology; genetic networks; protein-protein networks; transport networks; synthetic biology; cellular (in vivo) computing; and computations beyond the Turing model and philosophical aspects of computing.

Inhaltsverzeichnis

Frontmatter

Invited Papers

Frontmatter
The Unconventionality of Nature: Biology, from Noise to Functional Randomness
Abstract
In biology, phenotypes’ variability stems from stochastic gene expression as well as from extrinsic fluctuations that are largely based on the contingency of developmental paths and on ecosystemic changes. Both forms of randomness constructively contribute to biological robustness, as resilience, far away from conventional computable dynamics, where elaboration and transmission of information are robust when they resist to noise. We first survey how fluctuations may be inserted in biochemical equations as probabilistic terms, in conjunction to diffusion or path integrals, and treated by statistical approaches to physics. Further work allows to better grasp the role of biological “resonance” (interactions between different levels of organization) and plasticity, in a highly unconventional frame that seems more suitable for biological processes. In contrast to physical conservation properties, thus symmetries, symmetry breaking is particularly relevant in biology; it provides another key component of biological historicity and of randomness as a source of diversity and, thus, of onto-phylogenetic stability and organization as these are also based on variation and adaptativity.
Barbara Bravi, Giuseppe Longo
Ultrametric Algorithms and Automata
Abstract
We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.
Rūsiņš Freivalds
Realism and Texture: Benchmark Problems for Natural Computation
Abstract
We consider the problems of the realistic image synthesis, and texture synthesis, from the point of view of natural computation. These problems provide an interesting and relatively simple setting for considering issues such as the depth of simulation and the role of perception. We conclude with a discussion of recent results on the fundamental limits of image synthesis programs. Interpreting these results more generally suggests that “natural” signals may be exactly those that are compressible. This characterization provides a further link between the fields of natural computation and algorithmic information theory.
John P. Lewis
Quantum Computing Meets the Real World
Abstract
Quantum information processing as a scalable experimental pursuit has experienced significant progress in recent years. Multiple laboratories at large research organizations have constructed working systems with multiple interacting qubits, focused on the implementation of small-scale computational problems or the demonstration of quantum error correction techniques. This stage of development is particularly interesting because the engineering issues related to controlling multiple quantum systems in a noisy environment are being clarified as the various systems progress, illuminating where the best hopes for quantum computation may lie. These practical pathways are not always the same as what has been predicted in the closed-system theoretical context, so creative algorithmic thinking is needed to unlock the potential of the real devices.
Kristen L. Pudenz
BL: A Visual Computing Framework for Interactive Neural System Models of Embodied Cognition and Face to Face Social Learning
Abstract
Our behaviour emerges as the result of many systems interacting at different scales, from low level biology to high level social interaction. Is it possible to create naturalistic explanatory models which can integrate these factors? This paper describes the general approach and design of a framework to create autonomous expressive embodied models of behaviour based on affective and cognitive neuroscience theories.
Mark Sagar, Paul Robertson, David Bullivant, Oleg Efimov, Khurram Jawed, Ratheesh Kalarot, Tim Wu
Computations with Grossone-Based Infinities
Abstract
In this paper, a recent computational methodology is described. It has been introduced with the intention to allow one to work with infinities and infinitesimals numerically in a unique computational framework. It is based on the principle ‘The part is less than the whole’ applied to all quantities (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite). The methodology uses as a computational device the Infinity Computer (patented in USA and EU) working numerically with infinite and infinitesimal numbers that can be written in a positional system with an infinite radix. On a number of examples dealing mainly with infinite sets and Turing machines with different infinite tapes it is shown that it becomes possible to execute a fine analysis of these mathematical objects. The accuracy of the obtained results is continuously compared with results obtained by traditional tools used to work with mathematical objects involving infinity.
Yaroslav D. Sergeyev

Regular Papers

Frontmatter
Exploring the Effect of Cell Heterogeneity in Wound Healing Using a 3D Multicellular Tissue Growth Model
Abstract
We explore some aspects of cell population dynamics in a wound-healing environment using a three-dimensional simulation model for multicellular tissue growth. The computational model uses a discrete approach based on cellular automata to simulate wound-healing times and tissue growth rates of multiple populations of proliferating and migrating cells. Each population of cells has its own division, motion, collision, and aggregation characteristics resulting in a number of useful system parameters that allow us to investigate their emergent effects. These random dynamic processes can be modeled by appropriately choosing the governing rules of the state transitions of each computational site. Discrete systems of this kind constitute an important approach for studying the temporal dynamics of complex biological systems.
Belgacem Ben Youssef
Regularized Linear and Nonlinear Autoregressive Models for Dengue Confirmed-Cases Prediction
Abstract
Based solely on the dengue confirmed-cases of six densely populated urban areas in Brazil, distributed along the country, we propose in this paper regularized linear and nonlinear autoregressive models for one-week ahead prediction of the future behaviour of each time series. Though exhibiting distinct temporal behaviour, all the time series were properly predicted, with a consistently better performance of the nonlinear predictors, based on MLP neural networks. Additional local information associated with environmental conditions will possibly improve the performance of the predictors. However, without including such local environmental variables, such as temperature and rainfall, the performance was proven to be acceptable and the applicability of the methodology can then be directly extended to endemic areas around the world characterized by a poor monitoring of environmental conditions. For tropical countries, predicting the short-term evolution of dengue confirmed-cases may represent a decisive feedback to guide the definition of effective sanitary policies.
Larissa Braz Sousa, Claudio J. Von Zuben, Fernando J. Von Zuben
Asynchronous Spiking Neural P Systems with Structural Plasticity
Abstract
Spiking neural P (in short, SNP) systems are computing devices inspired by biological spiking neurons. In this work we consider SNP systems with structural plasticity (in short, SNPSP systems) working in the asynchronous (in short, asyn mode). SNPSP systems represent a class of SNP systems that have dynamic synapses, i.e. neurons can use plasticity rules to create or remove synapses. We prove that for asyn mode, bounded SNPSP systems (where any neuron produces at most one spike each step) are not universal, while unbounded SNPSP systems with weighted synapses (a weight associated with each synapse allows a neuron to produce more than one spike each step) are universal. The latter systems are similar to SNP systems with extended rules in asyn mode (known to be universal) while the former are similar to SNP systems with standard rules only in asyn mode (conjectured not to be universal). Our results thus provide support to the conjecture of the still open problem.
Francis George C. Cabarle, Henry N. Adorna, Mario J. Pérez-Jiménez
Expressive Power of Non-deterministic Evolving Recurrent Neural Networks in Terms of Their Attractor Dynamics
Abstract
We introduce a model of nondeterministic hybrid recurrent neural networks – made up of Boolean input and output cells as well as internal sigmoid neurons, and equipped with the possibility to have their synaptic weights evolve over time, in a nondeterministic manner. When subjected to some infinite input stream and some specific synaptic evolution, the networks necessarily exhibit some attractor dynamics in their Boolean output cells, and accordingly, recognize some specific neural \(\omega \) -languages. The expressive power of these networks is measured via the topological complexity of their underlying neural \(\omega \)-languages. In this context, we prove that the two models of rational-weighted and real-weighted nondeterministic hybrid neural networks are computationally equivalent, and recognize precisely the set of all analytic neural \(\omega \)-languages. They are therefore strictly more expressive than the nondeterministic Büchi and Muller Turing machines.
Jérémie Cabessa, Jacques Duparc
Duplications and Pseudo-Duplications
Abstract
A duplication is basic phenomenon that occurs through molecular evolution on a biological sequence. A duplication on a string copies any substring of the string. We define k-pseudo-duplication of a string w that consists, roughly speaking, of all strings obtained from w by inserting after a substring u another substring obtained from u by at most k edit operations. We consider three variants of duplication operations, duplication, k-pseudo-duplication and reverse-duplication. First, we give the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize duplications on a string. Then, we show that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Furthermore, we show that the class of context-sensitive languages is closed under duplication, pseudo-duplication and reverse-duplication.
Da-Jung Cho, Yo-Sub Han, Hwee Kim, Alexandros Palioudakis, Kai Salomaa
Going Beyond Turing with P Automata: Partial Adult Halting and Regular Observer $$\omega $$ ω -Languages
Abstract
In this paper we investigate several variants of P automata having infinite runs on finite inputs. By imposing specific conditions on the infinite evolution of the systems, it is easy to find ways for going beyond Turing if we are watching the behavior of the systems on infinite runs. As specific variants we introduce a new halting variant for P automata which we call partial adult halting with the meaning that a specific predefined part of the P automaton does not change any more from some moment on during the infinite run. In a more general way, we can assign \(\omega \)-languages as observer languages to the infinite runs of a P automaton. Specific variants of regular \(\omega \)-languages then, for example, characterize the red-green P automata.
Rudolf Freund, Sergiu Ivanov, Ludwig Staiger
DiSCUS: A Simulation Platform for Conjugation Computing
Abstract
In bacterial populations, cells are able to cooperate in order to yield complex collective functionalities. Interest in population-level cellular behaviour is increasing, due to both our expanding knowledge of the underlying biological principles, and the growing range of possible applications for engineered microbial consortia. The ability of cells to interact through small signalling molecules (a mechanism known as quorum sensing) is the basis for the majority of existing engineered systems. However, horizontal gene transfer (or conjugation) offers the possibility of cells exchanging messages (using DNA) that are much more information-rich. The potential of engineering this conjugation mechanism to suit specific goals will guide future developments in this area. Motivated by a lack of computational models for examining the specific dynamics of conjugation, we present a simulation framework for its further study.
(This paper was first presented at the Spatial Computing Workshop of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Paris, France, May 5–9 2014. There were no published proceedings).
Angel Goñi-Moreno, Martyn Amos
A Cost/Speed/Reliability Tradeoff to Erasing
Abstract
We present a KL-control treatment of the fundamental problem of erasing a bit. We introduce notions of reliability of information storage via a reliability timescale \(\tau _r\), and speed of erasing via an erasing timescale \(\tau _e\). Our problem formulation captures the tradeoff between speed, reliability, and the Kullback-Leibler (KL) cost required to erase a bit. We show that erasing a reliable bit fast costs at least \(\log 2 - \log \left( 1 - {\text {e}}^{-\frac{\tau _e}{\tau _r}}\right) > \log 2\), which goes to \(\frac{1}{2} \log \frac{2\tau _r}{\tau _e}\) when \(\tau _r>>\tau _e\).
Manoj Gopalkrishnan
Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
Abstract
In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes. Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies. The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes at scale factor 2. This improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were more constrained.
Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers
Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points
Abstract
Consider the holiday season, where there are n players who would like to exchange gifts. That is, we would like to generate a random permutation having no fixed point. It is known that such a random permutation can be obtained in a hidden form by using a number of physical cards of four colors with identical backs, guaranteeing that it has no fixed point (without revealing the permutation itself). This paper deals with such a problem and improves the known result: whereas the known protocol needs \(O(n^2)\) cards of four colors, our efficient protocol uses only \(O(n \log n)\) cards of two colors.
Rie Ishikawa, Eikoh Chida, Takaaki Mizuki
Simulation of the 2JLP Gene Assembly Process in Ciliates
Abstract
The gene assembly process in ciliates consists of a massive amount of DNA excision from the micronucleus and sometimes the rearrangement of the rest of the DNA sequences. Several models exist that describe certain parts of this process. In this research, a simulation is created and tested with real data to test the feasibility of the 2JLP model. Several parameters are introduced in the model that are used to test ambiguities or edge cases of the biological model. Parameters are systematically varied within the simulation to try to find their optimal values. Interestingly, a negative correlation is found between the degree to which the simulation successfully descrambles genes, and a parameter that is used to filter out scnRNAs that are similar to IES specific sequences from the macronucleus. This provides in silico evidence that if a scnRNA consists of both a portion of MDS and IES, then from the perspective of maximizing the accuracy of the descrambling, it is desirable to filter out this scnRNA. The simulator successfully performs the gene assembly process whether the inputs are scrambled or unscrambled DNA sequences. On average, before the proof checking stage that is in the model, the descrambling intermediate genes are 91.1 % similar to the descrambled genes. After the proof checking stage, the intermediate genes are 99.4 % similar. We hope that this work and further simulations can serve as a foundation for future computational and mathematical study of descrambling, and to help inform and refine the biological model.
Md. Sowgat Ibne Mahmud, Ian McQuillan
A Uniform Family of Tissue P Systems with Protein on Cells Solving 3-Coloring in Linear Time
Abstract
A new variant of tissue P systems called tissue P system with protein on cells is used in this paper. It has the ability to move proteins between cells. It is inspired from the biology that the cells communicate by sending and receiving signals. Signals most often move through the cell by passing from protein to protein. In tissue P systems with protein on cells, multisets of objects together with proteins between cells are exchanged. We present in this paper a linear solution of the 3-coloring problem, a well known NP-complete problem. In this new variant, these objects called proteins are used to obtain a new solution where the number of rules is lesser than that appears in the original solution with tissue P systems. The number of steps to obtain the solution is lesser than the conventional tissue P system. This is a strong point when someone wants to implement a solution in a practical way.
T. Mathu, Hepzibah A. Christinal, Daniel Díaz-Pernil
Asynchronous Dynamics of Boolean Automata Double-Cycles
Abstract
Because interaction networks occupy more and more space in our current life (social networks) and in our understanding of living systems(biological regulation networks), it seems necessary to develop the knowledge regarding them. By using Boolean automata networks as models of interaction networks, we present new results about the influence of cycles on their dynamics. Cycles in the architecture of boolean networks are known to be the primary engine of dynamical complexity. As a first particular case, we focus on cycle intersections and provide a characterisation of the dynamics of asynchronous Boolean automata networks composed of two cycles that intersect at one automaton. To do so, we introduce an efficient formalism inspired by algorithms to define long sequences of updates, which allows a more efficient description of their dynamics.
Tarek Melliti, Mathilde Noual, Damien Regnault, Sylvain Sené, Jérémy Sobieraj
Non-cooperative Algorithms in Self-assembly
Abstract
Imagine you are left alone in a forest with ogres and wolves, with a paper, a pen and a supply of small stones as your only weapons. How far can you go using a deterministic escape strategy, if you also want to be back in time for dinner (i.e. avoid running periodically)?
The answer to this question has been known for some time (and called the “pumping lemma”) in the simple case where the forest has exactly one self-avoiding trail: after at most \(2^n\) steps (where n is the number of bits writable on your paper) you start running periodically.
However, geometry can sometimes allow for better strategies: in this work, we show the first non-trivial positive algorithmic result (i.e. programs whose output is larger than their size), in a model of self-assembly that has been the center of puzzling open questions for almost 15 years: the planar non-cooperative variant of Winfree’s abstract Tile Assembly Model. Despite significant efforts, very little has been known on this model, until the first fully general results on its computational power, proven recently in SODA 2014.
In this model, tiles can stick to an existing assembly as soon as one of their sides matches the existing assembly. This feature contrasts with the general cooperative model, where it can be required that tiles match on several of their sides in order to bind.
Since the exact computational power of this model is still completely open, we also compare it with classical models from automata theory.
Pierre-Étienne Meunier
Tangle Machines
Abstract
Tangle machines are topologically inspired diagrammatic models. The novel feature of tangle machines is their natural notion of equivalence. Equivalent tangle machines may differ locally, but globally they share the same information content. The goal of tangle machine equivalence is to provide a context-independent method to select, from among many ways to perform a task, the ‘best’ way to perform the task. The concept of equivalent tangle machines is illustrated through an example in which tangle machines represent networks for distributed information processing.
Daniel Moskovich, Avishy Y. Carmi
Formalisation vs. Understanding
A Case Study in Isabelle
Abstract
We discuss how formalisation using proof assistants, an unconventional way of doing mathematics which seems to disregard Gödel’s celebrated Incompleteness Theorems, interacts with ideas of understanding. Our experience is based on a formalisation carried out in the Isabelle generic proof assistant.
Declan Thompson
Backmatter
Metadaten
Titel
Unconventional Computation and Natural Computation
herausgegeben von
Cristian S. Calude
Michael J. Dinneen
Copyright-Jahr
2015
Electronic ISBN
978-3-319-21819-9
Print ISBN
978-3-319-21818-2
DOI
https://doi.org/10.1007/978-3-319-21819-9

Premium Partner

    Bildnachweise