Two railway circuits: a universal circuit and an NP-difficult one

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.

Keywords

• Circuits
• switches
• registers
• universality
• NP-completeness