Unconventional Computation and Natural Computation

We introduce new possibilities to control the application of rules based on the preceding applications, which can be defined in a general way for (hierarchical) P systems and the main known derivation modes. Computational completeness can be obtained even with non-cooperative rules and using both activation and blocking of rules, especially for the set modes of derivation. When we allow the application of rules to influence the application of rules in previous derivation steps, applying a non-conservative semantics for what we consider to be a derivation step, we can even “go beyond Turing”.

The recently introduced Thermodynamic Binding Networks (TBN) model was developed with the purpose of studying self-assembling systems by focusing on their thermodynamically favorable final states, and ignoring the kinetic pathways through which they evolve. The model was intentionally developed to abstract away not only the notion of time, but also the constraints of geometry. Collections of monomers with binding domains which allow them to form polymers via complementary bonds are analyzed to determine their final, stable configurations, which are those which maximize the number of bonds formed (i.e. enthalpy) and the number of independent components (i.e. entropy). In this paper, we first develop a definition of what it means for a TBN to perform a computation, and then present a set of constructions which are capable of performing computations by simulating the behaviors of space-bounded Turing machines and boolean circuits. In contrast to previous TBN results, these constructions are robust to great variability in the counts of monomers existing in the systems and the numbers of polymers that form in parallel. Although the Turing machine simulating TBNs are inefficient in terms of the numbers of unique monomer types required, as compared to algorithmic self-assembling systems in the abstract Tile Assembly Model (aTAM), we then show that a general strategy of porting those aTAM system designs to TBNs produces TBNs which incorrectly simulate computations. Finally, we present a refinement of the TBN model which we call the Geometric Thermodynamic Binding Networks (GTBN) model in which monomers are defined with rigid geometries and form rigid bonds. Utilizing the constraints imposed by geometry, we then provide a GTBN construction capable of simulating Turing machines as efficiently as in the aTAM.

We analyze the complexity of building linear assemblies, sets of linear assemblies, and \(\mathcal {O}(1)\)-scale general shapes in the staged tile assembly model. For systems with at most b bins and t tile types, we prove that the minimum number of stages to uniquely assemble a \(1 \times n\) line is \(\varTheta (\log _t{n} + \log _b{\frac{n}{t}} + 1)\). Generalizing to \(\mathcal {O}(1) \times n\) lines, we prove the minimum number of stages is \(\mathcal {O}(\frac{\log {n} - tb - t\log t}{b^2} + \frac{\log \log b}{\log t})\) and \(\varOmega (\frac{\log {n} - tb - t\log t}{b^2})\).

Next, we consider assembling sets of lines and general shapes using \(t = \mathcal {O}(1)\) tile types. We prove that the minimum number of stages needed to assemble a set of k lines of size at most \(\mathcal {O}(1) \times n\) is \(\mathcal {O}(\frac{k\log n}{b^2}+\frac{k\sqrt{\log n}}{b}+\log \log n)\) and \(\varOmega (\frac{k\log n}{b^2})\). In the case that \(b = \mathcal {O}(\sqrt{k})\), the minimum number of stages is \(\varTheta (\log {n})\). The upper bound in this special case is then used to assemble “hefty” shapes of at least logarithmic edge-length-to-edge-count ratio at \(\mathcal {O}(1)\)-scale using \(\mathcal {O}(\sqrt{k})\) bins and optimal \(\mathcal {O}(\log {n})\) stages.

Using an imperfectly prepared state, we show that under a Lorentz transformation, the evolution of a massive spin-1/2 particle violates many standard assumptions made in quantum information theory, including complete positivity. Unlike other recent endeavors in relativistic quantum information, we are able to quantify and maximize how much information can be transferred through such a quantum process by calculating the scope. We show that, surprisingly, in many instances the relativistic noise increases the amount of information that can be transferred, and in fact, even if the initial state is arbitrarily close to the completely mixed state, information can still be transferred perfectly.

Here we demonstrate the first working example of a liquid marble-operated sequential binary counting device. We have designed a lightweight gate that can be actuated by the low mass and momentum of a liquid marble. By linking a number of these gates in series, we are able to digitally count up to binary 1111 (upper limit only by our requirements). Using liquid marbles in such a system opens up new avenues of research and design, by way of modifying the coating and/or core of the liquid marbles, and thereby giving extra dimensions for calculation (e.g. a calculation that takes into consideration the progress of a chemical reaction inside a liquid marble). In addition, the new gate design has multiple uses in liquid marble rerouting.

In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word blending between two words \(x w y_1\) and \(y_2 w z\) that share a non-empty overlap w, results in xwz. We study closure properties of families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smoke + fog), labradoodle (labrador + poodle), and Brangelina (Brad + Angelina).

An expression in a functional programming language can be compiled into a massively redundant, spatially distributed, concurrent computation called a distributed virtual machine (DVM). A DVM is comprised of bytecodes reified as actors undergoing diffusion on a two-dimensional grid communicating via messages containing encapsulated virtual machine states (continuations). Because the semantics of expression evaluation are purely functional, DVMs can employ massive redundancy in the representation of the heap to help ensure that computations complete even when large areas of the physical host substrate have failed. Because they can be implemented as asynchronous circuits, DVMs also address the well known problem affecting traditional machine architectures implemented as integrated circuits, namely, clock networks consuming increasingly large fractions of area as device size increases. This paper describes the first hardware implementation of a DVM. This was accomplished by compiling a VHDL specification of a special purpose distributed memory multicomputer with a mesh interconnection network into a globally asynchronous, locally synchronous (GALS) circuit in an FPGA. Each independently clocked node combines a processor based on a virtual machine for compiled Scheme language programs, with just enough local memory to hold a single heap allocated object and a continuation.

