Catálogo de publicaciones - libros

We introduce a new formal computational model designed for studying the information transfer among the generations of offspring–producing machines — so–called autopoietic automata. These can be seen as finite state transducers whose “program” can become a subject of their own processing. An autopoietic automaton can algorithmically generate an offspring controlled by a program which is a modification of its parent’s program. We show that the computational power of lineages of autopoietic automata is equal to that of an interactive nondeterministic Turing machine. We also prove that there exists an autopoietic automaton giving rise to an unlimited evolution, providing suitable inputs are delivered to individual automata. However, the problem of a sustainable evolution, asking for an arbitrary autopoietic automaton and arbitrary inputs whether there is an infinite lineage of its offspring is undecidable.

We present lower bounds on the computational power of an optical model of computation called the -CSM. We show that -CSM time is at least as powerful as sequential space, thus giving one of the two inclusions that are necessary to show that the model verifies the parallel computation thesis. Furthermore we show that -CSMs that simultaneously use polynomial space and polylogarithmic time decide at least the class NC.

In this paper we pursue two targets. First, showing that counterfactual computation can be rigorously formalised as a quantum computation. Second, presenting a new counterfactual protocol which improve previous protocols. Counterfactual computation makes use of quantum mechanics’ peculiarities to infer the outcome of a quantum computation without running that computation. In this paper, we first cast the definition of counterfactual protocol in the quantum programming language qGCL, thereby showing that counterfactual computation is an example of quantum computation. Next, we formalise in qGCL a probabilistic extension of counterfactual protocol for decision problems (whose result is either 0 or 1). If denotes for protocol the probability of obtaining result “for free” ( without running the quantum computer), then we show that for any probabilistic protocol + ≤ 1 (as for non-probabilistic protocols). Finally, we present a probabilistic protocol which satisfies +=1, thus being optimal. Furthermore, the result is attained with a single insertion of the quantum computer, while it has been shown that a non-probabilistic protocol would obtain the result only in the limit ( with an infinite number of insertions).