Catálogo de publicaciones - libros

Research in quantum computation is looking for the consequences of having information encoding, processing and communication exploit the laws of quantum physics, i.e. the laws of the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. After an introduction to the principles of quantum information processing and a brief survey of the major breakthroughs brought by the first ten years of research in this domain, this paper concentrates on a typically “computer science” way to reach a deeper understanding of what it means to compute with quantum resources, namely on the design of programming languages for quantum algorithms and protocols, and on the questions raised by the semantics of such languages. Special attention is devoted to the process algebraic approach to such languages, through a presentation of QPAlg, the Quantum Process Algebra which is being designed by the authors.

All information processing systems found in living organisms are based on chemical processes. Harnessing the power of chemistry for computing might lead to a new unifying paradigm coping with the rapidly increasing complexity and autonomy of computational systems. Chemical computing refers to computing with real molecules as well as to programming electronic devices using principles taken from chemistry. The paper focuses on the latter, called artificial chemical computing, and discusses several aspects of how the metaphor of chemistry can be employed to build technical information processing systems. In these systems, computation emerges out of an interplay of many decentralized relatively simple components analogized to molecules. Chemical programming encompassed then the definition of molecules, reaction rules, and the topology and dynamics of the reaction space. Due to the self-organizing nature of chemical dynamics, new programming methods are required. Potential approaches for chemical programming are discussed and a road map for developing chemical computing into a unifying and well grounded approach is sketched.

In reaction-diffusion (RD) processors, both the data and the results of the computation are encoded as concentration profiles of the reagents. The computation is performed via the spreading and interaction of wave fronts. Most prototypes of RD computers are specialized to solve certain problems, they can not be, in general, re-programmed. In the paper, we try to show possible means of overcoming this drawback. We envisage an architecture and interface of programmable RD media capable of solving a wide range of problems.

Achieving real-time response to complex, ambiguous, high-bandwidth data is impractical with conventional programming. Only the narrow class of compressible input-output maps can be specified with feasibly sized programs. Present computing concepts enforce formalisms that are arbitrary from the perspective of the physics underlying their implementation. Efficient physical realizations are embarrassed by the need to implement the rigidly specified instructions requisite for programmable systems. The conventional paradigm of erecting strong constraints and potential barriers that narrowly prescribe structure and precisely control system state needs to be complemented with a new approach that relinquishes detailed control and reckons with autonomous building blocks. Brittle prescriptive control will need to be replaced with resilient self-organisation to approach the robustness and efficiency afforded by natural systems. Structure-function self-consistency will be key to the spontaneous generation of functional architectures that can harness novel molecular and nano materials in an effective way for increased computational power.

Relational growth grammars (RGG) area graph rewriting formalism which extends the notations and semantics of Lindenmayer systems and which allows the specification of dynamical processes on dynamical structures, parti cular ly in biological and chemical applications. RGG were embedded in the language XL, combining rule-based and conventional object-oriented con structions. Key features of RGG and of the software GroIMP (Growth grammar related Interactive Modelling Platform) are listed. Five simple examples are shown which demonstrate the essential ideas and possibilities of RGG: signal propagation in a network, cellular automata, globally-sensitive growth of a plant, a “chemical” prime number generator, and a polymerisation model using a simple mass-spring kinetics.

In this contribution we shall introduce a new method of program execution, based on notions of Artificial Chemistries. Instead of executing instructions in a predefined sequential order, execution will be in random order in analogy to chemical reactions happening between substances. It turns out that such a model of program execution is able to achieve desirable goals if augmented by an automatic program searching method like Genetic Programming. We demonstrate the principle of this approach and discuss prospects and consequences for parallel execution of such programs.

The chemical reaction metaphor describes computation in terms of a chemical solution in which molecules interact freely according to reaction rules. Chemical solutions are represented by multisets of elements and reactions by rewrite rules which consume and produce new elements according to conditions. The chemical programming style allows to write many programs in a very elegant way. We go one step further by extending the model so that rewrite rules are themselves molecules. This higher-order extension leads to a programming style where the implementation of new features amounts to adding new active molecules in the solution representing the system. We illustrate this style by specifying an autonomic mail system with several self-managing properties.

The study of amorphous computing aims to identify useful programming methodologies that will enable us to engineer the emergent behaviour of a myriad, locally interacting computing elements (agents). We anticipate that in order to keep such massively distributed systems cheap, the elements must be bulk manufactured. Therefore, we use a conservative model in which the agents run asynchronously, are interconnected in unknown and possibly time-varying ways, communicate only locally, and are identically programmed. We present a description of this model, and some of the results that have been obtained with it, particularly in the areas of pattern formation and the development of programming languages that are specifically suited to our model. Finally, we briefly describe some of the ongoing efforts in amorphous computing, and we present some of the interesting and important problems that still remain open in amorphous computing.

We present an abstraction for pattern formation, called , which are suitable for constructing complex patterns from simpler ones in the amorphous computing environment. This work builds upon previous efforts that focused on creating suitable system-level abstractions for engineering the emergence of agent-level interactions. Our pattern networks are built up from combinations of these system-level abstractions, and may be combined to form bigger pattern networks. We demonstrate the power of this abstraction by illustrating how a few complex patterns could be generated by a combination of appropriately defined pattern networks. We conclude with a discussion of the challenges involved in parameterising these abstractions, and in defining higher-order versions of them.

Amorphous computing considers the problem of controlling millions of spatially distributed unreliable devices which communicate only with nearby neighbors. To program such a system, we need a high-level description language for desired global behaviors, and a system to compile such descriptions into locally executing code which robustly creates and maintains the desired global behavior. I survey existing amorphous computing primitives and give desiderata for a language describing computation on an amorphous computer. I then bring these together in Amorphous Medium Language, which computes on an amorphous computer as though it were a space-filling computational medium.