RO EN
Two railway circuits: a universal circuit and an NP-difficult one
Authors: Maurice Margenstern
Keywords: Circuits, switches, registers, universality, NP-completeness.
The switches that are used in the universality result are re-used in order to prove another result. Define the accessibility problem for railway circuits to consist in the following. The circuit is given with, at the same time, two points of the circuit, one is called the source point, the other one is called the target point and a fixed number of other points, called flip-flop switches, that can be initialized arbitrarily. The problem is to decide, whether or not there is an initialization of the flip-flop switches such that it is then possible to go from the source to the target. This problem is proved to be NP-complete.
– 0.83 Mb
Keywords: Circuits, switches, registers, universality, NP-completeness.
Abstract
In this paper, first we construct a railway circuit based on three types of switches and on crossings. Such a circuit is able to simulate the computation of any Turing machine, in particular of a universal one. That result was proved by Ian Stewart in [3]. In this paper, we give another construction, indeed a simpler one: here we show that it is possible to simulate the computation of any register machine, from which the same conclusion can be derived.The switches that are used in the universality result are re-used in order to prove another result. Define the accessibility problem for railway circuits to consist in the following. The circuit is given with, at the same time, two points of the circuit, one is called the source point, the other one is called the target point and a fixed number of other points, called flip-flop switches, that can be initialized arbitrarily. The problem is to decide, whether or not there is an initialization of the flip-flop switches such that it is then possible to go from the source to the target. This problem is proved to be NP-complete.
Maurice Margenstern,
L.I.T.A., EA 3097, Université de Metz,
I.U.T. de Metz, Département d'Informatique,
Île du Saulcy, 57045 Metz Cedex, France,
E-mail:
L.I.T.A., EA 3097, Université de Metz,
I.U.T. de Metz, Département d'Informatique,
Île du Saulcy, 57045 Metz Cedex, France,
E-mail:
Fulltext
– 0.83 Mb
Contents
- Two railway circuits: a universal circuit and an NP-difficult one
- Small Universal Circular Post Machines
- The system of molecular-genetic triggers as self-organizing computing system
- On strong quasistability of a vector problem on substitutions
- A generalization of the optimality for multicriterion problems
