General Computation using Slidable Tiles with Deterministic Global Forces Article Swipe

MAKE IMPACT

Avila-Jimenez, Alberto , Barreda, David , Evans, Sarah-Laurie , Luchsinger, Austin , Massie, Aiden , Schweller, Robert , Tomai, Evan , Wylie, Tim · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2512.06574

We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional ``tilts.'' We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per $O(1)$ rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of \emph{occupancy} (deciding if a given board location can be occupied by a tile), \emph{vacancy} (deciding if a location can be emptied), \emph{relocation} (deciding if a tile can be moved from one location to another), and \emph{reconfiguration} (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2512.06574

OA Status

green

OpenAlex ID

https://openalex.org/W7110819756

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7110819756

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2512.06574

Digital Object Identifier

Title

General Computation using Slidable Tiles with Deterministic Global Forces

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-12-06

Full publication date if available

Authors

Avila-Jimenez, Alberto, Barreda, David, Evans, Sarah-Laurie, Luchsinger, Austin, Massie, Aiden, Schweller, Robert, Tomai, Evan, Wylie, Tim

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2512.06574

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2512.06574

Direct OA link when available

Concepts

Computation, Computer science, Turing machine, Focus (optics), Sequence (biology), Algorithm, Tilt (camera), Computational complexity theory, Position (finance), Work (physics), Trajectory, Constant (computer programming), Power (physics), Theory of computation, Turing, Motion (physics), Time complexity, Hang, Domino, Domino effect, Line (geometry), Theoretical computer science, Bar (unit), Model of computation, Doors, Point (geometry), Mathematics, Simulation, Reduction (mathematics), Computational resource

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload