Irrationality is needed to compute with signal machines with only three speeds

Jérôme Durand-Lose (1)

1 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans

Space-time diagrams of signal machines on finite configurations are composed of interconnected line segments in the Euclidean plane. As the system runs, a network emerges. If segments extend only in one or two directions, the dynamics is finite and simplistic. With four directions, it is known that fractal generation, accumulation and any Turing computation are possible. This communication deals with the three directions/sp eeds case. If there is no irrational ratio (between initial distances between signals or between speeds) then the network follows a mesh preventing accumulation and forcing a cyclic behavior. With an irrational ratio (here, the Golden ratio) between initial distances, it becomes possible to provoke an accumulation that generates infinitely many interacting signals in a bounded portion of the Euclidean plane. This b ehavior is then controlled and used in order to simulate a Turing machine and generate a 25-state 3-speed Turing-universal signal machine

Mots clés: Accumulation; Computability; Fractal; Model of computation; Signal machine; Turing machine; Unconventional computation

Domaines: Logique en informatique [cs.LO]

Jérôme Durand-Lose. Irrationality is needed to compute with signal machines with only three speeds. 9th Conference on Computability in Europe 2013, Jul 2013, Milan, Italy. pp.108-119, ⟨10.1007/978-3-642-39053-1_12⟩. ⟨hal-00807227⟩