Skip to main content



Invited Papers

Graph Machines and Their Applications to Computer-Aided Drug Design: A New Approach to Learning from Structured Data

The recent developments of statistical learning focused on vector machines, which learn from examples that are described by vectors of features. However, there are many fields where structured data must be handled; therefore, it would be desirable to learn from examples described by graphs.Graph machines learn real numbers from graphs. Basically, for each graph, a separate learning machine is built, whose algebraic structure contains the same information as the graph. We describe the training of such machines, and show that virtual leave-one-out, a powerful method for assessing the generalization capabilities of conventional vector machines, can be extended to graph machines. Academic examples are described, together with applications to the prediction of pharmaceutical activities of molecules and to the classification of properties; the potential of graph machines for computer-aided drug design are highlighted.
Aurélie Goulon, Arthur Duprat, Gérard Dreyfus

Rational Models of Cognitive Control

Human behavior is remarkably flexible. An individual who drives the same route to work each day easily adjusts for a traffic jam or to pick up lunch. Any theory of human cognition must explain not only routine behavior, but how behavior is flexibly modulated by the current environment and goals. In this extended abstract, we discuss this ability, often referred to as cognitive control.
Michael C. Mozer

Fault-Tolerance in Biochemical Systems

Biochemistry is messy. It’s a miracle any of it works. And yet it does. The wonderful diversity and amazing talents of living things derive from the biochemical processes that copy genetic information and use that information as a program to construct a sophisticated organization of matter and behaviour – reliably and robustly overcoming insult after insult from the environment. In this talk I will first discuss how known techniques for fault-tolerant computing, such as von Neumann’s multiplexing technique for digital circuits, can be translated to the biochemical context. I will then discuss fault-tolerance in molecular self-assembly, which requires new techniques. Using a model of algorithmic self-assembly, a generalization of crystal growth processes, I will present techniques for controlling the nucleation of self-assembly, for reducing errors during growth, and for recovering after gross damage or fragmentation.
Erik Winfree

Optical Computing and Computational Complexity

This work concerns the computational complexity of a model of computation that is inspired by optical computers. The model is called the continuous space machine and operates in discrete timesteps over a number of two-dimensional images of fixed size and arbitrary spatial resolution. The (constant time) operations on images include Fourier transformation, multiplication, addition, thresholding, copying and scaling. We survey some of the work to date on the continuous space machine. This includes a characterisation of the power of an important discrete restriction of the model. Parallel time corresponds, within a polynomial, to sequential space on Turing machines, thus satisfying the parallel computation thesis. A characterisation of the complexity class NC in terms of the model is also given. Thus the model has computational power that is (polynomially) equivalent to that of many well-known parallel models. Such characterisations give a method to translate parallel algorithms to optical algorithms and facilitate the application of the complexity theory toolbox to optical computers. In the present work we improve on these results. Specifically we tighten a lower bound and present some new resource trade-offs.
Damien Woods

Regular Papers

If a Tree Casts a Shadow Is It Telling the Time?

Physical processes are computations only when we use them to externalize thought. Computation is the performance of one or more fixed processes within a contingent environment. We reformulate the Church-Turing thesis so that it applies to programs rather than to computability. When suitably formulated agent-based computing in an open, multi-scalar environment represents the current consensus view of how we interact with the world. But we don’t know how to formulate multi-scalar environments.
Russ Abbott

Peptide Computing – Universality and Theoretical Model

We present a new simulation of Turing machines by peptide-antibody interactions. In contrast to a simulation presented previously, this new technique simulates the computation steps automatically and does not rely on a “look-and-do” approach, in which the Turing machine program would be interpreted by an extraneous computing agent. We determine the resource requirements of the simulation. Towards a precise definition for peptide computing we construct a new theoretical model. We examine how the simulations presented in this paper fit this model. We prove that a peptide computing model can be simulated by a Turing machine under certain conditions.
M. Sakthi Balan, Helmut Jürgensen

Handling Markov Chains with Membrane Computing

In this paper we approach the problem of computing the n–th power of the transition matrix of an arbitrary Markov chain through membrane computing. The proposed solution is described in a semi–uniform way in the framework of P systems with external output. The amount of resources required in the construction is polynomial in the number of states of the Markov chain and in the power. The time of execution is linear in the power and is independent of the number of states involved in the Markov chain.
Mónica Cardona, M. Angels Colomer, Mario J. Pérez-Jiménez, Alba Zaragoza