Lindenmayer systems (L-systems) are parallel string rewriting systems (grammars). By attaching a graphical interpretation to the symbols in the derived strings, they can be applied to create simulations of temporal processes, and have been especially successful in the modeling of plants. With the objective of automatically inferring L-system models in mind, here we study the inductive inference problem: the inference of models from observed strings. Exact algorithms are given for inferring L-systems that can generate input strings for both deterministic context-free and deterministic context-sensitive L-systems. The algorithms run in polynomial time assuming a fixed number of alphabet symbols and fixed context size. Furthermore, if a specific matrix calculated from the input words is invertible, then a context-sensitive L-system can be automatically created (if it exists) in polynomial time without assuming any fixed parameters.

Reaction systems are a formal model for specifying and analysing computational processes in which reactions operate on sets of entities (molecules), providing a framework for dealing with qualitative aspects of biochemical systems. This paper is concerned with reaction systems in which entities can have discrete concentrations and reactions operate on multisets of entities, providing a succinct framework for dealing with quantitative aspects of systems. This is facilitated by a dedicated linear-time temporal logic which allows one to express and verify a wide range of behavioural system properties.

Card-based cryptography is an attractive and unconventional computation model; it provides secure computing methods using a deck of physical cards. It is noteworthy that a card-based protocol can be easily executed by non-experts such as high school students without the use of any electric device. One of the main goals in this discipline is to develop efficient protocols. The efficiency has been evaluated by the number of required cards, the number of colors, and the average number of protocol trials. Although these evaluation metrics are simple and reasonable, it is difficult to estimate the total number of operations or execution time of protocols based only on these three metrics. Therefore, in this paper, we consider adding other metrics to estimate the execution time of protocols more precisely. Furthermore, we actually evaluate some of the important existing protocols using our new criteria.

We address a biochemical folding obstacle of “polymerase trapping” that arises in the remarkable RNA origami tile design framework of Geary, Rothemund and Andersen (Science 2014). We present a combinatorial formulation of this obstacle, together with an optimisation procedure that yields designs minimising the risk of encountering the corresponding topological trap in the tile folding phase. The procedure has been embedded in an automated software pipeline, and we provide examples of designs produced by the software, including an optimised version of the RNA smiley-face tile proposed by Geary and Andersen (DNA 2014).

Watson-Crick (WK) finite automata are working on double stranded DNA molecule that is also called Watson-Crick tape. Subsequently, these automata have two reading heads, one for each strand. While in traditional WK automata both heads read the whole input in the same physical direction, in \(5'\rightarrow 3'\) WK automata the heads start from the two extremes (say \(5'\) end of the strands) and read the input in opposite direction. In sensing \(5'\rightarrow 3'\) WK automata the process on the input is finished when the heads meet. Since the heads of a WK automaton may read longer strings in a transition, in previous models a so-called sensing parameter took care for the proper meeting of the heads (not allowing to read the same positions of the input in the last step). Recently a new model is investigated, which works without the sensing parameter. In this paper, the deterministic counterpart is studied and proved to be accept the language class 2detLIN, i.e., the same class that is accepted by the deterministic variant of the earlier version. However, using some of restricted variants, e.g., all-final automata, the classes of the accepted languages are changed showing a more finer hierarchy inside the class of linear context-free languages.

Many forms of programmable matter have been proposed for various tasks. We use an abstract model of self-organizing particle systems for programmable matter which could be used for a variety of applications, including smart paint and coating materials for engineering or programmable cells for medical uses. Previous research using this model has focused on shape formation and other spatial configuration problems (e.g., coating and compression). In this work we study foundational computational tasks that exceed the capabilities of the individual constant size memory of a particle, such as implementing a counter and matrix-vector multiplication. These tasks represent new ways to use these self-organizing systems, which, in conjunction with previous shape and configuration work, make the systems useful for a wider variety of tasks. They can also leverage the distributed and dynamic nature of the self-organizing system to be more efficient and adaptable than on traditional linear computing hardware. Finally, we demonstrate applications of similar types of computations with self-organizing systems to image processing, with implementations of image color transformation and edge detection algorithms.

Natural systems often exhibit chaotic behavior in their space-time evolution. Systems transiting between chaos and order manifest a potential to compute, as shown with cellular automata and artificial neural networks. We demonstrate that swarms optimisation algorithms also exhibit transitions from chaos, analogous to motion of gas molecules, when particles explore solution space disorderly, to order, when particles follow a leader, similar to molecules propagating along diffusion gradients in liquid solutions of reagents. We analyse these ‘phase-like’ transitions in swarm optimization algorithms using recurrence quantification analysis and Lempel-Ziv complexity estimation. We demonstrate that converging and non-converging iterations of the optimization algorithms are statistically different in a view of applied chaos, complexity and predictability estimating indicators.