Article ID Journal Published Year Pages File Type
6874660 Journal of Computer and System Sciences 2018 17 Pages PDF
Abstract
In the context of abstract geometrical computation, computing with coloured line segments, we consider the possibility of an accumulation-topological limit point of segment intersections/collisions-with small signal machines, i.e. having only a very limited number of distinct slopes/speeds when started with finitely many segments/signals. The cases of 2 and 4 speeds are trivial: no machine can produce an accumulation with only 2 speeds and an accumulation can be generated with 4 speeds. The main result is the twofold 3-speed case. No accumulation can happen when all ratios between speeds and all ratios between initial distances are rational. Accumulation is possible in the case of an irrational ratio between two speeds or of an irrational ratio between two distances in the initial configuration. This dichotomy is explained by the presence of a phenomenon computing Euclid's gcd algorithm: it stops if and only if its input is commensurable, i.e., of rational ratio.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,