Approximation Classes for Real Number Optimization Problems

A fundamental research area in relation with analyzing the complexity of optimization problems are approximation algorithms. For combinatorial optimization a vast theory of approximation algorithms has been developed, see [1]. Many natural optimization problems involve real numbers and thus an uncountable search space of feasible solutions. A uniform complexity theory for real number decision problems was introduced by Blum, Shub, and Smale [4]. However, approximation algorithms were not yet formally studied in their model.
In this paper we develop a structural theory of optimization problems and approximation algorithms for the BSS model similar to the above mentioned one for combinatorial optimization. We introduce a class NPO of real optimization problems closely related to NP . The class NPO has four natural subclasses. For each of those we introduce and study real approximation classes APX and PTAS together with reducibility and completeness notions. As main results we establish the existence of natural complete problems for all these classes.
Uffe Flarup, Klaus Meer

Physical Systems as Constructive Logics

This paper is an investigation of S. Wolfram’s Principle of Computational Equivalence’ – that (discrete) systems in the natural world should be thought of as performing computations. We take a logical approach, and demonstrate that under almost trivial (physically reasonable) assumptions, discrete evolving physical systems give a class of logical models. Moreover, these models are of intuitionistic, or constructive logics – that is, exactly those logics with a natural computational interpretation under the Curry-Howard ‘proofs as programs’ isomorphism.
Peter Hines

On Spiking Neural P Systems and Partially Blind Counter Machines

A k-output spiking neural P system (SNP) with output neurons, O 1, ..., O k , generates a tuple (n 1, ..., n k ) of positive integers if, starting from the initial configuration, there is a sequence of steps such that during the computation, each O i generates exactly two spikes a a (the times the pair a a are generated may be different for different output neurons) and the time interval between the first a and the second a is n i . After the output neurons generate their pairs of spikes, the system eventually halts. We give characterizations of sets definable by partially blind multicounter machines in terms of k-output SNPs operating in a sequential mode. Slight variations of the models make them universal.
Oscar H. Ibarra, Sara Woodworth, Fang Yu, Andrei Păun

Chemical Information Processing Devices Constructed Using a Nonlinear Medium with Controlled Excitability

Chemical signals composed of excitation pulses can be processed in a medium with an appropriate geometrical arrangement of excitable and non-excitable regions. In this paper we consider two types of signal processing devices: a binary logic gate and a four input, neuron like structure. Using numerical simulations, we demonstrate that small local changes in the excitability level of the medium can completely change the function executed by the device and can thus be used to program it.
Yasuhiro Igarashi, Jerzy Gorecki, Joanna Natalia Gorecka

Flexible Versus Rigid Tile Assembly

DNA molecules have been assembled in rigid DX and TX molecules, arrayed in assemblies similar to Wang tiles, and, as flexible branched junction molecules with flexible arms have been used in assemblies representing arbitrary graphs. This paper considers both models of rigid and flexible tiles. A model representing complexes assembled out of rigid tiles based on tile displacements is presented. This presentation is used to simulate computations obtained from (bounded) rigid tile self-assembly by corresponding assemblies of flexible tiles.
Nataša Jonoska, Gregory L. McColm

On Pure Catalytic P Systems

Catalytic P systems is one of the basic classes of P systems. The number of catalysts required for optimal universality results (both in pure catalytic systems and catalytic systems) has been a problem of extensive research [3],[5],[6],[7],[12]. The differences that can give universality/non-universality are very small in these systems, and finding this borderline is one of the ‘jewel’ problems in P systems [12]. In this paper, we try to figure out this borderline and have obtained some interesting results. We have proved that with 2 catalysts, if λ-rules are not used, then universality cannot be obtained. We also consider two restricted variants of pure catalytic systems and prove that they are also not universal. Finally, we look at mobile catalytic systems and solve two open problems.
Shankara Narayanan Krishna

Mapping Non-conventional Extensions of Genetic Programming

Conventional genetic programming research excludes memory and iteration. We have begun an extensive analysis of the space through which GP or other unconventional AI approaches search and extend it to consider explicit program stop instructions (T8) and any time models (T7). We report halting probability, run time and functionality (including entropy of binary functions) of both halting and anytime programs. Turing complete program fitness landscapes, even with halt, scale poorly.
W. B. Langdon

The Number of Orbits of Periodic Box-Ball Systems

