## Machines, Computations, and Universality: Third International Conference, MCU 2001 Chisinau, Moldava, May 23-27, 2001 ProceedingsIn the ?rst part of the present volume of LNCS, the reader will ?nd the invited talks given at the MCU 2001 conference. In the second part, he/she will ?nd the contributions that were presented at the conference after selection. In both cases, papers are arranged in the alphabetical order of the authors. MCU 2001 is the third conference in theoretical computer science, Machines, computations and universality, formerly, Machines et calculs universels. Both previous conferences, MCU’95 and MCU’98, were organized by Maurice M- genstern in Paris and in Metz (France), respectively. From the very beginning, MCU conferences have been an international sci- ti?c event. For the third conference, in order to stress that aspect, it was decided to hold it outside France. Moldova was chosen thanks to the close cooperation between the present chairmen of MCU 2001. MCU 2001 also aims at high scienti?c standards. We hope that the present volume will convince the reader that the tradition of previous conferences have been upheld by this one. Cellular automata and molecular computing are well represented in this volume. And this is also the case for quantum computing, f- mal languages, and the theory of automata. MCU 2001 does not fail its tradition of providing our community with important results on Turing machines. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Three Small Universal Turing Machines | 1 |

Computation in Gene Networks | 11 |

Power Puzzles and Properties of Entanglement | 25 |

Combinatorial and Computational Problems on Finite Sets of Words | 69 |

Universality Results | 82 |

A Simple Universal Logic Element and Cellular Automata for Reversible Computing | 102 |

Some Applications of the Decidability of DPDAs Equivalence | 114 |

Decidable and Undecidable Cases | 133 |

Nonterminal Complexity of Programmed Grammars | 202 |

On the Number of Nonterminal Symbols in GraphControlled Programmed and Matrix Grammars | 214 |

A Direct Construction of a Universal Extended H System | 226 |

SpeedingUp Cellular Automata by Alternations | 240 |

Efficient Universal Pushdown Cellular Automata and Their Application to Complexity | 252 |

Firing Squad Synchronization Problem on Bidimensional Cellular Automata with Communication Constraints | 264 |

Universality and Efficiency | 276 |

On the Computational Power of a ContinuousSpace Optical Model of Computation | 288 |

Two Normal Forms for Rewriting P Systems | 153 |

On a Conjecture of Kůrka A Turing Machine with No Periodic Configurations | 165 |

On the Transition Graphs of Turing Machines | 177 |

JCNets | 190 |

On a Poptimal Proof System for the Set of All Satisfiable Boolean Formulas SAT | 300 |

D0L System + WatsonCrick Complementarity Universal Computation | 308 |

320 | |

### Other editions - View all

Machines, Computations, and Universality: Third International Conference ... Maurice Margenstern,Yurii Rogozhin No preview available - 2014 |

Machines, Computations, and Universality: Third International Conference ... MCU 2001,Maurice Margenstern No preview available - 2001 |

### Common terms and phrases

algorithm Alice and Bob alphabet appearance checking mode array axioms binary normal form bisimulation bound cell cellular automata coding complexity Computer Science consider construction context-free counter machines deﬁned Deﬁnition denote density matrix deterministic element encoding equations equivalence problem evolution rules exists finite set FOSPs function graph-controlled graphs halting hypergraph initial input isomorphism jc-nets join calculus label leftmost Lemma LNCS matrix grammar monoid multipartite multiset networks non-terminal symbols nonterminals objects obtained operation output P˘aun pair particles PDCA periodic configuration polynomial programmed grammars proof system pushdown quantum entanglement quantum teleportation qubits recursively enumerable languages regular languages resp result rewriting systems scheme sequence signal simulation skin membrane splicing Springer-Verlag stack step string subset synchronization tape Technical report teleportation terminal terminal symbols Theorem theory transition Turing machine undecidable universal variables word