Ricochet Robots with Infinite Horizontal Board is Turing-complete - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Information Processing Year : 2023

Ricochet Robots with Infinite Horizontal Board is Turing-complete

Abstract

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
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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⟩
34 View
52 Download

Altmetric

Share

Gmail Facebook X LinkedIn More