Two railway circuits: a universal circuit and an NP-difficult one - Maurice Margenstern (Computer Science Journal of Moldova, 2001)
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.