Two railway circuits: a universal circuit and an NP-difficult one
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2001-05-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/nrofdownloads.php?file=/files/csjm/v9-n1/v9-n1-(pp3-33).pdf |
| _version_ | 1798005923649683456 |
|---|---|
| author | Maurice Margenstern |
| author_facet | Maurice Margenstern |
| author_sort | Maurice Margenstern |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T12:46:49Z |
| format | Article |
| id | doaj.art-cbe1d27fb7a642d38248cd74c0a1ca50 |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-11T12:46:49Z |
| publishDate | 2001-05-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-cbe1d27fb7a642d38248cd74c0a1ca502022-12-22T04:23:20ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422001-05-0191(25)333Two railway circuits: a universal circuit and an NP-difficult oneMaurice Margenstern0L.I.T.A., EA 3097, Université de Metz, I.U.T. de Metz, Département d'Informatique, Île du Saulcy, 57045 Metz Cedex, FranceIn 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.http://www.math.md/nrofdownloads.php?file=/files/csjm/v9-n1/v9-n1-(pp3-33).pdfCircuitsswitchesregistersuniversalityNP-completeness |
| spellingShingle | Maurice Margenstern Two railway circuits: a universal circuit and an NP-difficult one Computer Science Journal of Moldova Circuits switches registers universality NP-completeness |
| title | Two railway circuits: a universal circuit and an NP-difficult one |
| title_full | Two railway circuits: a universal circuit and an NP-difficult one |
| title_fullStr | Two railway circuits: a universal circuit and an NP-difficult one |
| title_full_unstemmed | Two railway circuits: a universal circuit and an NP-difficult one |
| title_short | Two railway circuits: a universal circuit and an NP-difficult one |
| title_sort | two railway circuits a universal circuit and an np difficult one |
| topic | Circuits switches registers universality NP-completeness |
| url | http://www.math.md/nrofdownloads.php?file=/files/csjm/v9-n1/v9-n1-(pp3-33).pdf |
| work_keys_str_mv | AT mauricemargenstern tworailwaycircuitsauniversalcircuitandannpdifficultone |