The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The mutual mobile membrane systems represent a variant of mobile membrane systems in which the endocytosis and exocytosis work whenever the involved membranes “agree” on the movement (this agreement is described by using dual objects a and in the involved membranes). We study the computational power of this variant of mobile membrane systems, proving that only three membranes are...
An amoeboid organism, Physarum, exhibits rich spatiotemporal oscillatory behavior and various computational capabilities. Previously, the authors created a recurrent neurocomputer incorporating the amoeba as a computing substrate to solve optimization problems. In this paper, considering the amoeba to be a network of oscillators coupled such that they compete for constant amounts of resources, we...
In this paper we simplify the model of computation considered in [1], namely network of evolutionary picture processors, by moving the filters from the nodes to the edges. Each edge is now viewed as a two-way channel such that input and output filters, respectively, of the two nodes connected by the edge coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished...
We investigate the computation of mappings from a set Sn to itself with in situ programs, that is using no extra variables than the input, and performing modifications of one component at a time. We consider several types of mappings and obtain effective computation and decomposition methods, together with upper bounds on the program length (number of assignments)...
Using the model of real computability developed by Blum, Cucker, Shub, and Smale, we investigate the difficulty of determining the answers to several basic topological questions about manifolds. We state definitions of real-computable manifold and of real-computable paths in such manifolds, and show that, while BSS machines cannot in general decide such questions as nullhomotopy and simple connectedness...
In this paper we explore the structure and applicability of the Distributed Measurement Calculus (DMC), a formal assembly language for distributed measurement-based quantum computations. We describe its syntax and semantics, both operational and denotational, and state several properties that are crucial to the practical usability of our language, such as equivalence of our semantics, as well as compositionality...
Motivated by the recent emergence of ultra-high speed (e.g., 100Gb/s) optical networks, some researchers have recently started the study of optical encryption techniques that offer secrecy of information transfer over such networks. Despite significant attention to this problem, we are not aware of attempts made to define a formal cryptographic model for the study of such schemes. In this paper we...
We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform random numbers. Namely, given an integer range {0,...,n − 1}, we exhibit methods for randomly selecting a number within that range. We present three constructions exhibiting a trade-off between space requirements and closeness to uniformity. The first selector selects a...
Extended Signal machines are proven able to compute any computable function in the understanding of recursive/computable analysis (CA), here type-2 Turing machines (T2-TM) with signed binary encoding. This relies on an intermediate representation of any real number as an integer (in signed binary) plus an exact value in ( − 1,1) which allows to have only finitely many signals present outside of the...
In this paper we address the problem of describing the complexity of the evolution of a tissue-like P system with cell division. In the computations of such systems the number of (parallel) steps is not sufficient to evaluate the complexity. Following this consideration, Sevilla Carpets were introduced as a tool to describe the space-time complexity of P systems. Sevilla Carpets have already...
In this note we investigate the problem of computing the domain of attraction of a flow on ℝ2 for a given attractor. We consider an operator that takes two inputs, the description of the flow and a cover of the attractors, and outputs the domain of attraction for the given attractor. We show that: (i) if we consider only (structurally) stable systems, the operator is (strictly semi-)computable; (ii)...
The single celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs. We present a model multi-agent population which collectively approximates the network behaviours of Physarum. We demonstrate spontaneous transport network formation and evolution and show that the collective population also exhibits quasi-physical...
In order to develop an adaptive computing system, we investigate microscopic optical feedback to a group of microbes (Euglena gracilis in this study) with a neural network algorithm, expecting that the unique characteristics of microbes, especially their strategies to survive/adapt against unfavorable environmental stimuli, will explicitly determine the temporal evolution of the microbe-based feedback...
We present a logical approach to the separability analysis issue for a functional quantum computation language. This logic is inspired by previous works on logical analysis of aliasing for imperative functional programs. Both analyses share similarities notably because they are highly non-compositional. Nevertheless, the intrisic non determinism of quantum computation has a large impact on the definitions...
Some physical aspects related to the limit operations of the Thomson lamp are discussed. Regardless of the formally unbounded and even infinite number of “steps” involved, the physical limit has an operational meaning in agreement with the Abel sums of infinite series. The formal analogies to accelerated (hyper-) computers and the recursion theoretic diagonal methods are discussed. As quantum information...
Colossus, the first electronic digital (and very unconventional) computer, was not a stored-program general purpose computer in the modern sense, although there are printed claims to the contrary. At least one of these asserts Colossus was a Turing machine. Certainly, an appropriate Turing machine can simulate the operation of Colossus. That is hardly an argument for generality of computation. But...
Membrane systems with dividing and dissolving membranes are known to solve PSPACE problems in polynomial time. However, we give a P upperbound on an important restriction of such systems. In particular we examine systems with dissolution, elementary division and where each membrane initially has at most one child membrane. Even though such systems may create exponentially many membranes, each with...
Fredkin’s Billiard Ball Model (BBM) is considered one of the fundamental models of collision-based computing, and it is essentially based on elastic collisions of mobile billiard balls. Moreover, fixed mirrors or reflectors are brought into the model to deflect balls to complete the computation. However, the use of fixed mirrors is “physically unrealistic” and makes the BBM not perfectly momentum...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.