Ricochet Robots with Infinite Horizontal Board is Turing-complete - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Journal of Information Processing Année : 2023

Ricochet Robots with Infinite Horizontal Board is Turing-complete

Résumé

This paper investigates the Ricochet Robots game problem from a complexity standpoint. The problem consists of moving robots in a rectangular square-tiled board, from initial tiles to reach specific target tiles. A robot can only move vertically or horizontally and when it starts to move in a given direction, the robot follows this direction, until being blocked by a wall or another robot. This paper proves that the corresponding decision problem to Ricochet Robots is Turing-complete for endless board game and an infinite number of robots. A reduction from a universal Turing machine to Ricochet Robots is exhibited.
Fichier principal
Vignette du fichier
main.pdf (525.33 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-04164381 , version 1 (18-07-2023)

Identifiants

Citer

Samuel Masseport, Tom Davot, Rodolphe Giroudeau. Ricochet Robots with Infinite Horizontal Board is Turing-complete. Journal of Information Processing, 2023, 31, pp.413-420. ⟨10.2197/ipsjjip.31.413⟩. ⟨lirmm-04164381⟩
151 Consultations
173 Téléchargements

Altmetric

Partager

More