A box-ball system is a kind of cellular automata obtained by the ultradiscrete Lotka-Volterra equation. Similarities and differences between behavious of discrete systems (cellular automata) and continuous systems (differential equations) are investigated using techniques of ultradiscretizations. Our motivations is to take advantage of behavious of box-ball systems for new kinds of computations. Especially, we tried to find out useful periodic box-ball systems(pBBS) for random number generations. Applicable pBBS systems should have long fundamental cycles. We focus on pBBS with at most two kinds of solitons and investigate their behaviours, especially, the length of cycles and the number of orbits. We showed some relational equations of soliton sizes, a box size and the number of orbits. Varying a box size, we also found out some simulation results of the periodicity of orbits of pBBS with same kinds of solitons.
Akihiro Mikoda, Shuichi Inokuchi, Yoshihiro Mizoguchi, Mitsuhiko Fujio

The Euclid Abstract Machine: Trisection of the Angle and the Halting Problem

What is the meaning of hypercomputation, the meaning of computing more than the Turing machine? Concrete non-computable functions always hide the halting problem as far as we know. Even the construction of a function that grows faster than any recursive function — the Busy Beaver — a more natural function, hides the halting function, that can easily be put in relation with the Busy Beaver. Is this super-Turing computation concept related only with the halting problem and its derivatives? We built an abstract machine based on the historic concept of compass and ruler construction which reveals the existence of non-computable functions not related with the halting problem. These natural, and the same time, non-computable functions can help to understand the nature of the uncomputable and the purpose, the goal, and the meaning of computing beyond Turing.
Jerzy Mycka, Francisco Coelho, José Félix Costa

1/f Noise in Elementary Cellular Automaton Rule 110

Cellular Automata are considered to be discrete dynamical systems as well as computing systems. Spectral analysis has been employed to investigate the behavior of dynamical systems. We calculated the power spectra from the evolutions starting from a random initial configuration to analyze the temporal behavior in elementary cellular automata. As a result, rule 110 has 1/f spectrum for the longest time steps. Rule 110 alone has proved to be capable of supporting universal computation in elementary cellular automata. These results suggest that there is a relationship between computational universality and 1/f noise in cellular automata.
Shigeru Ninagawa

A Light-Based Device for Solving the Hamiltonian Path Problem

In this paper we suggest the use of light for performing useful computations. Namely, we propose a special device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.
Mihai Oltean

Optimizing Potential Information Transfer with Self-referential Memory

This paper investigates an information-theoretic design principle, intended to support an evolution of a memory structure fitting a specific selection pressure: potential information transfer through the structure. The proposed criteria measure how much does associativity in memory add to the information transfer in terms of precision, recall and effectiveness. Maximization of the latter results in holographic memory structures that can be interpreted in self-referential terms. The study introduces an analogy between self-replication and memory retrieval, with DNA as a partially-associative memory containing relevant information. DNA decoding by a complicated protein machinery (“cues” or ”keys”) may corresponds to an associative recall: i.e., a replicated offspring is an associatively-recalled prototype. The proposed information-theoretic criteria intend to formalize the notion of information transfer involved in self-replication, and enable bio-inspired design of more effective memory structures.
Mikhail Prokopenko, Daniel Polani, Peter Wang

On the Power of Bio-Turing Machines

In this paper, we continue the study of Bio-Turing machines introduced in [1]. It was proved in [1] that using two differentiated cells, and using antiport rules of weight 2, one can recognize the family 1RE. We show here that with just one differentiated cell, 1RE can be characterized, by using antiport rules of weight 2, or by using symport rules of weight 3. We also prove that RE can be characterized using arbitrary alphabets, using 2 differentiated cells, and antiport rules of weight 2. Finally, we examine the computational power when there are no differentiated cells and show that non-regular languages can be accepted.
H. Ramesh, Shankara Narayanan Krishna, Raghavan Rama

Ergodic Dynamics for Large-Scale Distributed Robot Systems

Intelligent autonomous robotics is a promising area with many potential applications that could benefit from non-traditional models of computation. Information processing systems interfaced with the real world must deal with a continuous and uncertain environment, and must cope with interactions across a range of time-scales. Robotics problems resist existing tools and, consequently, new perspectives are needed to address these challenges. Toward that end, we describe a dynamics-based model for computing in large-scale distributed robot systems. The proposed method employs a compositional approach, constructing robot controllers from ergodic processes. We describe application of the method to two multi-robot tasks: decentralised task allocation, and collective strategy selection.
Dylan A. Shell, Maja J. Matarić


Weitere Informationen